[performance] Array::sort_by

[illusory0x0]

current behavior

Please checkout array-sort-benchmark master branch

npm run benchmark

ffi:sort x 28.88 ops/sec ±6.95% (53 runs sampled)
moonbit:sort x 16.93 ops/sec ±1.12% (44 runs sampled)
javascript:sort x 33.45 ops/sec ±0.23% (59 runs sampled)

JavaScript intrinsic Array function is the fastest,

Anomalous benchmarking results

checkout the benchmark-similar branch

moonbit:sort x 31.17 ops/sec ±8.37% (58 runs sampled)
javascript:sort x 32.83 ops/sec ±0.44% (57 runs sampled)
Fastest is javascript:sort,moonbit:sort

moonbit implementation is the same fast as JavaScript intrinsic Array function, but I use both Array::sort and Array::sort_by in this benchmark.

Although it has the same performance in a particular benchmark, the moonbit implementation leads to code bloat.

FFI make generated javascript codesize smaller.

const username$hello$ffi$$_array_sort_by = (xs,f) => xs.sort(f);
function username$hello$ffi$$array_sort_by$0$(xs, f) {
  username$hello$ffi$$_array_sort_by(xs, f);
}
function username$hello$ffi$$moonbit_array_sort_int(xs) {
  username$hello$ffi$$array_sort_by$0$(xs, (x, y) => x - y | 0);
}
function username$hello$ffi$$moonbit_array_reverse_sort_int(xs) {
  username$hello$ffi$$array_sort_by$0$(xs, (x, y) => y - x | 0);
}
export { username$hello$ffi$$moonbit_array_sort_int as moonbit_array_sort_int, username$hello$ffi$$moonbit_array_reverse_sort_int as moonbit_array_reverse_sort_int }

Although I use minifier, still has 8392 bytes for one type's monomorphism code generation.

expected behavior

use FFI to implement Array::sort_by

Note

Array.sort is stable sort algorithm.

[peter-jerry-ye]

We do not prioritize the JavaScript performance for the moment. The code bloat is acknowledged, and we'll improve it in the future. We may refactor our JS backend in the future.

[hackwaly]

If make this changes:

  suite.add("ffi:sort", () => {
    ffi_moonbit_array_sort_int(ffi_test_data)
    // ffi_moonbit_array_reverse_sort_int(ffi_test_data)
  })


  suite.add("moonbit:sort", () => {
    mbt_moonbit_array_sort_int(mbt_test_data)
    // mbt_moonbit_array_reverse_sort_int(mbt_test_data)
  })

  suite.add("javascript:sort", () => {
    javascript_array_sort_int(js_test_data)
    // javascript_array_reverse_sort_int(js_test_data)
  })

It results:

ffi:sort x 109 ops/sec ±0.75% (81 runs sampled)
moonbit:sort x 404 ops/sec ±0.21% (95 runs sampled)
javascript:sort x 110 ops/sec ±0.20% (82 runs sampled)
Fastest is moonbit:sort

So, our implementation might just not optimized for this case.

We could employ other algorithm that optimized for case that input array is almost sorted.

[hackwaly]

I see there's timsort implementation in core, but only for FixedArray::stable_sort. So I created #2595 .

[hackwaly]

Tested on timsort version

ffi:sort x 50.08 ops/sec ±0.33% (66 runs sampled)
moonbit:sort x 204 ops/sec ±1.63% (88 runs sampled)
javascript:sort x 49.86 ops/sec ±0.70% (66 runs sampled)
Fastest is moonbit:sort

[hackwaly]

Tested on timsort_by version

ffi:sort x 50.39 ops/sec ±0.26% (67 runs sampled)
moonbit:sort x 87.71 ops/sec ±0.10% (77 runs sampled)
javascript:sort x 50.47 ops/sec ±0.22% (67 runs sampled)
Fastest is moonbit:sort