nsUrlClassifierPrefixSet does not correctly compact its storage

RESOLVED FIXED in Firefox 47

Status

()

Core
XPCOM
RESOLVED FIXED
2 years ago
2 years ago

People

(Reporter: gcp, Unassigned)

Tracking

Trunk
mozilla47
x86_64
Linux
Points:
---

Firefox Tracking Flags

(firefox47 fixed)

Details

Attachments

(1 attachment)

(Reporter)

Description

2 years ago
https://bugzilla.mozilla.org/show_bug.cgi?id=1205358#c13

I had a look at this, and the difference in the relevant code is:
https://dxr.mozilla.org/mozilla-central/rev/ac39fba33c6daf95b2cda71e588ca18e2eb752ab/toolkit/components/url-classifier/nsUrlClassifierPrefixSet.cpp#350
https://dxr.mozilla.org/mozilla-central/rev/ac39fba33c6daf95b2cda71e588ca18e2eb752ab/toolkit/components/url-classifier/nsUrlClassifierPrefixSet.cpp#375

versus:

https://dxr.mozilla.org/mozilla-central/rev/ac39fba33c6daf95b2cda71e588ca18e2eb752ab/toolkit/components/url-classifier/nsUrlClassifierPrefixSet.cpp#116
https://dxr.mozilla.org/mozilla-central/rev/ac39fba33c6daf95b2cda71e588ca18e2eb752ab/toolkit/components/url-classifier/nsUrlClassifierPrefixSet.cpp#128

Based on this, it looks like calling nsTArray.Compact() afterwards is not as memory efficient as calling nsTArray.SetLength() with the right size in advance. This seems unexpected to me. I would understand that there's copying overhead with Compact() afterwards that you don't get with SetLength() in advance, but if Compact() doesn't efficiently compact the memory usage, then it seems rather pointless.
Is there some sort of benchmark (and/or STR) we can run so we can add some logging and see where the memory is being wasted?  I could easily believe that jemalloc would not reallocate the memory in some situations.
Flags: needinfo?(gpascutto)
(Reporter)

Comment 2

2 years ago
What you can do on a fully updated Firefox profile is to set
browser.safebrowsing.provider.google.nextupdatetime=-1

And restart with:
export NSPR_LOG_MODULES=UrlClassifierDbService:5,UrlClassifierPrefixSet:5

This will force an update shortly after next startup. Look for the  "SB tree done, size = 798800 bytes" messages. The first values are the "SetLength" ones (you'll get one for every database we have), the next ones are the "Compact" ones. (There'll also have been a DB update causing slight size changes in-between, but the effect is much less than the reported memory on a "mature" profile).

On my profile, this produces:

