为什么使用 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 的 "partition phase" 期间移动数据）？为什么要花2倍多甚至5倍的时间来做呢？是不是也和处理器内部缓存中所有数据拟合，内部缓存能不能支持32位不支持IEEE 754数有关系？

Answer 1

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

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

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

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

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

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

它又节省了 10%。

On NodeJS, the difference is even more: 5.05 seconds vs 28.9 seconds.

对于 Node 13.11，我无法重现；我得到的数字几乎与 Chrome 81.

完全相同

Chrome or NodeJS able to optimize it by using 32-bit integers, vs using 64-bit integers, or IEEE 754 Numbers

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

would it take exactly one clock cycle to do the compare

估计现代 CPU 的时钟周期非常困难，几乎没有什么比 "exactly one clock cycle" 更简单了。一方面，CPUs 每个周期可以执行（部分）多条指令，另一方面，它们有流水线，这意味着完成一条指令的执行需要很多周期。特别是，频繁的分支（即 CPU 内的 "decision-making"），作为排序算法通常必须做的，往往会受到与管道相关的延迟的影响。

the "partition phase" of Quicksort

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

Does it also have something to do with fitting all data in the internal cache of the processor and whether the internal cache can support 32 bit but not IEEE 754 numbers?

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

V8 is capable of optimizing the numeric storage type if the optimizer can deduce that all the values in the array will fit in that size

差不多；不涉及推论：该数组乐观地从 Smi 后备存储开始，并根据需要对其进行概括，例如当存储第一个 double 时，存储切换到 double 数组。

You are probably seeing the effect of "just-in-time compiling."

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

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

Why does sorting 32-bit numbers using JavaScript so much faster than sorting 33-bit numbers?

javascript

performance

v8

node.js