CODEWITHSUNDEEP
javascriptarrayssorting
le_m
le_m

Reputation: 20248

Sorting integer arrays: Why is Int32Array.sort slower than Array.sort?

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.

Upvotes: 4

Views: 456

Answers (1)

nameofname
nameofname

Reputation: 190

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

Upvotes: 1

Related Questions