Hacker News new | past | comments | ask | show | jobs | submit login

I know that gcc and clang both have __builtin_expect(). If you tell the compiler the more likely path, wouldn't that make the branching version faster?

Actually, I've always wondered how __builtin_expect translates to something the CPU's branch prediction engine can use...

I think in general, most CPU architectures pick branch not taken for forward branches and branch taken for backwards branches on the first try. So I feel like builtin_expect gives weighting to let the compiler shuffle code around to make it fit that pattern.

There are ways of doing it in hardware, I remember a supervisor discussing it with respect to MIPS. I also remember them saying they went through the entire code generation stage of GCC and found that every single point at which GCC would try to use it was somewhere where it would be actively unhelpful.

__builtin_expect is good for error handling code, because gcc can avoid size-increasing optimizations in that path, and it can even move all the unlikely code out into another section so it won't take up space in your caches.

But its code generation is better for a 99%/1% case than a 60%/40% case, because Intel doesn't listen to branch hints anymore nor really give advice on how to tune for them.

On i386, CS and DS prefix bytes have no meaning but are valid for conditional jump instructions and are then used by some CPU's to provide hints to branch predictor.

As an example of another (arguably more sane) architecture, on Alpha, all branch instructions (including non-conditional ones) have bits reserved in their encoding for hints to branch predictor.

Branches can have prefixes x86 CPU can use as a hint. Modern x86 CPUs ignore these hints.

Applications are open for YC Winter 2021

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact