Avoid slop in nsTArray

RESOLVED WORKSFORME

Status

()

Core
XPCOM
RESOLVED WORKSFORME
4 years ago
3 years ago

People

(Reporter: njn, Assigned: njn)

Tracking

Trunk
Points:
---

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: [MemShrink:P2])

Attachments

(2 attachments, 1 obsolete attachment)

(Assignee)

Description

4 years ago
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.
(Assignee)

Updated

4 years ago
OS: Linux → All
Hardware: x86_64 → All
(Assignee)

Comment 1

4 years ago
Created attachment 8430543 [details] [diff] [review]
(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.
Attachment #8430543 - Flags: review?(nfroyd)
(Assignee)

Comment 2

4 years ago
Created attachment 8430545 [details] [diff] [review]
(part 2) - Avoid more slop in nsTArray
Attachment #8430545 - Flags: review?(nfroyd)
Attachment #8430543 - Flags: review?(nfroyd) → review+
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.
Attachment #8430545 - Flags: review?(nfroyd) → review+
(Assignee)

Comment 4

4 years ago
Created attachment 8431253 [details] [diff] [review]
(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 :)
Attachment #8431253 - Flags: review?(nfroyd)
(Assignee)

Updated

4 years ago
Attachment #8430545 - Attachment is obsolete: true
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!
Attachment #8431253 - Flags: review?(nfroyd) → review+
(Assignee)

Comment 6

4 years ago
> > +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 8

4 years ago
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?
(Assignee)

Comment 9

4 years ago
> 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.
(Assignee)

Updated

4 years ago
Whiteboard: [MemShrink] → [MemShrink:P2]
(Assignee)

Updated

4 years ago
Blocks: 1048044
(Assignee)

Updated

4 years ago
No longer blocks: 1048044
(Assignee)

Comment 11

4 years ago
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 :(
Flags: needinfo?(jschoenick)
(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)
Flags: needinfo?(jschoenick)
(Assignee)

Comment 13

3 years ago
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.)
Status: ASSIGNED → RESOLVED
Last Resolved: 3 years ago
Resolution: --- → WORKSFORME
You need to log in before you can comment on or make changes to this bug.