5 ms·

Oh dang, branch hints. I always thought they were so obvious, and never implemented, so they must be obviously bad. But, Intel is giving them a shot. Neat!

yjftsjthsd-h 2y ago
IIRC, SPARC also used them, which... probably suggests that it's not totally terrible.
- duskwuff 2y ago
  I believe PowerPC had them as well. No idea how effective they were.
  - seanmcdirmid 2y ago
    I took computer architecture in the mid-late-90s and branch hints were talked about as a thing that was being done.
    - bee_rider 2y ago
      Yeah, in my class (a couple years ago, but not decades) they were covered as something that seemed like a neat idea, but then didn’t help much for actual programs. The general theme in that class was that everything cool added more complexity than the performance benefit could justify, and got in the way of making things wider. Same for branch delays slots.
      - duskwuff 2y ago
        Branch delay slots were just a straight-up instance of exposing an ugly quirk of the pipeline to the programmer. They became a liability in later revisions of MIPS, as it no longer arose naturally from the architecture and had to be deliberately included.
  - KerrAvon 2y ago
    From distant memory: they were effective for at least some PowerPC implementations. I don't recall how much, but it was considered worthwhile in hot code for at least some machines. However, IIRC, branch prediction wasn't as advanced at that point; a modern implementation might not see the same benefits.
- nineteen999 2y ago
  Then again SPARC had register windows ... so ...
pclmulqdq 2y ago
Giving them another shot. Pentium 4 had them, but there were some skill issues on the part of programmers using them, and so code quality rose when CPUs started ignoring them.
- TrainedMonkey 2y ago
  Arguably on P4 they were required to get any kind of throughput due to an incredibly long execution pipeline Intel contrived to keep pushing clock frequency up. Branch mispredictions were extremely costly on that architecture.
  - pclmulqdq 2y ago
    Yes, the Pentium 4 pipeline was ~32 cycles long, which meant that a branch misprediction carried a huge penalty. Processors today have settled on using a ~15-cycle pipeline.
    - magicalhippo 2y ago
      I've probably read about it and forgotten, but what on earth was it doing in all those pipeline stages? Were there a lot of idle/no-op stages for simple instructions? Or did most instructions, even simple ones, actually get some useful work done for each of those 32ish stages?
      - pclmulqdq 2y ago
        Here's a good source for the earliest Pentium 4, which had a 20-cycle pipeline: https://courses.cs.washington.edu/courses/cse378/10au/lectures/Pentium4Arch.pdf https://courses.cs.washington.edu/courses/cse378/10au/lectur... Mostly the stages you expect from an out-of-order core all had their own pipeline slot in order to go super fast, and some were split into two stages. For example, you have two stages to calculate the next instruction (branch prediction), two stages to fetch, a stage to redrive a value from the memory bus, etc. From there, the ALUs could only do a 16-bit add in one cycle, so even an addition took at least 3 cycles. The later Pentium 4's took this subdivision even further with the goal of reaching 4-5 GHz clocks in 2005. The whole chip was hand-laid-out, so it was possible to put pipeline registers in places that would have been weird to do in Verilog.
IshKebab 2y ago
Do compilers even generate these hints?
- duskwuff 2y ago
  Usually not by default, but GCC and other compilers have intrinsics like __builtin_expect [1] which may generate branch hints. [1]: https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-_005f_005fbuiltin_005fexpect https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index...
  - unwind 2y ago
    Quite popular in the Linux kernel code, as far as I've seen over the years. See [1] for some discussion over on SO. [1]: https://stackoverflow.com/questions/109710 https://stackoverflow.com/questions/109710
  - menaerus 2y ago
    In practice this doesn't result with a special-kinded instruction to hint the CPU branch-predictor but only affects the compiler to generate a codegen that is optimized for better CPU instruction-cache utilization. E.g. it will try to move the less likely code out from the hot code path and as such the likely code is going to be more dense and co-located next to each other.
    - vlovich123 2y ago
      It can also change the instruction selection. For example, __builtin_unpredictable which is a close cousin of expect will indicate there's no prediction possible on a branch. This causes the compiler to select branchless instructions & is particularly useful in things like binary search where the CPU attempting to do prediction is worse than using a branchless version of the code.
  - Salgat 2y ago
    I think in general we're overdue for more compiler directives, and not just branch hints. As heterogenous architectures become more standard, we really need a way to tag what functions are best to run with what types of instructions. For example, tag a function that will utilize SIMD so that if a thread is running this function, the operating system knows to try to have it run on the cores that support SIMD. As of now, with P and E Cores for Intel, Intel is straight up disabling instructions to ensure uniform instruction support.
