Firefox is 17 times faster than Chrome at deleting items in a list

[Mr-Dave2]

Expected Behavior

Deleting individual items in a list should take about the same amount of time when running under different browsers.

Actual Behavior

Deleting the same number of items from a list (one at a time) takes about 17 times longer under Chrome than under Firefox.

Steps to Reproduce

Run this program: https://beta.scratch.mit.edu/#215021155 You can press "R" to see my results.

Operating System and Browser

Windows 10; Chrome 69.0.3497.100; Firefox 62.0.3

[towerofnix]

On my computer, a 2013-ish iMac running Debian, I get these results:

• Firefox 63.0b11: 0.17 to fill, 0.17 to empty.
• Chromium 68.0.3440.75: 0.11 to fill, 5.46 to empty.

Yikes, you're definitely right. It's super slow on Chrome. (My results actually mirror yours identically: on FF, equal fill/empty; on Chrome, faster fill, but much slower empty.)

[Kenny2github]

Chrome 69.0.3497.100 (Official Build) (64-bit) (cohort: Stable)
Windows 10.0.15063
Lenovo laptop bought a few weeks ago, 8GB RAM, Intel i5-8250U @ 1.60GHz 1.80GHz CPU

Unfortunately I don't have FF, but those are my Chrome results.

[kyleplo]

On my Chromebook, it took 0.9 seconds to fill, but 26 (!) seconds to empty.

[griffpatch]

Of course, if rather than adding to the list you insert to the beginning of the list, then both the insert and delete are almost the same timings. And if you delete the last item in the list rather than the 1st each time then the delete list becomes the fast part :) - It's all down to those internal list shifting operations. You'd think that would be pretty quick though?

…

On Sun, 7 Oct 2018 at 12:36, kyleplo ***@***.***> wrote: On my Chromebook, it took 0.9 seconds to fill, but 26 (!) seconds to empty. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#1637 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AGbNvgjO5qSWrz4ZxJoeaZXu0QsSI-Dyks5uiedMgaJpZM4XHVPW> .

[thisandagain]

/cc @mzgoddard @kchadha

[benjiwheeler]

Super weird, seems like we should get to the bottom of this!

[adroitwhiz]

It appears that in Chrome, Array.prototype.splice(0, 1) (executed here when Scratch deletes the first element of a list) becomes much slower after the size of the list reaches 50856 items (this might vary across machines, not sure). No idea why this happens.
You can test this for yourself with the following benchmark:

function testSplice(numItems) {
	let t = performance.now();
	let arr = [];
	for (let i = 0; i < numItems; i++) {
		arr.push(i);
	}
	for (let i = 0; i < numItems; i++) {
		arr.splice(0, 1);
	}
	return performance.now() - t;
}

function testSpliceTime(numSteps, increment) {
	for (let i = 0; i < numSteps; i++) {
		console.log(i * increment, "steps, ", testSplice(i * increment), "ms");
	}
}

testSpliceTime(100, 1000);

[adroitwhiz]

Looking further into this, it appears that V8 treats some arrays as "dictionary mode" and others as "fast mode" using some optimization voodoo. The former uses a dictionary-like structure for storing array values, and the latter is a more traditional array. Ironically, "fast mode" arrays delete lower-indexed elements much slower, as they have to shift all subsequent elements backwards, whereas "dictionary mode" arrays don't. While I haven't found a way to force "dictionary mode", using an object instead of an array seems to fix the problem:

function testSpliceObject(numItems) {
	let t = performance.now();
	let arr = {};
	for (let i = 0; i < numItems; i++) {
		arr[i] = i;
	}
	
	for (let i = 0; i < numItems; i++) {
		Array.prototype.splice.call(arr, 0, 1);
	}
	return performance.now() - t;
}

function testSpliceObjectTime(numSteps, increment) {
	for (let i = 0; i < numSteps; i++) {
		console.log(i * increment, "steps, ", testSpliceObject(i * increment), "ms");
	}
}

testSpliceObjectTime(100, 1000);