1120925440[7fc43b032380]: SB tree done, size = 249952 bytes  (goog-badbinurl-shavar)
1120925440[7fc43b032380]: SB tree done, size = 112 bytes     (test tables, I'll skip these)
1120925440[7fc43b032380]: SB tree done, size = 654528 bytes  (goog-malware-shavar)
1120925440[7fc43b032380]: SB tree done, size = 605952 bytes  (goog-unwanted-shavar)
1120925440[7fc43b032380]: SB tree done, size = 648832 bytes  (goog-phish-shavar)
<updates go through>
1120925440[7fc43b032380]: SB tree done, size = 249952 bytes  (goog-badbinurl-shavar)
1120925440[7fc43b032380]: SB tree done, size = 752224 bytes  (goog-malware-shavar)
1120925440[7fc43b032380]: SB tree done, size = 745680 bytes  (goog-phish-shavar)
1120925440[7fc43b032380]: SB tree done, size = 654016 bytes  (goog-unwanted-shavar)

Same again, next startup:
-1558190336[7f9697e31380]: SB tree done, size = 249952 bytes 
-1558190336[7f9697e31380]: SB tree done, size = 637584 bytes
-1558190336[7f9697e31380]: SB tree done, size = 646128 bytes
-1558190336[7f9697e31380]: SB tree done, size = 641664 bytes

So even though the databases are identical to the post-update ones, the memory size is smaller again.
Flags: needinfo?(gpascutto)
(Reporter)

Comment 4

2 years ago
Okay, I see what is going on. 

The core datastructure is a large array of nsTArray<uint16_t> that are at most 120 elements long (max 256 bytes due to overhead).

When using SetLength, the reported sizes are things like:
-668993792[7fb0cb1a18e0]: mIndexDeltas[635]=176
-668993792[7fb0cb1a18e0]: mIndexDeltas[636]=192
-668993792[7fb0cb1a18e0]: mIndexDeltas[637]=64
-668993792[7fb0cb1a18e0]: mIndexDeltas[642]=144
-668993792[7fb0cb1a18e0]: mIndexDeltas[643]=80
-668993792[7fb0cb1a18e0]: mIndexDeltas[644]=240
-668993792[7fb0cb1a18e0]: mIndexDeltas[646]=208
-668993792[7fb0cb1a18e0]: mIndexDeltas[647]=176
-668993792[7fb0cb1a18e0]: mIndexDeltas[648]=16
-668993792[7fb0cb1a18e0]: mIndexDeltas[663]=160

When using Compact, the reported sizes are things like:
-668993792[7fb0cb1a18e0]: mIndexDeltas[644]=64
-668993792[7fb0cb1a18e0]: mIndexDeltas[645]=256
-668993792[7fb0cb1a18e0]: mIndexDeltas[646]=32
-668993792[7fb0cb1a18e0]: mIndexDeltas[647]=128
-668993792[7fb0cb1a18e0]: mIndexDeltas[648]=256

I am guessing that jemalloc actually hands out memory in power of 2 sizes, so isn't the first case incorrectly measuring the overhead?
Depends on the code you are using to report those sizes...but yes, it does look like the first case is incorrectly measuring the overhead.

Why are you using a two-level array rather than a single-level array with indices into it?  (It's possible that the slop might be worse in the latter case, depending on the sizes...)
(Reporter)

Comment 6

2 years ago
(In reply to Nathan Froyd [:froydnj] from comment #5)
> Depends on the code you are using to report those sizes...but yes, it does
> look like the first case is incorrectly measuring the overhead.

Nicholas, any input here?
 
> Why are you using a two-level array rather than a single-level array with
> indices into it?  (It's possible that the slop might be worse in the latter
> case, depending on the sizes...)

Read through bug 1046038 for the entire story.
Flags: needinfo?(n.nethercote)
(Reporter)

Comment 7

2 years ago
(In reply to Nathan Froyd [:froydnj] from comment #5)
> Depends on the code you are using to report those sizes...

https://dxr.mozilla.org/mozilla-central/rev/ac39fba33c6daf95b2cda71e588ca18e2eb752ab/toolkit/components/url-classifier/nsUrlClassifierPrefixSet.cpp#283

It's basically ShallowSizeOfExcludingThis on nsTArray.
(In reply to Gian-Carlo Pascutto [:gcp] from comment #7)
> (In reply to Nathan Froyd [:froydnj] from comment #5)
> > Depends on the code you are using to report those sizes...
> 
> https://dxr.mozilla.org/mozilla-central/rev/
> ac39fba33c6daf95b2cda71e588ca18e2eb752ab/toolkit/components/url-classifier/
> nsUrlClassifierPrefixSet.cpp#283
> 
> It's basically ShallowSizeOfExcludingThis on nsTArray.

And you're just printing out the return value for ShallowSizeOfExcludingThis in the log above?

I misspoke, jemalloc has a more complicated scheme for bucketing memory requests:

http://mxr.mozilla.org/mozilla-central/source/memory/mozjemalloc/jemalloc.c#47

What would be most interesting is to measure ShallowSizeOfExcludingThis before and after compaction, and log that...
Flags: needinfo?(gpascutto)
As I understand it:

- If you call SetLength() on an empty array, it'll allocate exactly the amount you ask for. If you call SetLength() on a non-empty array, it'll allocate the nearest power-of-two amount above what you asked for. (The logic is in EnsureCapacity().)

- If you call Compact() it should resize the array to the exact size. (Logic is in ShrinkCapacity().) As Nathan says, it's conceivable that jemalloc is choosing to stick with a larger size block.

I suggest that you print the following for each array such as mIndexDeltas:

- Length()
- Capacity()
- ShallowSizeOfExcludingThis()

(It would also be good to print sizeof(nsTArray<uint16_t>) so the element size is known.)

Those numbers should make it clear if the powers of two are coming from nsTArray or from jemalloc. E.g. if Capacity() is a power-of-two then you know it's coming from nsTArray; if Capacity() is not a power of two but ShallowSizeOfExcludingThis() is then you know it's coming from jemalloc.
Flags: needinfo?(n.nethercote)
(Reporter)

Comment 10

2 years ago
Created attachment 8718775 [details] [diff] [review]
Fix off-by-one error in PrefixSet Delta storage compaction

Welp.
Attachment #8718775 - Flags: review?(nfroyd)
(Reporter)

Updated

2 years ago
Flags: needinfo?(gpascutto)
Summary: nsTArray.Compact() is not as memory efficient as nsTArray.SetLength() → nsUrlClassifierPrefixSet does not correctly compact its storage
Comment on attachment 8718775 [details] [diff] [review]
Fix off-by-one error in PrefixSet Delta storage compaction

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

::: toolkit/components/url-classifier/nsUrlClassifierPrefixSet.cpp
@@ +114,5 @@
>            (aPrefixes[i] - currentItem >= MAX_INDEX_DIFF)) {
> +      // Compact the previous element.
> +      // Note there are always at least one elements when we get here,
> +      // because we created the first element before the loop.
> +      mIndexDeltas[mIndexDeltas.Length() - 1].Compact();

This is mIndexDeltas.LastElement().Compact() if you like that better.

Alternatively, you could just hold a pointer to the last element:

nsTArray<uint16_t>* currentDeltas = mIndexDeltas.AppendElement();

for (uint32_t i = 1; i < aLength, i++) {
  if (...) {
    currentDeltas->Compact();
    currentDeltas = mIndexDeltas.AppendElement();
    ...
  } else {
    ...
    currentDeltas->AppendElement(delta);
  }
}

then you don't have to bother thinking about whether your array indexing is correct, and it might even be slightly faster, since you're not constantly re-indexing mIndexDeltas.  (I don't think the compiler is smart enough to perform this transformation on its own, but it might.)

@@ +119,1 @@
>        mIndexDeltas.AppendElement();

Add a Compact() call after the loop to ensure that this element gets compacted as well?
Attachment #8718775 - Flags: review?(nfroyd) → review+
(Reporter)

Comment 12

2 years ago
https://hg.mozilla.org/integration/mozilla-inbound/rev/de6e8bf0990f99e0dfbe72a1b976c08fba068884
Bug 1247615 - Fix off-by-one error in PrefixSet Delta storage compaction. r=froydnj

Comment 13

2 years ago
bugherder
https://hg.mozilla.org/mozilla-central/rev/de6e8bf0990f
Status: NEW → RESOLVED
Last Resolved: 2 years ago
status-firefox47: affected → fixed
Resolution: --- → FIXED
Target Milestone: --- → mozilla47
You need to log in before you can comment on or make changes to this bug.