4 ms·

Great explanation of why a branchless approach results in such a speed up. I've never really had to deal with performance optimization at this level. Generally

by bormaj 2mo ago

Great explanation of why a branchless approach results in such a speed up. I've never really had to deal with performance optimization at this level. Generally it's probably best not to get too involved letting the CPU black box do its thing. I do wonder, would the performance characteristics of branchless vs branching be consistent across different CPUs/architectures? If you had a CPU that wasn't trying to be fancy with branch prediction, would the regular algo be faster?

nvme0n1p1 2mo ago
Virtually every CPU has branch prediction, going back to at least the original Pentium (1993), maybe earlier. If you're running on a very old CPU, yes, the regular algo should be faster.
- deleted 2mo ago
  [deleted]
- phire 2mo ago
  I think the Pentium is more or less the first microprocessor with branch prediction. Certainly the most mainstream. PowerPC 601 arrived at more or less the same time, and the Alpha 21064 was a year earlier. There were a few minicomputers and mainframes before that with branch predictors. Arguably the 486 could have done with a branch predictor (even a single entry loop predictor would have helped), and maybe the 386 too. But microcoded CISC designs didn't benefit much from predictors because they have multiple cycles to work it out. And RISC cpus were in their "branch delay slots are awesome" phase throughout most of the 80s. With a bit of trickery (very simple branch conditions and a 2 phase clock), your classic 5-stage MIPS design can fully hide all branches with just a single branch delay slot, so they were a little slow to adopt predictors. I get the impression that CPU designers in the 80s and early 90s massively underestimated just how beneficial even a small predictor can be.
  - toast0 2mo ago
    > I get the impression that CPU designers in the 80s and early 90s massively underestimated just how beneficial even a small predictor can be. It's got a lot to do with how cpu clock speeds were getting way faster, but ram wasn't. That's what makes deeper pipelines attractive, and if you give a cpu a deeper pipeline, it's gonna want a good branch predictor.
    - phire 2mo ago
      I'm more thinking about how MIPS were quite late to branch predictors. They were shipping the high-performance R4000 and R4400 with 8 stage pipelines and no branch predictors. They could have really done with a branch predictor, each branch took three cycles (and the branch delay slot could fill only one instruction, often a useless NOP). The Pentium only had a 5 stage pipeline and massively benefited from its branch predictor. IBM was slapping branch predictors on PowerPC designs with 4 stage integer pipelines. You simply don't need a long pipeline to justify the benefits of a branch predictor.
  - adrian_b 2mo ago
    Pentium was the first CPU with a branch predictor that many people could afford to buy. Before dynamic branch prediction, where the prediction for every branch is updated after each branch execution, depending on its history, static branch prediction had been used for decades, since around 1960, typically using the rule that forwards branches are unlikely to be taken, but backwards branches are likely to be taken. An alternative was to have an instruction bit where the compiler stored its prediction about the probability of a branch being taken. Dynamic branch predictors began to be used since the mid seventies. I do not remember now if any notable monolithic CPU had a dynamic branch predictor before Pentium, but prior multi-chip CPUs certainly existed.
    - phire 2mo ago
      > Before dynamic branch prediction... static branch prediction had been used for decades. I'm not sure that's true. At least not the "predict backwards branches are taken" part. Many RISC cpus did kind of have "predict forwards as not taken", but really thats just speculative execution with the complete absence of any branch prediction at all. IMO "All branches are not taken" is not a prediction. Actual Static Branch prediction is something that seems to have shown up at the exact same time as dynamic branch prediction (ie Pentium and PowerPC 601). Seems to be more of a "well do speculative execution now, what do we do when there is no dynamic prediction?" thing. Maybe there is a multi-chip CPU out there that has proper static prediction but not dynamic? But I checked the likely candidate (The RS/6000 aka POWER1) and it doesn't have any prediction at all (just a hole where the static prediction bits will go later). Probably because static prediction requires support for speculative execution, which it doesn't do.
- vlovich123 2mo ago
  Cortex M0 and microprocessors generally do not. Cortex M3’s looks nothing like the branch prediction you think of when you think consumer or server CPU. Basically branch prediction requires extra power so it’s excluded or greatly simplified in low power use cases.
throwaway_95283 2mo ago
CPUs aren't black boxes. They are actually much better documented than almost all the software that runs on them. If you want to treat the CPU as a black box, trust me you do not want to use a CPU with out a branch predictor, your slow code will run like molasses frozen in antarctica. The regular algo will be lightyears slower on any CPU that does not have a branch predictor.
Brian_K_White 2mo ago
Another recent story from github about case folding as part of code search, the simple version of the code had a couple of ifs, and the branchless version was actually slower. They have a stupendously fast version and it is also branchless, but it just required more than branchless alone. I'm fuzzy on the details but I think one of the ifs was an early exit, and without that the loop does a memory assignment on every byte instead of skipping most. The really fast version was also vectorized. The branchless makes it possible to vectorize, but it was the vectorization that actually made it fast.
imtringued 2mo ago
I'm not sure how your intuition can be that off, if you don't have a branch predictor then any branching code is going to be even slower than it already is, favouring branchless code even more for obvious reasons. I say this as someone who is interested in a special type of processor architecture that has no branch prediction at all and would need a branchless subset of Rust to meaningfully program it at high performance.
- benj111 2mo ago
  Why no branch predictor at all? Even a brain-dead one that predicts all branches always/never taken is going to provide some benefit, it's not as if the processor can do anything else while it's waiting. Or am I missing something? I note the hazard 3 on the pi Pico rp2350 only predicts a branch if it's the last branch and was taken, ie a single loop. Which seems weird to me, so I'm probably lacking understanding somewhere.

