• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Selecting code without switch(...)

 
Ranch Hand
Posts: 750
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi, this is a strange problem, but its annoying me.
I want to run a certain piece of code depending on a value.
I can clearly do this with if...else if...else if...else statements,
or with a switch statement like below:

But since I am making chess program, I need code to run as fast as
possible.
If code 10 had to be run, then all the cases 1 to 9 have to be checked.
I think thats equivalent to 9 if statements.

I was trying to do something like this.
Create an array of 'chunks' of code, so that you could just call
array[7] and get the code for 7 is executed.

But I can't just put code in an array, that wouldn't make sense.
Is there any way around this, so I can avoid a big switch statement??

Thanks for any help

[Andrew: disabled smilies in this post]
[ July 08, 2006: Message edited by: Andrew Monkhouse ]
 
author and iconoclast
Posts: 24207
46
Mac OS X Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Define an interface "Handler", with a method "doIt()".

Write ten implementations of it, one for each case.

Make a HashMap, using Integers as the keys, and the Handler implementations as the values.

Instead of the switch, you write

((Handler) theMap.get(new Integer(x))).doIt();

Whether this is faster or not, it can be more elegant if the individual case statements are nontrivial.

Note, though, that a switch with contiguous indices is going to be compiled to a JVM "tableswitch" bytecode, which is going to look up the code to branch to using a binary search; it's already going to be far faster than the if-thens, although not necessarily as fast as the HashMap lookup.
 
colin shuker
Ranch Hand
Posts: 750
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks, but I only have 5 or 6 if statements in my switch block.
And I've found out using collections /Maps does slow things down.
I guess if I had a 1000 blocks of code, it would be better.

So does switch work faster than multiple if's?
That is worth knowing

Thanks for your help
[ July 08, 2006: Message edited by: colin shuker ]
 
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Since you're dealing with a very specific performance issue, I'm going to move this thread to the Performance forum. I would say that in general the switch statement is usually the last option to try, so I don't want the general readership to pick up the wrong message here (which is that for some high-performance applications, switch may be your best option).
 
Jim Yingst
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Following up some more:

Comparing the performance of these options depends on a number of variables, especially: how many choices are there, and are the numeric values of the coices close together, or widely spaced? Most statements about speed which we might make here can turn out to be false in some other circumstances. However, in general, for a large number of options, if/elseif is pretty bad. A hashmap is usually much better, but a switch statement can often be faster yet (especially if the options are closely-spaced). However the fastest option may be to use an array instead:

In some cases you can speed this further. If you are certain that this method is never called with an out-of-range value or a value for which h is null, you can skip those checks. This may well be the best option for you - I'd say it's worth a try.

Now if the number of choices is very small, the performance of a HashMap and the array solutions will probably remain exactly the same as above, but the if-else will get much better, maybe enough to justify using it. And the performance of the switch statement may improve, if the values are widely spaced. So for a very small number of choices, HashMap becomes the worst choice, and the other three are pretty close to each other. (Well, if/elseif doesn't become competitive until the nubmer of choices is two or maybe three.)

One minor advantage that the switch and (to a lesser extent) if/elseif have is that it's possible to in-line the method calls, manually or just letting the JVM do it. (I recommend the latter, as the JVM usually does a more reliable job.) In some situations this may be enough to make switch faster than an array.

With all of this, you really need to test the options yourself to find out for sure. And be aware that a different JVM on a different machine may give different results. However, for what you've described, I'm guessing best options are either a switch statement or an array.
 
author and jackaroo
Posts: 12200
280
Mac IntelliJ IDE Firefox Browser Oracle C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Just thought you might be interested in the bytecode that gets generated when you use if statements versus if you use case statements. For the classWe get:With i were set to 3, the if statement must first check that it is not equal to 1 and jump to line 14:It then repeats that logic when it checks that i is not equal to 2 and jumps to line 26:It can then do the real work (after verifying that i is equal to 3:Compare that with the switch statement, where a single instruction tells the java runtime what line it should execute next:So having decided that i is equal to 3, we know that the next line to be run will be line 78:It is interesting to compare how Java handled the switch statement at a low level compared with Jim's solution where he is using an array. Java seems to be doing a lookup (possibly in an array) to work out what line number to run next.

Based on that I would expect the switch statement to be faster than the if statement, and probably comparable to Jim's solution.

Regards, Andrew
 
Ranch Hand
Posts: 862
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
This seems like premature optimization. HashMaps are very very fast. I would guess to the tune of millions of calls to get per second. How many times are you expecting to call this code?
 
Jim Yingst
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
[steve]: This seems like premature optimization. HashMaps are very very fast. I would guess to the tune of millions of calls to get per second. How many times are you expecting to call this code?

He did say he's actually seen it execute more slowly with a Map here. And it's a chessplaying program, so it's not hard to imagine that there's a very tight loop in there somewhere. Though it does bear asking, Colin: was the slowdown observed as part of the overall execution of the program, or were you isolating the HashMap/switch performance on its own? If the latter, then yes it's still very possible that the performance difference you've observed will not actually matter in context.

[Andrew]: It is interesting to compare how Java handled the switch statement at a low level compared with Jim's solution where he is using an array. Java seems to be doing a lookup (possibly in an array) to work out what line number to run next.

Yup. Probably not, strictly speaking, a Java array, but same idea. If the case values are widely spaced, then a switch can also compile to a lookupswitch statement, which is likely to require log N time to execute as the instruction requires a binary search of the table.

You may also want to check out the JVM Spec on Compiling Switches, as well as the tableswitch and lookupswitch commands.

[Andrew]: Based on that I would expect the switch statement to be faster than the if statement, and probably comparable to Jim's solution.

Ah, but that seems to assume that each instruction takes the same amount of time to execute. That's not necessarily the case. Executing tableswitch may well take a bit longer than iload, iconst, if_icmpne. Hard to say exactly. I ran some tests comparing execution times; it seems that with just 2 or 3 brances, switch and if/else are virtually indistinguishable in time. At 4 branches if/else starts to take noticeably longer, and of course this gets worse as the number of branches increases.
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic