Optimize Array.prototype.unshift

RESOLVED FIXED in Firefox 55

Status

()

RESOLVED FIXED
2 years ago
2 years ago

People

(Reporter: jandem, Assigned: jandem)

Tracking

unspecified
mozilla55
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(firefox55 fixed)

Details

Attachments

(3 attachments)

(Assignee)

Description

2 years ago
A few things we can do pretty easily after bug 1348772:

(1) When there are enough shifted elements, we can just use them.

(2) When the array is sufficiently large we could unshift more elements than we actually need, and "shift" the ones we don't need, so if there are more unshift calls they will benefit from (1).
(Assignee)

Updated

2 years ago
Flags: needinfo?(jdemooij)
(Assignee)

Comment 1

2 years ago
Various optimizations to unshift() that are unrelated to what I mentioned in comment 0:

* The fast path now works for all native objects, not just arrays.

* Instead of first setting the elements to JS_ELEMENTS_HOLE and then calling SetArrayElements, the fast path now copies the arguments directly. The SetArrayElements call can then be moved to the slow path.

* The fast path is now also used when length == 0. In that case we don't have to move anything, but we still benefit from the optimized code for allocating/setting dense elements.

For the micro-benchmark below I get:

Before: 218, 184
After:  142, 122

---
function test1() {
    var t = new Date;
    for (var i = 0; i < 1000000; i++) {
	var a = [1, 2, 3];
	a.unshift(0);
    }
    print(new Date - t);
}
test1();

function test2() {
    var t = new Date;
    for (var i = 0; i < 1000000; i++) {
	var a = [];
	a.unshift(1, 2, 3);
    }
    print(new Date - t);
}
test2();
---
Assignee: nobody → jdemooij
Status: NEW → ASSIGNED
Flags: needinfo?(jdemooij)
Attachment #8870373 - Flags: review?(andrebargull)
(Assignee)

Comment 2

2 years ago
Comment on attachment 8870373 [details] [diff] [review]
Part 1 - Optimize unshift fast path

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

::: js/src/jsarray.cpp
@@ +2513,5 @@
> +            }
> +            if (length > 0)
> +                nobj->moveDenseElements(args.length(), 0, uint32_t(length));
> +            for (uint32_t i = 0; i < args.length(); i++)
> +                nobj->setDenseElement(i, args[i]);

Oops, this should be setDenseElementWithType now.
Comment on attachment 8870373 [details] [diff] [review]
Part 1 - Optimize unshift fast path

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

LGTM with setDenseElementWithType fixed!
Attachment #8870373 - Flags: review?(andrebargull) → review+
(Assignee)

Comment 4

2 years ago
I added unshiftElements as the method that gets rid of shifted elements by moving the elements + header to the beginning of the allocated elements. However "unshift" here is a bit confusing because it's unrelated to Array.prototype.unshift, so I renamed it to moveShiftedElements. I think this is nicer because it also makes it clear we're moving the elements in memory.

This also has a small change in behavior: in growElements, when initializedLength is small, we now just always call moveShiftedElements because it's cheap and may save a malloc/realloc.

If you can think of better names for any of this stuff just let me know, I'm happy to rename things.
Attachment #8870745 - Flags: review?(andrebargull)
(Assignee)

Comment 5

2 years ago
This implements what I described in comment 0 for both unshift and splice. We pre-shift elements to make unshifting fast. This requires some somewhat-tricky calculations, I tried a few approaches and I think this one is the least bad.

Repeatedly shifting/unshifting an element is now very fast even when the array is huge:
---
function f() {
    var arr = [];
    for (var i = 0; i < 10000; i++)
	arr.push(i);
    var t = new Date;
    for (var i = 0; i < 50000; i++) {
	arr.shift();
	arr.unshift(i);
    }
    alert(new Date - t);
    return arr;
}
f();
--
Chrome:      118 ms
Safari:        6 ms
Nightly old: 360 ms
Nightly new:   8 ms

And just unshift()ing many elements:
--
function f() {
    var arr = [];
    var t = new Date;
    for (var i=0; i<50000; i++)
        arr.unshift(i);
    alert(new Date - t);
    return arr;
}
f();
--
Chrome:      318 ms
Safari:        5 ms
Nightly old: 939 ms
Nightly new:   9 ms

We're still a bit slower than Safari due to other overhead: a profile shows we now spend most of our time under setDenseElementWithType, it has a fast path for elements at index > 0, but unshift usually writes to index 0 so it's a worst case for setDenseElementWithType.

SetLengthProperty is also pretty expensive, we can probably eliminate that similar to what we do in array_push.

Moving elements is especially slow when we're in an incremental GC or when the array contains GC things. I hope we eliminated most of that with these shift/unshift optimizations.
Attachment #8870750 - Flags: review?(andrebargull)
Comment on attachment 8870745 [details] [diff] [review]
Part 2 - Rename unshiftElements to moveShiftedElements

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

