--- a/js/xpconnect/loader/ScriptCacheActors.cpp
+++ b/js/xpconnect/loader/ScriptCacheActors.cpp
@@ -42,16 +42,17 @@ ScriptCacheChild::Finalize(LinkedList<Sc
         if (!script->mSize && !script->XDREncode(jsapi.cx())) {
             continue;
         }
 
         auto data = dataArray.AppendElement();
 
         data->url() = script->mURL;
         data->cachePath() = script->mCachePath;
+        data->loadTime() = script->mLoadTime;
 
         if (script->HasBuffer()) {
             auto& xdrData = script->Buffer();
             data->xdrData().AppendElements(xdrData.begin(), xdrData.length());
             script->FreeData();
         }
     }
 
@@ -78,17 +79,17 @@ ScriptCacheParent::Recv__delete__(nsTArr
 
     // Merge the child's script data with the parent's.
     auto parent = static_cast<dom::ContentParent*>(Manager());
     auto processType = ScriptPreloader::GetChildProcessType(parent->GetRemoteType());
 
     auto& cache = ScriptPreloader::GetChildSingleton();
     for (auto& script : scripts) {
         cache.NoteScript(script.url(), script.cachePath(), processType,
-                         Move(script.xdrData()));
+                         Move(script.xdrData()), script.loadTime());
     }
 
     return IPC_OK();
 }
 
 void
 ScriptCacheParent::ActorDestroy(ActorDestroyReason aWhy)
 {}

--- a/js/xpconnect/loader/ScriptPreloader.cpp
+++ b/js/xpconnect/loader/ScriptPreloader.cpp
@@ -493,17 +493,17 @@ ScriptPreloader::InitCacheInternal()
 
     auto start = TimeStamp::Now();
     LOG(Info, "Off-thread decoding scripts...\n");
 
     JS::CompileOptions options(cx, JSVERSION_LATEST);
     for (auto script : mRestoredScripts) {
         // Only async decode scripts which have been used in this process type.
         if (script->mProcessTypes.contains(CurrentProcessType()) &&
-            script->mSize > MIN_OFFTHREAD_SIZE &&
+            script->AsyncDecodable() &&
             JS::CanCompileOffThread(cx, options, script->mSize)) {
             DecodeScriptOffThread(cx, script);
         } else {
             script->mReadyToExecute = true;
         }
     }
 
     LOG(Info, "Initialized decoding in %fms\n",
@@ -550,18 +550,16 @@ ScriptPreloader::PrepareCacheWrite()
         if (!found) {
             mSaveComplete = true;
             return;
         }
     }
 
     AutoSafeJSAPI jsapi;
 
-    LinkedList<CachedScript> asyncScripts;
-
     for (CachedScript* next = mSavedScripts.getFirst(); next; ) {
         CachedScript* script = next;
         next = script->getNext();
 
         // Don't write any scripts that are also in the child cache. They'll be
         // loaded from the child cache in that case, so there's no need to write
         // them twice.
         CachedScript* childScript = mChildCache ? mChildCache->mScripts.Get(script->mCachePath) : nullptr;
@@ -574,30 +572,19 @@ ScriptPreloader::PrepareCacheWrite()
             }
         }
 
         if (childScript || (!script->mSize && !script->XDREncode(jsapi.cx()))) {
             script->remove();
             delete script;
         } else {
             script->mSize = script->Range().length();
-
-            if (script->mSize > MIN_OFFTHREAD_SIZE) {
-                script->remove();
-                asyncScripts.insertBack(script);
-            }
         }
     }
 
-    // Store async-decoded scripts contiguously, since they're loaded
-    // immediately at startup.
-    while (CachedScript* s = asyncScripts.popLast()) {
-        mSavedScripts.insertFront(s);
-    }
-
     mDataPrepared = true;
 }
 
 // Writes out a script cache file for the scripts accessed during early
 // startup in this session. The cache file is a little-endian binary file with
 // the following format:
 //
 // - A uint32 containing the size of the header block.
@@ -636,33 +623,42 @@ ScriptPreloader::WriteCache()
     NS_TRY(cacheFile->Exists(&exists));
     if (exists) {
         NS_TRY(cacheFile->Remove(false));
     }
 
     AutoFDClose fd;
     NS_TRY(cacheFile->OpenNSPRFileDesc(PR_WRONLY | PR_CREATE_FILE, 0644, &fd.rwget()));
 
+    nsTArray<CachedScript*> scripts;
+    for (auto script : mSavedScripts) {
+        scripts.AppendElement(script);
+    }
+
+    // Sort scripts by load time, with async loaded scripts before sync scripts.
+    // Since async scripts are always loaded immediately at startup, it helps to
+    // have them stored contiguously.
+    scripts.Sort(CachedScript::Comparator());
+
     OutputBuffer buf;
     size_t offset = 0;
