How are switches optimized

Dennis dkorpel at gmail.com
Sat Jun 2 12:56:05 UTC 2018


On Friday, 1 June 2018 at 21:18:25 UTC, IntegratedDimensions 
wrote:
> If one has a switch of N case then the last cost surely does 
> not cost N times the cost of the first, approximately?

It depends on the compiler and optimization level. In general, no 
optimization or just a handful of cases means it's as if you 
wrote a bunch of if-then-else statements. When there are many 
cases, a jump table is the go-to way to optimize it. But the 
compiler may do more clever transformations:

```
void smallCase();
void largeCase();
void defaultCase();

int switchfunc(int i)
{
     switch(i) {
         case 8: .. case 64:
             smallCase(); return 1;
         case 256: .. case 512:
             largeCase(); return 2;
         default:
             defaultCase(); return 3;
     }
}
```
Even though the front end expands the ranged cases to individual 
case statements, LDC with -O1 or higher will actually output code 
akin to this:

```
int switchfunc(int i) {
   if (cast(uint) (i - 256) >= 257) {
     if (cast(uint) (i - 8) > 56) {
       smallCase(); return 1;
     }
     defaultCase(); return 3;
   }
   largeCase(); return 2;
}
```
Notice how even though I put the 256-512 range second, LDC chose 
to check it first because it's a larger range than 8-64. Also 
notice the use of unsigned integer underflow to check whether an 
integer is in a certain range.

Something I like to do for text reading functions is this:

```
bool isOneOf(string str)(char chr) {
   switch (chr) {
     static foreach(c; str) {
       case c: return true;
     }
     default: return false;
   }
}

alias isHexadecimalDigit = isOneOf!"abcdefABCDEF0123456789";
```
This will efficiently check if a character is in a compile-time 
known character set using compile-time optimizations. While DMD 
makes a jumptable for this, LDC actually transforms it into this:
```
bool isHexadecimalDigit(char chr) {
   ubyte x = cast(ubyte) (chr - 48);
   if (x > 54) return false;
   return 
(0b1111110000000000000000000000000011111100000001111111111 >> x) 
& 1;
}

```
The cases can be encoded in a binary number that is shifted by 
the value of the character, so that the correct boolean return 
value (1 or 0) ends up as the least significant bit.
DMD uses the same trick if you write it in this way:
```
return (chr == 'a' || chr == 'b' || chr == 'c' || ...);
```

So the most common optimization is indexing in (jump) tables, but 
smart transformations are done too sometimes. By the way, a chain 
of if-then-else statements may also be optimized as if it was 
written in a switch statement.

If you want to see how the compiler optimizes your switch 
statement, check out run.dlang.io (DMD and LDC, press ASM button) 
or d.godbolt.org (DMD, LDC and GDC).


More information about the Digitalmars-d-learn mailing list