Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I've read in multiple answers that switch/case avoids "unnecessary" comparisons, but I never learned this in college, and I'm a little stumped on how the program would figure out which case to jump to without doing a comparison.

Obviously, in the case of int switchVar=3; switch (switchVar) { case 0: ... case 1: ... case 2: ... case 3: ... case n: ... }, this would be pretty easy, as it could just create an array of pointers that point to the beginning of each case's code block, and it would simply do something along the lines of instructionPointer = switchJumpTable[switchVar];.

However, this breaks down if you were to do a switch/case on a string, e.g. char switchVar[]="North"; instructionPointer = jumpTable[switchVar]; where trying to access the "North" index of an array would cause an error (or if the compiler allowed this behind the scenes, I still don't see how it would avoid comparisons when converting the char array into an integer in order to access the array.)

I can think of one way to get around unnecessary comparisons, but it wouldn't be terribly efficient, so I'm sorta curious as to how this is actually done, as I can't imagine that compilers are using the method that I have in mind.

share|improve this question
    
I'm pretty sure the whole reason switch statements were introduced in languages in the 70s was, if you wanted a jump table, that was a way to tell the compiler it could do it, assuming it could make the table. If not, it could just make an if-chain. Since jump tables are (were) so useful, there needed to be a way to tell the compiler it could try to make one. Otherwise the closest thing to it was computed goto in Fortran :( –  Mike Dunlavey Aug 6 '11 at 2:51
add comment

2 Answers

up vote 4 down vote accepted

The answer varies Enormously by the individual compiler, but there are a few strategies that "could" be used.

The usual answer is a jump table. The case variable is looked up in a table containing all of the allowed values, and the program jumps to the address the table specifies.

Of course, that's a fine strategy on the flat address models used in older CPU's, but the cost of an indirect branch on the deep pipelines of modern CPU's is often an order of magnitude greater than a simple conditional branch, (which is in turn more expensive than no branch). indirect branching usually breaks the branch prediction logic on most CPU's that have it, and so the instructions after the branch cannot be prefetched until the lookup instruction has actually completed. A regular conditional branch can prefetch one side of the branch and have a decent chance of 'guessing right'.

And so this optimization is rarely taken on compilers that target those CPU's, and instead the case statement is compiled as a tree of nested conditional branches.

share|improve this answer
    
When you say that a switch/case statement is "compiled as a tree of nested conditional branches," are you saying that the machine code produced is no different than if/else statements, and thus saying that the multiple people who claimed that switch/case is faster than if/else were mistaken? –  Michael Jul 28 '11 at 6:09
    
That's roughly what I'm getting at, but they aren't "neccisarily" mistaken, either. What's optimal will always be dependent on the specific application, the machine that it's running on, and the particular combination of inputs. For certain combinations of the three, almost any reasonable implementation might be optimial, but knowing which is optimal for a specific combination requires actual performance testing. –  TokenMacGuy Jul 28 '11 at 6:20
add comment

for string switches the compiler could create a trie to quickly check which case it needs to jump to

this is much faster (O(n) n is the length of the string) than a ifelse cascade (O(n*k) n is string length k is amount of if conditions)

share|improve this answer
    
Why do those stems have three leaves? Binary trees are faster, no? Should be letting the exponent do the work... –  Michael Jul 28 '11 at 15:57
    
@micheal actually all nodes will have 256 children; one for each character but most will point to the nil/default and binary tree search is O(n*log(k)) faster than ifelse cascade but still slower –  ratchet freak Jul 28 '11 at 16:02
    
Hmm, ok... I guess it is indeed faster since you know what stem to take... rather than comparing it to the current node and going left or right as you do in a binary tree, you can just do `if (currentNode.val==theString.charAt[i]) { return matchIndex; } else { currentNode = currentNode.takeStem(theString.charAt[++i]); }. This would avoid having to test the next character against each of the stems off the current node until you find a match... very cool! –  Michael Jul 28 '11 at 16:12
    
@micheal actually the I believe the trie code would be SwitchTableElem *table=init; while(str[i]){table=table[str[i++]]->ptr;} goto table[0]->instr; or similar (with SwitchTableElem having a pointer to a array with 256 other SwitchTableElem and an instruction pointer to the appropriate case) –  ratchet freak Jul 28 '11 at 16:30
    
Good point about the while(str[i])... no need to do an "==" comparison at all. –  Michael Jul 29 '11 at 0:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.