Hundreds of cases in a switch, optimization?

[Jean-Claude Arbaut]

Although the point David makes is valid, consider a swap function.
Wouldn't it be more readable to use a funtion to do the swapping than
write out the code for the same in a switch-case structure? Also,
consider functions where you rely on previous values of local variables
(static variables) such as sequence generators? Or recursive functions?
(I am thinking of fibonacci as an example in both cases). These
functions are usually small, but are better off as functions. If you
must expand, why not just inline them (though u are at the complier's
mercy here). And again if the switch is something like:
switch(x) {
case 1: f1(); break;
case 2: f2(); break;
case ...
}
then, i think, function pointers serve the purpose better. No
additional jump table look-ups,

You need at least one !

 

[forayer]

You need at least one !

Yes, you're right. In case of an array of function pointers, I'll be
explicitly maintaining a "jump table", right? But in that case, there
is no ambiguity as to whether a jump table is used or not.

forayer

 

[Jean-Claude Arbaut]

Yes, you're right. In case of an array of function pointers, I'll be
explicitly maintaining a "jump table", right? But in that case, there
is no ambiguity as to whether a jump table is used or not.

Yes. When you only call functions with your switch, an array of pointers
cannot be worse, and when you only "do some things" in your switch, it's
better not to use an array of pointers *if* the switch is correctly
optimized.

 

[Christian Bau]

Yes. When you only call functions with your switch, an array of pointers
cannot be worse, and when you only "do some things" in your switch, it's
better not to use an array of pointers *if* the switch is correctly
optimized.

An array of pointers can be worse. Functions calls in a switch case
could be inlined, function pointers are much harder to inline. All the
functions must have the same interface, otherwise there is more trouble.
Function calls through a function pointer could be less efficient than
direct function calls.

 

[Jean-Claude Arbaut]

An array of pointers can be worse. Functions calls in a switch case
could be inlined, function pointers are much harder to inline.

I forgot that point. But even if they are inlined, you need to read a value
in the "jump table" and jump there. Actually it's a call, but sometimes it
can be replaced with a jump: if the switch is the last statement, in some
cases a jump to the new function suffices (the return from that function
will return to the caller of the switch function). It's exactly the same
behaviour with an array of pointers: you read, then call (or jump if
enough). I don't see how inlined functions may help. And when the optimal
switch consists in a test chain, then it's already better than the array of
pointers (otherwise the switch would have been optimized another way).
Actually, there is no true inlining possible: the switch will always jump at
some point, so instead of a jump+call when the switch is not optimized, you
avoid the call and the jump remains. With an array of pointers there is only
a call. Not much difference.

All the functions must have the same interface, otherwise there is more

trouble.

When doing a switch, not necessary, but very likely to be better optimized.
When using an array of pointers, I don't see how it would be possible to
have different interfaces.

Function calls through a function pointer could be less efficient than
direct function calls.

You only need to load a value, if it's loaded long enough before the call,
the indirect call may be almost as fast as if it were a direct call (not
taking the load into account). But in the context of the switch, that does
make sense only if there are few cases: then the test chain is optimal, and
calls can be direct. If there are more cases, the switch uses a jump table,
so the call is necessarily indirect.

 

[Christian Bau]

You only need to load a value, if it's loaded long enough before the call,
the indirect call may be almost as fast as if it were a direct call (not
taking the load into account). But in the context of the switch, that does
make sense only if there are few cases: then the test chain is optimal, and
calls can be direct. If there are more cases, the switch uses a jump table,
so the call is necessarily indirect.

Have you ever seen a PowerPC/CFMG implementation of an indirect function
call? It's fun. (CFMG is the Code Fragment Manager, used on MacOS 9 and
to some extent on MacOS X).