5 ms·

Estimating branch probability using Intel LBR feature

69 points by ot 7y ago

titzer 7y ago
Nice work, and great writeup!
AstralStorm 7y ago
The thing is, branch prediction already in the CPU is so good, manual branch optimisations are equivalent to code cache layout optimizations, which given the ever bigger caches are getting ever less important too. The more important ones are for cache layout of bigger data structures, and there branch tracing is less than useful. That said, this is very useful for tracing thread execution in particular. (Inter thread cache flushes are a thing.)
- titzer 7y ago
  > manual branch optimisations are equivalent to code cache layout optimizations There is a big overlap, but they are not equivalent. Especially the default prediction and the fact that the number of predictions per cache line (branch density) has a limit. Also, loop unswitching is still worth it.
- reitzensteinm 7y ago
  Are caches actually getting bigger? They've remained essentially constant per core from Nehalem through Kaby Lake for L1-3. I have heard they're doubling L1/L2 in an upcoming chip, but it's been ten years!
  - ivl 7y ago
    Skylake-X has 1024 KiB of L2 per core. Which was a 4x increase over the 256 KiB of L2 per core that had been the standard forever since they've been going with the Core series.
    - tntn 7y ago
      But skylake also has much less L3 per core, so the increased L2 is less like cache growth and more like a rebalancing. The change to a non-inclusive L3 is more likely to contribute to greater capacity.
      - ivl 7y ago
        In the case I was thinking of, Skylake-X, the HEDT line, that wasn't entirely true. I was looking mostly at something like Broadwell-E vs Skylake-X, where the difference is huge: Core i7-6950X - $1,700 at launch in 05-2016: 10 × 256 KiB of L2, with 25 MiB of L3. Core i9-7960X - $1,700 at launch in 09-2017: 16 x 1024 KiB of L2, with 22 MiB of L3.
        tntn 7y ago
        i7-6950X: 256 KiB L2/core, 2.5 MiB L3/core i9-7960X: 1024 KiB L2/core, 1.375 MiB L3/core Seems to be exactly what I described? L2/core went up by 768 KiB, L3/core went down by 1.125 MiB.
        ivl 7y ago
        L3 went down per core, but total L3 only fell by 3 MiB. While total L2 flew up from 2.5 MiB to 16 MiB in a single generation for two processors that target the same segment at the same price. Per core you're correct, but I was looking at net cache available, as that had been remaining static, usually just seeing an extra 256 KiB of L2 per core with little L3 change.
- shereadsthenews 7y ago
  The LBR is great for giving feedback to compilers and PGO/FDO is usually good for 10% or more in branchy server code, so whatever the hardware can do on its own isn’t everything.
- kannanvijayan 7y ago
  I could see this being used in things like PGO compilers. Identifying a rare subpath (or more usefully: all the rare subpaths) in a particular control-flow allows a lot of down-stream leverage. Opportunities exist for biasing everything from register allocation to code-motion towards optimizing the fast-path branch. Additionally, if the rarely-taken branch is part of a conditional that introduces new definitions that are phi-ed later on, the joining block (and subsequent blocks) can be split (specialized) for the fast-path and slow-path cases. This would open up opportunities for constant-optimization - constants introduced in the common-path branch which stop being constants later on due to phis can remain constants in the modified control flow. And you get the usual round of benefits for DCE, GVN, etc. coming out of that too.
- CalChris 7y ago
  Yes, but trace scheduling [1] depends on finding important traces. You can do that heuristically in the compiler but it's more accurate to do it empirically with LBRs. [1] http://people.ee.duke.edu/~sorin/ece252/lectures/6.2-static-ilp.pdf http://people.ee.duke.edu/~sorin/ece252/lectures/6.2-static-...
- vardump 7y ago
  > ... are equivalent to code cache layout optimizations, which given the ever bigger caches are getting ever less important too. L1 code cache is just 32 kB. 512 cache lines of 64 bytes each. It's been 32 kB for almost 13 years, since Core 2 release. > The more important ones are for cache layout of bigger data structures, Bigger, like more than 500 cache lines (~31 kB) large? Also L1 data cache is just 32 kB. Wouldn't consider that very large data structure, although your mileage may vary. Intel Ice Lake is supposed to get a "massive" 48 kB L1 data cache. We'll see.

