1383648 - Measure if it's useful to keep the Array.prototype.sort entry point in self-hosted code

Status: RESOLVED FIXED

(Core :: JavaScript: Standard Library, defect)

Description

[André Bargull [:anba]]

Right now the entry point for Array.prototype.sort is in C++, but we call back to self-hosted code when a comparator function is present. So basically from user-JS to C++ and back to self-hosted JS.

In Speedometer (all frameworks run once from InteractiveRunner.html), we see approx. the same number of calls to the self-hosted ArraySort function and to the C++ sort implementation.

Name            self-hosted   c++
Vanilla         0             0
Vanilla2015     0             0
Vanilla-babel   0             0
React           401           0
React-Redux     300           0  
Ember           2             61 
Backbone        101           804
AngularJS       124           0
Angular2        0             0
Vue             3             0
jQuery          1             8
Preact          0             0
Inferno         0             0
Elm             0             0
Flight          1             31


But at least for Speedometer, it seems like the bytecode matching comparator matching isn't used [1]:

Backbone:
8       breakpoint     keep y   0x00007fffe88130dc in js::array_sort(JSContext*, unsigned int, JS::Value*) at /home/andre/hg/mozilla-inbound/js/src/jsarray.cpp:2116
        breakpoint already hit 838 times
9       breakpoint     keep y   0x00007fffe88130dc in js::array_sort(JSContext*, unsigned int, JS::Value*) at /home/andre/hg/mozilla-inbound/js/src/jsarray.cpp:2116
        stop only if fval.ptr->data.debugView.tag == JSVAL_TAG_NULL
        breakpoint already hit 837 times
10      breakpoint     keep y   0x00007fffe88130dc in js::array_sort(JSContext*, unsigned int, JS::Value*) at /home/andre/hg/mozilla-inbound/js/src/jsarray.cpp:2116
        stop only if fval.ptr->data.debugView.tag != JSVAL_TAG_NULL


Ember:

8       breakpoint     keep y   0x00007fffe88130dc in js::array_sort(JSContext*, unsigned int, JS::Value*) at /home/andre/hg/mozilla-inbound/js/src/jsarray.cpp:2116
        breakpoint already hit 61 times
9       breakpoint     keep y   0x00007fffe88130dc in js::array_sort(JSContext*, unsigned int, JS::Value*) at /home/andre/hg/mozilla-inbound/js/src/jsarray.cpp:2116
        stop only if fval.ptr->data.debugView.tag == JSVAL_TAG_NULL
        breakpoint already hit 61 times
10      breakpoint     keep y   0x00007fffe88130dc in js::array_sort(JSContext*, unsigned int, JS::Value*) at /home/andre/hg/mozilla-inbound/js/src/jsarray.cpp:2116
        stop only if fval.ptr->data.debugView.tag != JSVAL_TAG_NULL


so we could simply decide on whether or not to call into C++ even from self-hosted code (i.e. if the comparator is present, stay in self-hosted JS; otherwise call into C++). This may improve the overall performance of Array.prototype.sort, because the slowish C++ to self-hosted JS call is no longer present.

array_sort doesn't have a great ticks/call ratio per bug 1365361, so we could see if this change helps to improve the performance.

[1] http://searchfox.org/mozilla-central/rev/3a3af33f513071ea829debdfbc628caebcdf6996/js/src/jsarray.cpp#2065

Comment 1

[André Bargull [:anba]]

Except for BackboneJS, all other three frameworks with more than >100 calls are calling Array.prototype.sort on an array with less than 24 elements, where 24 is the insertion-sort cut-off [2].

                All     <24     >= 24
React:          401     401     0
React-Redux:    300     300     0
AngularJS:      124     124     0
Backbone:       905     827     78


Measured by placing breakpoints here [1]:
    br jsarray.cpp:2069
    br jsarray.cpp:2069 if ((*(obj.ptr)).group_.value->clasp_ == &js::ArrayObject::class_)&(((ObjectElements*)((uintptr_t)(((ArrayObject*)obj.ptr)->elements_)-16))->length<24)
    br jsarray.cpp:2069 if ((*(obj.ptr)).group_.value->clasp_ == &js::ArrayObject::class_)&(((ObjectElements*)((uintptr_t)(((ArrayObject*)obj.ptr)->elements_)-16))->length>=24)

[1] http://searchfox.org/mozilla-central/rev/3a3af33f513071ea829debdfbc628caebcdf6996/js/src/jsarray.cpp#2069
[2] http://searchfox.org/mozilla-central/rev/3a3af33f513071ea829debdfbc628caebcdf6996/js/src/builtin/Sorting.js#261

Comment 2

[André Bargull [:anba]]

Attachment: bug1383648.patch

There is a slight performance regression when the optimized comparator path can be taken, because we now have to perform one additional call (from user code -> self-hosted code -> native code instead of just user code -> native code), but the performance improvement when the optimized comparator path can't be taken outweighs clearly (at least in this µ-benchmark):

    // Optimized comparator, int32 elements.
    //    4 elements:  465ms ->  485ms
    //    8 elements:  540ms ->  560ms
    //   16 elements:  740ms ->  760ms
    //   32 elements: 1080ms -> 1100ms
    // Note: Runtime difference for all variations was between 10-20ms, rounded up to 20ms.
    function cmp(a, b) { return a - b; }

    // Non-optimized comparator, int32 elements.
    //    4 elements:  520ms ->  220ms
    //    8 elements:  780ms ->  410ms
    //   16 elements: 1200ms ->  800ms
    //   32 elements: 3600ms -> 3100ms
    function cmp(a, b) { var x = a - b; return x; }

    var a = Array(16).fill(0).map((v, k) => k);
    var dt = 0;
    for (var i = 0; i < 1000000; ++i) {
        a.reverse();

        var t = dateNow();
        a.sort(cmp);
        dt += dateNow() - t;
    }
    print(dt);

Comment 3

[Jan de Mooij [:jandem]]

Comment on attachment 8895353 [details] [diff] [review]
bug1383648.patch

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

Thanks. This is definitely the better design since C++ -> JS calls are slow.

::: js/src/jsarray.cpp
@@ +2113,5 @@
>      ComparatorMatchResult comp = MatchNumericComparator(cx, fval);
>      if (comp == Match_Failure)
>          return false;
>  
> +    if (!fval.isUndefined() && comp == Match_None) {

Do you know how common comparators are? Pre-existing but I think it would be easier to understand and a little bit faster to wrap the MatchNumericComparator call and this if-statement in an |if (fval.isObject())| block and then replace the isObject check in MatchNumericComparator with an assert or something.

Comment 4

[Jan de Mooij [:jandem]]

Also maybe rename array_sort to ArrayNativeSort or ArraySortIntrinsic? To make it a little clearer it's not the entry point.

Comment 5

[André Bargull [:anba]]

Attachment: bug1383648.patch

Updated the patch to include the review comments/suggestions from comment #3 and comment #4. Also changed the error message back to JSMSG_BAD_SORT_ARG (I didn't see we don't use the standard JSMSG_NOT_FUNCTION for Array.prototype.sort). Carrying r+ from :jandem.

Comment 6

[André Bargull [:anba]]

Try: https://treeherder.mozilla.org/#/jobs?repo=try&revision=4e66807e000e3de296029b7e4c356ef92703f762

Comment 7

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/5f199b9a3f47
Move the Array.prototype.sort entry point to self-hosted code. r=jandem

Comment 8

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

https://hg.mozilla.org/mozilla-central/rev/5f199b9a3f47