Estimating branch probability using Intel LBR feature | Hacker News Reader

Estimating branch probability using Intel LBR feature

easyperf.net

69 pointsot13 comments

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.)

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!

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.

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.

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.

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.

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.

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.

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.

> 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.

> ... 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.

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-...

Nice work, and great writeup!

Reply on news.ycombinator.com