1364346 - Optimize Array.prototype.unshift

Status: RESOLVED FIXED

(Core :: JavaScript Engine, enhancement)

Description

[Jan de Mooij [:jandem]]

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).

Comment 1

[Jan de Mooij [:jandem]]

Attachment: Part 1 - Optimize unshift fast path

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();
---

Comment 2

[Jan de Mooij [:jandem]]

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 3

[André Bargull [:anba]]

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

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

LGTM with setDenseElementWithType fixed!

Comment 4

[Jan de Mooij [:jandem]]

Attachment: Part 2 - Rename unshiftElements to moveShiftedElements

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.

Comment 5

[Jan de Mooij [:jandem]]

Attachment: Part 3 - Optimize unshift

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.

Comment 6

[André Bargull [:anba]]

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?

Comment 7

[André Bargull [:anba]]

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?

Comment 8

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/a5bee800882e
part 1 - Optimize Array.prototype.unshift fast path and use it more. r=anba

Comment 9

[Phil Ringnalda (:philor)]

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

Comment 10

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/efd4e852aca2
part 2 - Rename unshiftElements to moveShiftedElements, tweak heuristics. r=anba

Comment 11

[Ryan VanderMeulen [:RyanVM]]

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

Comment 12

[Jan de Mooij [:jandem]]

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

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/84ac08cff362
part 3 - Optimize Array.prototype.unshift by taking advantage of shifted elements. r=anba

Comment 14

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

https://hg.mozilla.org/mozilla-central/rev/84ac08cff362