908001 - OdinMonkey: better handle giant sparse table switches

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Alon Zakai (:azakai)]

Attachment: 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).

Comment 1

[Alon Zakai (:azakai)]

Attachment: good.js

Comment 2

[Alon Zakai (:azakai)]

Attachment: reduced testcase

Comment 3

[Alon Zakai (:azakai)]

Attachment: reduced-er still

Comment 4

[Alon Zakai (:azakai)]

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...

Comment 5

[Benjamin Bouvier [:bbouvier] (inactive)]

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.

Comment 6

[Alon Zakai (:azakai)]

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

[Luke Wagner [:luke]]

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.

Comment 8

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: 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?

Comment 9

[Benjamin Bouvier [:bbouvier] (inactive)]

Attachment: 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/

Comment 10

[Luke Wagner [:luke]]

OOC, what is the compile time of the testcase in comment 0?

Comment 11

[Benjamin Bouvier [:bbouvier] (inactive)]

(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

[Luke Wagner [:luke]]

Nice!

Comment 13

[Benjamin Bouvier [:bbouvier] (inactive)]

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

Comment 14

[Ryan VanderMeulen [:RyanVM]]

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