Closed Bug 1174230 Opened 9 years ago Closed 9 years ago

Switch cases with many case statements are quite slow to compile

Categories

(Core :: JavaScript Engine: JIT, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla42
Tracking Status
firefox42 --- fixed

People

(Reporter: bbouvier, Assigned: bhackett1024)

Details

Attachments

(2 files, 1 obsolete file)

Attached file generate_switch.py
From https://github.com/kripken/emscripten/issues/3534#issuecomment-111521395 :

> So I decided to make an experiment to see how compilation time was behaving
> with respect to the number of "else if" or the number of "case" statements
> within a switch statement. Here are the results:
> 
> Time of compilation, in ms (switch (number of cases) / if (number of "else
> if"))
> 
> 1: 0 / 0
> 10: 0 / 0
> 100: 0 / 0
> 200: 2 / 4
> 400: 18 / 37
> 800: 218 / 240
> 1000: 510 / 761
> 1100: 656
> 1200: 952 / 1257
> 1300: 1340 / 1495
> 1400: 1647 / 1800
> 1500: 2507 / 2273
> 1600: 2999 / 2774
> 1700: 3383 / 5533 (!)
> 1800: 4567 / 4517
> 1900: 5378 / 6499 (!)
> 2000: 7126 / 6367
> 3000: 29057 / 29855
> 
> For instance, the line 1600: 2999 / 2774 reads as:
> 
> - for a switch statement with 1600 cases + default, compilation took 2999ms
> - for a chain of if/else with 1600 else if, compilation took 2774ms
> 
> That shows two things;
> 
> - choosing switch over else if chains (almost) doesn't impact compilation time
> - the more cases, the longer the compilation

This is not an error: compiling a switch statement with 3,000 (quite simple) cases takes around 30 seconds on my machine. We should investigate why it gets so slow.

Attached is the script I've used to generate the test cases.
Summary: Switch cases with many case statements are quite low to compile → Switch cases with many case statements are quite slow to compile
Attached patch improve if/else chain parsing (obsolete) — Splinter Review
This patch changes frontendy bits so that chains of if/else statements are parsed and emitted using constant stack space.  BytecodeEmitter already does this, but Parser and a few constant folding related traversals don't.  This also fixes a quadratic blowup when constant folding if/else chains.
Attachment #8622014 - Flags: review?(jorendorff)
Jeez, I'm sorry, this is the wrong bug.
Attachment #8622014 - Attachment is obsolete: true
Attachment #8622014 - Flags: review?(jorendorff)
This may be a regression. See the testcase in bug 1175349 - it used to build in 30 seconds in the shell for me, but now it takes over 6 minutes and I'm giving up.

I'll try to bisect.
Bisection found, and I verified, the testcase described in the previous comment regressed due to

The first bad revision is:
changeset:   244449:261cadb83015
user:        Brian Hackett <bhackett1024@gmail.com>
date:        Mon May 18 20:20:14 2015 -0600
summary:     Bug 1067610 - Refactor backtracking allocator to handle grouped registers better, r=sunfish.
Flags: needinfo?(bhackett1024)
Early on in register allocation we try to merge bundles for different vregs together, e.g. merging a phi with all its inputs.  This process can be quadratic in the number of vregs being merged, which isn't easy to avoid, so this patch just limits the number of ranges we will look at when merging vregs before giving up.  With this change, the 3000 switches compile for me in ~10ms, and the testcase in bug 1175349 compiles about one second.
Assignee: nobody → bhackett1024
Flags: needinfo?(bhackett1024)
Attachment #8628405 - Flags: review?(sunfish)
Attachment #8628405 - Flags: review?(sunfish) → review+
https://hg.mozilla.org/mozilla-central/rev/5ba726ba4024
Status: NEW → RESOLVED
Closed: 9 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla42
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Created:
Updated:
Size: