为什么使用 JavaScript 对 32 位数字进行排序比对 33 位数字进行排序快得多？

Question

以下代码只是创建一个数组并对其进行排序。很奇怪，在我 2013 年的 Macbook Pro 上，对 30 位数字进行排序需要 5.8 秒：

n = 10000000;
numMax = 1000000000;

console.log(`numMax is how many bits: ${Math.ceil(Math.log(numMax) / Math.log(2))}`)

console.log("\n## Now creating array");

let start = Date.now();
let arr = new Array(n);

for (let i = 0; i < arr.length; ++i) 
    arr[i] = Math.floor(Math.random() * numMax);

console.log(`took ${(Date.now() - start)/ 1000} seconds to create the array`);


console.log("\n## Now sorting it");
start = Date.now();

arr.sort((a, b) => a - b);

console.log(`took ${(Date.now() - start)/ 1000} seconds to sort`);

但是假设我们将其设为 34 位数字。现在运行需要 12.7 秒：

n = 10000000;
numMax = 10000000000;

console.log(`numMax is how many bits: ${Math.ceil(Math.log(numMax) / Math.log(2))}`)

console.log("\n## Now creating array");

let start = Date.now();
let arr = new Array(n);

for (let i = 0; i < arr.length; ++i) 
    arr[i] = Math.floor(Math.random() * numMax);

console.log(`took ${(Date.now() - start)/ 1000} seconds to create the array`);


console.log("\n## Now sorting it");
start = Date.now();

arr.sort((a, b) => a - b);

console.log(`took ${(Date.now() - start)/ 1000} seconds to sort`);

在 NodeJS 上（更新：我使用的是 v12.14.0），差异更大：5.05 秒与 28.9 秒。为什么差别这么大？如果是因为 Chrome 或 NodeJS 能够使用 32 位整数优化它，而不是使用 64 位整数或 IEEE 754 数字，那么在排序期间进行比较（并移动数据）是否需要一个时钟周期？在 Quicksort 的“分区阶段”）？为什么要做2倍甚至5倍以上的时间？是否也与处理器内部缓存中的所有数据拟合以及内部缓存是否支持32位但不支持IEEE 754数字有关？

Answer 1

V8 开发人员在这里。简而言之：这就是为什么 V8 在可能的情况下在内部使用“Smis”（小整数）。

在 JavaScript 中，任何值通常可以是任何值，因此引擎通常以某种格式表示值，该格式将类型信息与值本身一起存储。这包括数字；所以堆上的数字是一个具有两个字段的对象：一个类型描述符和实际的数字值，它是每个 JavaScript 规范的 IEEE-754 64 位双精度值。由于小而整数值的数字特别常见，V8 使用一种特殊的技巧来更有效地对它们进行编码：它们根本不作为对象存储在堆上，而是将值直接编码到“指针”中，并且指针的位之一用于将其标记为所谓的 Smi。在所有当前版本的 Chrome 中，V8 使用 32 位堆指针，其中 31 位用于 Smi 的有效负载。由于数字数组也很常见，为每个元素存储一个类型描述符是相当浪费的；相反，V8 有双数组，其中数组本身记住了一个事实（只有一次！）它的所有元素都是双精度的；然后可以将这些元素直接存储在数组中。

所以在你的 30 位版本的代码中，数组的后备存储是一个充满 Smis 的数组，调用比较器函数可以直接传递其中的两个。反过来，该功能可以快速 Smi 检查并取消标记值以执行减法。

在 34 位版本中，数组的后备存储存储加倍。每次需要调用比较器时，都会从数组中读取两个原始双精度值，将其装箱为“堆编号”以用作函数调用的参数，并且比较器函数必须先从堆中读取值能够减去它们。我真的很惊讶这只是慢了两倍:-)

为了稍微了解一下这个测试用例的性能细节，您可以强制数组存储堆数而不是未装箱的双精度数。虽然这会预先消耗更多内存并在许多用例中产生性能成本，但在这种特殊情况下，它实际上节省了大约 10% 的时间，因为在执行期间分配的短期垃圾更少。如果您另外强制比较器的结果作为 Smi 返回：

arr.sort((a, b) => a > b ? 1 : a < b ? -1 : 0);

它又节省了 10%。

在 NodeJS 上，差异更大：5.05 秒与 28.9 秒。

使用 Node 13.11 我无法重现；我得到的数字与 Chrome 81 几乎完全相同。

Chrome 或 NodeJS 能够通过使用 32 位整数与使用 64 位整数或 IEEE 754 数字来优化它

能够使用 32 位整数 CPU 指令是使用 Smi 表示的副作用，但这不是此处性能差异的（主要）原因。在内部使用 64 位整数将违反 JavaScript 规范（除非引擎非常小心地检测并避免过于精确的结果）。

进行比较是否只需要一个时钟周期

估计现代 CPU 上的时钟周期非常困难，几乎没有什么比“正好一个时钟周期”那么简单。一方面，CPU 每个周期可以执行（部分）多条指令，另一方面，它们有流水线，这意味着仅完成一条指令的执行需要许多周期。特别是，排序算法通常必须执行的频繁分支（即 CPU 内部的“决策”）往往会受到与管道相关的延迟的影响。

Quicksort的“分区阶段”

V8 不再使用 Quicksort。也就是说，当然所有排序算法都必须移动数据。

是否也与处理器内部缓存中的所有数据拟合以及内部缓存是否支持32位但不支持IEEE 754数字有关？

CPU 的缓存并不关心数据的类型。但是，数据的大小（64 位双精度数是 32 位整数的两倍）可能会导致与缓存相关的性能差异。

如果优化器可以推断出数组中的所有值都适合该大小，则 V8 能够优化数字存储类型

几乎; 不涉及任何推论：数组乐观地以 Smi 后备存储开始，并根据需要进行概括，例如，当存储第一个双精度值时，存储将切换到双精度值数组。

您可能会看到“即时编译”的效果。

并不真地。当然，所有现代引擎都会对您的代码进行 JIT 编译，但对于所有代码都是如此，这里并没有解释差异。