drmpeg 2y ago
The i960CA and CF had branch hints. It was bit 1 in the branch and the compare and branch opcodes.
jeffbee 2y ago
I can see how branch hints are useful, but in practice isn't the sign of the distance to the branch target the implicit hint? If the predictor doesn't have any other information it assumes that backwards branches are taken and forward branches are not. So, you can imagine how the compiler would rearrange the program to align with that implication, where possible. One of the things that the BOLT post-link optimizer does is rearrange basic blocks to reduce taken forward branches, based on the profiles.
- BeeOnRope 2y ago
  Yes I don't really get it. For non-loop branches if the compiler has knows enough to insert a branch hint it would also already arrange the generated code so that was the fall through cases, which is already much more efficient when predicted and aligns the default fall through assumption in the CPU.
- marcosdumay 2y ago
  You can't reorder some kinds of branches, like retry sequences. I have absolutely no idea how important that it. But there exist that bit of extra complication on the real world.
  - taeric 2y ago
    Retry sequences are unlikely to be the kind that the branch prediction is that important? I'd also expect that they are larger than the threshold that is common for branches that are likely to be taken many times. That is, the stuff that will go into a retry of something likely has far more setup than your typical hot loop.
- bee_rider 2y ago
  Huh, that’s a funny and true perspective. I always took the “branches backwards tend to be loops” assumption as true, but of course there’s no reason a compiler or linker couldn’t use that assumption as well.

yjftsjthsd-h 2y ago

IIRC, SPARC also used them, which... probably suggests that it's not totally terrible.

duskwuff 2y ago
I believe PowerPC had them as well. No idea how effective they were.
- seanmcdirmid 2y ago
  I took computer architecture in the mid-late-90s and branch hints were talked about as a thing that was being done.
  - bee_rider 2y ago
    Yeah, in my class (a couple years ago, but not decades) they were covered as something that seemed like a neat idea, but then didn’t help much for actual programs. The general theme in that class was that everything cool added more complexity than the performance benefit could justify, and got in the way of making things wider. Same for branch delays slots.
    - duskwuff 2y ago
      Branch delay slots were just a straight-up instance of exposing an ugly quirk of the pipeline to the programmer. They became a liability in later revisions of MIPS, as it no longer arose naturally from the architecture and had to be deliberately included.
- KerrAvon 2y ago
  From distant memory: they were effective for at least some PowerPC implementations. I don't recall how much, but it was considered worthwhile in hot code for at least some machines. However, IIRC, branch prediction wasn't as advanced at that point; a modern implementation might not see the same benefits.
nineteen999 2y ago
Then again SPARC had register windows ... so ...

pclmulqdq 2y ago

Giving them another shot. Pentium 4 had them, but there were some skill issues on the part of programmers using them, and so code quality rose when CPUs started ignoring them.