-    for (auto script : mSavedScripts) {
+    for (auto script : scripts) {
         script->mOffset = offset;
         script->Code(buf);
 
         offset += script->mSize;
     }
 
     uint8_t headerSize[4];
     LittleEndian::writeUint32(headerSize, buf.cursor());
 
     MOZ_TRY(Write(fd, MAGIC, sizeof(MAGIC)));
     MOZ_TRY(Write(fd, headerSize, sizeof(headerSize)));
     MOZ_TRY(Write(fd, buf.Get(), buf.cursor()));
-
-    for (auto script : mSavedScripts) {
+    for (auto script : scripts) {
         MOZ_TRY(Write(fd, script->Range().begin().get(), script->mSize));
 
         if (script->mScript) {
             script->FreeData();
         }
     }
 
     NS_TRY(cacheFile->MoveTo(nullptr, mBaseName + NS_LITERAL_STRING(".bin")));
@@ -734,22 +730,24 @@ ScriptPreloader::NoteScript(const nsCStr
     } else if (!script) {
         script = new CachedScript(*this, url, cachePath, jsscript);
         mSavedScripts.insertBack(script);
         mScripts.Put(cachePath, script);
     } else {
         return;
     }
 
+    script->UpdateLoadTime(TimeStamp::Now());
     script->mProcessTypes += CurrentProcessType();
 }
 
 void
 ScriptPreloader::NoteScript(const nsCString& url, const nsCString& cachePath,
-                            ProcessType processType, nsTArray<uint8_t>&& xdrData)
+                            ProcessType processType, nsTArray<uint8_t>&& xdrData,
+                            TimeStamp loadTime)
 {
     CachedScript* script = mScripts.Get(cachePath);
     bool restored = script && FindScript(mRestoredScripts, cachePath);
 
     if (restored) {
         script->remove();
         mSavedScripts.insertBack(script);
 
@@ -767,16 +765,17 @@ ScriptPreloader::NoteScript(const nsCStr
             script->mSize = xdrData.Length();
             script->mXDRData.construct<nsTArray<uint8_t>>(Forward<nsTArray<uint8_t>>(xdrData));
 
             auto& data = script->Array();
             script->mXDRRange.emplace(data.Elements(), data.Length());
         }
     }
 
+    script->UpdateLoadTime(loadTime);
     script->mProcessTypes += processType;
 }
 
 JSScript*
 ScriptPreloader::GetCachedScript(JSContext* cx, const nsCString& path)
 {
     // If a script is used by both the parent and the child, it's stored only
     // in the child cache.

--- a/js/xpconnect/loader/ScriptPreloader.h
+++ b/js/xpconnect/loader/ScriptPreloader.h
@@ -71,17 +71,18 @@ public:
     JSScript* GetCachedScript(JSContext* cx, const nsCString& name);
 
     // Notes the execution of a script with the given URL and cache key.
     // Depending on the stage of startup, the script may be serialized and
     // stored to the startup script cache.
     void NoteScript(const nsCString& url, const nsCString& cachePath, JS::HandleScript script);
 
     void NoteScript(const nsCString& url, const nsCString& cachePath,
-                    ProcessType processType, nsTArray<uint8_t>&& xdrData);
+                    ProcessType processType, nsTArray<uint8_t>&& xdrData,
+                    TimeStamp loadTime);
 
     // Initializes the script cache from the startup script cache file.
     Result<Ok, nsresult> InitCache(const nsAString& = NS_LITERAL_STRING("scriptCache"));
 
     Result<Ok, nsresult> InitCache(const Maybe<ipc::FileDescriptor>& cacheFile, ScriptCacheChild* cacheChild);
 
 private:
     Result<Ok, nsresult> InitCacheInternal();
@@ -143,28 +144,64 @@ private:
         {
 #ifdef DEBUG
             auto hashValue = mCache->mScripts.Get(mCachePath);
             MOZ_ASSERT_IF(hashValue, hashValue == this);
 #endif
             mCache->mScripts.Remove(mCachePath);
         }
 
+        // For use with nsTArray::Sort.
+        //
+        // Orders scripts by:
+        //
+        // 1) Async-decoded scripts before sync-decoded scripts, since the
+        //    former are needed immediately at startup, and should be stored
+        //    contiguously.
+        // 2) Script load time, so that scripts which are needed earlier are
+        //    stored earlier, and scripts needed at approximately the same
+        //    time are stored approximately contiguously.
+        struct Comparator
+        {
+            bool Equals(const CachedScript* a, const CachedScript* b) const
+            {
+              return (a->AsyncDecodable() == b->AsyncDecodable() &&
+                      a->mLoadTime == b->mLoadTime);
+            }
+
+            bool LessThan(const CachedScript* a, const CachedScript* b) const
+            {
+              if (a->AsyncDecodable() != b->AsyncDecodable()) {
+                return a->AsyncDecodable();
+              }
+              return a->mLoadTime < b->mLoadTime;
+            }
+        };
+
         void Cancel();
 
         void FreeData()
         {
             // If the script data isn't mmapped, we need to release both it
             // and the Range that points to it at the same time.
             if (!mXDRData.empty()) {
                 mXDRRange.reset();
                 mXDRData.destroy();
             }
         }
 
+        void UpdateLoadTime(const TimeStamp& loadTime)
+        {
+          if (!mLoadTime || loadTime < mLoadTime) {
+            mLoadTime = loadTime;
+          }
+        }
+
+        bool AsyncDecodable() const { return mSize > MIN_OFFTHREAD_SIZE; }
+
         // Encodes this script into XDR data, and stores the result in mXDRData.
         // Returns true on success, false on failure.
         bool XDREncode(JSContext* cx);
 
         // Encodes or decodes this script, in the storage format required by the
         // script cache file.
         template<typename Buffer>
         void Code(Buffer& buffer)
@@ -232,16 +269,18 @@ private:
         nsCString mCachePath;
 
         // The offset of this script in the cache file, from the start of the XDR
         // data block.
         uint32_t mOffset = 0;
         // The size of this script's encoded XDR data.
         uint32_t mSize = 0;
 
+        TimeStamp mLoadTime{};
+
         JS::Heap<JSScript*> mScript;
 
         // True if this script is ready to be executed. This means that either the
         // off-thread portion of an off-thread decode has finished, or the script
         // is too small to be decoded off-thread, and may be immediately decoded
         // whenever it is first executed.
         bool mReadyToExecute = false;