Branch Misses

How bad do branch misses hurt a programs performance? In C and Java?

for example how big of an impact would :


int shitinanus()
{
    int val = getanus();
    if(val != 0)
        return ANALTONIGHT;
    return ALONETONIGHT;
}

be knowing that val will most likely be 0 99% of the time compared to the below function


int shitinanus()
{
    int val = getanus();
    if(val == 0)
        return ALONETONIGHT;
    return ANALTONIGHT;
}

>>1
Theoretically, branching is prejudicial to performance in general, because it tends to force pipeline flushes or stalls. The predicting circuitry avoid great part of the penalty. Thus, a branch miss hits performance somewhat bad in the machine-level, but not as bad as a cache miss (except, evidently, if the branch miss also causes an instruction cache miss).

This means that you'll have visible performance differences in certain situations; for example, if you're branching dozens of thousands of times in a tight loop. Otherwise, it won't even contribute to the execution time noise; such latencies are typically in the nanosecond range. Also, depending on the final code layout, the static predictor always hits if certain conditions are met (for example, conditional backwards jumps are always seen as taken). In C, you can't decide the code layout, except by hinting the compiler with builtin directives (which he'll probably ignore anyway, since programmers are very bad at predicting bottlenecks).

Thus, "branch misses" are a concern far, far, far away from the average application code, specially in the kind of conditional you've suggested in the snippet. In Java (and probably every language which is not C), it's even more true: Java has an ocean of low-level overhead between source code and the final instruction stream, making any attempt of justifying some "optimized" construct look just plain ridiculous.

Also, x86 processors have an optimization circuitry called "loop stream detector" which is able to optimize very heavily the execution of small loops up to 16 bytes in code length. (Remember that a loop always have a conditional branch associated with it.)

Ultimately, people who're paranoid about such issues rarely understand anything about the subject. They typically have bad programming practices (like littering the code with __builtin_expect() directives), kludges data structures with "optimized" expressions, and overinline function calls, causing an even greater performance loss (due to the forementioned and imminent instruction cache miss caused by big thunks of linear code). People don't profile, because profiling makes you look uncool, since it always proves that all of "those highly and expertly optimized sites in your C code" is just girlyish bullshit.

IOW: don't waste energy "optimizing" branch sites in Java. In C, it'll make sense only in very specific scenarios, with which you'll probably never meet.