node.js - 为什么 nodejs 数组移位/推送循环在数组长度 87369 以上运行速度慢 1000 倍？

Question

为什么 nodejs 数组移位/压入操作的速度与数组大小不是线性关系？ 87370 处有一个戏剧性的拐点，完全压垮了系统。

试试这个，首先在 q 中使用 87369 个元素，然后使用 87370。(或者，在 64 位系统上，尝试 85983 和 85984。)对我来说，前者运行时间为 0.05 秒；后者在 80 秒内——慢了 1600 倍。 (在 Node v0.10.29 的 32 位 debian linux 上观察到)

q = [];

// preload the queue with some data
for (i=0; i<87369; i++) q.push({});

// fetch oldest waiting item and push new item
for (i=0; i<100000; i++) {
    q.shift();
    q.push({});
    if (i%10000 === 0) process.stdout.write(".");
}

64 位 debian linux v0.10.29 从 85984 开始抓取并在 .06/56 秒内运行。 Node v0.11.13 具有类似的断点，但数组大小不同。

Answer 1

Shift 对数组来说是一个非常慢的操作，因为您需要移动所有元素，但是当数组内容适合页面 (1mb) 时，V8 能够使用一个技巧来快速执行它。

空数组以 4 个槽开始，当您不断插入时，它将使用公式 1.5 * (old length + 1) + 16 调整数组的大小。

var j = 4;
while (j < 87369) {
    j = (j + 1) + Math.floor(j / 2) + 16
    console.log(j);
}

打印:

23
51
93
156
251
393
606
926
1406
2126
3206
4826
7256
10901
16368
24569
36870
55322
83000
124517 

所以你的数组大小最终实际上是 124517 个项目，这使得它太大了。

您实际上可以将您的数组预分配到正确的大小，它应该能够再次快速移动:

var q = new Array(87369); // Fits in a page so fast shift is possible

// preload the queue with some data
for (i=0; i<87369; i++) q[i] = {};

如果你需要更大的，使用 the right data structure