TrainedMonkey 2y ago
Arguably on P4 they were required to get any kind of throughput due to an incredibly long execution pipeline Intel contrived to keep pushing clock frequency up. Branch mispredictions were extremely costly on that architecture.
- pclmulqdq 2y ago
  Yes, the Pentium 4 pipeline was ~32 cycles long, which meant that a branch misprediction carried a huge penalty. Processors today have settled on using a ~15-cycle pipeline.
  - magicalhippo 2y ago
    I've probably read about it and forgotten, but what on earth was it doing in all those pipeline stages? Were there a lot of idle/no-op stages for simple instructions? Or did most instructions, even simple ones, actually get some useful work done for each of those 32ish stages?
    - pclmulqdq 2y ago
      Here's a good source for the earliest Pentium 4, which had a 20-cycle pipeline: https://courses.cs.washington.edu/courses/cse378/10au/lectures/Pentium4Arch.pdf https://courses.cs.washington.edu/courses/cse378/10au/lectur... Mostly the stages you expect from an out-of-order core all had their own pipeline slot in order to go super fast, and some were split into two stages. For example, you have two stages to calculate the next instruction (branch prediction), two stages to fetch, a stage to redrive a value from the memory bus, etc. From there, the ALUs could only do a 16-bit add in one cycle, so even an addition took at least 3 cycles. The later Pentium 4's took this subdivision even further with the goal of reaching 4-5 GHz clocks in 2005. The whole chip was hand-laid-out, so it was possible to put pipeline registers in places that would have been weird to do in Verilog.

IshKebab 2y ago

Do compilers even generate these hints?

duskwuff 2y ago
Usually not by default, but GCC and other compilers have intrinsics like __builtin_expect [1] which may generate branch hints. [1]: https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-_005f_005fbuiltin_005fexpect https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index...
- unwind 2y ago
  Quite popular in the Linux kernel code, as far as I've seen over the years. See [1] for some discussion over on SO. [1]: https://stackoverflow.com/questions/109710 https://stackoverflow.com/questions/109710
- menaerus 2y ago
  In practice this doesn't result with a special-kinded instruction to hint the CPU branch-predictor but only affects the compiler to generate a codegen that is optimized for better CPU instruction-cache utilization. E.g. it will try to move the less likely code out from the hot code path and as such the likely code is going to be more dense and co-located next to each other.
  - vlovich123 2y ago
    It can also change the instruction selection. For example, __builtin_unpredictable which is a close cousin of expect will indicate there's no prediction possible on a branch. This causes the compiler to select branchless instructions & is particularly useful in things like binary search where the CPU attempting to do prediction is worse than using a branchless version of the code.
- Salgat 2y ago
  I think in general we're overdue for more compiler directives, and not just branch hints. As heterogenous architectures become more standard, we really need a way to tag what functions are best to run with what types of instructions. For example, tag a function that will utilize SIMD so that if a thread is running this function, the operating system knows to try to have it run on the cores that support SIMD. As of now, with P and E Cores for Intel, Intel is straight up disabling instructions to ensure uniform instruction support.

drmpeg 2y ago

The i960CA and CF had branch hints. It was bit 1 in the branch and the compare and branch opcodes.

jeffbee 2y ago

I can see how branch hints are useful, but in practice isn't the sign of the distance to the branch target the implicit hint? If the predictor doesn't have any other information it assumes that backwards branches are taken and forward branches are not. So, you can imagine how the compiler would rearrange the program to align with that implication, where possible. One of the things that the BOLT post-link optimizer does is rearrange basic blocks to reduce taken forward branches, based on the profiles.

BeeOnRope 2y ago
Yes I don't really get it. For non-loop branches if the compiler has knows enough to insert a branch hint it would also already arrange the generated code so that was the fall through cases, which is already much more efficient when predicted and aligns the default fall through assumption in the CPU.
marcosdumay 2y ago
You can't reorder some kinds of branches, like retry sequences. I have absolutely no idea how important that it. But there exist that bit of extra complication on the real world.
- taeric 2y ago
  Retry sequences are unlikely to be the kind that the branch prediction is that important? I'd also expect that they are larger than the threshold that is common for branches that are likely to be taken many times. That is, the stuff that will go into a retry of something likely has far more setup than your typical hot loop.
bee_rider 2y ago
Huh, that’s a funny and true perspective. I always took the “branches backwards tend to be loops” assumption as true, but of course there’s no reason a compiler or linker couldn’t use that assumption as well.