--- a/netwerk/cache2/CacheIndex.cpp
+++ b/netwerk/cache2/CacheIndex.cpp
@@ -38,26 +38,39 @@ namespace mozilla {
 namespace net {
 
 namespace {
 
 class FrecencyComparator
 {
 public:
   bool Equals(CacheIndexRecord* a, CacheIndexRecord* b) const {
+    if (!a || !b) {
+      return false;
+    }
+
     return a->mFrecency == b->mFrecency;
   }
   bool LessThan(CacheIndexRecord* a, CacheIndexRecord* b) const {
-    // Place entries with frecency 0 at the end of the array.
+    // Removed (=null) entries must be at the end of the array.
+    if (!a) {
+      return false;
+    }
+    if (!b) {
+      return true;
+    }
+
+    // Place entries with frecency 0 at the end of the non-removed entries.
     if (a->mFrecency == 0) {
       return false;
     }
     if (b->mFrecency == 0) {
       return true;
     }
+
     return a->mFrecency < b->mFrecency;
   }
 };
 
 } // namespace
 
 /**
  * This helper class is responsible for keeping CacheIndex::mIndexStats and
@@ -90,29 +103,49 @@ public:
 
     const CacheIndexEntry *entry = FindEntry();
     mIndex->mIndexStats.AfterChange(entry);
     if (!entry || !entry->IsInitialized() || entry->IsRemoved()) {
       entry = nullptr;
     }
 
     if (entry && !mOldRecord) {
-      mIndex->InsertRecordToFrecencyArray(entry->mRec);
+      mIndex->mFrecencyArray.AppendRecord(entry->mRec);
       mIndex->AddRecordToIterators(entry->mRec);
     } else if (!entry && mOldRecord) {
-      mIndex->RemoveRecordFromFrecencyArray(mOldRecord);
+      mIndex->mFrecencyArray.RemoveRecord(mOldRecord);
       mIndex->RemoveRecordFromIterators(mOldRecord);
     } else if (entry && mOldRecord) {
       if (entry->mRec != mOldRecord) {
         // record has a different address, we have to replace it
         mIndex->ReplaceRecordInIterators(mOldRecord, entry->mRec);
-        mIndex->RemoveRecordFromFrecencyArray(mOldRecord);
-        mIndex->InsertRecordToFrecencyArray(entry->mRec);
+
+        if (entry->mRec->mFrecency == mOldFrecency) {
+          // If frecency hasn't changed simply replace the pointer
+          mIndex->mFrecencyArray.ReplaceRecord(mOldRecord, entry->mRec);
+        } else {
+          // It is expected that when the frecency is changed the new value is
+          // always bigger than the old one. There is also a special case when
+          // we zero the frecency if eviction of the entry fails. If the above
+          // isn't true, this algorithm might not work properly and needs to be
+          // changed.
+          MOZ_ASSERT(entry->mRec->mFrecency == 0 ||
+                     entry->mRec->mFrecency > mOldFrecency);
+
+          // Remove old pointer and insert the new one at the end of the array
+          mIndex->mFrecencyArray.RemoveRecord(mOldRecord);
+          mIndex->mFrecencyArray.AppendRecord(entry->mRec);
+        }
       } else if (entry->mRec->mFrecency != mOldFrecency) {
-        mIndex->mFrecencyArraySorted = false;
+        MOZ_ASSERT(entry->mRec->mFrecency == 0 ||
+                   entry->mRec->mFrecency > mOldFrecency);
+
+        // Move the element at the end of the array
+        mIndex->mFrecencyArray.RemoveRecord(entry->mRec);
+        mIndex->mFrecencyArray.AppendRecord(entry->mRec);
       }
     } else {
       // both entries were removed or not initialized, do nothing
     }
   }
 
   // We cannot rely on nsTHashtable::GetEntry() in case we are removing entries
   // while iterating. Destructor is called before the entry is removed. Caller
@@ -247,17 +280,16 @@ CacheIndex::CacheIndex()
   , mUpdateEventPending(false)
   , mSkipEntries(0)
   , mProcessEntries(0)
   , mRWBuf(nullptr)
   , mRWBufSize(0)
   , mRWBufPos(0)
   , mRWPending(false)
   , mJournalReadSuccessfully(false)
-  , mFrecencyArraySorted(false)
   , mAsyncGetDiskConsumptionBlocked(false)
 {
   sLock.AssertCurrentThreadOwns();
   LOG(("CacheIndex::CacheIndex [this=%p]", this));
   MOZ_COUNT_CTOR(CacheIndex);
   MOZ_ASSERT(!gInstance, "multiple CacheIndex instances!");
 }
 
@@ -1185,53 +1217,54 @@ CacheIndex::GetEntryForEviction(bool aIg
   if (!index)
     return NS_ERROR_NOT_INITIALIZED;
 
   if (!index->IsIndexUsable()) {
     return NS_ERROR_NOT_AVAILABLE;
   }
 
   SHA1Sum::Hash hash;
-  bool foundEntry = false;
-  uint32_t i;
+  CacheIndexRecord *foundRecord = nullptr;
+  uint32_t skipped = 0;
 
   // find first non-forced valid and unpinned entry with the lowest frecency
-  if (!index->mFrecencyArraySorted) {
-    index->mFrecencyArray.Sort(FrecencyComparator());
-    index->mFrecencyArraySorted = true;
-  }
-
-  for (i = 0; i < index->mFrecencyArray.Length(); ++i) {
-    memcpy(&hash, &index->mFrecencyArray[i]->mHash, sizeof(SHA1Sum::Hash));
+  index->mFrecencyArray.SortIfNeeded();
+
+  for (auto iter = index->mFrecencyArray.Iter(); !iter.Done(); iter.Next()) {
+    CacheIndexRecord *rec = iter.Get();
+
+    memcpy(&hash, rec->mHash, sizeof(SHA1Sum::Hash));
+
+    ++skipped;
 
     if (IsForcedValidEntry(&hash)) {
       continue;
     }
 
-    if (CacheIndexEntry::IsPinned(index->mFrecencyArray[i])) {
+    if (CacheIndexEntry::IsPinned(rec)) {
       continue;
     }
 
-    if (aIgnoreEmptyEntries &&
-        !CacheIndexEntry::GetFileSize(index->mFrecencyArray[i])) {
+    if (aIgnoreEmptyEntries && !CacheIndexEntry::GetFileSize(rec)) {
       continue;
     }
 
-    foundEntry = true;
+    --skipped;
+    foundRecord = rec;
     break;
   }
 
-  if (!foundEntry)
+  if (!foundRecord)
     return NS_ERROR_NOT_AVAILABLE;
 
-  *aCnt = index->mFrecencyArray.Length() - i;
+  *aCnt = skipped;
 
   LOG(("CacheIndex::GetEntryForEviction() - returning entry from frecency "
         "array [hash=%08x%08x%08x%08x%08x, cnt=%u, frecency=%u]",
-        LOGSHA1(&hash), *aCnt, index->mFrecencyArray[i]->mFrecency));
+        LOGSHA1(&hash), *aCnt, foundRecord->mFrecency));
 
   memcpy(aHash, &hash, sizeof(SHA1Sum::Hash));
 
   return NS_OK;
 }
 
 
 // static
@@ -1315,18 +1348,18 @@ CacheIndex::GetCacheStats(nsILoadContext
 
   if (!aInfo) {
     return NS_ERROR_INVALID_ARG;
   }
 
   *aSize = 0;
   *aCount = 0;
 
-  for (uint32_t i = 0; i < index->mFrecencyArray.Length(); ++i) {
-    CacheIndexRecord* record = index->mFrecencyArray[i];
+  for (auto iter = index->mFrecencyArray.Iter(); !iter.Done(); iter.Next()) {
+    CacheIndexRecord *record = iter.Get();
     if (!CacheIndexEntry::RecordMatchesLoadContextInfo(record, aInfo))
       continue;
 
     *aSize += CacheIndexEntry::GetFileSize(record);
     ++*aCount;
   }
 
   return NS_OK;
@@ -1399,32 +1432,31 @@ CacheIndex::GetIterator(nsILoadContextIn
   if (!index) {
     return NS_ERROR_NOT_INITIALIZED;
   }
 
   if (!index->IsIndexUsable()) {
     return NS_ERROR_NOT_AVAILABLE;
   }
 
-  RefPtr<CacheIndexIterator> iter;
+  RefPtr<CacheIndexIterator> idxIter;
   if (aInfo) {
-    iter = new CacheIndexContextIterator(index, aAddNew, aInfo);
+    idxIter = new CacheIndexContextIterator(index, aAddNew, aInfo);
   } else {
-    iter = new CacheIndexIterator(index, aAddNew);
+    idxIter = new CacheIndexIterator(index, aAddNew);
   }
 
-  if (!index->mFrecencyArraySorted) {
-    index->mFrecencyArray.Sort(FrecencyComparator());
-    index->mFrecencyArraySorted = true;
+  index->mFrecencyArray.SortIfNeeded();
+
+  for (auto iter = index->mFrecencyArray.Iter(); !iter.Done(); iter.Next()) {
+    idxIter->AddRecord(iter.Get());
   }
 
-  iter->AddRecords(index->mFrecencyArray);
-
-  index->mIterators.AppendElement(iter);
-  iter.swap(*_retval);
+  index->mIterators.AppendElement(idxIter);
+  idxIter.swap(*_retval);
   return NS_OK;
 }
 
 // static
 nsresult
 CacheIndex::IsUpToDate(bool *_retval)
 {
   LOG(("CacheIndex::IsUpToDate()"));
@@ -3226,34 +3258,90 @@ CacheIndex::ReleaseBuffer()
 
   free(mRWBuf);
   mRWBuf = nullptr;
   mRWBufSize = 0;
   mRWBufPos = 0;
 }
 
 void
-CacheIndex::InsertRecordToFrecencyArray(CacheIndexRecord *aRecord)
+CacheIndex::FrecencyArray::AppendRecord(CacheIndexRecord *aRecord)
 {
-  LOG(("CacheIndex::InsertRecordToFrecencyArray() [record=%p, hash=%08x%08x%08x"
+  LOG(("CacheIndex::FrecencyArray::AppendRecord() [record=%p, hash=%08x%08x%08x"
        "%08x%08x]", aRecord, LOGSHA1(aRecord->mHash)));
 
-  MOZ_ASSERT(!mFrecencyArray.Contains(aRecord));
-  mFrecencyArray.AppendElement(aRecord);
-  mFrecencyArraySorted = false;
+  MOZ_ASSERT(!mRecs.Contains(aRecord));
+  mRecs.AppendElement(aRecord);
+
+  // If the new frecency is 0, the element should be at the end of the array,
+  // i.e. this change doesn't affect order of the array
+  if (aRecord->mFrecency != 0) {
+    ++mUnsortedElements;
+  }
+}
+
+void
+CacheIndex::FrecencyArray::RemoveRecord(CacheIndexRecord *aRecord)
+{
+  LOG(("CacheIndex::FrecencyArray::RemoveRecord() [record=%p]", aRecord));
+
+  decltype(mRecs)::index_type idx;
+  idx = mRecs.IndexOf(aRecord);
+  MOZ_RELEASE_ASSERT(idx != mRecs.NoIndex);
+  mRecs[idx] = nullptr;
+  ++mRemovedElements;
+
+  // Calling SortIfNeeded ensures that we get rid of removed elements in the
+  // array once we hit the limit.
+  SortIfNeeded();
 }
 
 void
-CacheIndex::RemoveRecordFromFrecencyArray(CacheIndexRecord *aRecord)
+CacheIndex::FrecencyArray::ReplaceRecord(CacheIndexRecord *aOldRecord,
+                                         CacheIndexRecord *aNewRecord)
+{
+  LOG(("CacheIndex::FrecencyArray::ReplaceRecord() [oldRecord=%p, "
+       "newRecord=%p]", aOldRecord, aNewRecord));
+
+  decltype(mRecs)::index_type idx;
+  idx = mRecs.IndexOf(aOldRecord);
+  MOZ_RELEASE_ASSERT(idx != mRecs.NoIndex);
+  mRecs[idx] = aNewRecord;
+}
+
+void
+CacheIndex::FrecencyArray::SortIfNeeded()
 {
-  LOG(("CacheIndex::RemoveRecordFromFrecencyArray() [record=%p]", aRecord));
-
-  DebugOnly<bool> removed;
-  removed = mFrecencyArray.RemoveElement(aRecord);
-  MOZ_ASSERT(removed);
+  const uint32_t kMaxUnsortedCount = 512;
+  const uint32_t kMaxUnsortedPercent = 10;
+  const uint32_t kMaxRemovedCount = 512;
+
+  uint32_t unsortedLimit =
+    std::min<uint32_t>(kMaxUnsortedCount, Length() * kMaxUnsortedPercent / 100);
+
+  if (mUnsortedElements > unsortedLimit ||
+      mRemovedElements > kMaxRemovedCount) {
+    LOG(("CacheIndex::FrecencyArray::SortIfNeeded() - Sorting array "
+       "[unsortedElements=%u, unsortedLimit=%u, removedElements=%u, "
+       "maxRemovedCount=%u]", mUnsortedElements, unsortedLimit,
+       mRemovedElements, kMaxRemovedCount));
+
+    mRecs.Sort(FrecencyComparator());
+    mUnsortedElements = 0;
+    if (mRemovedElements) {
+#ifdef DEBUG
+      for (uint32_t i = Length(); i < mRecs.Length(); ++i) {
+        MOZ_ASSERT(!mRecs[i]);
+      }
+#endif
+      // Removed elements are at the end after sorting.
+      mRecs.RemoveElementsAt(Length(), mRemovedElements);
+      mRemovedElements = 0;
+    }
+  }
 }
 
 void
 CacheIndex::AddRecordToIterators(CacheIndexRecord *aRecord)
 {
   sLock.AssertCurrentThreadOwns();
 
   for (uint32_t i = 0; i < mIterators.Length(); ++i) {
@@ -3621,17 +3709,17 @@ CacheIndex::SizeOfExcludingThisInternal(
   n += mallocSizeOf(mRWBuf);
   n += mallocSizeOf(mRWHash);
 
   n += mIndex.SizeOfExcludingThis(mallocSizeOf);
   n += mPendingUpdates.SizeOfExcludingThis(mallocSizeOf);
   n += mTmpJournal.SizeOfExcludingThis(mallocSizeOf);
 
   // mFrecencyArray items are reported by mIndex/mPendingUpdates
-  n += mFrecencyArray.ShallowSizeOfExcludingThis(mallocSizeOf);
+  n += mFrecencyArray.mRecs.ShallowSizeOfExcludingThis(mallocSizeOf);
   n += mDiskConsumptionObservers.ShallowSizeOfExcludingThis(mallocSizeOf);
 
   return n;
 }
 
 // static
 size_t
 CacheIndex::SizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf)
@@ -3705,17 +3793,19 @@ void
 CacheIndex::ReportHashStats()
 {
   // We're gathering the hash stats only once, exclude too small caches.
   if (CacheObserver::HashStatsReported() || mFrecencyArray.Length() < 15000) {
     return;
   }
 
   nsTArray<CacheIndexRecord *> records;
-  records.AppendElements(mFrecencyArray);
+  for (auto iter = mFrecencyArray.Iter(); !iter.Done(); iter.Next()) {
+    records.AppendElement(iter.Get());
+  }
 
   records.Sort(HashComparator());
 
   for (uint32_t i = 1; i < records.Length(); i++) {
     ReportHashSizeMatch(&records[i-1]->mHash, &records[i]->mHash);
   }
 
   CacheObserver::SetHashStatsReported();

--- a/netwerk/cache2/CacheIndex.h
+++ b/netwerk/cache2/CacheIndex.h
@@ -916,20 +916,16 @@ private:
   static char const * StateString(EState aState);
   void ChangeState(EState aNewState);
   void NotifyAsyncGetDiskConsumptionCallbacks();
 
   // Allocates and releases buffer used for reading and writing index.
   void AllocBuffer();
   void ReleaseBuffer();
 
-  // Methods used by CacheIndexEntryAutoManage to keep the arrays up to date.
-  void InsertRecordToFrecencyArray(CacheIndexRecord *aRecord);
-  void RemoveRecordFromFrecencyArray(CacheIndexRecord *aRecord);
-
   // Methods used by CacheIndexEntryAutoManage to keep the iterators up to date.
   void AddRecordToIterators(CacheIndexRecord *aRecord);
   void RemoveRecordFromIterators(CacheIndexRecord *aRecord);
   void ReplaceRecordInIterators(CacheIndexRecord *aOldRecord,
                                 CacheIndexRecord *aNewRecord);
 
   // Memory reporting (private part)
   size_t SizeOfExcludingThisInternal(mozilla::MallocSizeOf mallocSizeOf) const;
@@ -1026,22 +1022,89 @@ private:
   CacheIndexStats               mIndexStats;
 
   // When reading journal, we must first parse the whole file and apply the
   // changes iff the journal was read successfully. mTmpJournal is used to store
   // entries from the journal file. We throw away all these entries if parsing
   // of the journal fails or the hash does not match.
   nsTHashtable<CacheIndexEntry> mTmpJournal;
 
-  // An array that keeps entry records ordered by eviction preference; we take
-  // the entry with lowest valid frecency. Zero frecency is an initial value
-  // and such entries are stored at the end of the array. Uninitialized entries
-  // and entries marked as deleted are not present in this array.
-  nsTArray<CacheIndexRecord *>  mFrecencyArray;
-  bool                          mFrecencyArraySorted;
+  // FrecencyArray maintains order of entry records for eviction. Ideally, the
+  // records would be ordered by frecency all the time, but since this would be
+  // quite expensive, we allow certain amount of entries to be out of order.
+  // When the frecency is updated the new value is always bigger than the old
+  // one. Instead of keeping updated entries at the same position, we move them
+  // at the end of the array. This protects recently updated entries from
+  // eviction. The array is sorted once we hit the limit of maximum unsorted
+  // entries.
+  class FrecencyArray
+  {
+    class Iterator
+    {
+    public:
+      explicit Iterator(nsTArray<CacheIndexRecord *> *aRecs)
+        : mRecs(aRecs)
+        , mIdx(0)
+      {
+        while (!Done() && !(*mRecs)[mIdx]) {
+          mIdx++;
+        }
+      }
+
+      bool Done() const { return mIdx == mRecs->Length(); }
+
+      CacheIndexRecord* Get() const
+      {
+        MOZ_ASSERT(!Done());
+        return (*mRecs)[mIdx];
+      }
+
+      void Next()
+      {
+        MOZ_ASSERT(!Done());
+        ++mIdx;
+        while (!Done() && !(*mRecs)[mIdx]) {
+          mIdx++;
+        }
+      }
+
+    private:
+      nsTArray<CacheIndexRecord *> *mRecs;
+      uint32_t mIdx;
+    };
+
+  public:
+    Iterator Iter() { return Iterator(&mRecs); }
+
+    FrecencyArray() : mUnsortedElements(0)
+                    , mRemovedElements(0) {}
+
+    // Methods used by CacheIndexEntryAutoManage to keep the array up to date.
+    void AppendRecord(CacheIndexRecord *aRecord);
+    void RemoveRecord(CacheIndexRecord *aRecord);
+    void ReplaceRecord(CacheIndexRecord *aOldRecord,
+                       CacheIndexRecord *aNewRecord);
+    void SortIfNeeded();
+
+    size_t Length() const { return mRecs.Length() - mRemovedElements; }
+    void Clear() { mRecs.Clear(); }
+
+  private:
+    friend class CacheIndex;
+
+    nsTArray<CacheIndexRecord *> mRecs;
+    uint32_t                     mUnsortedElements;
+    // Instead of removing elements from the array immediately, we null them out
+    // and the iterator skips them when accessing the array. The null pointers
+    // are placed at the end during sorting and we strip them out all at once.
+    // This saves moving a lot of memory in nsTArray::RemoveElementsAt.
+    uint32_t                     mRemovedElements;
+  };
+
+  FrecencyArray mFrecencyArray;
 
   nsTArray<CacheIndexIterator *> mIterators;
 
   // This flag is true iff we are between CacheStorageService:Clear() and processing
   // all contexts to be evicted.  It will make UI to show "calculating" instead of
   // any intermediate cache size.
   bool mAsyncGetDiskConsumptionBlocked;
 

--- a/netwerk/cache2/CacheIndexIterator.cpp
+++ b/netwerk/cache2/CacheIndexIterator.cpp
@@ -85,24 +85,16 @@ CacheIndexIterator::CloseInternal(nsresu
 void
 CacheIndexIterator::AddRecord(CacheIndexRecord *aRecord)
 {
   LOG(("CacheIndexIterator::AddRecord() [this=%p, record=%p]", this, aRecord));
 
   mRecords.AppendElement(aRecord);
 }
 
-void
-CacheIndexIterator::AddRecords(const nsTArray<CacheIndexRecord *> &aRecords)
-{
-  LOG(("CacheIndexIterator::AddRecords() [this=%p]", this));
-
-  mRecords.AppendElements(aRecords);
-}
-
 bool
 CacheIndexIterator::RemoveRecord(CacheIndexRecord *aRecord)
 {
   LOG(("CacheIndexIterator::RemoveRecord() [this=%p, record=%p]", this,
        aRecord));
 
   return mRecords.RemoveElement(aRecord);
 }

--- a/netwerk/cache2/CacheIndexIterator.h
+++ b/netwerk/cache2/CacheIndexIterator.h
@@ -38,17 +38,16 @@ public:
 
 protected:
   friend class CacheIndex;
 
   nsresult CloseInternal(nsresult aStatus);
 
   bool ShouldBeNewAdded() { return mAddNew; }
   virtual void AddRecord(CacheIndexRecord *aRecord);
-  virtual void AddRecords(const nsTArray<CacheIndexRecord *> &aRecords);
   bool RemoveRecord(CacheIndexRecord *aRecord);
   bool ReplaceRecord(CacheIndexRecord *aOldRecord,
                      CacheIndexRecord *aNewRecord);
 
   nsresult                     mStatus;
   RefPtr<CacheIndex>           mIndex;
   nsTArray<CacheIndexRecord *> mRecords;
   bool                         mAddNew;