Closed Bug 1087963 Opened 10 years ago Closed 10 years ago

Slice is slow on sparse arrays

Categories

(Core :: JavaScript Engine, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla36
Tracking Status
firefox33 --- affected
firefox34 --- affected
firefox35 --- affected
firefox36 --- fixed
firefox-esr31 --- affected

People

(Reporter: jandem, Assigned: jandem)

References

(Blocks 1 open bug)

Details

(Keywords: perf, reproducible)

Attachments

(2 files)

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.
(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.
V8's slice implementation does not account for new properties added by getters...
Attached patch PatchSplinter Review
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.
Attachment #8510334 - Flags: review?(bhackett1024)
Attachment #8510334 - Flags: review?(bhackett1024) → review+
Depends on: 1088189
Blocks: 1088189
No longer depends on: 1088189
https://hg.mozilla.org/mozilla-central/rev/f4a77b74abc3
Status: ASSIGNED → RESOLVED
Closed: 10 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla36
Given the visibility of Google Inbox, we should consider backporting this to Aurora or even Beta.
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
(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.”
You need to log in before you can comment on or make changes to this bug.