Can you use builtin_expect with switch statement

Question

I have a switch statement in some time-critical code. I was trying to optimize it with __builtin_expect, but it does not seem to be working. I'm wondering if anyone can tell me if I'm missing some detail, or if the compiler simply does not optimize for it. I have tried the following on my host machine:

int main() {
    volatile int v=0;
    long i = 0;

    for (i=0; i<1000000000L; i++) {
            switch(__builtin_expect(v, EXPT)) {
            case 7:
                    v=7;
                    break;
            default:
                    v=7;
                    break;
            }
    }
    return v;
}

Then I compile and run as follows:

~/code/builtinexpect> gcc bie.c -o bie -D EXPT=0 && time ./bie 

real    0m2.092s  
user    0m2.086s
sys     0m0.000s
~/code/builtinexpect> gcc bie.c -o bie -D EXPT=7 && time ./bie 

real    0m2.092s
user    0m2.086s
sys     0m0.000s

I am using GCC version 4.5.1.

Platto

How does the produced assembly code look like in both cases? – Bestow

Answer 1

GCC does not support this on any architecture I'm aware of. If you have a switch statement which strongly favors a particular case, your best recourse is to do an if ... else switch ... statement. This would result in the optimization you're looking for.

Anisometropia

GCC seems to have added support: <gcc.gnu.org/bugzilla/show_bug.cgi?id=59521#c20> – Longitudinal

Answer 2

Both case branches (and therefore all cases) do the same thing, so the compiler is free to replace the whole switch statement with v=7. Even if it doesn't (without optimization), would you expect any real difference in timing?

But more to the point, __builtin_expect evaluates as (v == EXPT), either (0) or (1), so case 7: will never be taken.

Girondist

He didn't use compiler optimizations, so the code should differ and may cause forced mispredictions, but nice catch about the boolean-ness! – Bestow

@Bestow - I like to think a branch-predictor would get it mostly right with a billion iterations:) – Girondist

I would hope for a decent __builtin_expect to be strong enough to force the HW not to. Those HW folks need to know their place :) – Bestow

Thanks for the replies. I shaved down the example to post here to only two case statements (though I had tried it with more, with differing side-effects, but got the same results). The real-life scenerio is run millions of times per second, and even a 1% improvement would be significant. – Platto

According to gcc documentation, "The return value is the value of exp, which should be an integral expression" (it says it expects exp == c, but does not say it returns the result of this)... I just tried it, and case 1 and 0 are never hit if I initialize to -1. – Platto