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

RESOLVED FIXED in mozilla35

Status

()

defect
RESOLVED FIXED
5 years ago
5 years ago

People

(Reporter: njn, Assigned: njn)

Tracking

unspecified
mozilla35
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(1 attachment, 1 obsolete attachment)

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.
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.
Attachment #8458477 - Flags: review?(bhackett1024)
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.
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 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'
Attachment #8458477 - Flags: review?(bhackett1024)
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.
Attachment #8481023 - Flags: review?(jdemooij)
Attachment #8481023 - Flags: review?(bhackett1024)
Attachment #8458477 - Attachment is obsolete: true
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.
Attachment #8481023 - Flags: review?(bhackett1024) → review+
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.
Attachment #8481023 - Flags: review?(jdemooij) → review+
> > +    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.
> 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.
Flags: needinfo?(jdemooij)
(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.
Flags: needinfo?(jdemooij)
Blocks: 1063253
> 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.
A missing header broken non-unified builds. New version:

https://hg.mozilla.org/integration/mozilla-inbound/rev/0f2020c52ad7
Flags: needinfo?(n.nethercote)
https://hg.mozilla.org/mozilla-central/rev/0f2020c52ad7
Status: ASSIGNED → RESOLVED
Closed: 5 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla35
You need to log in before you can comment on or make changes to this bug.