Finding the predictor in my own CPU

How big are the branch structures of a real core, and how far are they from the ones I modelled?

The last three articles built branch prediction into a model of a small RISC-V core. There, a misprediction costs 2 cycles, the branch target buffer has 16 entries, the return stack 8, and the direction tables 4 KiB. This time I measured the real thing: the laptop I write on. Its Intel Core Ultra 7 258V (Lunar Lake) has two core designs on one chip, four Lion Cove P-cores and four Skymont E-cores. They run the same instructions and the same binary. They answer the same design questions differently.

I measured both from user space, with small loops in assembly and a clock. A measurement like this sees a curve, not a circuit. A step at 1,024 jumps says that something holds about 1,024 jumps, not how it is built. Intel publishes few of these numbers. Where others have measured them, I compare.

01Setup

Each probe is a loop in assembly, generated by a Python script, built with gcc and pinned to one core: cpu 3 is a Lion Cove core, cpu 7 a Skymont core. The loop runs once untimed, which also trains the predictors, then five more times. Every number below is the median of those five.

The clock is the time-stamp counter, which ticks at a fixed rate whatever the core's frequency. To turn ticks into core cycles, I run a chain of dependent additions next to the loop. Each addition waits for the previous one, so the chain takes one cycle per addition. The laptop ran on battery in its power-saver profile, and the core's frequency moved during a run (Lion Cove ran at 1.5 to 2.1 GHz, Skymont at 1.7 to 2.7 GHz). So each run is cut into slices of about 65,000 branches (32,000 calls for the return-stack probes), and each slice is converted with a reference chain measured just before and just after it. A frequency change between slices then cancels out.

There are no hardware counters here. On this machine kernel.perf_event_paranoid is 4, which forbids them to a user, so every result is a time. Where a time alone is ambiguous, I designed a second experiment to separate the cases.

02Checks

• The reference holds. Counted as one cycle per addition, the chain gives a frequency that matches the kernel's own reading from the hardware's cycle counters (APERF and MPERF) to within 2 %, in three runs on each core type. An addition is one cycle.
• A known latency. A chain of dependent 64-bit multiplications measures 3.00 cycles per multiplication on Lion Cove, where the documented latency is 3. On Skymont it measures 4.00. That is an observation, not a check: I know of no published figure for it.
• Spread. Over the 1,886 measurements, the slowest of the five runs is a median 1.7 % slower than the fastest, and within 5.7 % for nine measurements in ten. The widest spreads are on Lion Cove near the limits of its direction predictor, where some runs learn a pattern and others do not: four branches with a period of 4,096 measured 1.8 cycles per branch in one run and 7.5 in another. Skymont repeats itself.

03What a misprediction costs

The first probe tests 64 branches per 64-bit word. A shift moves the next bit into the carry flag and a jump tests it, so the condition is ready one cycle after the previous shift, with no load in its path. With random words, half the branches are mispredicted. With words of all ones or all zeros, none are.

A misprediction costs about 20 cycles on both cores, ten times the 2 cycles of the five-stage model. It costs more when the condition comes from memory, and grows with every cycle the branch waits for its operands: the work after the branch is thrown away and done again. The model's 2 cycles are right for a five-stage core and nothing like a modern one.

Skymont pays 2.4 cycles for each taken branch when they are packed every five bytes. Lion Cove pays 1. I come back to dense branches below.

04How much one branch remembers

The second probe has one branch whose outcomes follow a random pattern that repeats every P branches. To predict it, the predictor must store the whole pattern, one outcome per position, and find its position from the recent history. A 2-bit counter learns nothing from a random pattern. The figure shows the extra cycles per branch over a pattern that alternates taken and not taken, which is just as often taken but easy to learn.

View larger ↗

• Skymont costs nothing extra up to a period of 4,871, a little at 5,793, and fails from about 6,900. By 55,000, nearly half the branches miss.
• Lion Cove learns longer patterns, up to twice as long, but its limit moves from run to run: in the two sweeps of the final run, it fails from 11,585 in one and 13,777 in the other. But from a period of 23 onwards, each branch costs about 0.66 cycles more than the alternating pattern, long before the pattern is too long.

That extra cost on Lion Cove is not a misprediction. To show it, I delayed the branch: 24 cycles of dependent multiplications by one before the branch reads its byte. A misprediction is paid when the branch resolves, so delaying the branch makes it more expensive, and it does: 43 cycles instead of 24. A bubble in the front end costs nothing when the back end is the bottleneck, and the multiplications make it so (3.26 cycles per branch instead of 2.27).

The extra cost vanished instead of growing, so it is a delay in the front end, not a misprediction. Lion Cove predicts short patterns at once and long ones a little late. That is what the overriding predictor of the previous article does: a fast predictor redirects fetch at once, and a slower, more accurate one corrects it when they disagree. I cannot see which structure does it here, only that its answer arrives late.

05Branches sharing the predictor

The third probe has B branches, each with its own random pattern of the same period. For each B, I take the longest period learned: the last one before the extra cost reaches a tenth of a full misprediction. B times that period is the number of outcomes the predictor holds at once.

View larger ↗

Skymont holds about 6,000 outcomes for one branch and about 23,000 when they are spread over 32 branches or more. With 512 branches it learns patterns of 45 and fails at 64. Chips and Cheese, with the same kind of test, reports that Skymont fails beyond 48. Lion Cove holds 8,000 outcomes for one branch and about 16,000 at most. Measured this way, the small core holds more than the big one, by one step of the test, a factor of 1.4. On neither core can a single branch use all of the storage.

