Issue 2131 in v8: Array.splice() slows down at arrays larger than 114467

[codesite...@google.com]

Status: New
Owner: ----

New issue 2131 by manishsm...@gmail.com: Array.splice() slows down at
arrays larger than 114467
http://code.google.com/p/v8/issues/detail?id=2131

I'm getting an astronomical difference in speeds for running splice(0,1)
for arrays of lengths 114467 and 114468 respectively.

Running this benchmark:

var t;
function startBench(){t=new Date().getTime();}
function stopBench(){console.log(new Date().getTime()-t);}
var arr=[];
for (var i = 114467; i > 0; i--) {
arr.push([i - 1, i]);
}
var arr2=[];
for (var i = 114468; i > 0; i--) {
arr2.push([i - 1, i]);
}
startBench();
for(i=0;i<1000;i++){
arr.splice(0,1);
}

stopBench();
startBench();
for(i=0;i<1000;i++){
arr2.splice(0,1);
}
stopBench();


I get 3ms for the array of length 114467 and 2750ms for the array of length
114468.

Firefox gives 170ms for both, but that's irrelevant.

Is this a bug?

[codesite...@google.com]

Updates:
Status: Assigned
Owner: mstar...@chromium.org

Comment #1 on issue 2131 by yan...@chromium.org: Array.splice() slows down

at arrays larger than 114467
http://code.google.com/p/v8/issues/detail?id=2131

Both arrays are in fast (non-dictionary) mode.

Profiling for splicing the first array:
Ticks per symbol:
600 6.4%
v8::internal::Heap::DoScavenge(v8::internal::ObjectVisitor*, unsigned char*)
428 4.6%
v8::internal::ScavengingVisitor<(v8::internal::MarksHandling)1,
(v8::internal::LoggingAndProfiling)0>::EvacuateFixedArray(v8::internal::Map*,
v8::internal::HeapObject**, v8::internal::HeapObject*)
405 4.3% void
v8::internal::ScavengingVisitor<(v8::internal::MarksHandling)1,
(v8::internal::LoggingAndProfiling)0>::EvacuateObject<(v8::internal::ScavengingVisitor<(v8::internal::MarksHandling)1,
(v8::internal::LoggingAndProfiling)0>::ObjectContents)1,
(v8::internal::ScavengingVisitor<(v8::internal::MarksHandling)1,
(v8::internal::LoggingAndProfiling)0>::SizeRestriction)0,
4>(v8::internal::Map*, v8::internal::HeapObject**,
v8::internal::HeapObject*, int)
346 3.7% LazyCompile:* test.js:1 [js]
261 2.8% CallIC:push [js]
200 2.1%
v8::internal::FlexibleBodyVisitor<v8::internal::NewSpaceScavenger,
v8::internal::FixedArray::BodyDescriptor, int>::Visit(v8::internal::Map*,
v8::internal::HeapObject*)
198 2.1% GLIBC_2.0 _IO_vfprintf
183 2.0% v8::internal::Heap::CopyBlock(unsigned char*, unsigned
char*, int)
164 1.8%
v8::internal::Deserializer::ReadChunk(v8::internal::Object**,
v8::internal::Object**, int, unsigned char*)
[...]

Profiling for splicing the second array:
101296 59.3% v8::internal::StoreBuffer::Compact()
30562 17.9% v8::internal::MoveElements(v8::internal::Heap*,
v8::internal::AssertNoAllocation*, v8::internal::FixedArray*, int,
v8::internal::FixedArray*, int, int)
25010 14.7% T.2601
440 0.3%
v8::internal::ScavengingVisitor<(v8::internal::MarksHandling)1,
(v8::internal::LoggingAndProfiling)0>::EvacuateFixedArray(v8::internal::Map*,
v8::internal::HeapObject**, v8::internal::HeapObject*)
436 0.3% void
v8::internal::ScavengingVisitor<(v8::internal::MarksHandling)1,
(v8::internal::LoggingAndProfiling)0>::EvacuateObject<(v8::internal::ScavengingVisitor<(v8::internal::MarksHandling)1,
(v8::internal::LoggingAndProfiling)0>::ObjectContents)1,
(v8::internal::ScavengingVisitor<(v8::internal::MarksHandling)1,
(v8::internal::LoggingAndProfiling)0>::SizeRestriction)0,
4>(v8::internal::Map*, v8::internal::HeapObject**,
v8::internal::HeapObject*, int)
382 0.2%
v8::internal::Heap::DoScavenge(v8::internal::ObjectVisitor*, unsigned char*)
265 0.2% GLIBC_2.0 _IO_vfprintf
220 0.1%
v8::internal::FlexibleBodyVisitor<v8::internal::NewSpaceScavenger,
v8::internal::FixedArray::BodyDescriptor, int>::Visit(v8::internal::Map*,
v8::internal::HeapObject*)
213 0.1% v8::internal::Heap::CopyBlock(unsigned char*, unsigned
char*, int)
201 0.1%
v8::internal::Deserializer::ReadChunk(v8::internal::Object**,
v8::internal::Object**, int, unsigned char*)
[...]

There seems to be a lot more GC work going on. Assigning to Michael.

[codesite...@google.com]

Updates:
Labels: Type-FeatureRequest Priority-Low

Comment #2 on issue 2131 by mstar...@chromium.org: Array.splice() slows

down at arrays larger than 114467
http://code.google.com/p/v8/issues/detail?id=2131

I strongly suspect that this is due to the backing store of the larger
array being allocated in large-object space, where we currently cannot do
efficient trimming of arrays from the left. So we end up moving the whole
content to the left and adding the slots to the store-buffer because the
backing store is not in new-space. This is especially brain-dead in this
case, where we actually do not move anything at all, because 'start' is set
to zero. I have some ideas how to improve Array.prototype.splice for these
cases.