• Advertisement
Sign in to follow this  

Switch speed

This topic is 4312 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi As part of a function which is executed very many times I have a switch statement that will act based on the closed set of inputs S. S={0,1,2,3,4}; I know that the default can never be reached. Is there anything I can do to speed execution without writing jump tables myself? Is there any intrinsic or anything to tell the compiler that it can't happen? cheers

Share this post


Link to post
Share on other sites
Advertisement
I doubt you could improve on the efficieny of a compiler interpreting a switch statement without writing assembly, and even then it would be going some.

Why would a default case affect the speed?

Share this post


Link to post
Share on other sites
Quote:
Original post by lincsimp
Hi
As part of a function which is executed very many times I have a switch statement that will act based on the closed set of inputs S.

S={0,1,2,3,4};

I know that the default can never be reached. Is there anything I can do to speed execution without writing jump tables myself? Is there any intrinsic or anything to tell the compiler that it can't happen?
Just don't include a "default" clause.

Share this post


Link to post
Share on other sites
If you know the relative probabilities of the cases in advance, you could arrange them so that the most probable ones are handled early in the statement. However, this is micro-optimization and it will most likely not affect your application's performance noticeably - thus, you'd just do extra work and gain effectively nothing.

Share this post


Link to post
Share on other sites
If the switch statement is decently compiled, the order of the cases shouldn't affect the speed. To my understanding, this is why you can only switch on integral types, so a jump table can be created that can be accessed in linear time.

Share this post


Link to post
Share on other sites
Quote:
Original post by Nik02
If you know the relative probabilities of the cases in advance, you could arrange them so that the most probable ones are handled early in the statement. However, this is micro-optimization and it will most likely not affect your application's performance noticeably - thus, you'd just do extra work and gain effectively nothing.

Your compiler can [and in the case of VC++, will] reorder case statements at will. So you won't gain effectively nothing, you will gain actually nothing.

CM

Share this post


Link to post
Share on other sites
Quote:
Original post by EasilyConfused
If the switch statement is decently compiled, the order of the cases shouldn't affect the speed. To my understanding, this is why you can only switch on integral types, so a jump table can be created that can be accessed in linear time.

Only if the cases are sequential, ie. { 1, 2, 3, 4, 5 }, rather then just any old numbers.

Actually, a compiler could probably hack any old switch statement into a jump table if it was so inclined, but that's another story [grin]

Share this post


Link to post
Share on other sites
Quote:
Original post by lincsimp
Is there anything I can do to speed execution without writing jump tables myself? Is there any intrinsic or anything to tell the compiler that it can't happen?

Use profile guided compilation, that is what it is good for.

Share this post


Link to post
Share on other sites
Switch(){} statements over high-range types (anything except enum and bool) resolve into conditional binary search trees (hence the arbitrary reordering of your case statements - not quite arbitrary), even if the number of cases is as low as you have.

Given that it is impossible for the value of the input to fall outside the range, you should convert it to an enum. Switch(){} over an enumerator resolves into a jump table, which is much faster (especially on intel chips) than any conditional search.

This came up when I was reviewing the generated code for my particle engine. I found that the tight inner loops ran best with switch(enum){}.

Share this post


Link to post
Share on other sites
Quote:
Original post by Symphonic
... resolves into a jump table, which is much faster (especially on intel chips) than any conditional search.

Ok, now I'm curious. Why are Intel chips particularly good at jump tables?

Share this post


Link to post
Share on other sites
Microsoft actually specifies how to do this for their compilers. Which makes me wonder if they wouldn't normally be able to take advantage of a default case that is never reached, without being explicitly told to do so. Anyway, the relevant link is here.
Quote:
void gloo(int p)
{
switch(p){
case 1:
blah(1);
break;
case 2:
blah(-1);
break;
default:
__assume(0);
// This tells the optimizer that the default
// cannot be reached. As so it does not have to generate
// the extra code to check that 'p' has a value
// not represented by a case arm. This makes the switch
// run faster.
}
}

Share this post


Link to post
Share on other sites
Quote:
Original post by Spoonbender
Quote:
Original post by Symphonic
... resolves into a jump table, which is much faster (especially on intel chips) than any conditional search.

Ok, now I'm curious. Why are Intel chips particularly good at jump tables?


With the i486 or i386 they introduced a double-indirect memory addressing mode that works with most instructions. It speeds up things like jump tables since all the location decode logic is pieplined in microcode, this also reduces the overhead of member function invokation. It's only a few CPU cycles in savings, but its across the board.

Share this post


Link to post
Share on other sites
Quote:
Original post by SirLuthor
Only if the cases are sequential, ie. { 1, 2, 3, 4, 5 }, rather then just any old numbers.


There may be gaps, as long as the gaps are short enough that the compiler's heuristics decide that jump tabling1 is still worth it.

Quote:
Actually, a compiler could probably hack any old switch statement into a jump table if it was so inclined, but that's another story [grin]


Well, should it decide not to jump table the switch, it will extremely probably turn it into a binary search instead - still plenty fast with O(lg n) complexity.

--
1 Verbing nouns is fun, isn't it?

[Edited by - Sharlin on April 5, 2006 4:37:35 PM]

Share this post


Link to post
Share on other sites
You can make a jump table using a wide range: you just need to calculate a perfect hashing function (which you can do at compile time, because the case values are all constants), build the table using the hashed values, and add guard code to each case (in case of collision between a "default" value and a real one. Or as the guy puts it (though I figured this out on my own):

Quote:

Switch statements could be compiled as a perfect hash (perfect -hp < hex.txt), followed by a jump into a spring table by hash value, followed by a test of the case (since non-case values could have the same hash as a case value). That would be faster than the binary tree of branches currently used by gcc and the Solaris compiler.


But yeah. Unless you're the guy writing the compiler, you really have no excuse for thinking about it at all. And even then, there need to be a LOT of cases in any given switch statement for basically any optimization to matter. Go to work on the code for each case instead.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement