🔒 Locked

Switch or If statements for speed? (c++)

Started by pinkMayhem Dec 16, 2005 at 8:42 AM 24 replies 7.9k views

Original Post

Dec 16, 2005 at 8:42 AM

When c++ code is compiled, is there any big differance in the binary output of switch or if? I remeber someone saying something fuzzy about switches made the code a bit slower, is this true? If so, how big is the differance? (Not that i'll need it now, but who knows) cheers!

Skeleton_V@T

Dec 16, 2005 at 8:48 AM

I personally won't care about the minor difference (if any) between switch and if statements. What I care is which one of them will be faster/easier to write/maintain in a particular circumstance.

If you're really curious, just take a look at the assembly generated code, switch implements a jump table while if implements series of jump instructions.

Generally, for code segment requires 3 or more branches, I'll use switch, otherwise if is prefered.
(in the case we can use switch and if interchangeable)

pinkMayhem

Dec 16, 2005 at 8:51 AM

Ah okay, thanks =), if thats the case then i guess its not such a big differance after all ;), switches looks way better =)

SiCrane

Dec 16, 2005 at 8:51 AM

Quote:
Original post by Skeleton_V@T
If you're really curious, just take a look at the assembly generated code, switch implements a jump table while if implements series of jump instructions.

Not all switch statements will be jump tabled. Some will compile to the same code as the equivalent mass of if statements and some will be compiled to a binary search, depending on the compiler.

Xai

Dec 16, 2005 at 8:59 AM

The normal rules is that switches USED TO BE faster in many special cases (not slower), because compilers knew how to build jump tables out of switchs (a compiler optimization). I have never heard of switch being considered slower (although of course all constructs have some cases that are better than others).

I would expect that most modern compilers can see the same kinds of jump table patterns in if/else sytems as switchs (but I might be wrong).

Skeleton_V@T

Dec 16, 2005 at 9:07 AM

Quote:
Original post by SiCrane
Not all switch statements will be jump tabled. Some will compile to the same code as the equivalent mass of if statements and some will be compiled to a binary search, depending on the compiler.

I wonder when will binary search be faster than a jump table ?. Honestly I haven't used a lot of C++ compilers (tried GCC and sticked with VC).

SiCrane

Dec 16, 2005 at 9:11 AM

When you have relatively sparse non-contiguous case values over a large range. Try switching on 1, 2, 5, 10, 11, 100, 456, 457, 1000, 10000, 10001, 2000000, 2000002, 2000004, 10000000, 10200000. I guarantee you that the compiler won't jump table that.

Skeleton_V@T

Dec 16, 2005 at 9:13 AM

Doh!. Thank both of you[smile].

doynax

Dec 16, 2005 at 9:45 AM

Are there any compilers out there that can generate (gperf-style) hash tables?
I couldn't get MSVC to do it at least..

Extrarius

Dec 16, 2005 at 10:58 AM

Quote:
Original post by doynax
Are there any compilers out there that can generate (gperf-style) hash tables?
I couldn't get MSVC to do it at least..

In order for a hash table to be valid, the compiler would have to have be able to generate a perfect hash function that is never wrong, which could be exceedingly difficult (or require excessively large hash tables) since all values not in a 'case' statement must either go to 'default' or the end of the switch. Did you try using the __assume intrinsic in MSVC to tell it the default will never be called? Just make sure it's true =-)

doynax

Dec 16, 2005 at 11:17 AM

Quote:
Original post by Extrarius
Quote:
Original post by doynax
Are there any compilers out there that can generate (gperf-style) hash tables?
I couldn't get MSVC to do it at least..
In order for a hash table to be valid, the compiler would have to have be able to generate a perfect hash function that is never wrong, which could be exceedingly difficult (or require excessively large hash tables) since all values not in a 'case' statement must either go to 'default' or the end of the switch.

Well, it wouldn't always work but it should be "good enough" anyway. And you could still live with a few collisions if necessary.
It works pretty well for gperf after all..

Quote:
Original post by Extrarius
Did you try using the __assume intrinsic in MSVC to tell it the default will never be called? Just make sure it's true =-)

No, but even without it the compiler should be able to reduce the tree to two conditional jumps.

I just tried the following but it still didn't make much of a difference:

bool default_executed = false;switch(..) { default:  default_executed = true;}__assume(!default_executed);

The test wasn't very exhaustive or scientific however, so I might have missed something.

SiCrane

Dec 16, 2005 at 11:19 AM

__assume generally only works to apply program transformations to code that occurs after the __assume.

doynax

Dec 16, 2005 at 11:22 AM

Quote:
Original post by SiCrane
__assume generally only works to apply program transformations to code that occurs after the __assume.

Oh, that's good to know. Any suggestions on how to inform the compiler that the default case won't occur?
I doubt checking every condition in an initial assume would be a good idea, at the very least it's a maintenance nightmare (without a fair bit of macro hacking at least).

Extrarius

Dec 16, 2005 at 11:25 AM

Quote:
Original post by doynax
Quote:
Original post by SiCrane
__assume generally only works to apply program transformations to code that occurs after the __assume.
Oh, that's good to know. Any suggestions on how to inform the compiler that the default case won't occur?[...]

The example in MSDN seems to indicate that "__assume(0)" is used to tell the compiler that execution cannot reach a specific point (makes sense, since 0 is never true) and even uses a switch as the example:

