1039965 - JS array elements clownshoes

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Nicholas Nethercote [inactive]]

Consider this program:

> var length = 3000;
> var array = new Array(length);
> for (var i = 0; i < length; ++i) {
>   array[i] = i;
> }

Here are the underlying allocations that occur for the array elements:

>  new-elements:     10 (80)
> grow-elements:     10 ->     18 (144)
> grow-elements:     18 ->     34 (272)
> grow-elements:     34 ->     66 (528)
> grow-elements:     66 ->    130 (1040)
> grow-elements:    130 ->    258 (2064)
> grow-elements:    258 ->    514 (4112)
> grow-elements:    514 ->   1026 (8208)
> grow-elements:   1026 ->   2050 (16400)
> grow-elements:   2050 ->   4098 (32784)

The numbers on either side of the '->' are slot counts; the number in
parentheses is the number of bytes allocated. Every allocation is 2 more than a
power of two. This is due to VALUES_PER_HEADER, which is needed (I think) to
hold the ObjectElements. As a result, the byte counts are also slightly more
than powers of two, and so subject to rounding up (e.g. 528 --> 1024, 1040 -->
2048, 2064 --> 4096, 4112 --> 8192).

Loading one PDF in pdf.js, DMD tells me there is just under 10 MiB of slop
present.

Nb: if I change the |new Array(length)| to |[]| then the sequence becomes this:

>  new-elements:     14 b.js:4 (112)
> grow-elements:     14 ->     26 b.js:4 (208)
> grow-elements:     26 ->     50 b.js:4 (400)
> grow-elements:     50 ->     98 b.js:4 (784)
> grow-elements:     98 ->    194 b.js:4 (1552)
> grow-elements:    194 ->    386 b.js:4 (3088)
> grow-elements:    386 ->    770 b.js:4 (6160)
> grow-elements:    770 ->   1538 b.js:4 (12304)
> grow-elements:   1538 ->   3074 b.js:4 (24592)

I don't know why the initial size is 14, but it's also awkward, and leads to
lots of slop (400 --> 512, 784 --> 1024, 1552 --> 2048, 3088 --> 4096). We can
do better here.

Finally, when arrays are shrunk (e.g. due to Array.pop()) we realloc to reduce
capacity by a single slot:

> let a = new Array(20);
> for (i = 0; i < 20; i++) {
>     a.pop();
> }
> 
>    new-elements:     22 c.js:1 (176)
> shrink-elements:     22 ->     21 c.js:3 (168)
> shrink-elements:     21 ->     20 c.js:3 (160)
> shrink-elements:     20 ->     19 c.js:3 (152)
> shrink-elements:     19 ->     18 c.js:3 (144)
> shrink-elements:     18 ->     17 c.js:3 (136)
> shrink-elements:     17 ->     16 c.js:3 (128)
> shrink-elements:     16 ->     15 c.js:3 (120)
> shrink-elements:     15 ->     14 c.js:3 (112)
> shrink-elements:     14 ->     13 c.js:3 (104)
> shrink-elements:     13 ->     12 c.js:3 (96)
> shrink-elements:     12 ->     11 c.js:3 (88)
> shrink-elements:     11 ->     10 c.js:3 (80)

We should realloc more selectively on shrinking actions such as pop().

Comment 1

[Nicholas Nethercote [inactive]]

Attachment: Avoid slop in JS arrays

This patch changes JS array resizing to always allocate power-of-two-sized
slot requests. Previously it would frequently make non-power-of-two-sized
requests, which cause lots of slop.

Also, shrinkElements() now only does a reallocation if it would result in going
down a size class. E.g. if you pop all the elements from a 1000-element array,
it would realloc 999, then 998, then 997, all the way down the minimum size.
Now it does 512, then 256, down to the minimum size (which is 8).

I confirmed with DMD that the element allocations now have zero slop. I also
measured peak RSS loading a couple of large PDF files (four times each) with
pdf.js:

prorail.pdf:
- old: 521, 504, 511, 519 MiB
- new: 443, 459, 406, 438 MiB

stacks.pdf:
- old: 825, 787, 754, 760 MiB
- new: 508, 506, 510, 517 MiB

Big wins!

Comment 2

[Nicholas Nethercote [inactive]]

Here is the output for the programs described in comment 0 with the patch 
applied:

Original:

   new-elements:      8 (64)
  grow-elements:      8 ->     16 (128)
  grow-elements:     16 ->     32 (256)
  grow-elements:     32 ->     64 (512)
  grow-elements:     64 ->    128 (1024)
  grow-elements:    128 ->    256 (2048)
  grow-elements:    256 ->    512 (4096)
  grow-elements:    512 ->   1024 (8192)
  grow-elements:   1024 ->   2048 (16384)
  grow-elements:   2048 ->   4096 (32768)