The new names sound good to me!

::: js/src/vm/NativeObject.cpp
@@ +853,3 @@
>      uint32_t numShifted = getElementsHeader()->numShiftedElements();
>      if (numShifted > 0) {
> +        // If the number of elements is small, it's cheap to just move them and

s/cheap/cheaper/ and s/and/as/ ?

@@ +853,5 @@
>      uint32_t numShifted = getElementsHeader()->numShiftedElements();
>      if (numShifted > 0) {
> +        // If the number of elements is small, it's cheap to just move them and
> +        // it may avoid a malloc/realloc.
> +        if (getElementsHeader()->initializedLength <= 20)

Can this be a constant? And should we emphasise that 20 wasn't chosen for technical reasons, but instead because it turned out to be a reasonable limit in real-world use cases?
Attachment #8870745 - Flags: review?(andrebargull) → review+
Comment on attachment 8870750 [details] [diff] [review]
Part 3 - Optimize unshift

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

We may want to reorder some of the optimizations in Array.prototype.splice, because with the current patch, we'll now be a bit slower in certain edge cases. 

For example:

  var a = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20];
  a.splice(0, 0, 100, 200, 300, 400, 500);

will lead to the following executions:

|arr->ensureDenseElements(cx, uint32_t(len), itemCount - deleteCount);| in array_splice_impl increase initializedLength to 25 (and capacity to 30), and initializes the new elements with JS_ELEMENTS_HOLE.

|obj->as<NativeObject>().tryUnshiftDenseElements(itemCount)| will then increase initializedLength to 30 and initialize the new trailing elements with Undefined, and then we'll move the elements, delete the elements at the front, re-initialize the elements at the front with Undefined, then delete the 5 holes originally added by |ensureDenseElements|. And finally we'll set the new elements when we're back in array_splice_impl. 


And do we also need a new test for splice() similar to shifted-elements7.js?

::: js/src/jsarray.cpp
@@ +2946,5 @@
>              uint32_t start = uint32_t(actualStart);
>              uint32_t length = uint32_t(len);
>  
> +            uint32_t dstStart = start + itemCount;
> +            uint32_t srcStart = start + deleteCount;

Can you change this to use the same names as for the shrinking case above ("sourceIndex" and "targetIndex")?

@@ +2949,5 @@
> +            uint32_t dstStart = start + itemCount;
> +            uint32_t srcStart = start + deleteCount;
> +            if (srcStart != 0 ||
> +                !obj->is<NativeObject>() ||
> +                !obj->as<NativeObject>().tryUnshiftDenseElements(dstStart))

It's maybe easier to understand if we use |itemCount| instead of |dstStart| here.

@@ +2953,5 @@
> +                !obj->as<NativeObject>().tryUnshiftDenseElements(dstStart))
> +            {
> +                DenseElementResult result =
> +                    MoveAnyBoxedOrUnboxedDenseElements(cx, obj, dstStart, srcStart,
> +                                                       length - (start + deleteCount));

|start + deleteCount| can be replaced with |srcStart|.

::: js/src/vm/NativeObject.cpp
@@ +761,5 @@
> +        // We need more elements than are easily available. Try to make space
> +        // for more elements than we need (and shift the remaining ones) so
> +        // that unshifting more elements later will be fast.
> +
> +        if (header->initializedLength <= 10 ||

Similar to the constant in part 2, should we say the limit wasn't chosen for technical reasons?
Attachment #8870750 - Flags: review?(andrebargull) → review+

Comment 8

2 years ago
Pushed by jandemooij@gmail.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/a5bee800882e
part 1 - Optimize Array.prototype.unshift fast path and use it more. r=anba
(Assignee)

Updated

2 years ago
Keywords: leave-open

Comment 10

2 years ago
Pushed by jandemooij@gmail.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/efd4e852aca2
part 2 - Rename unshiftElements to moveShiftedElements, tweak heuristics. r=anba
(Assignee)

Comment 12

2 years ago
I think I'll remove the splice changes from part 3, for splice we're less likely to hit the shifted-elements fast path and we can always add it back if it shows up somewhere.

On some websites I see us hit the new unshift fast path on an array with length 100 many times per second. Probably some bad ads because I don't see it on all page loads.

Comment 13

2 years ago
Pushed by jandemooij@gmail.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/84ac08cff362
part 3 - Optimize Array.prototype.unshift by taking advantage of shifted elements. r=anba
(Assignee)

Updated

2 years ago
Status: ASSIGNED → RESOLVED
Last Resolved: 2 years ago
status-firefox55: --- → fixed
Keywords: leave-open
Resolution: --- → FIXED
Target Milestone: --- → mozilla55
Depends on: 1373356
(Assignee)

Updated

2 years ago
Depends on: 1372956
You need to log in before you can comment on or make changes to this bug.