OdinMonkey: better handle giant sparse table switches

RESOLVED FIXED in mozilla26

Status

()

Core
JavaScript Engine
RESOLVED FIXED
5 years ago
5 years ago

People

(Reporter: azakai, Assigned: bbouvier)

Tracking

unspecified
mozilla26
x86_64
Linux
Points:
---
Bug Flags:
in-testsuite +

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(5 attachments, 1 obsolete attachment)

(Reporter)

Description

5 years ago
Created attachment 793774 [details]
bad.js

Attached is a script with and without switches instead of if-else chains. With switches, it hangs OdinMonkey in the shell and in the browser (no slow script dialog).
(Reporter)

Comment 1

5 years ago
Created attachment 793775 [details]
good.js
(Reporter)

Comment 2

5 years ago
Created attachment 793788 [details]
reduced testcase
(Reporter)

Comment 3

5 years ago
Created attachment 793789 [details]
reduced-er still
(Reporter)

Comment 4

5 years ago
Seems to be O(n^2) in the span of case values. Span of 10,000 takes 1 second, 20,000 takes 4, 30,000 takes 9, etc...
Odin creates one block containing a 'goto' for each default case. The switch in PullInfo has a range >380k, and only a few cases handled, so the number of 'goto default' blocks rises to around 380k.

All the MIR algorithms go through each block then, which takes some time.
(Reporter)

Comment 6

5 years ago
Must be O(blocks^2) time in those MIR algorithms based on the measurements from before.

We can get emscripten to not emit switches with such large and sparse spans (already done), but given how easy it is to DOS the browser beyond the control of even a slow script dialog, perhaps switches in such cases should be turned into if-else chains? Or asm validation should fail?

I guess if asm compilation is done off thread this would be less painful though?

Comment 7

5 years ago
IIRC, each time we see this problem, we re-have the idea: let's just make ONE MBasicBlock to handle all the holes in the switch.  This ends up busting because the backend assumes that each case in the table is unique, so we shy away and reduce the max table size.  However, I bet with a bit of work we could fix Ion to allow this.

Updated

5 years ago
Summary: OdinMonkey hangs on compilation of script with switches → OdinMonkey: better handle giant sparse table switches
Assignee: general → bbouvier
Created attachment 795445 [details] [diff] [review]
WIP

This patch fixes this hanging by separating the notions of successors and cases.

Currently, each MTableSwitch's case is equivalent to a successor of the block containing the MTableSwitch (getCase(...) calls getSuccessor(...)). We can get rid of that by storing the successor's index corresponding to the case (which allows several cases to map a single successor). Also, when adding a new case, we can check that we're not adding a successor that was already present in the list. This way, we can reuse the default case for all non implemented cases in the MTableSwitch, which dramatically reduces the number of successors and the complexity of the MIR graph.

Luke, I implemented the search in the existing list of successors as a linear search, which is O(n^2) in the worst case if there are n total cases. It can be reduced to O(n) by using a hashmap but I felt it would cost too much in term of memory, as there is already a new vector storing the indexes. On the reduc-er test case, it takes 32ms to compile and on the non-reduced one, it takes less than 200ms (the function doesn't appear in the slow compiled list). What do you think?
Attachment #795445 - Flags: feedback?(luke)
Created attachment 796805 [details] [diff] [review]
proposed fix

This slightly changes the interface of MTableSwitch, replacing addCase(MBasicBlock) by two functions addSuccessor(MBasicBlock) -> int and addCase(int). Otherwise, the logic behind the patch is the same as the one above, with the advantage that we avoid the search.

Asking Marty for review as he volunteered on IRC \o/
Attachment #795445 - Attachment is obsolete: true
Attachment #795445 - Flags: feedback?(luke)
Attachment #796805 - Flags: review?(mrosenberg)
Attachment #796805 - Flags: review?(mrosenberg) → review+

Comment 10

5 years ago
OOC, what is the compile time of the testcase in comment 0?
(In reply to Luke Wagner [:luke] from comment #10)
> OOC, what is the compile time of the testcase in comment 0?

Without patch applied:
opt build: no idea
debug build: no idea
These take more than 5 minutes, even with the most reduced benchmark.

With patch applied:
opt build: total compilation time 31ms
debug build: total compilation time 1059ms; 1 functions compiled slowly: _malloc:9297:9 (735ms)

Comment 12

5 years ago
Nice!
https://hg.mozilla.org/mozilla-central/rev/cd4f0f51af69
Status: NEW → RESOLVED
Last Resolved: 5 years ago
Flags: in-testsuite+
Resolution: --- → FIXED
Target Milestone: --- → mozilla26
You need to log in before you can comment on or make changes to this bug.