IF-ELSIF vs. SWITCH/CASE

[Kharybdis]

use case statements... they help.

[syntax_error]

Kharybdis wrote:

use case statements... they help.

case Vs. If no difference. imo.

[Vermette]

syntax_error @ 26/3/2008, 12:16 wrote:

Kharybdis wrote:

use case statements... they help.

case Vs. If no difference. imo.

I can't speak to Turing's performance capabilities in this case since it is interpreted (and I haven't used it in ~8yrs), but as a general rule where applicable switch/case is preferred as it is easier for a compiler to optimize the code. Multiple ifs demand multiple comparisons and jump points. switch/case is also more self-documenting than a block of matching if statements with a lot of code repetition.

[Tony]

Vermette @ Wed Mar 26, 2008 12:38 pm wrote:

... performance capabilities ... multiple comparisons and jump points ...

There's a comparison for each case, and a jump point for each break, same as if-elsif-else structure. I doubt any significant optimization gain, so I'd equate switch/case statements as syntactical sugar.

[Vermette]

Tony @ March 26th 2008, 13:19 wrote:

Vermette @ Wed Mar 26, 2008 12:38 pm wrote:

... performance capabilities ... multiple comparisons and jump points ...

There's a comparison for each case, and a jump point for each break, same as if-elsif-else structure. I doubt any significant optimization gain, so I'd equate switch/case statements as syntactical sugar.

I wouldn't necessarily believe that's true. During translation to assembly level code, a switch/case can be converted into a jump table, representing a series of unconditional jump statements offset from a base address. The machine code for this is much more efficient. Only a single comparison need be performed, and the break(if any) is simply another unconditional jump out of the relevant code section.

with a sequential list of if sequences however, multiple comparisons must be performed. Average case = worst case = best case, for x if statements, x conditions have to be tested. One way of lessening the number of conditions to test would be to nest the if statements like so:

code:

if(!condition1){    if(!condition2){       if(!condition3){          ...          perform default code       }       else perform condition 3 code    }    else perform condition 2 code } else perform condition 1 code

Obviously this is a coding style that could quickly be difficult to maintain. And in the worst case, every condition must still be tested. Sorry if I didn't really explain myself clearly on that. Maybe I'm still not explaining myself clearly. And this is probably all moot in an interpretive environment

[Tony]

I said

Tony @ Wed Mar 26, 2008 1:19 pm wrote:

same as if-elsif-else structure

The number of comparisons is the number of tries it takes until the first match, then control breaks out of the structure.

You still need to perform just as many comparisons to figure out the index of the jump-table.

And this has very little to do with "This is a first step to doing graphics in Turing."

[Vermette]

Yeah, I shouldn't be injecting a discussion about code optimization for C-style in an intro Turing thread. My bad.

[Tony]

*split into a new topic*

Carry on Vermette

[wtd]

Use whichever bit of syntax allows you to best express your intent. Avoid premature optimization. The compiler's probably better at it anyway.

[Vermette]

wtd @ March 26th 2008, 16:14 wrote:

Use whichever bit of syntax allows you to best express your intent. Avoid premature optimization. The compiler's probably better at it anyway.

Yeah. I'm always inclined to self-documenting code rather that tight optimized code. At least when I'm prototyping that is.

But I can see where you're coming from about sugar Tony. switch/case is just a specialized conditional statement. But I maintain that it is easier for a compiler to optimize a switch/case block than an if cascade. If your switch can be reduced to a jump table, we're talking O(1) versus O(n). And personally I find them to be easier to read. Plus in C there's cool things like Duff's Device

[Tony]

I guess I'm not quite understanding something about the jump tables. If I have a construct like

code:

switch(word){ case "a" : foo; case "b" : bar; ... case "n" : baz; }

How do you figure that word == "n" in O(1) time?

[Vermette]

From the wiki article on jump tables:

Quote:

A branch table consists of a serial list of unconditional branch instructions that is branched into using an offset created by multiplying a sequential index by the instruction length (the number of bytes in memory occupied by each branch instruction). It makes use of the fact that machine code instructions for branching have a fixed length and can be executed extremely efficiently by most hardware, and is most useful when dealing with raw data values that may be easily converted to sequential index values.

So when you have sequential cases, identifying the correct case is simply moving to *switch+word. In one instruction I can directly move to the appropriate unconditional jump instruction and run the necessary code. This is exactly how array addressing is performed in C (a[i] is sugar for *a+i). In the if/else cascade environment, I need to compare, jump if equal. This is slower than an unconditional jump which only takes a single clock cycle. Even after the correct code block is jumped to and executed, all those comparisons are still performed in a cascade. Nesting the conditions like I demonstrated above lowers the complexity of the average and best cases, but the worst case is still O(n) as every comparison is performed.

I'll grant that this kind of optimization isn't always possible, but when it can it can mean big performance savings.

[Tony]

yeah, but a list of sequential cases is such a specialized case... it's likely that you don't even need a control structure there, and could write a O(1) call as it is.

[OneOffDriveByPoster]

An interesting implementation of switch is to encode it in a binary search style.

[md]

Tony @ 2008-03-27, 10:38 am wrote:

I guess I'm not quite understanding something about the jump tables. If I have a construct like

code:

switch(word){ case "a" : foo; case "b" : bar; ... case "n" : baz; }

How do you figure that word == "n" in O(1) time?

In C/C++ at least this is not possible - as strings are not integer values and switch works on integers only.

code:

switch(letter) { case 'a' : foo(); break; case 'b' : bar(); break; ... default : zod(); }

Does work, and it's trivial to see how a table be constructed. For larger integer cases I imaging a switch() ends up being exactly as complex as an if/else if. Also, a switch() can be emulated with labels, goto, and an if/else if very easily