1087963 - Slice is slow on sparse arrays

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Jan de Mooij [:jandem]]

According to Google Inbox engineers, us being slow on this is/was a major problem for them:

https://news.ycombinator.com/item?id=8495939

Testcase as mentioned there:

var xx = []; xx[30000000]=42; var yy = xx.slice(0);

Thanks to evilpie for mentioning this in #jsapi.

Comment 1

[Frederik Braun [:freddy]]

Possible duplicate of bug 1045391.

Comment 2

[Jan de Mooij [:jandem]]

(In reply to Frederik Braun [:freddyb] from comment #1)
> Possible duplicate of bug 1045391.

It's a similar issue but not a duplicate. I want to fix slice first, after that we can do something similar for forEach et al.

Comment 3

[Jan de Mooij [:jandem]]

Attachment: Testcase, fails in Chrome

V8's slice implementation does not account for new properties added by getters...

Comment 4

[Jan de Mooij [:jandem]]

Attachment: Patch

This patch optimizes slice on sparse objects: it fills a Vector with all indexed properties and then only calls GetElement for those properties. This is similar to what V8 does, but we check for getters so we don't have the bug mentioned in comment 3.

On the testcase in comment 0:

Before: 2503 ms
After:     0 ms

Here's a modified testcase that adds a lot more properties (but the array is still sparse):

var xx = [];
xx[30000000]=42;
for (var i=100000; i<300000; i += 2)
    xx[i] = i;
var t = new Date;
var yy = xx.slice(0);
print(new Date - t);

Before: 3269 ms
After:    39 ms
V8:       74 ms

Note that the GetIndexedPropertiesInRange function is pretty large, but it's way faster than the generic property iteration stuff in jsiter.cpp, and also checks for proxies and getters etc as mentioned above. Furthermore, I think we can use it later to speed up forEach and friends (bug 1045391), so it seemed useful enough to add.

Comment 5

[Jan de Mooij [:jandem]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/f4a77b74abc3

(https://treeherder.mozilla.org/ui/#/jobs?repo=try&revision=5e5825a3d496)

Comment 6

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/f4a77b74abc3

Comment 7

[Nicholas Nethercote [inactive]]

Given the visibility of Google Inbox, we should consider backporting this to Aurora or even Beta.

Comment 8

[Dirkjan Ochtman (:djc)]

Note that it's already fixed in Inbox, so I don't think that's a great reason to backport:

https://news.ycombinator.com/item?id=8496304

Comment 9

[Mathias Bynens]

(In reply to Dirkjan Ochtman (:djc) from comment #8)
> Note that it's already fixed in Inbox, so I don't think that's a great
> reason to backport:
> 
> https://news.ycombinator.com/item?id=8496304

Fixed, but not shipped:

“In this case, a workaround is available, and it is already fixed, but not shipped, because we froze commits some time ago for launch.”