1017418 - Avoid slop in nsTArray

Status: RESOLVED WORKSFORME

(Core :: XPCOM, defect)

Description

[Nicholas Nethercote [inactive]]

Bug 685438 fixed one cause of slop in nsTArray, by making ensureCapacity() round up its allocations appropriately. But it overlooked the |mHdr == EmptyHdr()| case.

I did some measurements with over 50 tabs open, and this causes over 4 MiB of slop, which is our second-largest single source of slop.

Comment 1

[Nicholas Nethercote [inactive]]

Attachment: (part 1) - Don't assume that nsTArray::SetCapacity() will result in exactly the requested capacity

Currently, if you call nsTArray::SetCapacity() on an empty array it'll end up
having exactly the capacity you requested. But this isn't guaranteed, and this
code assumed that it was.

Comment 2

[Nicholas Nethercote [inactive]]

Attachment: (part 2) - Avoid more slop in nsTArray

Comment 3

[Nathan Froyd [:froydnj]]

Comment on attachment 8430545 [details] [diff] [review]
(part 2) - Avoid more slop in nsTArray

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

Nice catch.

::: xpcom/glue/nsTArray-inl.h
@@ +146,5 @@
> +  if (mHdr == EmptyHdr()) {
> +    // Malloc() new data
> +    header = static_cast<Header*>(Alloc::Malloc(bytesToAlloc));
> +    if (!header)
> +      return Alloc::FailureResult();

Might as well brace this if while you're moving it.

@@ +161,5 @@
>      Copy::CopyHeaderAndElements(header, mHdr, Length(), elemSize);
>  
>      if (!UsesAutoArrayBuffer())
>        Alloc::Free(mHdr);
> +

No extra blank line.

Comment 4

[Nicholas Nethercote [inactive]]

Attachment: (part 2) - Avoid more slop in nsTArray

Updated patch: I discovered that ShrinkCapacity() has the same issue, so I
factored out the good size computation and reused it there too.

Even better: most of the time when we call ShrinkCapacity() it's not worth
shrinking, because the good-size computation shows that the realloc will
actually end up giving us a block of the same size (but we'll have limited our
use of that block by reducing |capacity|).

With my patch applied, during some brief browsing, there were 563 calls to
ShrinkCapacity() but only 42 of them ended up doing a realloc :)

Comment 5

[Nathan Froyd [:froydnj]]

Comment on attachment 8431253 [details] [diff] [review]
(part 2) - Avoid more slop in nsTArray

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

r=me with the changes below.

::: xpcom/glue/nsTArray-inl.h
@@ +101,5 @@
>  
>  template<class Alloc, class Copy>
> +void
> +nsTArray_base<Alloc, Copy>::GoodSizeForCapacity(
> +  size_t capacity, size_t elemSize, size_t& nbytes, size_t& newCapacity)

This seems like a weird way to break the arguments; why not:

  ...(size_t capacity, size_t elemSize,
      size_t& nbytes, size_t& newCapacity)

?

@@ +104,5 @@
> +nsTArray_base<Alloc, Copy>::GoodSizeForCapacity(
> +  size_t capacity, size_t elemSize, size_t& nbytes, size_t& newCapacity)
> +{
> +  // We increase our capacity so that |capacity * elemSize + sizeof(Header)| is
> +  // a size that won't give slop -- if |nbytes| is less than |pageSize| we

Nit: this is really "a size that attempts to _minimize_ slop without getting too cozy with the details of the memory allocator", right?  Please reword.

@@ +220,5 @@
>      mHdr = EmptyHdr();
>      return;
>    }
>  
> +  // Only shrink if it would actually result in us using less memory.

Can you add an appropriate blurb to the ShrinkCapacity documentation in nsTArray.h about this new behavior?

::: xpcom/glue/nsTArray.h
@@ +395,5 @@
> +  // minimize slop, and how many elements will fit in that space.
> +  // @param capacity     The required capacity.
> +  // @param elemSize     The size of an array element.
> +  // @param capacity     The computed size, in bytes (outparam).
> +  // @param capacity     The resulting capacity (outparam).

