3 ms·

How does the compiler arrange for the CPU to mispredict the branch most of the time? I didn't think there were any knobs for the branch predictor other than sta

How does the compiler arrange for the CPU to mispredict the branch most of the time? I didn't think there were any knobs for the branch predictor other than static ones (e.g. backwards-jumps statically predicted as taken, or PowerPC branch hint bit).

bluGill 4y ago
CPUs have documentation, for this. I forget which one, but the one I did read it was as simple as the true case is assumed more common, and it is easy to arrange logic around that (I probably mis remember, but close enough to that). The common case also should be near the if in memory (inline code), so it is likely on the same cache line (or the next which is prefetched), while the other case is farther away and so you can stall the cache if the if goes that way.
mikepurvis 4y ago
C++20 is gaining the [[likely]] attribute for guiding the predictor in a portable way: http://eel.is/c++draft/dcl.attr.likelihood http://eel.is/c++draft/dcl.attr.likelihood Prior to this it was also possible, but required compiler-specific macros like GCC's __builtin_expect, which is used all over the kernel: https://github.com/torvalds/linux/search?q=__builtin_expect https://github.com/torvalds/linux/search?q=__builtin_expect
- wumpus 4y ago
  20 years of "progress" and hey, C++20 is gaining the likely attribute.
- astrange 4y ago
  There are no ways to hint the branch predictor on some common CPUs. I think Intel says it's fully dynamic and has no static predictions. If you want to cause a pipeline stall, there's usually serializing instructions like cpuid/eieio.
  - vgatherps 4y ago
    I believe intel used to always predict forward branches not taken and backward branches always taken if it didn’t have any history. Regardless, you can at least lay out code in a way that heavily favors one branch over the other, and potentially optimize for one branch (I.e. give one branch very expensive prelude/exit to make another branch very cheap). The last thing I’ve seen compilers greatly struggle with though…
- menaerus 4y ago
  To my knowledge this does not have any direct impact to the CPU branch prediction mechanism. If that had been the case then we would at least have some x86-(64) instruction to manipulate with the BP. If I write a quick example such as https://godbolt.org/z/j7Y81j5fe https://godbolt.org/z/j7Y81j5fe, I also see no such instruction in the generated output. But what likely/unlikely mechanism can do is that it can serve as a hint to the compiler which the compiler can then use to generate more optimal code layout. For example, if we provide the compiler with likely/unlikely hints in our code, compiler will try to use that hint to stitch together the more probable code paths first. In theory this approach should result with better utilization of CPU instruction cache and thus it may lead to better performance.

bluGill 4y ago

CPUs have documentation, for this. I forget which one, but the one I did read it was as simple as the true case is assumed more common, and it is easy to arrange logic around that (I probably mis remember, but close enough to that). The common case also should be near the if in memory (inline code), so it is likely on the same cache line (or the next which is prefetched), while the other case is farther away and so you can stall the cache if the if goes that way.

mikepurvis 4y ago

C++20 is gaining the [[likely]] attribute for guiding the predictor in a portable way: http://eel.is/c++draft/dcl.attr.likelihood http://eel.is/c++draft/dcl.attr.likelihood Prior to this it was also possible, but required compiler-specific macros like GCC's __builtin_expect, which is used all over the kernel: https://github.com/torvalds/linux/search?q=__builtin_expect https://github.com/torvalds/linux/search?q=__builtin_expect

wumpus 4y ago
20 years of "progress" and hey, C++20 is gaining the likely attribute.
astrange 4y ago
There are no ways to hint the branch predictor on some common CPUs. I think Intel says it's fully dynamic and has no static predictions. If you want to cause a pipeline stall, there's usually serializing instructions like cpuid/eieio.
- vgatherps 4y ago
  I believe intel used to always predict forward branches not taken and backward branches always taken if it didn’t have any history. Regardless, you can at least lay out code in a way that heavily favors one branch over the other, and potentially optimize for one branch (I.e. give one branch very expensive prelude/exit to make another branch very cheap). The last thing I’ve seen compilers greatly struggle with though…
menaerus 4y ago
To my knowledge this does not have any direct impact to the CPU branch prediction mechanism. If that had been the case then we would at least have some x86-(64) instruction to manipulate with the BP. If I write a quick example such as https://godbolt.org/z/j7Y81j5fe https://godbolt.org/z/j7Y81j5fe, I also see no such instruction in the generated output. But what likely/unlikely mechanism can do is that it can serve as a hint to the compiler which the compiler can then use to generate more optimal code layout. For example, if we provide the compiler with likely/unlikely hints in our code, compiler will try to use that hint to stitch together the more probable code paths first. In theory this approach should result with better utilization of CPU instruction cache and thus it may lead to better performance.