The numbers don't look much different, but these byte sizes are all 
powers-of-two, and thus allocate with zero slop.

With [] instead of |new Array(length)|:

   new-elements:     16 (128)
  grow-elements:     16 ->     32 (256)
  grow-elements:     32 ->     64 (512)
  grow-elements:     64 ->    128 (1024)
  grow-elements:    128 ->    256 (2048)
  grow-elements:    256 ->    512 (4096)
  grow-elements:    512 ->   1024 (8192)
  grow-elements:   1024 ->   2048 (16384)
  grow-elements:   2048 ->   4096 (32768)

Popping example:

   new-elements:     32 (256)
shrink-elements:     32 ->     16 (128)
shrink-elements:     16 ->      8 (64)

Comment 3

[:Ms2ger (he/him; ⌚ UTC+1/+2)]

Comment on attachment 8458423 [details] [diff] [review]
Avoid slop in JS arrays

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

::: js/src/jsobj.cpp
@@ +3219,5 @@
> +    // Beyond that, it's a multiple of SlotCountDoublingMax:
> +    //   2 Mi, 3 Mi, 4 Mi, ...
> +    //
> +    // This lets us add N elements to an array in amortized O(N) time. Having
> +    // the second class means that for bigger arrays the constant factor it

s/it/is/? Also, I'm pretty sure adding a constant amount of space when the array is full is a textbook example of not-amortized-constant.

@@ +3225,5 @@
> +
> +    static const uint32_t SlotCountDoublingMax = 1024 * 1024;
> +
> +    if (count < SlotCountDoublingMax) {
> +        // Round up to the next power of two.  See

mozilla::RoundUpPow2?

Comment 4

[Terrence Cole [:terrence]]

Comment on attachment 8458423 [details] [diff] [review]
Avoid slop in JS arrays

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

\o/ Thanks for fixing this! I would have gotten to this much sooner myself if I had know how bad the situation was.

In addition to what's here, I think we should also bump up our pre-allocation max size to something that actually handles a modern, representative workload, e.g. pdf.js.

::: js/src/jsobj.cpp
@@ +3210,5 @@
>                                                            newCount * sizeof(HeapSlot)));
>  }
>  
> +/* static */ uint32_t
> +JSObject::goodSlotCount(uint32_t count)

Please take and return CheckedInt<uint32_t>. In theory our users should all be passing in sane values -- having skimmed jsarray.cpp, you'd obviously have to be crazy to trust that though.

@@ +3225,5 @@
> +
> +    static const uint32_t SlotCountDoublingMax = 1024 * 1024;
> +
> +    if (count < SlotCountDoublingMax) {
> +        // Round up to the next power of two.  See

Yes, please use RoundUpPow2. It looks like the mfbt version is going to use BSR, which the above article claims to have similar perf. In any case, we're feeding this into realloc, so a few instructions are not going to matter.

@@ +3240,5 @@
> +            count = JSObject::SLOT_CAPACITY_MIN;
> +    } else {
> +        count = JS_ROUNDUP(count, SlotCountDoublingMax);
> +    }
> +    return count;

Add a MOZ_ASSERT(count.isValid()) for good measure.

@@ +3254,5 @@
> +    JS_ASSERT(oldCapacity < reqCapacity);
> +
> +    uint32_t oldSlotCount = oldCapacity + ObjectElements::VALUES_PER_HEADER;
> +    uint32_t reqSlotCount = reqCapacity + ObjectElements::VALUES_PER_HEADER;
> +    uint32_t newSlotCount;

CheckedInt<uint32_t>

@@ +3269,5 @@
> +                  (oldSlotCount <= MAX_FIXED_SLOTS && (oldSlotCount % 2 == 0)));
> +        newSlotCount = goodSlotCount(reqSlotCount);
> +    }
> +
> +    /* Don't let nelements get close to wrapping around uint32_t. */

Use // for this comment as well, since you're here.

@@ +3271,5 @@
> +    }
> +
> +    /* Don't let nelements get close to wrapping around uint32_t. */
> +    uint32_t newCapacity = newSlotCount - ObjectElements::VALUES_PER_HEADER;
> +    if (newCapacity >= NELEMENTS_LIMIT || newCapacity < oldCapacity || newCapacity < reqCapacity) {

* NELEMENTS_LIMIT is actually pretty small compared to MAX_ARRAY_INDEX. I think we should bump this all the way up to be == MAX_ARRAY_INDEX on 64bit. 

* The 2nd and 3rd conditions should be flat-out assertions at this point, please make it so.

* Please MOZ_ASSERT(newSlotCount.isValid()).

@@ +3277,1 @@
>      }

