Bug 1249304 - Optimize sorting of CacheIndex::mFrecencyArray, r=honzab
authorMichal Novotny <michal.novotny@gmail.com>
Thu, 06 Oct 2016 11:23:52 +0200
changeset 316814 86045bf00531d709031889f5fe27061ac8a522b6
parent 316813 b508adb15d65a4e5cf535e987b1e0da8d6d7a77f
child 316815 01bf91bcaeb2f2fa2123e8c2516568e569ef73d7
push id32932
push userphilringnalda@gmail.com
push dateFri, 07 Oct 2016 03:24:25 +0000
treeherderautoland@7affb66131bb [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewershonzab
bugs1249304
milestone52.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1249304 - Optimize sorting of CacheIndex::mFrecencyArray, r=honzab
netwerk/cache2/CacheIndex.cpp
netwerk/cache2/CacheIndex.h
netwerk/cache2/CacheIndexIterator.cpp
netwerk/cache2/CacheIndexIterator.h
--- 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;