Thread: Branching vs array indexing

I was wondering... if I had many different functions that I wanted to call based on what the value of a variable would be, and the limits of that value where integral [0, N) , would the second method be much faster than the first?:

Code:

void proc1();
void proc2();
...
void procN();

1st:

Code:

switch (value)
{
    case 0:
        proc1();
    break;
    case 1:
        proc2();
    break;
    ...
    case N-1:
        procN();
    break;
}

2nd:

Code:

typedef void (*procedure)();

procedure procArray[N] = { proc1, proc2, ... , procN };
...
procArray[value]();

In the case of indexing though, what "guessing" rules would apply, if any?

Premature optimization.
The compiler may very well optimize a switch into a function table. Regardless, don't concern yourself about it. Let the compiler do its work, while you keep the code readable.

In my opinion indexing is more useful and I try to use it when I can. Indexing is an important operation to consider, especially if you want to speed up something nontrivial like random file access. Sometimes I just do it this way for the practice.

The compiler may very well optimize a switch into a function table. Regardless, don't concern yourself about it. Let the compiler do its work, while you keep the code readable.

That really sounds like you made it up. Surprise me.

Originally Posted by Elysia

Premature optimization.
The compiler may very well optimize a switch into a function table. Regardless, don't concern yourself about it. Let the compiler do its work, while you keep the code readable.

Second that. Even if you optimize it to save 1ms (a LOT of time in computing) per run, you would need a lot of runs to compensate for the one additional working day (28.800.000ms) your colleague needs to understand your program because you optimized it for speed. Optimize for readability while keeping it "fast enough" is probably more rewarding.

That said I think your second approach using a table would indeed be more readable as the number of functions increases. I would not want to read a 2000 line switch statement where I can never be sure if there isn't one case that is not just the single function call. So it's win-win. Probably faster, most likely more readable.

Thanks guys. I asked this because I've been building some old PC emulators( like Kenbak-1 ), and I thought I could use the opcodes as indices! It'd be nice if I managed to get it to run at approx 300 IPS( speaking about the Kenbak-1 ) with less than 5% of my CPU( Core2 Duo 2.4GHz ) .

Originally Posted by whiteflags

That really sounds like you made it up. Surprise me.

If this suffices for you...

Code:

#include <iostream>

void foo0() { std::cout << "I am foo0!\n"; }
void foo1() { std::cout << "I am foo1!\n"; }
void foo2() { std::cout << "I am foo2!\n"; }
void foo3() { std::cout << "I am foo3!\n"; }
void foo4() { std::cout << "I am foo4!\n"; }
void foo5() { std::cout << "I am foo5!\n"; }
void foo6() { std::cout << "I am foo6!\n"; }
void foo7() { std::cout << "I am foo7!\n"; }
void foo8() { std::cout << "I am foo8!\n"; }
void foo9() { std::cout << "I am foo9!\n"; }

int main(void)
{
	int n;
	std::cout << "Enter function to call: ";
	std::cin >> n;

	switch (n)
	{
		case 0: foo0(); break;
		case 1: foo1(); break;
		case 2: foo2(); break;
		case 3: foo3(); break;
		case 4: foo4(); break;
		case 5: foo5(); break;
		case 6: foo6(); break;
		case 7: foo7(); break;
		case 8: foo8(); break;
		case 9: foo9(); break;
	}
	
	return 0;
}

Looking at optimized assembly from VC++, we see:

Code:

switch (n)
003610FF  mov         eax,dword ptr [n]  
00361102  cmp         eax,9  
00361105  ja          $LN1+5 (361152h)  
00361107  jmp         dword ptr  (361159h)[eax*4]  
	{
		case 0: foo0(); break;
0036110E  call        foo0 (36101Bh)  
00361113  jmp         $LN1+5 (361152h)

Essentially, it jumps directly to the right position in the switch, then performs the call. If I enable inlining, it inlines the functions directly into the switch.
Not a direct function table call, but almost. But that's what I meant, if it isn't clear. The compiler can optimize the switch to essentially jump to the right position.
Dunno if a compiler is smart enough to understand that all cases essentially just call a function, though.

Originally Posted by whiteflags

That really sounds like you made it up. Surprise me.

Seriously? That's literally the textbook way of implementing switch statements.

map<"some kind of key", object> .... have the objects inherit from an abstract class which has a public void function like "execute()", then you can insert various objects in there that do different jobs, and fire them all off using the same command after you've looked up what you want (command pattern)

Maybe I just spoke craziness there. Don't know. I'm trying to translate java style OO with interfaces into "c++ style". Either way, I'm quite sure I can count on a good chastising if I am wrong on any count.