4

I observed a lower performance of the .sort() implementation for typed integer arrays compared to untyped arrays on current JavaScript engines.

My intuition tells me that TypedArray.prototype.sort() should be faster since it performs a numeric comparison by default rather than the string comparison used by Array.prototype.sort() for which we would thus need to supply a compare function (a, b) => b - a.

In practice however, this intuition is wrong. Chrome and Firefox both sort the untyped array (much) faster:

var length = 1000,
  array = new Array(length),
  int32Array = new Int32Array(length);

// Fill arrays with random integers:
for (var i = 0; i < length; ++i) {
  int32Array[i] = array[i] = Math.random() * length | 0;
}

// Run benchmark.js test suite:
var suite = new Benchmark.Suite;
suite.add('Array.sort', function() {
  var input = array.slice();
  var result = input.sort((a, b) => b - a);
})
.add('Int32Array.sort', function() {
  var input = int32Array.slice();
  var result = input.sort();
})
.on('complete', function() {
  console.log(this[0].toString());   
  console.log(this[1].toString()); 
  console.log('Fastest is ' + this.filter('fastest').map('name'));
})
.run();
<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.13.1/lodash.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/benchmark/2.1.0/benchmark.js"></script>

The difference must be caused by .sort and not .slice which runs about two orders of magnitude faster than the former.

Is there an inherent reason explaining the observed low performance?

PS: According to Fastest way to sort 32bit signed integer arrays in JavaScript?, the fastest way to sort an integer array is to supply one's own .sort implementation.

2017 Update: On Firefox 52 / Ubuntu, sorting Int32Array now performs slightly faster than for the untyped array.

Community
  • 1
  • 1
le_m
  • 19,302
  • 9
  • 64
  • 74
  • You're performing different types of sort, some of which might be optimized out because you're not using (or assigning or passing) the return value at all. This is not a particularly direct comparison. – ssube Jun 07 '16 at 17:10
  • @Dan Why do you suggest removing the stack snippet? – le_m Jun 07 '16 at 17:12
  • @ssube Might be the case, do you have a suggestion on how to build a better performance comparison? – le_m Jun 07 '16 at 17:13
  • [This article](http://www.oracle.com/technetwork/articles/java/architect-benchmarking-2266277.html) isn't specific to JS, but some of the concepts are shared between most dynamic VMs. You need to make sure the VM can't optimize your code out and passing objects across modules tends to be a good way to out-smart the optimizer. You should also run as many samples as you reasonably can (a few minutes, at least) to make sure any optimizations have been run and the code stops changing. Warming up the VM by running a bunch of throw-away samples is a good idea, then take your actual measurements. – ssube Jun 07 '16 at 17:19
  • @ssube Thanks! I have updated the question to use benchmark.js which at least performs warmup. – le_m Jun 07 '16 at 17:52
  • You're measuring `slice` operation as well, not only sorting. They also have different performance characteristics. – zerkms Mar 16 '17 at 21:22
  • @zerkms Quoting from the question: "The difference must be caused by .sort and not .slice which runs about two orders of magnitude faster than the former." (at least it was like that back then in 2016) – le_m Mar 16 '17 at 21:24
  • Then the title is misleading. Nothing in the benchmark reveals that sorting is slower. :shrug: – zerkms Mar 16 '17 at 21:26
  • @zerkms You have to read this question in the context of when it was asked. I might add a [2016] to the title - but since we already have a date associated with questions, that might be redundant. What do you suggest? – le_m Mar 16 '17 at 21:34

1 Answers1

1

This is an old question but I got interested in it after seeing another developer use Int32Array.sort on Leetcode. The sort answer is : IT'S NOT SLOWER... at least on all platforms.

I performed my own benchmark against native sort (with a comparator), my own implementations of merge sort and quick sort, and Int32Array.sort was by far the fastest - in Node.js version 16, in 2022.

Now this question was originally posted back in 2017 so I'm going to assume a lot has changed since then, but I also ran this test in Google Chrome and the results were about the same - this makes sense as both Node.js and Chrome are powered by V8... so I tried in FireFox - Int32 still won, but the running times were much closer.

DISCLAIMER! I only put medium effort into these benchmarks, I didn't use Benchmark.js or anything like that. Also note that the test arrays I used were randomized sort, which shouldn't have much of a difference because according to MDN both Array.sort and TypedArray.sort use the same algorithm under the hood, but still, DISCLAIMER! mileage may vary with how accurate these numbers are. That said, after running the test over a bunch of times and in a variety of ways, I didn't encounter any case where Array.sort was faster.

Example running times from Node.js v 16 :

sort 2448
sort32 387

Example running times from Google Chrome v 104.0.5112.101 :

sort 2351
sort32 357

Times from FireFox

sort 1097
sort32 722
nameofname
  • 91
  • 5