Closed Bug 1249304 Opened 5 years ago Closed 4 years ago

Optimize sorting of CacheIndex::mFrecencyArray

Categories

(Core :: Networking: Cache, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla52
Tracking Status
firefox47 --- affected
firefox52 --- fixed

People

(Reporter: michal, Assigned: michal)

Details

(Whiteboard: [necko-active])

Attachments

(1 file, 1 obsolete file)

Sorting frecency array in CacheIndex can take quite a lot of time. The problem was fixed partially in bug 1248389 so that we call sort() only when we append some element to the array, i.e. the array is unsorted. This helps only in case the cache is resized and we need to evict a lot of entries to match the new size. If we need to evict some entry because the cache is over the limit while browsing normally, we would always end up sorting the array because the array will be unsorted due to newly added entry.
Just an idea, but what using heap sort?
Whiteboard: [necko-active]
Attached patch patch (obsolete) — Splinter Review
FrecencyArray class has a detailed comment explaining the logic. Please note that there is no particular reason for the chosen values of kMaxUnsortedCount, kMaxUnsortedPercent and kMaxRemovedCount.
Attachment #8795664 - Flags: review?(honzab.moz)
Comment on attachment 8795664 [details] [diff] [review]
patch

Review of attachment 8795664 [details] [diff] [review]:
-----------------------------------------------------------------

didn't test locally.

::: netwerk/cache2/CacheIndex.cpp
@@ +50,4 @@
>      return a->mFrecency == b->mFrecency;
>    }
>    bool LessThan(CacheIndexRecord* a, CacheIndexRecord* b) const {
> +    // Removed entries must be at the end of the array.

Removed (=null) entries

@@ +129,2 @@
>        } else if (entry->mRec->mFrecency != mOldFrecency) {
> +        // Move the element at the end of the array

maybe add MOZ_ASSERT(entry->mRec->mFrecency > mOldFrecency) ?  just for fun :)

@@ +3272,4 @@
>  {
> +  LOG(("CacheIndex::FrecencyArray::RemoveRecord() [record=%p]", aRecord));
> +
> +  nsTArray<CacheIndexRecord *>::index_type idx;

you can also do:

decltype(mRecs)::index_type

@@ +3273,5 @@
> +  LOG(("CacheIndex::FrecencyArray::RemoveRecord() [record=%p]", aRecord));
> +
> +  nsTArray<CacheIndexRecord *>::index_type idx;
> +  idx = mRecs.IndexOf(aRecord);
> +  MOZ_RELEASE_ASSERT(idx != mRecs.NoIndex);

would MOZ_DISAGNOSTIC_ASSERT be enough?  or we are totally screwed when this fails?

@@ +3290,5 @@
> +  LOG(("CacheIndex::FrecencyArray::ReplaceRecord() [oldRecord=%p, "
> +       "newRecord=%p]", aOldRecord, aNewRecord));
> +
> +  nsTArray<CacheIndexRecord *>::index_type idx;
> +  idx = mRecs.IndexOf(aOldRecord);

IndexOf is btw expensive too..  this does a flat scan

::: netwerk/cache2/CacheIndex.h
@@ +1094,5 @@
> +    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::RemoteElementsAt.

Remo*v*eElementsAt
Attachment #8795664 - Flags: review?(honzab.moz) → review+
Attached patch patch v2Splinter Review
(In reply to Honza Bambas (:mayhemer) from comment #3)
> @@ +3273,5 @@
> > +  LOG(("CacheIndex::FrecencyArray::RemoveRecord() [record=%p]", aRecord));
> > +
> > +  nsTArray<CacheIndexRecord *>::index_type idx;
> > +  idx = mRecs.IndexOf(aRecord);
> > +  MOZ_RELEASE_ASSERT(idx != mRecs.NoIndex);
> 
> would MOZ_DISAGNOSTIC_ASSERT be enough?  or we are totally screwed when this
> fails?

Yes, if it ever happens we're screwed. If I change it to diagnostic assert we would access mRecs[-1] just one line below. It's better to crash on the assertion.
Attachment #8795664 - Attachment is obsolete: true
Attachment #8798039 - Flags: review+
Pushed by mnovotny@mozilla.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/86045bf00531
Optimize sorting of CacheIndex::mFrecencyArray, r=honzab
https://hg.mozilla.org/mozilla-central/rev/86045bf00531
Status: NEW → RESOLVED
Closed: 4 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla52
You need to log in before you can comment on or make changes to this bug.