Closed
Bug 1040593
Opened 8 years ago
Closed 8 years ago
Tweak how |new Array(N)| works for N > 2048
Categories
(Core :: JavaScript Engine, defect)
Core
JavaScript Engine
Tracking
()
RESOLVED
FIXED
mozilla35
People
(Reporter: n.nethercote, Assigned: n.nethercote)
References
Details
Attachments
(1 file, 1 obsolete file)
37.96 KB,
patch
|
bhackett1024
:
review+
jandem
:
review+
|
Details | Diff | Splinter Review |
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.
![]() |
Assignee | |
Comment 1•8 years ago
|
||
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)
Comment 2•8 years ago
|
||
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•8 years ago
|
||
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•8 years ago
|
||
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)
![]() |
Assignee | |
Comment 5•8 years ago
|
||
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)
![]() |
Assignee | |
Updated•8 years ago
|
Attachment #8458477 -
Attachment is obsolete: true
Comment 6•8 years ago
|
||
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 7•8 years ago
|
||
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+
![]() |
Assignee | |
Comment 8•8 years ago
|
||
> > + 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.
![]() |
Assignee | |
Comment 9•8 years ago
|
||
> 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)
Comment 10•8 years ago
|
||
(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)
![]() |
Assignee | |
Comment 11•8 years ago
|
||
> 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.
![]() |
Assignee | |
Comment 12•8 years ago
|
||
https://hg.mozilla.org/integration/mozilla-inbound/rev/94eed55e5a5b
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
Flags: needinfo?(n.nethercote)
![]() |
Assignee | |
Comment 14•8 years ago
|
||
A missing header broken non-unified builds. New version: https://hg.mozilla.org/integration/mozilla-inbound/rev/0f2020c52ad7
Flags: needinfo?(n.nethercote)
Comment 15•8 years ago
|
||
https://hg.mozilla.org/mozilla-central/rev/0f2020c52ad7
Status: ASSIGNED → RESOLVED
Closed: 8 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla35
You need to log in
before you can comment on or make changes to this bug.
Description
•