69 points by ot 7y ago

Nice work, and great writeup!

The thing is, branch prediction already in the CPU is so good, manual branch optimisations are equivalent to code cache layout optimizations, which given the ever bigger caches are getting ever less important too. The more important ones are for cache layout of bigger data structures, and there branch tracing is less than useful. That said, this is very useful for tracing thread execution in particular. (Inter thread cache flushes are a thing.)

titzer 7y ago
> manual branch optimisations are equivalent to code cache layout optimizations There is a big overlap, but they are not equivalent. Especially the default prediction and the fact that the number of predictions per cache line (branch density) has a limit. Also, loop unswitching is still worth it.
reitzensteinm 7y ago
Are caches actually getting bigger? They've remained essentially constant per core from Nehalem through Kaby Lake for L1-3. I have heard they're doubling L1/L2 in an upcoming chip, but it's been ten years!
- ivl 7y ago
  Skylake-X has 1024 KiB of L2 per core. Which was a 4x increase over the 256 KiB of L2 per core that had been the standard forever since they've been going with the Core series.
  - tntn 7y ago
    But skylake also has much less L3 per core, so the increased L2 is less like cache growth and more like a rebalancing. The change to a non-inclusive L3 is more likely to contribute to greater capacity.
    - ivl 7y ago
      In the case I was thinking of, Skylake-X, the HEDT line, that wasn't entirely true. I was looking mostly at something like Broadwell-E vs Skylake-X, where the difference is huge: Core i7-6950X - $1,700 at launch in 05-2016: 10 × 256 KiB of L2, with 25 MiB of L3. Core i9-7960X - $1,700 at launch in 09-2017: 16 x 1024 KiB of L2, with 22 MiB of L3.
      - tntn 7y ago
        i7-6950X: 256 KiB L2/core, 2.5 MiB L3/core i9-7960X: 1024 KiB L2/core, 1.375 MiB L3/core Seems to be exactly what I described? L2/core went up by 768 KiB, L3/core went down by 1.125 MiB.
        ivl 7y ago
        L3 went down per core, but total L3 only fell by 3 MiB. While total L2 flew up from 2.5 MiB to 16 MiB in a single generation for two processors that target the same segment at the same price. Per core you're correct, but I was looking at net cache available, as that had been remaining static, usually just seeing an extra 256 KiB of L2 per core with little L3 change.
shereadsthenews 7y ago
The LBR is great for giving feedback to compilers and PGO/FDO is usually good for 10% or more in branchy server code, so whatever the hardware can do on its own isn’t everything.
kannanvijayan 7y ago
I could see this being used in things like PGO compilers. Identifying a rare subpath (or more usefully: all the rare subpaths) in a particular control-flow allows a lot of down-stream leverage. Opportunities exist for biasing everything from register allocation to code-motion towards optimizing the fast-path branch. Additionally, if the rarely-taken branch is part of a conditional that introduces new definitions that are phi-ed later on, the joining block (and subsequent blocks) can be split (specialized) for the fast-path and slow-path cases. This would open up opportunities for constant-optimization - constants introduced in the common-path branch which stop being constants later on due to phis can remain constants in the modified control flow. And you get the usual round of benefits for DCE, GVN, etc. coming out of that too.
CalChris 7y ago
Yes, but trace scheduling [1] depends on finding important traces. You can do that heuristically in the compiler but it's more accurate to do it empirically with LBRs. [1] http://people.ee.duke.edu/~sorin/ece252/lectures/6.2-static-ilp.pdf http://people.ee.duke.edu/~sorin/ece252/lectures/6.2-static-...
vardump 7y ago
> ... are equivalent to code cache layout optimizations, which given the ever bigger caches are getting ever less important too. L1 code cache is just 32 kB. 512 cache lines of 64 bytes each. It's been 32 kB for almost 13 years, since Core 2 release. > The more important ones are for cache layout of bigger data structures, Bigger, like more than 500 cache lines (~31 kB) large? Also L1 data cache is just 32 kB. Wouldn't consider that very large data structure, although your mileage may vary. Intel Ice Lake is supposed to get a "massive" 48 kB L1 data cache. We'll see.