No braces around a single-line body.

@@ +3277,3 @@
>      }
>  
>      uint32_t initlen = getDenseInitializedLength();

It looks like this isn't used except in Debug_SetSlotRangeToCrashOnTouch, so please move this down to right above that call.

@@ +3312,1 @@
>          return;

Move the early exit for !hasDynamicElements above the accessor for dense element capacity.

@@ +3321,5 @@
> +    uint32_t newSlotCount = goodSlotCount(reqSlotCount);
> +    if (newSlotCount == oldSlotCount)
> +        return;  // Leave elements at its old size.
> +
> +    uint32_t newCapacity = newSlotCount - ObjectElements::VALUES_PER_HEADER;

MOZ_ASSERT(newSlotCount > ObjectElements::VALUES_PER_HEADER);

Alternatively, make newSlotCount and newSlotCapacity CheckedInt and assert .isValid() here.

::: js/src/vm/ObjectImpl.h
@@ +259,5 @@
>      static const size_t VALUES_PER_HEADER = 2;
>  };
>  
> +static_assert(ObjectElements::VALUES_PER_HEADER * sizeof(HeapSlot) == sizeof(ObjectElements),
> +              "ObjectElements doesn't fit in the given number of slots");

This static assert is already present in the staticAsserts() function above. I'm pretty sure the use of a called staticAsserts() function is no longer required, so please keep this hunk and remove the staticAsserts() function.

@@ +540,5 @@
>       * Minimum size for dynamically allocated slots in normal Objects.
>       * ArrayObjects don't use this limit and can have a lower slot capacity,
>       * since they normally don't have a lot of slots.
> +     *
> +     * njn: is that second sentence true?

Somewhat? It appears to get applied both against objects that are Arrays and objects that do not have dynamic elements -- roughly small arrays and objects without elements.

In either case, I doubt it's a useful optimization anymore. And if it is useful, we should be doing something more consistent anyway.

Comment 5

[Jeff Walden [:Waldo]]

Comment on attachment 8458423 [details] [diff] [review]
Avoid slop in JS arrays

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

::: js/src/jsobj.cpp
@@ +3210,5 @@
>                                                            newCount * sizeof(HeapSlot)));
>  }
>  
> +/* static */ uint32_t
> +JSObject::goodSlotCount(uint32_t count)

I think I'm going to have to disagree on taking and returning a CheckedInt<uint32_t>.  In general, CheckedInt is great for internal calculations, but when it shows up at interface boundaries, it's 1) a sign that something's wrong, and 2) extra, unusual complexity for all callers to deal with.  If this method is going to compute a value, it should either always compute a correct value, or it should signal failure the usual way by returning bool and providing value via outparam.

Looking at this, for uint32_t(-2) and similar values there's a true overflow hazard.  At least, if we ignore the max-elements limits already.  So I'd make this method fallible with outparam.

@@ +3219,5 @@
> +    // Beyond that, it's a multiple of SlotCountDoublingMax:
> +    //   2 Mi, 3 Mi, 4 Mi, ...
> +    //
> +    // This lets us add N elements to an array in amortized O(N) time. Having
> +    // the second class means that for bigger arrays the constant factor it

Yeah, this is totally not amortized constant time any more, once the non-doubling behavior hits.

@@ +3271,5 @@
> +    }
> +
> +    /* Don't let nelements get close to wrapping around uint32_t. */
> +    uint32_t newCapacity = newSlotCount - ObjectElements::VALUES_PER_HEADER;
> +    if (newCapacity >= NELEMENTS_LIMIT || newCapacity < oldCapacity || newCapacity < reqCapacity) {

If the bump-up suggestion is a 64-bit-only suggestion, I think I'm not much a fan.  I'd rather see consistent behavior between 32/64-bit for now, as long as arrays of 16M elements (or was it 512M elements?  memory hazy) are uncommon.  Which they are.  By the time it matters, hopefully 32-bit will be dead.

::: js/src/vm/ObjectImpl.h
@@ +259,5 @@
>      static const size_t VALUES_PER_HEADER = 2;
>  };
>  
> +static_assert(ObjectElements::VALUES_PER_HEADER * sizeof(HeapSlot) == sizeof(ObjectElements),
> +              "ObjectElements doesn't fit in the given number of slots");

Actually you can/should move it to class scope within ObjectElements.  Putting it inside a method also works, to a point, but if the method is templated or is in a class that's templated it can potentially not be instantiated, so class scope is best.

Comment 6

[Jeff Walden [:Waldo]]

