Hi, I've seen answers here for specific languages, about switches with more than 5 cases being optimized with jump tables to guarantee constant access time for any case.
Is that so for C / C++?
Is it in particular for gcc? for visual studio?
If not, would sorting cases in order of occurrence frequency help?
views:
335answers:
6
A:
This is what the compiler will do for you. In case of GCC it will use a jump table.
St3fan
2010-01-25 01:41:37
+7
A:
The standard doesn't guarantee anything about how the switch statement will be implemented. I've never seen a compiler produce a hash table, though quite a few will produce a jump table. Unless my memory is working even worse than usual, both VS and gcc can produce jump tables when the cases are sufficiently dense (for different values of "sufficiently"). Unfortunately, it's almost impossible to say (or necessarily even figure out) when sorting by frequency of occurrence will help -- it's different not only between compilers, but even between different versions of the same compiler.
Jerry Coffin
2010-01-25 01:43:31
Sorry, I meant jump tables.
Petruza
2010-01-25 15:04:44
@Pretruza: you could fix your original post
peterchen
2010-01-26 08:37:59
+2
A:
- C and C++ guarantee nothing about the running time of switch statements.
- I'm afraid I don't know the implementation details for any compiler. It probably depends on optimisation flags.
- Sorting cases isn't guaranteed to help, again it's not specified by the standard, and your implementation may or may not:
- Do different things according to compiler options
- Document what it does
- Guarantee not to change what it does in future versions
- Completely ignore the order of cases in the source, and re-order them however it likes. Assuming of course the cases are "independent": no fall-through; no variable declarations starting in one case and spanning another case; no anything else I've forgotten.
Steve Jessop
2010-01-25 01:45:27
A:
c (and by extension c++) only switches on integer types, so hashing is not necessary. The compiler will typically use an idiom appropriate to the architecture you're compiling for. This could be indexed addressing (if a small range is used), jump tables, or something entirely different.
dmckee
2010-01-25 01:45:37
Hashing isn't necessary, but occasionally it's possible to optimise a bunch of integer cases using a perfect hash as the index into a jump table - basically take a set of non-consecutive numbers and map them to a consecutive space faster than you could traverse a binary decision tree. Whether that's an optimisation any compiler-writer can be bothered with is another matter...
Steve Jessop
2010-01-25 01:49:29
@Steve: I'll take your word for it, but on the architectures that I have known enough assembly to even comment on (mostly pretty old these days) a jump table would uniformly be faster. Even a two level jump table to manage sparse targets over a large integer range.
dmckee
2010-01-25 01:52:55
The one exception I could image would be a perfect hash for a set of binary flags. I.e. if all "case values" are powers of 2.
MSalters
2010-01-25 12:34:13
Or suppose the cases are sequential multiples of 147. I would strongly expect the perfect hash "divide by 147" (and check remainder is 0), followed by a jump table, to be faster than any generic switch. But I also wouldn't expect a compiler to come up with that. There are lots of situations where a perfect hash would be fast, the difficulty is finding the hashing function that does it. And in C, enumerated types don't quite do what you want, so a perfect hash on the cases does need a check to catch other values.
Steve Jessop
2010-01-25 15:01:39
+2
A:
For gcc's implementation see:
http://old.nabble.com/optimization-of-switch-statements-on-i386-to15366926.html#a15367662
smt
2010-01-25 01:52:09
A:
A hash does not seem like an efficient way to implement a switch, because you will have extra cache misses due to the lookup.
Charles Eli Cheese
2010-01-25 08:09:24