1293971 - Don't use wrapped search for Float64Array with default comparator

Status: RESOLVED FIXED

(Core :: JavaScript: Standard Library, defect)

Description

[André Bargull [:anba]]

We should directly call QuickSort for Float64Array if the default comparator is used.


Micro benchmark:
---
// Use high resolution timer if available.
if (typeof dateNow === "undefined") {
  if (typeof preciseTime === "function") {
    dateNow = () => preciseTime() * 1000;
  } else if (typeof performance === "object" && typeof performance.now === "function") {
    dateNow = performance.now;
  } else {
    dateNow = Date.now;
  }
}

function f() {
    var TA = Float64Array;
    // Use 'small' length to avoid V8 type pollution bug, otherwise it's
    // not possible to compare our time to V8, cf. results in bug 1291463.
    var len = 2000;
    var ab = new ArrayBuffer(len * TA.BYTES_PER_ELEMENT);
    var ta = new TA(ab);
    var t = 0;
    for (var i = 0; i < 5000; ++i) {
        for (var j = 0; j < len; ++j) ta[j] = (j % 2) === 0 ? j : len - j;
        var d = dateNow();
        ta.sort();
        t += (dateNow() - d);
    }
    return t;
}

for (var i = 0; i < 10; ++i) print(f());
---


Non-patched version: ~2500 ms
Patched version: ~600 ms

V8: ~2750 ms
JSC: ~215 ms (uses native std::sort)

Comment 1

[André Bargull [:anba]]

Attachment: bug1293971.patch

Comment 2

[Tom S. (please needinfo tschuster)]

Comment on attachment 8803531 [details] [diff] [review]
bug1293971.patch

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

Nice perf improvement!

::: js/src/builtin/TypedArray.js
@@ +1138,1 @@
>              return RadixSort(obj, len, buffer, 2 /* nbytes */, true /* signed */, false /* floating */, comparefn);

I feel like this would be clearer now if we used TypedArrayCompare everywhere.

@@ +1142,5 @@
>              return RadixSort(obj, len, buffer, 4 /* nbytes */, true /* signed */, false /* floating */, comparefn);
>          } else if (IsFloat32TypedArray(obj)) {
>              return RadixSort(obj, len, buffer, 4 /* nbytes */, true /* signed */, true /* floating */, comparefn);
>          }
> +        return QuickSort(obj, len, comparefn);

This works, I think, because Quicksort can't cause the buffer the become detached.

Comment 3

[Tom S. (please needinfo tschuster)]

Btw, while looking at the source, I noticed TypedArrayCompare could probably be specialized for integers, so we don't have to care about NaN or +-0.

Comment 4

[André Bargull [:anba]]

(In reply to Tom Schuster [:evilpie] from comment #3)
> Btw, while looking at the source, I noticed TypedArrayCompare could probably
> be specialized for integers, so we don't have to care about NaN or +-0.

Filed bug 1312411.

Comment 5

[André Bargull [:anba]]

Attachment: bug1293971.patch

Applied suggested review comments, carrying r+ from evilpie.

Comment 6

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/414ec636549d
Don't wrap default comparator when sorting Float64 typed array. r=evilpie

Comment 7

[Phil Ringnalda (:philor)]

https://hg.mozilla.org/mozilla-central/rev/414ec636549d