switch case statement vs table

Modern GCC and MSVC compilers will use jump table if your values in switch statement are more or less dense. I believe for GCC limit is 5 cases. If you have 5 or less, then it will generate sequential if comparisons.

You can instruct GCC not to generate jump tables with "-fno-jump-tables" command line switch.

Also GCC will change switch statement to balanced binary search tree for large case of sparse values. Here's some info on this: http://gcc.gnu.org/ml/gcc/2009-04/msg00483.html

How good are the C++ and Java compilers at optimizing switch case statements?

About 43%. Towards green.



The question itself is wrong.

Something either works or it doesn't. If it doesn't work, change it, use different approach, until it works. Repeat.

Will the compiler generate an optimal table automatically?[/quote]Maybe. Depends on compiler and whether it's possible to prove that optimal solution exists and that it can be implemented in finite time.

Is there a limit to how much case statements there can be in the switch[/quote]Yes, storage is finite. Infinite tape only exists in theory, so every resource is always limited. The question is again: am I exceeding these limits?

do compilers always generate tables of function pointers to execute the case statements[/quote]Maybe. Depends on compiler.

or can they also generate simple lookup tables if all you do in the switch case statement is return values?[/quote]Maybe. Depends on compiler.

How intelligent are compilers nowadays? [/quote]They are not. Compilers transform code, sort of like search and replace, they lack any kind of intelligence.

I'm interested in this both for C++ and for Java.[/quote]Write the code. Compile. Benchmark.

Preemptive optimization is never a good idea.

After your code is working, profile it, if the statement is an issue then look at a way to optimize, until then, don't worry about.

theTroll

Preemptive optimization is never a good idea.

Why? Ive seen this posted over and over...but why?

Why waste time implementing something you KNOW will be too slow and you already know a better solution that will take 50% longer to code? When coding both the first, then the second will take even longer in the long run?

[quote name='TheTroll' timestamp='1301929653' post='4794228']
Preemptive optimization is never a good idea.

Why? Ive seen this posted over and over...but why?

Why waste time implementing something you KNOW will be too slow and you already know a better solution that will take 50% longer to code? When coding both the first, then the second will take even longer in the long run?
[/quote]
The situation you mention doesn't fit the case of being preemptive or premature so Troll's comment wouldn't apply.

This article provides some insight into premature optimization problems.

When I make this decision, it's always from a programming point of view (what's going to be easier to work with, change, debug in the future), not a performance one.

If I'm doing a real FSM (something with more than 4-5 states, or that uses transitions), function tables are much cleaner. If it's simpler (for example a Socket), I'll leave it as a switch.

EDIT: Oh, I see you're talking about a large switch that probably isn't modeling a state machine. I like function tables in this case still. But, if your case statements are simply calling functions, then break/return, it's generated jump table code for me in every case I've measured. (For example, a packet handler switching over 40 or so packet IDs generated a jump table rather than branches).

Why? Ive seen this posted over and over...but why?

Why waste time implementing something you KNOW will be too slow and you already know a better solution that will take 50% longer to code? When coding both the first, then the second will take even longer in the long run?

In that case, since we're talking about "transforming a large amount of values", Hadoop is best choice. Scale it up to 200 instances and it will be done in a day. Much better than waiting several months. Map/reduce is a natural fit for this type of problem. It will also scale up to 1000 instances and even more after then new version is released.

In other words: don't optimize prematurely. Also, no product ever failed for being too slow. None.

I greatly prefer lookup tables when possible. (i.e. lookups from a contiguous range of enum values are the major candidate here) The amount of code to do a lookup is trivial compared to just about any switch, and won't contain any branches (aside from any manual range checking asserts etc)

Preemptive optimization is never a good idea.

After your code is working, profile it, if the statement is an issue then look at a way to optimize, until then, don't worry about.

theTroll

If after you done with 100K LOC, complicated app design, then found the slow is due to the design, it's too late to optimize.

It's always good to keep optimization in mind at the very beginning, and optimize when it won't cost non-trivial development time.

Of course this really depends. At beginning we can definitely use bubble to sort z order then change it to better algorithm later. We don't need to spend one day to optimize the sort at the beginning.

