Last Comment Bug 704387 - Switch statements slower than If statements
: Switch statements slower than If statements
Status: RESOLVED FIXED
:
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: unspecified
: All All
: -- normal (vote)
: mozilla12
Assigned To: Brian Hackett (:bhackett)
:
: Jason Orendorff [:jorendorff]
Mentors:
Depends on: 714645 716255 719758 723099 748044 751320
Blocks: 467263 670885
  Show dependency treegraph
 
Reported: 2011-11-21 18:30 PST by Alon Zakai (:azakai)
Modified: 2012-05-19 15:20 PDT (History)
12 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
switch version (38.74 KB, application/javascript)
2011-11-21 18:30 PST, Alon Zakai (:azakai)
no flags Details
if version (38.64 KB, text/plain)
2011-11-21 18:30 PST, Alon Zakai (:azakai)
no flags Details
patch (e6179f497b74) (14.53 KB, patch)
2011-12-19 07:56 PST, Brian Hackett (:bhackett)
dvander: review+
Details | Diff | Splinter Review

Description Alon Zakai (:azakai) 2011-11-21 18:30:26 PST
Created attachment 576061 [details]
switch version

Attached are two versions of the same benchmark. One uses a switch in the inner loop,

  switch(x) {
    case v1:
    case v2:
  }

another uses an if/if-else,

  if (x == v1) {
  } else if (x == v2) {
  }

In theory, it seems the if could be slower since it can end up comparing the same variable once to one value and later to another - but the fact that it is the same variable twice is not explicit - while the switch knows the crucial value in an explicit way. But, results are the opposite:

js -m -n iffy.js      1.353 seconds
js -m -n switchy.js   2.250 seconds

Perhaps the switch should not be much faster, but it seems odd it is much slower.
Comment 1 Alon Zakai (:azakai) 2011-11-21 18:30:53 PST
Created attachment 576062 [details]
if version
Comment 2 Alon Zakai (:azakai) 2011-11-21 18:36:58 PST
Jan, do you perhaps know what is going on here? I think I remember you saying something about this in another bug.
Comment 3 Brian Hackett (:bhackett) 2011-11-21 19:05:10 PST
The switch statements in the example are getting compiled as LOOKUPSWITCH opcodes, which get used when the switch'ed values are not integers or are integers in a relatively large range.  Compiling these efficiently would require doing a hashtable lookup in jitcode, which would be kind of tricky especially when dealing with string comparison.  Instead the lookup is always stubbed, and the stub call does a linear search (!) to find the target, so it does the same asymptotic amount of work as the 'if' version, except it will be slower than jitcode because it needs to do these comparisons in the VM.

Currently, switch will be faster than cascading 'if' when the lookup is on packed integers (either fully or just tightly packed, I'm not sure), when we compile in a computed goto.  There is another performance fault that needs to get fixed where the presence of the switch (or a catch/finally block) disables SSA and leads to less precise types and worse code.  This latter one does not seem to be the issue here, though.
Comment 4 Alon Zakai (:azakai) 2011-11-21 21:05:45 PST
I'm not sure what you mean by (fully/tightly) packed integers in this context? The variable in the switch is __label__, which is only assigned integer values in the range 1..10, and the values checked in the switch are 4 and 6. I changed it so that it is immediately assigned 0 (so it never has undefined as its value), and I replaced values so that the values in the switch are 0 and 1. These changes didn't have an effect on speed.

Is there a plan for not disabling SSA in switch? Seems like it could be a nice way to speed up compiled code, assuming the packed integer stuff works out.
Comment 5 Brian Hackett (:bhackett) 2011-11-22 09:49:56 PST
(In reply to Alon Zakai (:azakai) from comment #4)
> I'm not sure what you mean by (fully/tightly) packed integers in this
> context? The variable in the switch is __label__, which is only assigned
> integer values in the range 1..10, and the values checked in the switch are
> 4 and 6. I changed it so that it is immediately assigned 0 (so it never has
> undefined as its value), and I replaced values so that the values in the
> switch are 0 and 1. These changes didn't have an effect on speed.
> 
> Is there a plan for not disabling SSA in switch? Seems like it could be a
> nice way to speed up compiled code, assuming the packed integer stuff works
> out.

Oh, I was looking at the other switch statements in the program.  The one with labels 4 and 6 gets compiled as a tableswitch, but if the 6 changes to an 8 then it becomes a lookupswitch (in which case the labels are not packed tightly enough).  So the SSA issue is likely a problem here.  That definitely needs to get fixed (though I don't know the timeline), it will affect IonMonkey as well as JM.
Comment 6 Alon Zakai (:azakai) 2011-11-22 10:34:23 PST
Ah, sorry, I should have been clearer. The switch with 4 and 6, inside _main(), is the only important one (that's the inner loop). The other switches are negligible.
Comment 7 Brian Hackett (:bhackett) 2011-12-19 07:56:41 PST
Created attachment 582829 [details] [diff] [review]
patch (e6179f497b74)

Handle switch and try blocks during SSA analysis.  With this change I get about the same time in the two versions of the benchmark.
Comment 8 Brian Hackett (:bhackett) 2011-12-24 06:26:29 PST
https://hg.mozilla.org/integration/mozilla-inbound/rev/eaac85c4c05f
Comment 9 Phil Ringnalda (:philor) 2011-12-24 22:15:34 PST
https://hg.mozilla.org/mozilla-central/rev/eaac85c4c05f
Comment 10 Hannes Verschore [:h4writer] 2012-01-04 08:48:21 PST
I noticed a regression with this patch on jslinux (avg 20x in shell using the code in bug #670885)

Revision before this patch landed: 4b2c62d75dea
5.3315 s

Revision when this patch landed: eaac85c4c05f
5.468 s
Comment 11 Brian Hackett (:bhackett) 2012-01-04 09:19:19 PST
The extra analysis precision with this patch probably ended up increasing compilation time due to more recompilations being triggered.  This should be helped greatly by bug 706914.
Comment 12 Hannes Verschore [:h4writer] 2012-01-19 02:12:02 PST
(In reply to Brian Hackett (:bhackett) from comment #11)
> The extra analysis precision with this patch probably ended up increasing
> compilation time due to more recompilations being triggered.  This should be
> helped greatly by bug 706914.

Indeed the patch in bug 706914 improves performance of jslinux again. Even much higher then it was before this regression. Awesome! Now jslinux takes something like 4.6 s an increase in performance of 1.172x
Comment 13 Benoit Jacob [:bjacob] (mostly away) 2012-04-18 00:21:17 PDT
This patch ( http://hg.mozilla.org/mozilla-central/rev/eaac85c4c05f ) regressed a certain video game (not public yet, sorry). The regression is that some sprites intermittently disappear.
Comment 14 David Mandelin [:dmandelin] 2012-04-18 17:40:14 PDT
(In reply to Benoit Jacob [:bjacob] from comment #13)
> This patch ( http://hg.mozilla.org/mozilla-central/rev/eaac85c4c05f )
> regressed a certain video game (not public yet, sorry). The regression is
> that some sprites intermittently disappear.

Would you be able to show someone the test case privately?
Comment 15 Luke Wagner [:luke] 2012-04-18 18:00:59 PDT
We have the source now.

Note You need to log in before you can comment on or make changes to this bug.