Why C compilers optimize switch and if differently

user_4217072 0
Viewed 279

I was working on a personal project recently when I stumbled across an odd issue.

In a very tight loop I have an integer with a value between 0 and 15. I need to get -1 for values 0, 1, 8, and 9 and 1 for values 4, 5, 12, and 13.

I turned to godbolt to check a few options and was surprised that it seemed the compiler couldn't optimize a switch statement the same way as an if chain.

The link is here: https://godbolt.org/z/WYVBFl

The code is:

const int lookup[16] = {-1, -1, 0, 0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 0, 0};

int a(int num) {
    return lookup[num & 0xF];
}

int b(int num) {
    num &= 0xF;

    if (num == 0 || num == 1 || num == 8 || num == 9) 
        return -1;

    if (num == 4 || num == 5 || num == 12 || num == 13)
        return 1;

    return 0;
}

int c(int num) {
    num &= 0xF;
    switch (num) {
        case 0: case 1: case 8: case 9: 
            return -1;
        case 4: case 5: case 12: case 13:
            return 1;
        default:
            return 0;
    }
}

I would have thought that b and c would yield the same results, and I was hoping that I could read the bit-hacks to come up with an efficient implementation myself since my solution (the switch statement - in another form) was fairly slow.

Oddly, b compiled to bit-hacks while c was either pretty much un-optimized or reduced to a different case of a depending on target hardware.

Can anybody explain why there is this discrepancy? What is the 'correct' way to optimize this query?

EDIT:

Clarification

I want the switch solution to be the fastest, or a similarly "clean" solution. However when compiled with optimizations on my machine the if solution is significantly faster.

I wrote a quick program to demonstrate and TIO has the same results as I find locally: Try it online!

With static inline the lookup table speeds up a bit: Try it online!

disassembly bit-manipulation gcc optimization c
4 Answers

If you explicitely enumerate all the cases, gcc is very efficient :

int c(int num) {
    num &= 0xF;
    switch (num) {
        case 0: case 1: case 8: case 9: 
            return -1;
        case 4: case 5: case 12: case 13:
            return 1;
            case 2: case 3: case 6: case 7: case 10: case 11: case 14: case 15: 
        //default:
            return 0;
    }
}

is just compiled in a simple indexed branch :

c:
        and     edi, 15
        jmp     [QWORD PTR .L10[0+rdi*8]]
.L10:
        .quad   .L12
        .quad   .L12
        .quad   .L9
        .quad   .L9
        .quad   .L11
        .quad   .L11
        .quad   .L9
        .quad   .L9
        .quad   .L12
etc...

Note that if default: is uncommented, gcc turns back to its nested branch version.

user_108086740

C compilers have special cases for switch, because they expect programmers to understand the idiom of switch and exploit it.

Code like:

if (num == 0 || num == 1 || num == 8 || num == 9) 
    return -1;

if (num == 4 || num == 5 || num == 12 || num == 13)
    return 1;

would not pass review by competent C coders; three or four reviewers would simultaneously exclaim "this should be a switch!"

It's not worth it for C compilers to analyze the structure of if statements for conversion to a jump table. The conditions for that have to be just right, and the amount of variation that is possible in a bunch of if statements is astronomical. The analysis is both complicated and likely to come up negative (as in: "no, we can't convert these ifs to a switch").

user_12507720

The following code will compute your lookup branchfree, LUT-free, in ~3 clock cycles, ~4 useful instructions and ~13 bytes of highly-inline-able x86 machine code.

It depends on a 2's complement integer representation.

You must, however, ensure that the u32 and s32 typedefs really point to 32-bit unsigned and signed integer types. stdint.h types uint32_t and int32_t would have been suitable but I have no idea if the header is available to you.

const int lookup[16] = {-1, -1, 0, 0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 0, 0};

int a(int num) {
    return lookup[num & 0xF];
}


int d(int num){
    typedef unsigned int u32;
    typedef signed   int s32;

    // const int lookup[16]     = {-1, -1, 0, 0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 0, 0};
    // 2-bit signed 2's complement: 11 11 00 00 01 01 00 00 11 11 00 00 01 01 00 00
    // Hexadecimal:                   F     0     5     0     F     0     5     0
    const u32 K = 0xF050F050U;

    return (s32)(K<<(num+num)) >> 30;
}

int main(void){
    for(int i=0;i<16;i++){
        if(a(i) != d(i)){
            return !0;
        }
    }
    return 0;
}

See for yourself here: https://godbolt.org/z/AcJWWf

On the selection of the constant

Your lookup is for 16 very small constants between -1 and +1 inclusive. Each fits within 2 bits and there are 16 of them, which we may lay out as follows:

// const int lookup[16]     = {-1, -1, 0, 0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 0, 0};
// 2-bit signed 2's complement: 11 11 00 00 01 01 00 00 11 11 00 00 01 01 00 00
// Hexadecimal:                   F     0     5     0     F     0     5     0
u32 K = 0xF050F050U;

By placing them with index 0 nearest the most-significant bit, a single shift of 2*num will place the sign bit of your 2-bit number into the sign bit of the register. Shifting right the 2-bit number by 32-2=30 bits sign-extends it to a full int, completing the trick.

user_28090950

You can create the same effect using only arithmetic:

// produces : -1 -1 0 0 1 1 0 0 -1 -1 0 0 1 1 0 0 ...
int foo ( int x )
{
    return 1 - ( 3 & ( 0x46 >> ( x & 6 ) ) );
}

Even though, technically, this is still a (bitwise) lookup.

If the above seems too arcane, you can also do:

int foo ( int x )
{
    int const y = x & 6;
    return (y == 4) - !y;
}
user_35176220
Related