For scale, the 4 KiB tables of the previous article hold 16,384 two-bit counters. A counter keeps one guess per branch, and a random pattern needs one per position.

06Taken jumps and the branch target buffer

A taken branch has to redirect fetch before the branch is even decoded, so the core keeps a cache of branch targets: the branch target buffer, or BTB. The fourth probe chains n unconditional jumps, each to the next, 4, 16 or 64 bytes apart, and runs them in a loop. While the BTB holds every jump, the jumps cost little; past each of its levels, they cost more.

View larger ↗

On Lion Cove, with jumps 16 bytes apart:

• Up to about 23 jumps, the loop runs at three jumps per cycle (0.3 cycles each). It probably runs from a loop buffer, which replays it without fetching it again.
• Up to about 200 jumps, one jump per cycle. The level ends at about 400 jumps when they are 4 or 8 bytes apart, and at about 45 when they are 64 bytes apart.
• Up to about 5,000 jumps, two cycles per jump; then three cycles up to about 11,600.
• Beyond, about 13 cycles per jump: the jump is found only when it is decoded.

Chips and Cheese measured a 12K-entry BTB on Lion Cove, and Wikipedia's table lists levels of 256, 6K and 12K entries, without a source. The steps fall close to those sizes.

On Skymont, with jumps 16 bytes apart, a jump costs one cycle up to about 1,000 jumps, 2.5 to 4 cycles up to about 8,000, then 9 or more. Chips and Cheese reports a 1,024-entry first level with no bubble, a second level at 3 to 4 cycles and 8,192 entries in the last. The match is close. Dense jumps are Skymont's weak point: four bytes apart, they cost 7.5 cycles each beyond about a dozen.

07Returns

A return jumps to wherever the matching call came from, so its target changes from one call to the next. A return stack predicts it: each call pushes its return address, and each return pops one. Two probes test its depth.

• The chain. D distinct functions, each calling the next. Every return has a single target.
• The random sites. One recursive function, called at each level from one of four call sites chosen at random. Only a return stack can know where each return goes, and a guess is right one time in four.

View larger ↗

Skymont's stack holds 128 levels, and Chips and Cheese reports 128 entries. With functions 16 bytes apart, a call and its return cost 4.1 to 4.6 cycles; 64 bytes apart, 2.0 to 2.1. Chips and Cheese notes that calls and returns must be a cache line apart to use this stack. Here, closer ones still reach 128 levels, at twice the cost.

Lion Cove is less clear. Chips and Cheese reports 24 entries. Three of my four tests find about 17 levels, and the fourth finds 25:

I tested two explanations, and both failed.

• The frames below the test. The loop runs inside other functions, whose return addresses sit in the stack too. Twelve more of them change nothing, so the stack overwrites its oldest entries, as it should.
• The wrong path. A mispredicted call site sends the core down a wrong path, which may call and push before it is undone. Delaying the choice by 24 cycles, so the wrong path runs longer, changes nothing either.

I do not know why the chain of functions 16 bytes apart goes further. On this core, the depth of the return stack is not a single number: it depends on where the code sits.

08Against the model

The previous article concluded that, on a five-stage core, a fast predictor beats an accurate one. Its own limitations said that a deeper pipeline would favour accuracy. Here is the deeper pipeline: at 20 cycles per misprediction, every miss avoided is worth ten times more. A cycle of latency still costs one cycle, and the measurements suggest that Lion Cove pays it only when its front end is the bottleneck. A real core does not choose between fast and accurate. It layers them.

09Limitations

• Times only. Without counters, a misprediction is inferred from cycles. The delayed-branch experiment separates mispredictions from front-end delays, but it is one experiment, not a count.
• One laptop. One chip, one core of each type, on battery, with a clock that moved during the runs. The slices cancel the frequency changes, not every interference from the rest of the system.
• Random patterns. They measure how much a predictor can store, not how well it predicts real code. Real branches are mostly easier.
• Steps, not structures. A level found at about 4,000 jumps may be a table of 6,000 entries that loses some to collisions. The comparisons with published sizes are the closest I have to a check.
• Other people's numbers. The published figures come from Chips and Cheese's measurements, partly on Arrow Lake, which uses the same Lion Cove core, and from a Wikipedia table that cites no source.

10How far can this be trusted?

The method has checks I trust: the cycle reference agrees with the hardware's own counters through the kernel, and a multiplication measures its documented latency. On Skymont, four results land on published ones: a 1,024-entry first BTB level, an 8,192-entry last one, a 128-entry return stack, and patterns of 48 outcomes or fewer across 512 branches. The misprediction costs and the BTB steps repeat from run to run, and so do Skymont's pattern limits; Lion Cove's move by a step of the test between runs. What remains open is in the text: why Lion Cove's return stack looks 17 deep in three layouts and 25 in one, and which structure delays its long patterns.

11Reproduction

Everything runs from the cpu-systemc folder, on Linux and x86-64. The probes are in probe/:

run.py writes one JSON file per experiment to probe/results/. The core numbers are set at the top of run.py; on another machine, pick one core of each type, or one core.

Sources: Chips and Cheese, Skymont: Intel's E-Cores reach for the Sky and Intel's Lion Cove P-Core and Gaming; Wikipedia, Lion Cove.