4 ms·
Is the moral of CPU branch prediction that generating dynamically branch-free code is preferable to generating statically branch-free?
by 082349872349872 4y ago
Is the moral of CPU branch prediction that generating dynamically branch-free code is preferable to generating statically branch-free?
- jleahy 4y agoThat’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).
- mhh__ 4y agoA 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.
- sweetjuly 4y agoI 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).
- mhh__ 4y agoThe "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)
- titzer 4y agoBy "hitting the backend" do you mean generating μ-ops? Because nops don't generate μ-ops yet branches definitely do.
- moonchild 4y agoNops 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 https://www.agner.org/optimize/instruction_tables.pdf): on intel, conditional jumps can be filled by ports 0 and 6.
- taeric 4y agoI 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.)
- marcosdumay 4y agoThe 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.
- taeric 4y agoI suspect it is a curve?
- delta_p_delta_x 4y ago> 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-processing-a-sorted-array-faster-than-processing-an-unsorted-array https://stackoverflow.com/questions/11227809/why-is-processi...
- superjan 4y ago
- mhh__ 4y agoAvoiding either > Easily predicted branch > conditional move > difficult to predict branch
- masklinn 4y ago> Avoiding either > Easily predicted branch Branchless code can easily out-cost a well-predicted branch (and its content if any).
- marcosdumay 4y agoWell, 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.
- mungoman2 4y agoThe branches still take (instruction) cache. So it is beneficial to reduce the number of branches, even if they could have been predicted accurately.
- taeric 4y agoThat 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?
- atq2119 4y agoI'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.
- taeric 4y agoMy 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 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 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 https://en.wikipedia.org/wiki/Data-oriented_design is probably what I actually had in mind.
- jasonwatkinspdx 4y agoThe 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."