by bormaj 2mo ago

nvme0n1p1 2mo ago

Virtually every CPU has branch prediction, going back to at least the original Pentium (1993), maybe earlier. If you're running on a very old CPU, yes, the regular algo should be faster.

deleted 2mo ago
[deleted]
phire 2mo ago
I think the Pentium is more or less the first microprocessor with branch prediction. Certainly the most mainstream. PowerPC 601 arrived at more or less the same time, and the Alpha 21064 was a year earlier. There were a few minicomputers and mainframes before that with branch predictors. Arguably the 486 could have done with a branch predictor (even a single entry loop predictor would have helped), and maybe the 386 too. But microcoded CISC designs didn't benefit much from predictors because they have multiple cycles to work it out. And RISC cpus were in their "branch delay slots are awesome" phase throughout most of the 80s. With a bit of trickery (very simple branch conditions and a 2 phase clock), your classic 5-stage MIPS design can fully hide all branches with just a single branch delay slot, so they were a little slow to adopt predictors. I get the impression that CPU designers in the 80s and early 90s massively underestimated just how beneficial even a small predictor can be.
- toast0 2mo ago
  > I get the impression that CPU designers in the 80s and early 90s massively underestimated just how beneficial even a small predictor can be. It's got a lot to do with how cpu clock speeds were getting way faster, but ram wasn't. That's what makes deeper pipelines attractive, and if you give a cpu a deeper pipeline, it's gonna want a good branch predictor.
  - phire 2mo ago
    I'm more thinking about how MIPS were quite late to branch predictors. They were shipping the high-performance R4000 and R4400 with 8 stage pipelines and no branch predictors. They could have really done with a branch predictor, each branch took three cycles (and the branch delay slot could fill only one instruction, often a useless NOP). The Pentium only had a 5 stage pipeline and massively benefited from its branch predictor. IBM was slapping branch predictors on PowerPC designs with 4 stage integer pipelines. You simply don't need a long pipeline to justify the benefits of a branch predictor.
- adrian_b 2mo ago
  Pentium was the first CPU with a branch predictor that many people could afford to buy. Before dynamic branch prediction, where the prediction for every branch is updated after each branch execution, depending on its history, static branch prediction had been used for decades, since around 1960, typically using the rule that forwards branches are unlikely to be taken, but backwards branches are likely to be taken. An alternative was to have an instruction bit where the compiler stored its prediction about the probability of a branch being taken. Dynamic branch predictors began to be used since the mid seventies. I do not remember now if any notable monolithic CPU had a dynamic branch predictor before Pentium, but prior multi-chip CPUs certainly existed.
  - phire 2mo ago
    > Before dynamic branch prediction... static branch prediction had been used for decades. I'm not sure that's true. At least not the "predict backwards branches are taken" part. Many RISC cpus did kind of have "predict forwards as not taken", but really thats just speculative execution with the complete absence of any branch prediction at all. IMO "All branches are not taken" is not a prediction. Actual Static Branch prediction is something that seems to have shown up at the exact same time as dynamic branch prediction (ie Pentium and PowerPC 601). Seems to be more of a "well do speculative execution now, what do we do when there is no dynamic prediction?" thing. Maybe there is a multi-chip CPU out there that has proper static prediction but not dynamic? But I checked the likely candidate (The RS/6000 aka POWER1) and it doesn't have any prediction at all (just a hole where the static prediction bits will go later). Probably because static prediction requires support for speculative execution, which it doesn't do.
vlovich123 2mo ago
Cortex M0 and microprocessors generally do not. Cortex M3’s looks nothing like the branch prediction you think of when you think consumer or server CPU. Basically branch prediction requires extra power so it’s excluded or greatly simplified in low power use cases.

throwaway_95283 2mo ago

CPUs aren't black boxes. They are actually much better documented than almost all the software that runs on them. If you want to treat the CPU as a black box, trust me you do not want to use a CPU with out a branch predictor, your slow code will run like molasses frozen in antarctica. The regular algo will be lightyears slower on any CPU that does not have a branch predictor.

Brian_K_White 2mo ago

Another recent story from github about case folding as part of code search, the simple version of the code had a couple of ifs, and the branchless version was actually slower. They have a stupendously fast version and it is also branchless, but it just required more than branchless alone. I'm fuzzy on the details but I think one of the ifs was an early exit, and without that the loop does a memory assignment on every byte instead of skipping most. The really fast version was also vectorized. The branchless makes it possible to vectorize, but it was the vectorization that actually made it fast.

imtringued 2mo ago

I'm not sure how your intuition can be that off, if you don't have a branch predictor then any branching code is going to be even slower than it already is, favouring branchless code even more for obvious reasons. I say this as someone who is interested in a special type of processor architecture that has no branch prediction at all and would need a branchless subset of Rust to meaningfully program it at high performance.

benj111 2mo ago
Why no branch predictor at all? Even a brain-dead one that predicts all branches always/never taken is going to provide some benefit, it's not as if the processor can do anything else while it's waiting. Or am I missing something? I note the hazard 3 on the pi Pico rp2350 only predicts a branch if it's the last branch and was taken, ie a single loop. Which seems weird to me, so I'm probably lacking understanding somewhere.