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)
Core
JavaScript Engine: JIT
Tracking
()
RESOLVED
FIXED
mozilla42
Tracking | Status | |
---|---|---|
firefox42 | --- | fixed |
People
(Reporter: bbouvier, Assigned: bhackett1024)
Details
Attachments
(2 files, 1 obsolete file)
471 bytes,
text/x-python
|
Details | |
1.26 KB,
patch
|
sunfish
:
review+
|
Details | Diff | Splinter Review |
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.
Updated•9 years ago
|
Summary: Switch cases with many case statements are quite low to compile → Switch cases with many case statements are quite slow to compile
Assignee | ||
Comment 1•9 years ago
|
||
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)
Assignee | ||
Comment 2•9 years ago
|
||
Jeez, I'm sorry, this is the wrong bug.
Assignee | ||
Updated•9 years ago
|
Attachment #8622014 -
Attachment is obsolete: true
Attachment #8622014 -
Flags: review?(jorendorff)
Comment 3•9 years ago
|
||
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.
Comment 4•9 years ago
|
||
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)
Assignee | ||
Comment 5•9 years ago
|
||
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)
Updated•9 years ago
|
Attachment #8628405 -
Flags: review?(sunfish) → review+
Comment 7•9 years ago
|
||
https://hg.mozilla.org/mozilla-central/rev/5ba726ba4024
Status: NEW → RESOLVED
Closed: 9 years ago
status-firefox42:
--- → fixed
Resolution: --- → FIXED
Target Milestone: --- → mozilla42
You need to log in
before you can comment on or make changes to this bug.
Description
•