Oh, RoundUpPow2 takes and returns size_t right now, so it isn't (naively) adequate.  If you use it, beware of size_t-assignment-to-uint32_t bugs, and beware of the case where there are no leading zeroes and so rounding up overflows.  (The latter would trigger an assert if hit.  The former is silent except for compiler warnings that we either have foolishly turned off or would probably ignore because we think compiler warnings can be ignored.)

Comment 7

[Nicholas Nethercote [inactive]]

> I think we should also bump up our pre-allocation max size to something that actually
> handles a modern, representative workload, e.g. pdf.js.

Do you mean EagerAllocationMaxLength?

Comment 8

[Terrence Cole [:terrence]]

(In reply to Nicholas Nethercote [:njn] from comment #7)
> > I think we should also bump up our pre-allocation max size to something that actually
> > handles a modern, representative workload, e.g. pdf.js.
> 
> Do you mean EagerAllocationMaxLength?

Yes.

(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #5)
> Comment on attachment 8458423 [details] [diff] [review]
> Avoid slop in JS arrays
> 
> Review of attachment 8458423 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: js/src/jsobj.cpp
> @@ +3210,5 @@
> >                                                            newCount * sizeof(HeapSlot)));
> >  }
> >  
> > +/* static */ uint32_t
> > +JSObject::goodSlotCount(uint32_t count)
> 
> I think I'm going to have to disagree on taking and returning a
> CheckedInt<uint32_t>.  In general, CheckedInt is great for internal
> calculations, but when it shows up at interface boundaries, it's 1) a sign
> that something's wrong,

I'd argue that something /is/ wrong: specifically, all the numerical code in jsarray.cpp that is held together with wishes and hope.

> and 2) extra, unusual complexity for all callers to
> deal with.  If this method is going to compute a value, it should either
> always compute a correct value, or it should signal failure the usual way by
> returning bool and providing value via outparam.

I'm fine with making this explicitly fallible -- the point is it's likely to be a choke-point for length changes in jsarray.cpp, so if we do something to detect overflow here we're likely to catch bugs.

> @@ +3271,5 @@
> > +    }
> > +
> > +    /* Don't let nelements get close to wrapping around uint32_t. */
> > +    uint32_t newCapacity = newSlotCount - ObjectElements::VALUES_PER_HEADER;
> > +    if (newCapacity >= NELEMENTS_LIMIT || newCapacity < oldCapacity || newCapacity < reqCapacity) {
> 
> If the bump-up suggestion is a 64-bit-only suggestion, I think I'm not much
> a fan.  I'd rather see consistent behavior between 32/64-bit for now, as
> long as arrays of 16M elements (or was it 512M elements?  memory hazy) are
> uncommon.  Which they are.  By the time it matters, hopefully 32-bit will be
> dead.

Fair point. It's currently 2**28, so 256M elements.
 
> ::: js/src/vm/ObjectImpl.h
> @@ +259,5 @@
> >      static const size_t VALUES_PER_HEADER = 2;
> >  };
> >  
> > +static_assert(ObjectElements::VALUES_PER_HEADER * sizeof(HeapSlot) == sizeof(ObjectElements),
> > +              "ObjectElements doesn't fit in the given number of slots");
> 
> Actually you can/should move it to class scope within ObjectElements. 
> Putting it inside a method also works, to a point, but if the method is
> templated or is in a class that's templated it can potentially not be
> instantiated, so class scope is best.

I tried it in class scope and failed to build on sizeof(ObjectElements) not being available yet. Given that Nick just failed to find it in staticAsserts(), I'll continue to argue that right after the class is the right spot.

Comment 9

[Nicholas Nethercote [inactive]]

I've done my best to address the combination of all the comments above. It's not easy when you're disagreeing :)

> In addition to what's here, I think we should also bump up our
> pre-allocation max size to something that actually handles a modern,
> representative workload, e.g. pdf.js.

I'm not sure that's necessary. pdf.js builds up *many* small-to-medium arrays, e.g. 10s or 100s of elements, and a moderate number in the 1000s. But the really big arrays (e.g. 10s or 100s of 1000s of elements, e.g. for images) are typed arrays. 

> > +/* static */ uint32_t
> > +JSObject::goodSlotCount(uint32_t count)
> 
> Please take and return CheckedInt<uint32_t>. In theory our users should all
> be passing in sane values -- having skimmed jsarray.cpp, you'd obviously
> have to be crazy to trust that though.

I don't think we need CheckedInt here -- this function basically does "round up to a power of two, or something like that", which is a valid function for every possible uint32_t.

> Yes, please use RoundUpPow2.

Done. The size_t vs. uint32_t difference won't matter, because I'm only using it for the slot counts less than 1 Mi.

