为什么一个nodejs数组移位/推循环比数组长度87369慢1000倍?

为什么nodejs数组移位/推送操作的速度在数组大小上不是线性的? 在87370有一个戏剧性的膝盖,完全粉碎了系统。

试试这个,首先是q中的87369个元素,然后是87370.(或者,在64位系统上,尝试85983和85984)。对我而言,前者运行时间为0.05秒; 后者在80秒 – 1600倍慢。 (在节点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开始爬行,运行时间为0.06 / 56秒。 节点v0.11.13具有相似的断点,但具有不同的数组大小。

       

网上收集的解决方案 "为什么一个nodejs数组移位/推循环比数组长度87369慢1000倍?"

对于数组来说,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] = {}; 

如果您需要比这更大,请使用正确的数据结构

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

我testing了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 / heap-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); } } } 

这是(store-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_); } } 

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

我猜测内存压缩可能会震荡,但是对我来说还没有到位。

编辑:忘记最后编辑输出缓冲文物,我是过滤重复。

这个bug已经报告给谷歌,谷歌没有研究这个问题就closures了它。

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

当从队列(数组)中移出并调用任务(函数)时,GC(?)停滞了一段过长的时间。

114467class次确定114468class次有问题,出现症状

响应:

他与GC没有任何关系,也没有任何阻碍。

Array.shift()是一个昂贵的操作,因为它需要移动所有的数组元素。 对于堆的大部分区域来说,V8已经实现了一个特殊的技巧来隐藏这个代价:它只是将指针碰到对象的开始,有效地切断了第一个元素。 但是,当一个数组太大以至于它必须被放置在“大对象空间”中时,这个技巧不能被应用,因为对象的开始必须被alignment,所以在每一个.shift()操作中,所有的元素都必须被移到内存中。

我不确定我们能做些什么。 如果你想在JavaScript中使用“Queue”对象,并保证.enqueue()和.dequeue()操作的O(1)复杂性,你可能需要实现你自己的。

编辑:我只是抓住了微妙的“所有元素必须被移动”的一部分 – 是RecordWrites不GC,但实际元素复制呢? 数组内容的移位是0.04毫秒。 RecordWrites循环是1.1 ms运行时的96%。

编辑:如果“alignment”意味着第一个对象必须在第一个地址,这就是memmove做的。 什么是RecordWrites?