Hacker News Reader

Comment by 082349872349872 | Hacker News Reader

Is the moral of CPU branch prediction that generating dynamically branch-free code is preferable to generating statically branch-free?

View on HN

I would think it is less on the "don't have branches" but more "try to have a happy/common path." This is oddly at odds with how humans work as operators. For human operators, you typically want each interaction to be as unpredictable as possible, to keep their attention. Falling into rote action is a sure way to get a mistake out of a person. (Or to get them to quit.)

However, for computers, it is good to view them as a machine. As most machines, they are best if they are doing the exact same thing over and over. And over.

As such, if you can contrive for the machine to always take the same branch the vast majority of the time, you will get it to work faster. Whether this is done with a dynamic arrangement of the data, or a static arrangement of the code depends largely on the specifics. Consider sorting networks as a fun exploration of the idea. They can be ridiculously fast, as they always do the same amount of work. (Provided you have enough execution units.)

The more predictable a work process becomes, the quicker people can do it too.

Our issue is with correctness, that is something we not even think about in computers. So, it's not really surprising that this completely different issue has different constraints than speed.

I suspect it is a curve?

> The more predictable a work process becomes, the quicker people can do it too.

The most highly-voted question on Stack Overflow[1] relates to branch predictability. There's an almost 10× speed-up when the branch predictor of the asker's CPU is fully engaged.

Modern branch predictors are extremely powerful, with TAGE and perceptrons achieving 99.5%+ prediction accuracy.

https://stackoverflow.com/questions/11227809/why-is-processi...

This is related to an idea from data oriented design: Split up your data such that each piece of data needs exactly the same transform, and do all those at once.

The way Linus put it in an old newsgroup posting from his Transmeta days was something like: "the job of a cpu is to generate the minimum number of cache misses as early as possible."

That’s certainly true, a correctly predicted branch costs little more than a nop or unconditional jmp.

Code doesn’t have to be branch free, just branch in a predictable way.

Statically branch free code is great when you have things that are genuinely unpredictable, think branches driven by data. You might reach for min/max as an example of that, but in most cases these tend to be highly predictable. Control flow in a decompressor is probably a better example (eg. literal vs copy).

A correctly predicted branch, in a sense can cost less than a nop in that it does actual work and requires no additional effort from the backend.

I mean, not really. All branches will need to hit the backend in order to verify that they were correctly predicted. RISC-V conditional branches, for example, require doing register register comparisons for verification which means they must be entered into the ROB and issued like any other instruction. This consumes real backend resources and is significantly more than a nop (which can be eliminated by the front end).

The "in a sense" was doing a lot of heavy lifting. They still hit the backend but the idea is that a nop also hits the backend but does no work.

Programmers, I think, sometimes still think of a very backend heavy idea of branch prediction (e.g. old static predictors)

By "hitting the backend" do you mean generating μ-ops? Because nops don't generate μ-ops yet branches definitely do.

Nops do not hit the backend. And conditional branches do eventually make their way to the backend—at some point, you have to actually check that the condition was satisfied. Refer to agner (https://www.agner.org/optimize/instruction_tables.pdf): on intel, conditional jumps can be filled by ports 0 and 6.

Well, reducing the share number of branches in your code has exactly the same impact as improving the predictor's performance. So, no I don't think you can get this conclusion from the article.

The article is only biased into improving the CPU and ignoring any opportunity of improving your program. What is understandable, because it's about CPU architectures.

In practice, you will want to improve whatever part you have the freedom to change. You usually can not choose.

The branches still take (instruction) cache. So it is beneficial to reduce the number of branches, even if they could have been predicted accurately.

That said, I have seen people tricked into thinking branches are only if statements. If using polymorphism to reduce if statements, you'll still want to reduce the variations of the types sent through the code. Well, strictly you just want the variations to be predictable, I suppose?

I've been wondering about this recently. Modern branch predictors are really good at predicting correlated conditional branches. That is, if you have two if statements near each other that use the same condition, modern branch predictors have a very good chance of learning to predict the second one perfectly based on what the first one did.

Is the same true for indirect calls, i.e. virtual function calls? That could be quite the powerful optimization, but it's probably really hard to do.

My understanding is that this is, essentially, the optimization that you get with many common "entity component system" frameworks. That is, you typically try to keep homogeneous collections of entities so that when you are processing them, you are doing a similar processing in a loop.

Amusingly, as I try to google to make sure I am using the right terms, I find https://news.ycombinator.com/item?id=28200030 as a good result. Seems to cover the general idea and hints at other terms to look into. In particular, have fun with https://en.wikipedia.org/wiki/AoS_and_SoA. :D

Edit: I should add that I'm pretty sure my memory conjuring up ECS stuff was just mistaken, btw. https://en.wikipedia.org/wiki/Data-oriented_design is probably what I actually had in mind.

Things are getting way too high-level here. Nobody will be able to answer your question because it depends on an overwhelming amount of details.

Your compiler capabilities will have a much larger influence on your code performance than the lower level properties of your GPU. As always, it's a matter of profiling and discovering what is actually happening. Most times when people use polymorphism, it's free.

Agreed it is tough to answer. Highly polymorphic code is often not that diverse, for one. And many languages that encourage polymorphism are run with a jit. Which can be seen as a higher level branch predictor. And, predictably, benefits code paths that don't have a lot of diversity in the types being sent through code.

Avoiding either > Easily predicted branch > conditional move > difficult to predict branch

> Avoiding either > Easily predicted branch

Branchless code can easily out-cost a well-predicted branch (and its content if any).

This is where I was trying to use sorting networks as a fun example. Without independent compare/swap units, they will go slower than sequential sorting. Despite not necessarily "branching."

Of course, perhaps this should be reduced to "keep an eye out for silly branches"

Reply on news.ycombinator.com