If after you done with 100K LOC, complicated app design, then found the slow is due to the design, it's too late to optimize

To go back to the context of the OP, choosing between a switch statement and a manually written jump table is an implementation choice, not a design choice. So in this case it should be possible to write the readable way first (possibly switch) and optimise the implementation (possibly LUT) later.

Preemptive optimization is never a good idea.

People always come up with this statement in an inappropriate context. What it really refers to is avoiding the kind of ninja trickery that makes code hard to read and harder to maintain until you know that you need to use it. There's absolutely nothing wrong with writing good clean and efficient code first time around despite that.

After your code is working, profile it, if the statement is an issue then look at a way to optimize, until then, don't worry about.

And how do you know that the OP hasn't already done this, anyway?

I greatly prefer lookup tables when possible. (i.e. lookups from a contiguous range of enum values are the major candidate here) The amount of code to do a lookup is trivial compared to just about any switch, and won't contain any branches (aside from any manual range checking asserts etc)

A branch by any other name...

Lookup tables have fallen out of favor in recent years. They require memory access, which will likely be slow.

As for branching. Branching is not bad, it's fundamental to programming. The performance implications of a branch come from inability to decide which code will execute next. "if (something) go left else go right". CPU needs to fully execute 'something' to know which way to go. By using a table or a switch, this branch doesn't go away. CPU is still unable to decide which code to execute after jump.

To minimize impact of branching, CPUs have pipelines and branch prediction. They simply execute both paths and once they know the result to 'something', discard the wrong choice. In case of tables, they cannot do that. Not only the CPU can't recognize it's a table, even if it did, it cannot speculatively execute all possible outcomes. Tables discard branch prediction.


Switch statements are perfect for continuous register-sized values. Most compilers will generate a code jump table. 0: jmp value*4
4: foo
5: ret
8: bar
9 ret
12: baz
...It becomes an implicit lookup table, but without the memory access penalty. Depending on compiler, switch may translate to such table even for different sets of values. It doesn't eliminate the branching penalty.


But none of that matters. Code should be readable first, so the choice of table vs. switch vs. if statements should depend on use case.

And how do you know that the OP hasn't already done this, anyway?[/quote]
Because then this question would not have been posted.

If after you done with 100K LOC, complicated app design, then found the slow is due to the design, it's too late to optimize.

It's always good to keep optimization in mind at the very beginning, and optimize when it won't cost non-trivial development time.

Nope. Optimization is not the problem.


The project you developed was *too ambitious*.


Can you build a space rocket? Of course. Really - you can. If it gets finished, it will likely blow up. If it does get in the air, it will fall apart. Chances of actually reaching space are very low.

Yet nobody would ever say: The rocket wasn't optimized enough.


Never optimize - solve the problem. And learn how to recognize what you actually *know*, what you *don't know* and accept that 99% of the stuff is something you could never even dream of thinking about. Rather than learning tons of hackery for optimization (those will come anyway), learn how to recognize the scale of the project. And when you do not have hard numbers from actually completed past projects, just go with the flow. Any choice you make, no matter how informed it seems, will be pure luck. Most of the time it simply won't matter.


"But but, but, ...."

Since we all have limited time and experience, we cannot know everything. So instead, look what others have done. "Can I build a FPS engine with 1000 actors?" - go to google, seaarch for existing engines, see how many actors they have. If you find one, then it's doable. If not, why isn't there one? Is it impossible? If so, what is the highest number of actors? Why do all stop at 75? Why not 80? Then, go build something for 75, scale it to 80 and then 100. And by then you will have learned enough to be able to think beyond. Maybe the reason nobody goes to 1000 lies elsewhere and not in technical limitations.

Almost every problem that can be solved has been solved and is available in 5 different languages on github. Yet every single solution can still be pushed way beyond current state if needed. There is just very little actual need to do so, so nobody does it.

Engineering is not about banging your head against the wall to break it down with sheer force. No other engineering discipline does it and they have it much harder. They cannot google for construction techniques or simply take one from the internet. We can, so use this knowledge. Rather than trying to fight wind mills, take what others have done and improve from a known base state. Then it's no longer a question of "maybe it will be too slow" - you have a reference point.

