1040593 - Tweak how |new Array(N)| works for N > 2048

Status: RESOLVED FIXED

Description

[Nicholas Nethercote [:njn]]

Imagine, you want to create an array and you know how big it is, like this:

> let a = new Array(N);
> for (let i = 0; i < N; i++) {
>   a[i] = i;
> }

If N <= 2048 (EagerAllocationMaxLength) you can do this without a single allocation for the array slots. But if N > 2048, you'll end up getting lots of reallocations -- e.g. 8 elements, then 16, then 32, 64, 128, ... N.

This is a real-world idiom I want to take advantage of for pdf.js -- there are numerous places where we create large arrays whose size is known in advance.

Comment 1

[Nicholas Nethercote [:njn]]

Attachment: Tweak how |new Array(N)| works for N > 2048

This patch makes |new Array(N)| always allocate at least
|EagerAllocationsMaxLength| elements up front.

It also changes |EagerAllocationsMaxLength| from 2048 to 2046, so that when the
two extra slots needed for |ObjectElements| are included, the resulting
allocation size is a power-of-two.

Comment 2

[Jan de Mooij [:jandem]]

Please make sure this doesn't regress the Kraken audio-* tests. I originally added this check for those tests but I don't remember how big the arrays were exactly.

Comment 3

[Jan de Mooij [:jandem]]

Oh and we should also fix the code in IonBuilder::inlineArray.

The easiest fix is to just not inline Array(x) with x > 2046, the alternative is to add a new MNewArray::AllocatingBehaviour value for this case and then call a different VM function.

Comment 4

[Brian Hackett (:bhackett)]

Comment on attachment 8458477 [details] [diff] [review]
Tweak how |new Array(N)| works for N > 2048

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

Looks good, but canceling per comment 3.

::: js/src/jsarray.cpp
@@ +3158,5 @@
>  
>      return true;
>  }
>  
> +template<uint32_t maxCapacity>

Preexisting, but can you use 'template <'?  That seems to be preferred in the code base vs. 'template<'

::: js/src/jsarray.h
@@ +54,5 @@
>                         NewObjectKind newKind = GenericObject);
>  
>  /*
> + * Create a dense array with length and capacity == 'length', initialized length set to 0,
> + * but with the elements only partially allocated.

maybe 'with the elements of larger arrays'

Comment 5

[Nicholas Nethercote [:njn]]

Attachment: Tweak how |new Array(N)| works for N > 2048

Sorry for the delay on this one. The new version deals with Ion (I took the
"easiest fix" suggestion from comment 3), and is a bit more complex as a
result.

The main new thing is encoding the three kinds of array allocations
(Unallocated, PartlyAllocated, FullyAllocate) everywhere. This required moving
AllocatingBehaviour out of MNewArray to somewhere more visible, and renaming a
bunch of things.

Also, as a result of the goodAllocated heuristic changes in bug 1052248 --
which let us allocate up to 50% elements past a power-of-two if it allows us to
reach |length| -- we will now eagerly allocate up to length=3068; for lengths
greater than that it'll eagerly allocate 2046 elements.

I checked there was no regression with Kraken. It's actually a slight win on
audio-oscillator, because it creates a lot of arrays of length 8192. With the
old code, we'd have to resize 10 times up from the initial capacity of 6
elements. With the new code we only have to resize twice up from the initial
capacity of 2046.

This patch took me a fair way out of my SM comfort zone, hence the two review
requests. Please review carefully.

Comment 6

[Brian Hackett (:bhackett)]

Comment on attachment 8481023 [details] [diff] [review]
Tweak how |new Array(N)| works for N > 2048

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

::: js/src/jsarray.cpp
@@ +3091,5 @@
>       */
> +    AllocatingBehaviour allocating = (length <= ArrayObject::EagerAllocationMaxLength)
> +                                   ? NewArray_FullyAllocating
> +                                   : NewArray_PartlyAllocating;
> +    RootedObject obj(cx, NewDenseArray(cx, length, type, allocating));

Can't you just make this NewArray_PartlyAllocating all the time?

::: js/src/jsarray.h
@@ +71,5 @@
> +
> +enum AllocatingBehaviour {
> +    NewArray_Unallocating = 0,
> +    NewArray_PartlyAllocating = 1,
> +    NewArray_FullyAllocating = 2

The explicit values here don't seem to help anything.

Comment 7

[Jan de Mooij [:jandem]]

Comment on attachment 8481023 [details] [diff] [review]
Tweak how |new Array(N)| works for N > 2048

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

Sorry for the delay, r=me with comment below addressed.

::: js/src/jit/MIR.h
@@ +1888,5 @@
>  
>      // Heap where the array should be allocated.
>      gc::InitialHeap initialHeap_;
>      // Allocate space at initialization or not
>      AllocatingBehaviour allocating_;

CodeGenerator::visitNewArrayCallVM emits a call to NewInitArray, which always uses NewDenseFullyAllocatedArray. If we start using MNewArray with NewArray_PartlyAllocating somewhere, that's probably not what we want/expect.

We'll also call this function if the inline allocation fails for some reason, so if this happens for NewArray_Unallocating we will fully allocate anyway.

I think we should change visitNewArrayCallVM to call NewDenseArray instead of NewInitArray and pass it the enum value. That'd also nicely match the RNewArray changes. Followup for this is fine though.

Comment 8

[Nicholas Nethercote [:njn]]

> > +    AllocatingBehaviour allocating = (length <= ArrayObject::EagerAllocationMaxLength)
> > +                                   ? NewArray_FullyAllocating
> > +                                   : NewArray_PartlyAllocating;
> > +    RootedObject obj(cx, NewDenseArray(cx, length, type, allocating));
> 
> Can't you just make this NewArray_PartlyAllocating all the time?

I could, but I think the code would be harder to read that way.

Comment 9

[Nicholas Nethercote [:njn]]

> CodeGenerator::visitNewArrayCallVM emits a call to NewInitArray, which
> always uses NewDenseFullyAllocatedArray. If we start using MNewArray with
> NewArray_PartlyAllocating somewhere, that's probably not what we want/expect.
> 
> We'll also call this function if the inline allocation fails for some
> reason, so if this happens for NewArray_Unallocating we will fully allocate
> anyway.
> 
> I think we should change visitNewArrayCallVM to call NewDenseArray instead
> of NewInitArray and pass it the enum value. That'd also nicely match the
> RNewArray changes. Followup for this is fine though.

Sorry, I don't understand what is the change you want made. Can you clarify? Thanks.

Comment 10

[Jan de Mooij [:jandem]]

(In reply to Nicholas Nethercote [:njn] from comment #9)
> Sorry, I don't understand what is the change you want made. Can you clarify?
> Thanks.

CodeGenerator::visitNewArrayCallVM emits the slow path for the MNewArray/LNewArray instruction. The problem is that it emits JIT code to call NewInitArray and this function completely ignores the MIR instruction's AllocatingBehaviour value and always calls NewDenseFullyAllocatedArray.

So we should change this code to call NewDenseArray instead of NewInitArray, and pass it the AllocatingBehaviour value.

Does this help? It's a bit of a pre-existing issue; I can also fix it as a follow-up patch/bug.

Comment 11

[Nicholas Nethercote [:njn]]

> Does this help?

It does. Thank you.

> It's a bit of a pre-existing issue; I can also fix it as a follow-up patch/bug.

I'd be a fool to pass up such a generous offer :) I filed bug 1063253.

Comment 12

[Nicholas Nethercote [:njn]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/94eed55e5a5b

Comment 13

[Wes Kocher (:KWierso)]

Backed out for build bustage: https://hg.mozilla.org/integration/mozilla-inbound/rev/c234ba51a1d1

https://tbpl.mozilla.org/php/getParsedLog.php?id=47440319&tree=Mozilla-Inbound

Comment 14

[Nicholas Nethercote [:njn]]

A missing header broken non-unified builds. New version:

https://hg.mozilla.org/integration/mozilla-inbound/rev/0f2020c52ad7

Comment 15

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/0f2020c52ad7