void func1(int i){}int main(int p){   switch(p){      case 1:         func1(1);         break;      case 2:         func1(-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.   }}

Nitage

Dec 16, 2005 at 11:27 AM

Quote:
From MSDN:
The use of assume(0) tells the optimizer that the default case cannot be reached. As a result, the compiler does not generate code to test whether p has a value not represented in a case statement. Note that assume(0) must be the first statement in the body of the default case for this to work.

Nitage

Dec 16, 2005 at 11:28 AM

Quote:
Original post by Nitage
Quote:
From MSDN:
The use of assume(0) tells the optimizer that the default case cannot be reached. As a result, the compiler does not generate code to test whether p has a value not represented in a case statement. Note that assume(0) must be the first statement in the body of the default case for this to work.

EDIT: I always get beaten :(

EDIT: I also often press the quote button instead of the edit button

doynax

Dec 16, 2005 at 11:42 AM

Quote:
Original post by Extrarius
The example in MSDN seems to indicate that "__assume(0)" is used to tell the compiler that execution cannot reach a specific point (makes sense, since 0 is never true) and even uses a switch as the example:*** Source Snippet Removed ***

Thanks, that does seem reasonable.

I played around a bit with the test to try to make things easier for the compiler. And it's doing some kind of math to combine a few of the cases but it's still based on dozens of conditional branches.

Here's my test code BTW. Feel free to suggest improvements or try it on something a bit more modern than VC6.

void hash_switch(unsigned id) {	unsigned result;	switch(id) {#		define _(id) case id: result = __LINE__; break;		_(0x8d67b181)		_(0x0bea2236)		_(0x6d513acf)		_(0x6921a8eb)		_(0x274800fd)		_(0x04fa3d8e)		_(0xf51663bc)		_(0xd2e538e6)		_(0x16a765cb)		_(0xed1fa2aa)		_(0x4f2946ff)		_(0xd9919888)		_(0xfa80c7d9)		_(0x099bf713)		_(0x5c9657de)		_(0xbbfa7417)		_(0xf8f2cb97)		_(0x853dd887)		_(0x817b1e87)		_(0xddf52333)		_(0x04ece725)		_(0x17f701c6)		_(0xce06d7f1)		_(0xba08b708)		_(0x73cc6ed9)		_(0x09611d78)		_(0xb3e083ac)		_(0xc4cf4807)		_(0xa88024c4)		_(0x1421b619)		_(0x1f9b6c2d)		_(0xb434b717)		_(0x96aa034a)		_(0xa070e4aa)		_(0xd18b645b)		_(0x135526af)		_(0x65b7e901)		_(0x80299437)		_(0x433c484b)		_(0x355a3517)		_(0x83892fb4)		_(0xf8d35e99)		_(0xffaa813c)		_(0x853e3d7c)		_(0x00f09b10)		_(0x59f4c409)		_(0xa90bc526)		_(0x87ce2442)		_(0x91ea244a)		_(0x45895940)		_(0x2e3bcc5d)		_(0x9c113d8f)		_(0x753f5418)		_(0xc122d270)		_(0x2a3ddee1)		_(0xd4c3057b)		_(0x18609165)		_(0x27f19098)		_(0x00ca9c71)		_(0xc6021c29)		_(0xa6525186)		_(0x608b57ef)		_(0x9b065899)		_(0xee89d4a0)		default: __assume(0); break;	}	printf("%d", result);}

I got the numbers from random.org BTW.

Extrarius

Dec 16, 2005 at 1:37 PM

The problem is that you're asking it to compress essentially random data. Sure, gperf can create a hash table, but consider how much extra space it is using: With the switch, you're probably storing each one as a 32 bit(4-byte) int that is part of an instruction (or smaller), while gperf is storing up to 9 bytes (8 hex digits + NUL) but actually much more (for the character lookup table and also for empty table entries, plus each item in the list is actually stored as a pointer to the string so that is 4 more bytes on a 32-bit machine, plus each time you want to look up a number you must convert it to a string first which probably takes more time by itself than the whole binary search 'switch' probably does.

doynax

Dec 16, 2005 at 1:57 PM

Quote:
Original post by Extrarius
The problem is that you're asking it to compress essentially random data. Sure, gperf can create a hash table, but consider how much extra space it is using: With the switch, you're probably storing each one as a 32 bit(4-byte) int that is part of an instruction (or smaller), while gperf is storing up to 9 bytes (8 hex digits + NUL) but actually much more (for the character lookup table and also for empty table entries, plus each item in the list is actually stored as a pointer to the string so that is 4 more bytes on a 32-bit machine, plus each time you want to look up a number you must convert it to a string first which probably takes more time by itself than the whole binary search 'switch' probably does.

I didn't suggest actually using gperf, just applying the same techniques. Developing a "perfect" hasing function for integers should be significantly easier anyway. The result should essentially be a small array of function pointers (slightly larger than the number of cases in the switch) and integer keys (unless you've used an __assume(0) trick to eliminate the default case), a trivial hashing algorithm and conditional jump into the table.

In the best case my (somewhat contrived) test code above would expand to something like this:

void hash_switch(unsigned id) { static const unsigned hash_tab[32] = { ... }; // some hashing function id *= 17; id ^= 131; id &= 31; printf("%d", hash_tab[id]);}

Besides, the amount of other overhead in MSVC's binary search + bithack output dwarfs even a string table anyway.

Really, I see no reason why compilers shouldn't be able to perform this kind of optimization. It could potentially save get rid of a huge number of conditional branches, at the expense of some code generation overhead.

Extrarius

Dec 16, 2005 at 2:31 PM

The problem with integers is that many many many more operations make sense than do on strings, so while it might be somewhat easy to make _A_ hash function, it probably isn't at all easy to make an efficient one, much less a near-optimal one. I think you effectively have the currently-undecidable lambda equivalence problem (combined with a need to essentially compress random data within the very rigid constraint that the result includes the decompressor).

Also, there wasn't a lot of overhead for the switch function on VS2003 after I turned on all optimzations(not ideal by any means, but I'm guessing far far better than VS 6). With the default code generated by gpref (using "-m 10000 -L ANSI-C -C"), the initialization code for the word_array table (stored on the stack because it was a local) was longer than the whole assembly for the switch tree. After adding "-G", it changed the table to reside in read-only pre-initialized memory, which greatly reduced it's overhead but I'm still nearly certain (very difficult to properly test, and I'm not that interested) certain that the hash version would be slower because of the string conversion required (unless you make a thread unsafe wrapper that uses a single static buffer for the conversion, you'll be constantly allocating either from the stack or worse, the heap).

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.