为什么nodejs数组移位/推回路在数组长度87369以上运行速度要慢1000倍？

问题描述：

为什么nodejs数组移位/推送操作的速度在数组大小上不是线性的？在87370有一个戏剧性的膝盖，彻底粉碎了这个系统。为什么nodejs数组移位/推回路在数组长度87369以上运行速度要慢1000倍？

尝试此操作，首先在q中使用87369个元素，然后使用87370.（或者，在64位系统上，尝试85983和85984.）对于我而言，前者运行时间为0.05秒;后者在80秒内 - 1600倍慢。（在32位的Debian Linux的观察节点v0.10.29）

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和在0.06/56秒运行一次。节点v0.11.13具有类似的断点，但是具有不同的数组大小。

我修正了错字85983（5，不是6） – Andras 2014-12-07 09:58:19

答

我开始深入研究v8源代码，但我仍然不明白。

我仪表DEPS/V8/SRC/builtins.cc：MoveElemens（称为从Builtin_ArrayShift，它实现与的memmove移位），它清楚地示出的减速：每秒1000只移位，因为每一个取为1ms：

AR: at 1417982255.050970: MoveElements sec = 0.000809 
AR: at 1417982255.052314: MoveElements sec = 0.001341 
AR: at 1417982255.053542: MoveElements sec = 0.001224 
AR: at 1417982255.054360: MoveElements sec = 0.000815 
AR: at 1417982255.055684: MoveElements sec = 0.001321 
AR: at 1417982255.056501: MoveElements sec = 0.000814

其中的memmove是0.000040秒，本体是按堆> RecordWrites（DEPS/V8/SRC /堆inl.h）：

void Heap::RecordWrites(Address address, int start, int len) { 
    if (!InNewSpace(address)) { 
    for (int i = 0; i < len; i++) { 
     store_buffer_.Mark(address + start + i * kPointerSize); 
    } 
    } 
}

，其为（商店buffer- inl.h）

void StoreBuffer::Mark(Address addr) { 
    ASSERT(!heap_->cell_space()->Contains(addr)); 
    ASSERT(!heap_->code_space()->Contains(addr)); 
    Address* top = reinterpret_cast<Address*>(heap_->store_buffer_top()); 
    *top++ = addr; 
    heap_->public_set_store_buffer_top(top); 
    if ((reinterpret_cast<uintptr_t>(top) & kStoreBufferOverflowBit) != 0) { 
    ASSERT(top == limit_); 
    Compact(); 
    } else { 
    ASSERT(top < limit_); 
    } 
}

当代码运行缓慢时，会有运行的移位/推送操作，然后对每个MoveElements运行5-6次调用Compact()。当它快速运行时，MoveElements不会被调用，直到最后几次，并且当它结束时只有一次压缩。

我猜内存压缩可能会出现抖动，但它对我来说还没有到位。

编辑：忘记最后编辑输出缓冲工件，我是过滤重复。

答

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

空阵列以4个插槽开始，随着您继续推动，它将使用公式1.5 * (old length + 1) + 16调整阵列大小。

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

打印：

所以你的数组的大小最终实际并非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

谢谢，但问题是'shift'，而不是'unshift' - 数组越来越小（它被预先分配给87369和附加数据）。 v8使用memmove（）来移动它们，只需要0.04 ms;总共花费的时间是1.10毫秒，慢了25倍。放缓来自RecordWrites内部。为什么RecordWrites在这种情况下需要？它有什么作用？ – Andras 2014-12-09 14:24:28

我试过你的建议，把它改成'q = new Array（20000）'，但它仍然很慢。 – Andras 2014-12-09 14:27:44

你不能预先分配'.push'，它会动态调整大小，当数字变大时，调整大小非常慷慨，因为调整大小操作非常昂贵（需要将所有元素复制到新阵列） – Esailija 2014-12-09 18:40:22

答

这个bug已经被报道谷歌，谁没有研究这个问题关闭它。

https://code.google.com/p/v8/issues/detail?id=3059

当移出并从队列中（阵列）调用任务（功能）的GC（α）拖延过多的时间长度。

114467班次正常 114468班次是有问题的，出现症状

响应：

他GC无关这一点，并没有什么拖延无论是。

Array.shift（）是一个昂贵的操作，因为它需要移动所有数组元素。对于堆中的大部分区域，V8已经实现了一个特殊技巧来隐藏这个成本：它只是将指针对着对象起点加1，从而有效地切断了第一个元素。但是，当数组太大以至于必须将其放置在“大对象空间” 中时，此技巧无法应用，因为对象开始必须对齐，所以在每个.shift（）操作中，实际上所有元素都必须移动到记忆。

我不确定我们可以对此做很多事情。如果您想在JavaScript中使用 “Queue”对象，并确保O（1）复杂性为 .enqueue（）和.dequeue（）操作，您可能需要实现自己的。

编辑：我刚刚发现了微妙的“所有元素都必须移动”的部分 - RecordWrites不是GC，而是一个实际的元素复制呢？数组内容的移位是0.04毫秒。 RecordWrites循环是1.1 ms运行时的96％。

编辑：如果“对齐”意味着第一个对象必须在第一个地址，这就是memmove所做的。什么是RecordWrites？

在v8使用的分代垃圾回收中，记录写入在某种意义上是钩子，用于检查是否将旧空间中的对象指向新空间中的对象。 – Esailija 2014-12-09 18:43:52

啊，这很有用，谢谢。那么memmove（）在数组中移动指针还是对象本身？没有新的对象正在创建，列表也没有被创建 – Andras 2014-12-09 19:15:37

为什么nodejs数组移位/推回路在数组长度87369以上运行速度要慢1000倍？

相关推荐