As for Java:

There is actually a bytecode instruction called "tableswitch" (opcode "0xaa"), which effectively relieves the compiler of any optimizations of switch statements.

That makes perfect sense, since the only participant in the whole Java contraption knowing on what kind of machine the code will actually run on is the VM.

Consequently, it's the VM's job to optimize (or rather, its JIT), and not the compiler's (who btw could make some very bad decisions and effectively make things worse).

So, unless you compile directly to native code (e.g., when using GCJ), you shouldn't even bother. Just code it your way and rely on the JIT for the rest.

As for Java:

There is actually a bytecode instruction called "tableswitch" (opcode "0xaa"), which effectively relieves the compiler of any optimizations of switch statements.

Java also has a 64k per method limit. So huge switch statements can exceed that simply through number of symbols or operations. Hence it's important to know what the original "huge" number means.

Oh man the whole never optimize thing is getting a bit old.

You could argue design is optimization, like optimizing your own production of code. It's easy to waste time designing and the more time you spend the more chance of wasting time, especially since if you make changes your design and optimization both go out the window.

The truth is for both the answer is to the optimal amount of each, which is unknown except on the simplest projects.

And if you don't do any optimization to the end, yes you will fail. Or rather you will find out that you have failed much much sooner if you do a proof of concept early on, something the people of the billion dollar larraby flop probably wish they'd done before wasting all that money on hardware design, eh? You need to establish pretty quickly that you can reach your optimization goals. There's a case where one good programmer could have avoided a billion dollars of wasted money by not just assuming the optimization goals could be met later on.

It's not a big deal if you are making some web page because any idiot can manage that. So yes you can waste a lot of time trying to optimize, also and more important unless you really know what you are doing you can't optimize very well but that's not to say it's a waste of time. For some projects there's loops that could be aptly called makeFatMonies(), with an endless supply of money available just waiting for your program to grab it, the faster it is the more you grab. In those cases optimizing even a tiny bit means millions of dollars. Or on the other hand maybe you have this crazy expensive render farm you rent for 2000 dollars an hour 24 hours a day to crunch numbers for you. So you get 10% faster you save 200 bucks an hour, 24 hours a day.

So yeah, maybe people can give up this trope now it's old news and really played out.

How good are the C++ and Java compilers at optimizing switch case statements?

Better than you. You can measure execution time, runtime memory usage and compiled code size; technical speculation, such as these questions, is no substitute for data.

When transforming a large amount of possible values, into different values, where you could use a table, or a large switch case statement, which would give the most efficient result?
[/quote]
If this simple "transformation" is nothing more than figuring out the address of the answer and returning it, whatever is most compact in memory is likely to be be better. Are we talking about dense or sparse tables? How would you implement your lookup table in terms of memory layout?

Will the compiler generate an optimal table automatically?
[/quote]
Optimal, or at least very good, only with respect to other possible realizations of the same switch statement. Doing better than completely unrelated code (your own lookup table) cannot be a compiler's objective; you really need to try both approaches and measure.

Is there a limit to how much case statements there can be in the switch (I mean, a limit after which the compiler would generate hundreds of branch operations instead)?
[/quote]
It's none of your business. Either your specific switch statement, however the compiler renders it, is faster than your specific lookup table, or not. You can choose between the two solutions, possibly after benchmarking at runtime, and you can switch to a better compiler (including empirically better options for the same compiler).

Also, do compilers always generate tables of function pointers to execute the case statements, or can they also generate simple lookup tables if all you do in the switch case statement is return values? How intelligent are compilers nowadays?
[/quote]
It's highly plausible for a compiler to optimize a table of jumps to small blocks that return constants to a table of these blocks themselves, but it's the same wrong question again: you shouldn't care because there's nothing you can do to affect this behaviour except trying different compilers and compiler options.

When you recognise that a lookup table can easily be used, the resulting code is basically always going to be shorter than the equivalent switch statement, and is realistically never going to slower in speed than the switch statement.

Therefore, prefer lookup tables. 'nuf said.