Per discussion elsewhere, I guess we do use C++-style comments for block documentation comments!

Comment 6

[Nicholas Nethercote [inactive]]

> > +nsTArray_base<Alloc, Copy>::GoodSizeForCapacity(
> > +  size_t capacity, size_t elemSize, size_t& nbytes, size_t& newCapacity)
> 
> This seems like a weird way to break the arguments; why not:
> 
>   ...(size_t capacity, size_t elemSize,
>       size_t& nbytes, size_t& newCapacity)

Because that doesn't fit in 80 chars. So I changed it to one parameter per line instead.

Aside: I'm becoming increasingly convinced that the standard way to format multi-line function decls/calls in C++ is bad. Indenting to the opening parenthesis gives absurdly inconsistent results, and causes multiple lines to need re-indenting whenever the function name changes. Indenting subsequent lines by one indent would avoid these problems. That general discussion is definitely for another time.

> Nit: this is really "a size that attempts to _minimize_ slop without getting
> too cozy with the details of the memory allocator", right?  Please reword.

Well, knowing mozjemalloc's size classes I know that it gives zero slop :) But I'll change it to "minimize" for maximum generality.

> Can you add an appropriate blurb to the ShrinkCapacity documentation in
> nsTArray.h about this new behavior?

Done.

> Per discussion elsewhere, I guess we do use C++-style comments for block
> documentation comments!

As is right and proper! :)

Comment 7

[Nicholas Nethercote [inactive]]

I had to tweak a C++ unit test slightly as well before landing:

https://hg.mozilla.org/integration/mozilla-inbound/rev/1f5266cae802
https://hg.mozilla.org/integration/mozilla-inbound/rev/1b81b771aee6

Comment 8

[[e-mail]]

Comment on attachment 8431253 [details] [diff] [review]
(part 2) - Avoid more slop in nsTArray

>+  // We increase our capacity so that |capacity * elemSize + sizeof(Header)| is
>+  // a size that won't give slop -- if |nbytes| is less than |pageSize| we
>+  // round up to the next power of two, otherwise we round up to the next
>+  // multiple of |pageSize|.
>+  const size_t pageSizeBytes = 12;
>+  const size_t pageSize = 1 << pageSizeBytes;
>+
>+  nbytes = capacity * elemSize + sizeof(Header);
>+  if (nbytes >= pageSize) {
>+    // Round up to the next multiple of pageSize.
>+    nbytes = pageSize * ((nbytes + pageSize - 1) / pageSize);
>+  } else {
>+    // Round up to the next power of two.
Wouldn't it be better to use malloc_good_size() here instead?

Comment 9

[Nicholas Nethercote [inactive]]

> Wouldn't it be better to use malloc_good_size() here instead?

I considered that, but it gives different results for the sub-page case. So I decided to stick with what we already had to minimize the change.

Comment 10

[Carsten Book [:Tomcat]]

sorry had to backout for test failures like https://tbpl.mozilla.org/php/getParsedLog.php?id=40849142&tree=Mozilla-Inbound

Comment 11

[Nicholas Nethercote [inactive]]

I did a before/after AWSY run, but I'm getting nonsense results: https://areweslimyet.com/?series=njn-1048044#evenspacing

johns, any idea what I'm doing wrong? I actually triggered 5 "before" jobs and 5 "after", but the status page told me that it filtered out the duplicate requests :(

Comment 12

[John Schoenick [:johns]]

(In reply to Nicholas Nethercote [:njn] from comment #11)
> I did a before/after AWSY run, but I'm getting nonsense results:
> https://areweslimyet.com/?series=njn-1048044#evenspacing
> 
> johns, any idea what I'm doing wrong? I actually triggered 5 "before" jobs
> and 5 "after", but the status page told me that it filtered out the
> duplicate requests :(

You need to check the "force re-test" box so it wont drop subsequent tests as duplicates (it should probably be checking for duplicates on series+revision instead of just revision)

Comment 13

[Nicholas Nethercote [inactive]]

With bug 1048044 having been fixed, this doesn't appear to be a problem any more. (I just looked at some slop measurements with DMD and nsTArray was a pretty tiny source of slop.)