> * NELEMENTS_LIMIT is actually pretty small compared to MAX_ARRAY_INDEX. I
> think we should bump this all the way up to be == MAX_ARRAY_INDEX on 64bit. 

I left that alone, as you and Waldo seemed to agree on it.

> >      uint32_t initlen = getDenseInitializedLength();
> 
> It looks like this isn't used except in Debug_SetSlotRangeToCrashOnTouch, so
> please move this down to right above that call.

Nope. It has another use in the js_memcpy().

> I'm pretty sure the use of a called staticAsserts() function is no longer
> required, so please keep this hunk and remove the staticAsserts() function.

Done.

> > +     * njn: is that second sentence true?
> 
> Somewhat? It appears to get applied both against objects that are Arrays and
> objects that do not have dynamic elements -- roughly small arrays and
> objects without elements.
> 
> In either case, I doubt it's a useful optimization anymore. And if it is
> useful, we should be doing something more consistent anyway.

So should I change the comment, delete it, or leave it alone?

Comment 10

[Nicholas Nethercote [inactive]]

Attachment: Avoid slop in JS arrays

This patch changes JS array resizing to always allocate power-of-two-sized
slot requests. Previously it would frequently make non-power-of-two-sized
requests, which cause lots of slop.

Also, shrinkElements() now only does a reallocation if it would result in going
down a size class. E.g. if you pop all the elements from a 1000-element array,
it would realloc 999, then 998, then 997, all the way down the minimum size.
Now it does 512, then 256, down to the minimum size (which is 8).

I confirmed with DMD that the element allocations now have zero slop.

Comment 11

[Brian Hackett [Laid off!]]

Comment on attachment 8459388 [details] [diff] [review]
Avoid slop in JS arrays

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

Wow, does the malloc implementation on all platforms behave this way?  Is there any documentation on what we can expect the actual allocated size of a malloc call to be?

::: js/src/jsobj.cpp
@@ +3226,5 @@
> +// Having the second class means that for bigger arrays the constant factor is
> +// higher, but we waste less space.
> +//
> +/* static */ uint32_t
> +JSObject::goodSlotCount(uint32_t count)

'slot' already has a very specific meaning with objects, so using that term to talk about something completely different (allocated byte capacity / sizeof(Value)) is really confusing.

I think that this should be called goodElementsCapacity(), and take/return a dense elements capacity value.  Just bias the input/output by ObjectElements::VALUES_PER_HEADER, and this looks like it will allow removing some cruft in the callers too.

@@ +3250,5 @@
> +        295698432, 333447168, 375390208, 422576128, 476053504, 535822336,
> +        602931200, 678428672, 763363328, 858783744, 966787072, 1088421888,
> +        1224736768, 1377828864, 1550843904, 1744830464, 1962934272, 2208301056,
> +        2485125120, 2796552192, 3146776576, 3541041152, 3984588800, 0
> +    };

Is this precomputed here for efficiency vis a vis shrinkElements() called in a loop?  Have you seen it measurably speed anything up?  (Just noticed that when Ion inlines array.pop it never shrinks the elements, btw).

::: js/src/vm/ObjectImpl.h
@@ +249,5 @@
>  
>      static bool ConvertElementsToDoubles(JSContext *cx, uintptr_t elements);
>  
> +    // This is enough slots to store an object of this class. See the static
> +    // assertion below.

Ditto on confusing use of 'slots'.  This comment is obvious from the variable's name and static assert and can be removed.

@@ +535,5 @@
>       * Minimum size for dynamically allocated slots in normal Objects.
>       * ArrayObjects don't use this limit and can have a lower slot capacity,
>       * since they normally don't have a lot of slots.
> +     *
> +     * njn: is that second sentence true?

Yeah, for the first part see bug 957542.  The second part of the second sentence probably isn't true, bug 957542 is just tuning for the array objects created by RegExp.exec.

Comment 12

[Nicholas Nethercote [inactive]]

I just re-did the measurements from comment 1 after rebasing and addressing review comments.

Old

> prorail.pdf:
> - old: 521, 504, 511, 519 MiB
> - new: 443, 459, 406, 438 MiB
>
> stacks.pdf:
> - old: 825, 787, 754, 760 MiB
> - new: 508, 506, 510, 517 MiB

New

> prorail.pdf:
> - old: 535, 529, 509
> - new: 505, 511, 498
>
> stacks.pdf:
> - 830, 842, 784
> - 794, 784, 790

Still a clear improvement but a lot smaller. I wish I knew what had changed. I'd be doubting the old measurements if I hadn't done them each four times and written them down.

Comment 13

[Nicholas Nethercote [inactive]]

