Closed Bug 704387 Opened 13 years ago Closed 12 years ago

Switch statements slower than If statements

Categories

(Core :: JavaScript Engine, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla12

People

(Reporter: azakai, Assigned: bhackett1024)

References

(Blocks 1 open bug)

Details

Attachments

(3 files)

Attached file 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.
Attached file if version
Jan, do you perhaps know what is going on here? I think I remember you saying something about this in another bug.
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.
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.
(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.
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.
Blocks: 670885
Handle switch and try blocks during SSA analysis.  With this change I get about the same time in the two versions of the benchmark.
Assignee: general → bhackett1024
Attachment #582829 - Flags: review?(dvander)
Attachment #582829 - Flags: review?(dvander) → review+
https://hg.mozilla.org/mozilla-central/rev/eaac85c4c05f
Status: NEW → RESOLVED
Closed: 12 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla12
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
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.
Depends on: 716255
(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
Depends on: 723099
Depends on: 714645
Depends on: 719758
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.
(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?
We have the source now.
Depends on: 751320
Depends on: 748044
No longer depends on: 751320
Depends on: 751320
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Created:
Updated:
Size: