1291463 - Array.prototype.sort performance improvements

Status: RESOLVED FIXED

(Core :: JavaScript: Standard Library, defect, P3)

Description

[André Bargull [:anba]]

Attachment: Benchmark script

Possible performance improvements for Array.prototype.sort:
- Move "ArraySort" to vm/CommonPropertyNames.h instead of calling Atomize repeatedly
- Directly return in ArraySort() if the length less than 2
- Handle partially sorted sublists in Merge
- Reduce stores in Merge() by using a single additional buffer
- Use std_Array instead of List (also avoids a JIT bug [1] when there's only one element)
- Handle packed arrays when storing from the array to the denseList
- Use InsertionSort() instead of Merge() for windowSize=1 and windowSize=2


[1]: 
---
function t(array) {
    function c(a, b) { var d = a - b; return d; }
    var t = 0;
    for (var i = 0; i < 100000; ++i) {
        var arrays = [];
        for (var j = 0; j < 10; ++j) arrays[j] = array();

        var d = dateNow();
        for (var j = 0; j < 10; ++j) arrays[j].sort(c);
        t += (dateNow() - d);
    }
    print(t);
}

// Slow
t(() => [1,,,,,,,,,,]);

// Faster
// t(() => [,,,,,,,,,,]);
// t(() => [1,2,,,,,,,,,]);
---

Comment 1

[André Bargull [:anba]]

Attachment: Array.sort-performance.patch

Patch which implements the suggestions mentioned in comment #0

Comment 2

[André Bargull [:anba]]

Attachment: Benchmark results

Results when running the attached benchmark, including comparisons to JavaScriptCore and V8.

Comment 3

[André Bargull [:anba]]

SpiderMonkey version: m-c ffac2798999c
JSC version: trunk rev204022
V8 version: master 8552e6822317c48638eb25d71c902cffebee21f1

Comment 4

[Jeff Walden [:Waldo]]

I have difficulty thinking of pretty much any situation where it makes sense to have Atomize(cx, "...", ...) in regularly executed, non-test code.  Things like ArraySort and similar should always be in CommonPropertyNames.h, IMO.

Comment 5

[André Bargull [:anba]]

Attachment: Benchmark script

Comment 6

[André Bargull [:anba]]

Attachment: Benchmark results

Comment 7

[4esn0k]

see also https://bugzilla.mozilla.org/show_bug.cgi?id=1259007

Comment 8

[André Bargull [:anba]]

Attachment: Bug 1291463: Apply TypedArray sort optimisations to normal Array sort. r=jorendorff!

Also change the temporary buffer to a normal Array to ensure the Merge helper
is called with the same object class.

Comment 9

[André Bargull [:anba]]

With bug 1538692 also applied, this improves µ-benchmark from bug 1502882 when the str_cmp_full comparator function is used from 6.2ms (when only bug 1538692 is applied) to 5.5ms for me.

Comment 10

[Jason Orendorff [:jorendorff]]

Anba, do you want to land this?

Comment 11

[André Bargull [:anba]]

Try: https://treeherder.mozilla.org/#/jobs?repo=try&selectedJob=255261545&revision=03ffdfb797e741917cae13f89cbef4eea44f29c8

Comment 12

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/a869bc3e91a4
Apply TypedArray sort optimisations to normal Array sort. r=jorendorff

Comment 13

[Narcis Beleuzu [:NarcisB]]

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