bhackett: I don't know how to interpret the cancelling of your review request. Should I treat it as an r- and submit an updated patch, or treat it as an r+ and wait for terrence's 2nd review? Thanks.

(I often use f+ to indicate "this is heading in the right direction but I want to see it again", to avoid this kind of confusion.)

> Wow, does the malloc implementation on all platforms behave this way?  Is
> there any documentation on what we can expect the actual allocated size of a
> malloc call to be?

We use our own, hacked version of jemalloc on all tier-1 platforms. Its buckets sizes are described at http://dxr.mozilla.org/mozilla-central/source/memory/mozjemalloc/jemalloc.c#47. The slop potential is highest in the range 512 bytes to 8192 bytes, because the buckets double in size within that range.

> @@ +3250,5 @@
> > +        295698432, 333447168, 375390208, 422576128, 476053504, 535822336,
> > +        602931200, 678428672, 763363328, 858783744, 966787072, 1088421888,
> > +        1224736768, 1377828864, 1550843904, 1744830464, 1962934272, 2208301056,
> > +        2485125120, 2796552192, 3146776576, 3541041152, 3984588800, 0
> > +    };
> 
> Is this precomputed here for efficiency vis a vis shrinkElements() called in
> a loop?

Not particularly. It just seemed easier to implement this way and I liked being able to see the actual numbers involved to get a better sense of the progression.

> Ditto on confusing use of 'slots'.  This comment is obvious from the
> variable's name and static assert and can be removed.

I disagree about the obviousness -- I specifically had to ask about this to understand what this value was used for. I prefer to keep it in.

Comment 14

[Brian Hackett [Laid off!]]

