1249304 - Optimize sorting of CacheIndex::mFrecencyArray

Status: RESOLVED FIXED

(Core :: Networking: Cache, defect)

Description

[Michal Novotny [:michal]]

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.

Comment 1

[Honza Bambas (:mayhemer)]

Just an idea, but what using heap sort?

Comment 2

[Michal Novotny [:michal]]

Attachment: patch

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.

Comment 3

[Honza Bambas (:mayhemer)]

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

Comment 4

[Michal Novotny [:michal]]

Attachment: patch v2

(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.

Comment 5

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/86045bf00531
Optimize sorting of CacheIndex::mFrecencyArray, r=honzab

Comment 6

[Phil Ringnalda (:philor)]

https://hg.mozilla.org/mozilla-central/rev/86045bf00531