整数数组排序:为什么Int32Array.sort比Array.sort慢？

Question

我观察到类型化整数数组的.sort()实现性能低于当前JavaScript引擎上的非类型化数组。

我的直觉告诉我，TypedArray.prototype.sort()应该更快，因为它在默认情况下执行数字比较，而不是Array.prototype.sort()使用的字符串比较，因此我们需要提供一个比较函数(a, b) => b - a。

然而，在实践中，这种直觉是错误的。Chrome和Firefox都能更快地对非类型化数组进行排序：

​

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>

​

这种差异必须是由.sort引起的，而不是.slice，它比前者快两个数量级。

是否有内在的原因来解释观察到的低性能？

PS:根据在JavaScript中对32位带符号整数数组进行排序的最快方法？，排序整数数组的最快方法是提供自己的.sort实现。

更新:在Firefox52/ Ubuntu上，排序Int32Array的执行速度略快于非类型化数组。

Answer 1

这是一个老问题，但在看到另一个开发人员使用Int32Array.sort 关于Leetcode之后，我对它感兴趣。答案是:它不会慢..。至少在所有平台上。

我对本机排序(使用比较器)执行了自己的基准测试，我自己实现了合并排序和快速排序，到目前为止，Int32Array.sort是最快的--2022年在Node.js版本16中。

现在这个问题最初是在2017年发布的，所以我想从那以后会有很大的变化，但我也在Google上运行了这个测试，测试结果也差不多--这是有道理的，因为Node.js和Chrome都是由V8提供动力的。所以我试了一下FireFox - Int32还是赢了，但是跑步时间更近了。

免责声明我只在这些基准测试中付出了中等的努力，我没有使用Benchmark.js或类似的东西。还请注意，我使用的测试数组是随机排序，这不应该有太大的区别，因为根据MDN和Array.sort和TypedArray.sort都在幕后使用了相同的算法，但是还是免责声明！里程数可能因这些数字的准确程度而不同。尽管如此，在多次以各种方式运行测试之后，我没有遇到Array.sort速度更快的任何情况。

Node.js v 16的示例运行时间：

sort 2448
sort32 387

Google Chrome v 104.0.5112.101的运行时间示例：

sort 2351
sort32 357

距离FireFox的时间

sort 1097
sort32 722