(In reply to Nicholas Nethercote [:njn] from comment #13)
> bhackett: I don't know how to interpret the cancelling of your review
> request. Should I treat it as an r- and submit an updated patch, or treat it
> as an r+ and wait for terrence's 2nd review? Thanks.
>
> (I often use f+ to indicate "this is heading in the right direction but I
> want to see it again", to avoid this kind of confusion.)

Can you submit another patch?  Historically I've used cancel-review for cases where I'd like to see an updated patch but think the approach is good, though yeah that is confusing when there are two reviewers.

> Not particularly. It just seemed easier to implement this way and I liked
> being able to see the actual numbers involved to get a better sense of the
> progression.

OK, I think it would be tidier if the C++ code computed the size directly, but no strong preference.  Can you remove the big comment before the table though and just point out it is the values computed by the above formula up to NELEMENTS_LIMIT?

> I disagree about the obviousness -- I specifically had to ask about this to
> understand what this value was used for. I prefer to keep it in.

OK but the comment you added doesn't really help with that, it's very operational.  Can you make the comment something like:

// Number of values used by a header when it is stored inline with element arrays.

Comment 15

[Nicholas Nethercote [inactive]]

Attachment: Avoid slop in JS arrays

I changed "{old,new,req}SlotCount" to "{old,new,req}Allocated", which was the
pre-existing terminology.

I kept goodSlotCount() as is (except for the name, which is now
goodAllocated()) because it's simpler if it doesn't need to know about
VALUES_PER_HEADER, and so can just work with nice round numbers (e.g. powers of
two).

Comment 16

[Nicholas Nethercote [inactive]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/dd2018a5f894

Comment 17

[Jan de Mooij [:jandem]]

This seems to have regressed some Kraken audio tests (see AWFY). It'd be interesting to look at their allocation behavior; maybe the old code was optimized for those tests or something..

Comment 18

[Ed Morley [:emorley]]

https://hg.mozilla.org/mozilla-central/rev/dd2018a5f894

Comment 19

[Nicolas B. Pierron [:nbp] {away}]

(In reply to Jan de Mooij [:jandem] from comment #17)
> This seems to have regressed some Kraken audio tests (see AWFY). It'd be
> interesting to look at their allocation behavior; maybe the old code was
> optimized for those tests or something..

We should backout this patch because of a Major regression (106.5% worse on sunspider, 10% on kraken) on FxOS Unagi [1][2].

Note that this regression is not visible on flame 512MB.  Can you reproduce this issue with what is documented on the hacking tips page[3] ?

[1] http://www.arewefastyet.com/#machine=14
[2] http://hg.mozilla.org/integration/mozilla-inbound/pushloghtml?fromchange=95f31fa01c7a0068a96766e63f608880cfd7e0bf&tochange=15494053f7dd65d11e191224e653004c90750f92
[3] https://developer.mozilla.org/en-US/docs/Mozilla/Projects/SpiderMonkey/Hacking_Tips#Benchmarking_without_a_Phone

Comment 20

[Nicholas Nethercote [inactive]]

Backout:
https://hg.mozilla.org/integration/mozilla-inbound/rev/352fa9a8ea8e

Comment 21

[Nicholas Nethercote [inactive]]

audio-oscillator is the most-affected Kraken test. The problem is that is repeatedly builds up a 8192 element array, which requires repeated resizings of the elements buffer. With the old code, the sequence of buffer sizes is this:

- 0, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192

It's perfect -- we fill up the final buffer fully. (Nb: that final buffer is actually 8194 values long, because we need the extra 16 bytes for the ObjectElements. So the allocation request size is not a power-of-two, which leads to slop.)

With the new code, the sequence is this

- 0, 6, 14, 30, 62, 126, 254, 510, 1022, 2046, 4094, 8190, 16382

Zero slop, but the second-last buffer is *just* too small for the 8192 elements so we have to resize it and only end up half-filling the final buffer. As a result, we do an extra reallocation (which also results in twice as many element copies). And this is repeated 500 times, which accounts for the slow-down.

If you have randomly distributed array sizes, the new code is a clear improvement: the number of reallocations is likely to be almost the same -- cusp cases like this will be rare -- but we'll waste much less memory. But for arrays that are built up from nothing to sizes that are powers-of-two, it'll be slower. Hmph.

I don't see how to avoid this problem so long as ObjectElements is stored in the same buffer as the elements. Well, if |new Array(8192)| actually gave a dense array with that many elements immediately, it would fix this case... but that doesn't happen because EagerAllocationMaxLength is 2048, and it wouldn't fix the case where the array was initially set to [].

Comment 22

[Brian Hackett [Laid off!]]

Which line of the benchmark are these arrays created on?

Comment 23

[Nicholas Nethercote [inactive]]

This line:

> this.signal = new Array(bufferSize);

It's line 578 of kraken-1.1/audio-oscillator-data.js.

|bufferSize| is passed in from this line:

> harmonic = new Oscillator(Oscillator.Sine, frequency*nthHarmonic, 1/nthHarmonic, bufferSize, sampleRate);

from line 11 of kraken-1.1/audio-oscillator.js.

Comment 24

[Brian Hackett [Laid off!]]

(In reply to Nicholas Nethercote [:njn] from comment #23)
> This line:
> 
> > this.signal = new Array(bufferSize);
> 
> It's line 578 of kraken-1.1/audio-oscillator-data.js.
> 
> |bufferSize| is passed in from this line:
> 
> > harmonic = new Oscillator(Oscillator.Sine, frequency*nthHarmonic, 1/nthHarmonic, bufferSize, sampleRate);
> 
> from line 11 of kraken-1.1/audio-oscillator.js.

OK, so that array creation should be affected by changes to EagerAllocationMaxLength.  What happens to the regression if you increase EagerAllocationMaxLength to 16382?  This problem does seem unavoidable in general, we just flipped from the best to the worst case for the amortized O(1) array growth.  So while it would be nice if we did well on these kraken allocations, I don't think this issue should block this patch landing.

Comment 25

[Nicholas Nethercote [inactive]]

> What happens to the regression if you increase EagerAllocationMaxLength to 16382?

Hmm, it helps, but doesn't entirely fix the regression. Here are instruction counts (millions) from Cachegrind:

>           Eager=2048   Eager=16382
> old code     738.202       730.505    
> new code     764.104       746.413

I'll try to work out where the rest of the regression comes from.

Comment 26

[Nicholas Nethercote [inactive]]

Here's Cachegrind's function-level instruction count diff, with the Eager=16382 change applied to
both the old and the new code:

> --------------------------------------------------------------------------------
>         Ir
> --------------------------------------------------------------------------------
> 15,901,377  PROGRAM TOTALS
> 
> --------------------------------------------------------------------------------
>        Ir  file:function
> --------------------------------------------------------------------------------
> 9,721,538  ???:???
> 1,874,630  ???:adler32
>   423,950  /home/njn/moz/nnn/js/src/gc/Marking.cpp:js::GCMarker::processMarkStackTop(js::SliceBudget&)
>   244,826  /home/njn/moz/nnn/js/src/nnn/js/src/../../dist/include/js/Value.h:js::GCMarker::processMarkStackTop(js::SliceBudget&)
>    78,877  /home/njn/moz/nnn/js/src/jsgcinlines.h:unsigned long js::gc::Arena::finalize<JSString>(js::FreeOp*, js::gc::AllocKind, unsigned long)
>    69,662  /home/njn/moz/nnn/js/src/nnn/js/src/../../dist/include/js/HeapAPI.h:js::gc::MarkPermanentAtom(JSTracer*, JSAtom*, char const*)
>    66,607  /home/njn/moz/nnn/js/src/nnn/js/src/../../dist/include/js/HeapAPI.h:js::GCMarker::processMarkStackTop(js::SliceBudget&)
>   -60,987  /home/njn/moz/nnn/js/src/nnn/js/src/../../dist/include/js/HashTable.h:js::detail::HashTable<js::types::TypeObjectWithNewScriptEntry const, js::HashSet<js::types::TypeObjectW
> ithNewScriptEntry, js::types::TypeObjectWithNewScriptEntry, js::SystemAllocPolicy>::SetOps, js::SystemAllocPolicy>::lookup(js::types::TypeObjectWithNewS
>    60,934  /home/njn/moz/nnn/js/src/nnn/js/src/../../dist/include/js/HeapAPI.h:PushMarkStack(js::GCMarker*, js::Shape*)
>    57,808  /home/njn/moz/nnn/js/src/gc/Nursery.cpp:js::Nursery::collectToFixedPoint(js::gc::MinorCollectionTracer*, js::Nursery::TenureCountCache&)
>    55,623  /build/buildd/eglibc-2.19/malloc/malloc.c:_int_malloc
>    54,342  /home/njn/moz/nnn/js/src/gc/Heap.h:js::GCMarker::processMarkStackTop(js::SliceBudget&)

"???:???" means "I couldn't get a stack" and usually indicates JIT code. So
that part is opaque.

I have no idea why |adler32| is in there... that seems to be part of zlib,
which is only used for source compression.

Beyond that, there seems to be a bit more GC stuff happening. I thought it
might be the case that an extra GC is occurring because the GC's malloc counter
is increasing more quickly in the new code. But instrumenting js::GC()
indicates it's called twice in both the old and new code.

Comment 27

[Jan de Mooij [:jandem]]

When you grow the ObjectElements, can't you add some code that'd reason like this:

"Hm, we're growing to capacity 8190, but ObjectElements::length is only slightly more (8192), so I'll grow to 8192 instead to potentially avoid a reallocation later on?"

Comment 28

[Nicholas Nethercote [inactive]]

> We should backout this patch because of a Major regression (106.5% worse on
> sunspider, 10% on kraken) on FxOS Unagi [1][2].

As far as I can tell, the Sunspider regression is still present even after I backed this patch out, which suggests that it wasn't the root cause. So I think I just have to worry about the Kraken regression at this point.

Comment 29

[Nicholas Nethercote [inactive]]

Attachment: (attempt 2) - Avoid slop in JS arrays

I implemented Jan's suggestion from comment 27. On my machine, it's eliminated
the Kraken regression (measuring both time and instruction counts).

Comment 30

[Brian Hackett [Laid off!]]

Comment on attachment 8462260 [details] [diff] [review]
(attempt 2) - Avoid slop in JS arrays

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

::: js/src/jsobj.cpp
@@ +3294,5 @@
> +    // re-doubling, and we don't have to pay the cost of re-doubling.
> +    //
> +    uint32_t capacity = goodAllocated - ObjectElements::VALUES_PER_HEADER;
> +    if (length > capacity && (length - capacity) < 16) {
> +        goodAllocated = length + ObjectElements::VALUES_PER_HEADER;

I think that |length| can be any uint32, and goodAllocated can be uint32(-1), so this addition can overflow, right?

Also, do the instruction counts change if you round up the new value given to goodAllocated here, per the above logic?  It seems like if allocating 8194 elements vs. 16384 elements uses the same amount of space in the allocator, mallocs of those two sizes should take the same amount of time.

Comment 31

[Nicholas Nethercote [inactive]]

> It seems like if allocating 8194 elements vs. 16384 elements uses the same amount of space in the
> allocator

They don't take the same amount of space. Although some size classes in jemalloc are powers-of-two (notably the 512..8192 B range) lots of them aren't.

And given that the array's length has been explicitly set, it seems likely that we won't need to make the capacity greater than the length.

Comment 32

[Nicholas Nethercote [inactive]]

To make comment 31 more concrete: for 128 elements, the relevant size classes are 1 KiB and 2 KiB, so nudging the capacity up will result in almost 50% slop, so your suggestion of just going to the next power-of-two would be sensible as the result is much the same.

But for 8192 elements, the relevant jemalloc size classes are 64 KiB and 68 KiB, so we have only ~4 KiB of slop by nudging the capacity up to match the length. So going to the next power-of-two would waste a lot of space.

Comment 33

[Nicholas Nethercote [inactive]]

Fingers crossed:
https://hg.mozilla.org/integration/mozilla-inbound/rev/6bfbf32dcd44

Comment 34

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/6bfbf32dcd44