The Most Expensive Instruction Might Be… cmov | QuestDB<br>New: QuestDB For AI Agents<br>New: QuestDB For AI Agents<br>Learn more<br>Or: how I fact-checked my own LinkedIn comment and found a compiler heuristic that measures the wrong thing.

It started with a LinkedIn comment. Tomáš Pitner published a nice article about branch mispredictions and how Clang turns if into conditional instructions on ARM64. I did what the platform is optimized for: replied instantly, with my brain on auto-pilot:

"[...] on x86-64 conditional instructions win if and only if a branch is unpredictable. When a branch predictor wins then a branch is cheap and beats cmov & friends. JIT compilers have an advantage here - they can emit different code for different patterns observed."

Then I re-read what I wrote and it made me slightly uneasy: JIT compilers can emit different code for different patterns observed. Can they? And do they? What does HotSpot actually observe about a branch? Tomáš is a university professor after all, I don't want to be wrong under HIS status!

I decided to find out: analyze Hotspot source code and then measure. Spoiler: my comment was wrong. HotSpot doesn't observe branch patterns at all. It observes something that looks deceptively similar and in a hot loop the difference can be worth 2.9×.

Bias is not predictability

Take a branch in a loop. There are two different questions you can ask about it:

Bias: How often does it go each way? A 90/10 branch is heavily biased; a 50/50 branch is not.

Predictability: Can the CPU's branch predictor guess the next outcome?

These two properties are independent. Consider four data patterns driving the same value > 0 test:

50/50 bias90/10 biaspredictable TNTNTNTN… (strict alternation)TTTTTTTTTN repeatingunpredictable random, 50% positiverandom, 90% positive

A modern branch predictor has no problem with the alternating pattern at all: It has near-zero mispredictions despite the 50/50 split. The random 90%-positive data, despite its comfortable 90/10 bias, still mispredicts about 10% of the time.

Why does the compiler care anyway? Because it has a choice to make! It can keep the branch, or it can flatten the whole if/else shape (a "diamond", in compiler speak) into a conditional move, cmov on x86. The trade:

A branch is a guess. The CPU doesn't wait for the condition. Instead, it speculates on the outcome and races ahead. So a correctly predicted branch costs almost nothing. A misprediction throws away the speculated work and restarts, and that is expensive.

A cmov is a wait, but only for whoever uses its result. It can never mispredict, and independent work still runs ahead freely; but anything that consumes the chosen value has to wait for the condition and both inputs to be computed. If each iteration's result feeds the next one, you pay that latency every iteration, regardless of how predictable the data was.

So the right choice depends on several things: how much work each side of the if does, whether anything downstream waits on the result and how much other work the loop offers to hide latency behind.

What the profile actually contains

HotSpot's strength is profile-guided compilation: code starts in the interpreter and the quick C1 compiler, both of which record statistics as they go, and the optimizing C2 compiler later uses those statistics. For an ordinary two-way branch, here is what they record. In MethodData, every such branch gets a BranchData record:

class JumpData : public ProfileData {<br>enum {<br>taken_off_set, // the "taken" counter<br>displacement_off_set,<br>jump_cell_count // number of slots above<br>};

// It consists of taken and not_taken counts as well as a data displacement<br>class BranchData : public JumpData {<br>enum {<br>// the "not taken" counter, appended after JumpData's slots<br>not_taken_off_set = jump_cell_count,

Two aggregate outcome counters. The x86 interpreter bumps one of them per profiled execution:

increment_mdp_data_at(mdp, in_bytes(JumpData::taken_offset()));<br>// ...<br>increment_mdp_data_at(mdp, in_bytes(BranchData::not_taken_offset()));

C1 does the equivalent. (Pedantic footnote: the C++ increment helpers saturate, but the x86 interpreter's fast path is an unchecked addptr, a discrepancy that matters to approximately nobody.)

When C2 compiles the method, Parse::dynamic_branch_prediction reads a snapshot of the two counts (the snapshot itself is explicitly approximate and racy), requires at least 40 combined observations, and computes their ratio:

prob = (float)taken / (float)(taken + not_taken);

That ratio is all the conversion heuristic will see. The MethodData profile this decision consumes does not contain outcome ordering, branch history or hardware misprediction counts. A strictly alternating branch and a randomly driven branch with equal counts are indistinguishable to everything downstream.

So the branch-outcome signal that reaches C2's cmov decision measures bias. Where does it get used?

The comment vs. the code

The branch-to-cmov...