Hacker News Reader

Comment by brainburn | Hacker News Reader

Are there architectures where a programmer can just use a specific opcode to inform the cpu what's most likely?

There were some. At at least some points. However they cannot generally be used and I do not think they are included in current CPUs. You can however do hints to GCC and GCC should convert them to the opcodes if they exist. You do this by using "__builtin_expect".

Yes, the Pentium 4 had such instructions; but it turns out it they are mostly useless as a modern dynamic branch predictor can a) quickly learn any branch and adapt quickly b) use simple metaheuristics like a loop detector or BTFN(backwards taken forward not taken) essentially backward paths are more likely to be taken c) adaptively change the branch prediction based on the status of previous branching

any static prediction will do worse in case A on any branch which changes and will do much worse in C case while always doing worse in the B case if the branch occurs in a loop. It doesn't matter how 'smart' the static predictions are and whether they come from some guided optimization or otherwise; static predictions are worse in the vast majority of cases.

So when he talks about how he is going to build branch prediction into the ISA and load it asynchronously from memory this simply isn't going to improve performance. I might also point out that the claim that context switching hurts branch prediction performance results from the changed behavior of the branches in a new context and not from the processor not being able to reuse old predictions.

I think the Mill design isn't feasible and this is a good example of one problem: a massive new hardware investment of a cpu unit that caches and manipulates predictions in main memory while adding complexity to the internal pipeline that ends up performs demonstrably(in most cases) worse.

Looks like we need to add some clarifying slides to this presentation :-(. I'll do my best here.

Prediction is not in the instructions set; there are no "likely taken" flags, opcodes, or the like. You are correct that machines that have these features have found them useless, because compilers cannot predict very well. That's why we used the (saved) dynamic experience rather than static prediction.

In all machines, task change kills prediction behavior because the new task uses the prediction hardware and table for its own code, overwriting the learned predictions that were present before the change. When control switches back to the original task, the table contents and other state are no longer what they had been, and everything has to be retrained again. Training is costly due to mispredictions.

The predictions that get loaded are those from previous executions that were streamed out to memory, post-processed, and saved in the load module. They are not as good as up-to-the-cycle dynamic predictions, because programs have phases and the save predictions can only capture the overall experience; still, they are much better than static, or no predictions at all, which is the situation at program initiation or after a different task has scrubbed the tables.

Lastly, I agree that your proposed design isn't feasible. That's why the Mill doesn't work that way.

Ivan

There is a gcc extension that doesn't necessarily inform the CPU on x86/64, but it does restructure code so that the unlikely branch doesn't pollute the cache:

        #define likely(x)       _builtin_expect ((x), 1)
        #define unlikely(x)     _builtin_expect ((x), 0)

The machine code for the unlikely branch will be moved off into an unrelated area of memory, while the likely code will stay located with the rest of your function's code.

Yes, its called static branch prediction. I'm not sure how popular it is in modern ISAs, but MIPS and SPARC had such instructions.

I think that those instructions marked as obsolete in MIPS ISA manuals.

The Pentium 4 introduced prefix opcodes that hinted that the next branch would be likely or unlikely to be taken. These are still legal, but afaik post-NetBurst CPUs ignore them, and Intel's optimization manuals have dropped mention of them.

When a new branch is found, the CPU will predict it based on some simple and documented heuristics. It's been a while since I checked, but IIRC it boils down to: backward jumps are predicted to be taken (think loops) while forward jumps are predicted not to be taken.

When you give your compiler hints about what to expect, using either profiling data or explicit hints like __builtin_expect, the compiler will generally try to rearrange the code to be favourable for the CPU's branch prediction.

it's better to let the compiler decide (with gcc, you build a branch profile version, then rebuild the code with profiling results). unless you have something unusual, and have some deep insight into your code (unlikely), you're not going to do better than the compiler.

I find it strange you find it so unlikely that people have that much insight into their own code. The code I work on has several instances of likely/unlikely in the main path for cases that we know happen either once, rarely, or when we are moving off the optimized path.

Have you tried benchmarking it against a non-annotated compiled version?

I have not, but I believe those who originally wrote it did.

i've never came across code that has performed better with manual hints than compiler profiling.

at best, you can match the compiler, but.. i find that improbable, unless you have only a handful of branches.

These are situations where the branch will be taken, literally, millions of times in one direction, and once in the other.

There are many DSP system that have this (also, lots of attention to prefetching the right stuff). Compilers can pretend to get it right for you, or you just dive into tha sssembly if you want to save money and buy a slower CPU.

Reply on news.ycombinator.com