Fine-tune array built-ins

RESOLVED FIXED in Firefox 56

Status

()

enhancement
RESOLVED FIXED
2 years ago
2 years ago

People

(Reporter: anba, Assigned: anba)

Tracking

unspecified
mozilla56
Points:
---

Firefox Tracking Flags

(firefox56 fixed)

Details

Attachments

(1 attachment, 1 obsolete attachment)

We can fine-tune some of the array built-ins to save a few ms for the common cases.

The following performance improvements are possible:
---
    // 200 ms-> 175 ms
    // (Fast path for arrays in SetLengthProperty)
    var dt = 0;
    for (var i = 0; i < 1000000; ++i) {
        var a = [1, 2, 3];
        var t = dateNow();
        a.splice(0, 0);
        dt += (dateNow() - t);
    }
    print(dt);

    // 195 ms-> 170 ms
    // (Fast path for arrays in SetLengthProperty)
    var dt = 0;
    for (var i = 0; i < 1000000; ++i) {
        var a = [1, 2, 3];
        var t = dateNow();
        a.unshift(0);
        dt += (dateNow() - t);
    }
    print(dt);

    // 395 ms -> 330 ms
    // (Array instead of List when collecting array elements)
    function cmp(a, b) { var d = a - b; return d; }
    var dt = 0;
    for (var i = 0; i < 1000000; ++i) {
        var a = [1, 2, 3];
        var t = dateNow();
        a.sort(cmp);
        dt += (dateNow() - t);
    }
    print(dt);

    // 280 ms -> 250 ms
    // (Fast path for packed arrays when collecting array elements)
    function cmp(a, b) { return a - b; }
    var dt = 0;
    for (var i = 0; i < 1000000; ++i) {
        var a = [1, 2, 3];
        var t = dateNow();
        a.sort(cmp);
        dt += (dateNow() - t);
    }
    print(dt);

    // 135 ms -> 115 ms
    // (Avoiding prototype chain walk in ObjectMayHaveExtraIndexedProperties)
    var dt = 0;
    for (var i = 0; i < 1000000; ++i) {
        var a = ["", ""];
        var t = dateNow();
        a.join("");
        dt += (dateNow() - t);
    }
    print(dt);

    // 120 ms -> 86 ms
    // (Avoiding prototype chain walk in ObjectMayHaveExtraIndexedProperties and no forced dense elements initialization for packed arrays)
    // (95 ms when only changing ArrayReverseDenseKernel)
    var dt = 0;
    for (var i = 0; i < 1000000; ++i) {
        var a = [1, 2, 3];
        var t = dateNow();
        a.reverse();
        dt += (dateNow() - t);
    }
    print(dt);

    // 180 ms -> 145 ms
    // (Avoiding prototype chain walk in ObjectMayHaveExtraIndexedProperties and SetLengthProperty for arrays)
    // (160 ms when only changing SetLengthProperty)
    var dt = 0;
    for (var i = 0; i < 1000000; ++i) {
        var a = [null, null, null];
        var t = dateNow();
        a.shift()
        dt += (dateNow() - t);
    }
    print(dt);
---
Posted patch bug1377279.patch (obsolete) — Splinter Review
Do you think these changes will help in real-world situations?
Attachment #8882366 - Flags: feedback?(kvijayan)
Updated patch so it actually passes the tests.
Attachment #8882366 - Attachment is obsolete: true
Attachment #8882366 - Flags: feedback?(kvijayan)
Attachment #8884552 - Flags: feedback?(kvijayan)
André, I think this is great, I'd be happy to review.
Yeah, all of these help and seem like reasonable fixes.  Much of our improvements are going to come from a slew of small opts like this.  I'll be happy to help review with jandem.
Comment on attachment 8884552 [details] [diff] [review]
bug1377279.patch

I think the patch is good enough for reviewing. It basically consists of avoid shape lookups when calling SetLengthProperty with an ArrayObject and avoiding prototype walks in ObjectMayHaveExtraIndexedProperties when array methods are called with packed arrays (*).
Attachment #8884552 - Flags: feedback?(kvijayan) → review?(kvijayan)
Comment on attachment 8884552 [details] [diff] [review]
bug1377279.patch

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

Nice work!  Looks good.  r=me with answer to comment please.

::: js/src/builtin/Sorting.js
@@ +249,5 @@
>      var denseLen = 0;
>  
>      for (var i = 0; i < len; i++) {
>          if (i in array)
> +            _DefineDataProperty(denseList, denseLen++, array[i]);

I don't understand the reason for this change, can you explain why it is there?
Attachment #8884552 - Flags: review?(kvijayan) → review+
(In reply to Kannan Vijayan [:djvj] from comment #6)
> ::: js/src/builtin/Sorting.js
> @@ +249,5 @@
> >      var denseLen = 0;
> >  
> >      for (var i = 0; i < len; i++) {
> >          if (i in array)
> > +            _DefineDataProperty(denseList, denseLen++, array[i]);
> 
> I don't understand the reason for this change, can you explain why it is
> there?

Do you mean the change from List to Array for |denseList| or using _DefineDataProperty to copy the elements? It seems to be faster to use Arrays than List when the input array is small (<100), and _DefineDataProperty is needed so we don't call setters on Array.prototype or Object.prototype.
I meant the _DefineDataProperty.  My bad, I saw the "new List" in the old code and my mind automatically substituted "new Array", so it looked like you were replacing "new Array" with "[]", and a SETELEM with a call to _DefineDataProperty.

It makes sense now, thanks!
(In reply to Kannan Vijayan [:djvj] from comment #8)
> I meant the _DefineDataProperty.  My bad, I saw the "new List" in the old
> code and my mind automatically substituted "new Array", so it looked like
> you were replacing "new Array" with "[]", and a SETELEM with a call to
> _DefineDataProperty.

I'm replacing SETELEM with INITELEM [1], :jandem beefed _DefineDataProperty a bit up in bug 1344463. :-)

[1] http://searchfox.org/mozilla-central/rev/a83a4b68974aecaaacdf25145420e0fe97b7aa22/js/src/frontend/BytecodeEmitter.cpp#9377-9401

> 
> It makes sense now, thanks!

Okay, great!
https://hg.mozilla.org/mozilla-central/rev/52da209e46fb
Status: ASSIGNED → RESOLVED
Closed: 2 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla56
You need to log in before you can comment on or make changes to this bug.