   switch case statement vs table
  How good are the C++ and Java compilers  at optimizing switch case statements?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? Will the compiler generate an optimal table automatically? 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)? 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? I'm interested in this both for C++ and for Java.Thanks!   
  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.theTrollIf 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.   