Use likely() and unlikely() Hints with Verify Branch Statistics

Topic Overview

Likely vs Unlikely Branches

__builtin_expect(expr, c) tells GCC/Clang the probability of a branch, influencing layout so the hot path falls through. Linux kernel likely()/unlikely() macros wrap it. Mis-hinting can slow code by fighting the hardware predictor.

Syntax and Effect

Mark error checks as cold. Keep the common path straight-line when possible.

cCopy
Loading…

• Modern CPUs learn patterns; hints help most on unpredictable branches
• Read perf stat -e branch-misses before sprinkling hints
• PGO often beats manual hints by using real frequencies
• Hints do not change program semantics

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

• Trace first: walk one failing input step by step
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will add branch hints to a hot path and compare assembly layout. This exercise requires explaining when hints helped versus when the predictor already learned the branch.

Document one invariant you will assert in tests and how you would detect its violation from observable symptoms.

Your Task

likely()/unlikely() (__builtin_expect) do not talk to the CPU's branch predictor. They tell the compiler which side of an if to lay out as the fall-through path. The unlikely side moves out of line, so the common case runs straight through without a taken jump. Model this. For each branch, lay the code out with and without the hint, run the recorded condition outcomes through a 2-bit predictor, and charge for taken jumps and mispredictions. Wrong hints should visibly hurt.

Input

cCopy
Loading…

OUTCOMES is a list of tokens made of T (condition true) and N (false), each optionally repeated with *COUNT. For example N*999 T, or TN*50 for 100 alternating outcomes. At most 100000 outcomes per branch.

Model

• Layout. By default (no hint, or likely), the then block falls through, and the conditional jump is taken when the condition is false. With unlikely, the then block is moved out of line: the else/continuation falls through, and the jump is taken when the condition is true. The "without hint" run always uses the default layout.
• Prediction. Each branch has its own 2-bit saturating counter over the physical jump, starting at 1 (weakly not taken). A value of 2 or 3 predicts taken. A wrong prediction costs MISPREDICT cycles. Every taken jump costs TAKEN cycles. Then the counter moves toward the outcome.
• Warn when the hint disagrees with the profile: likely while the condition is true less than half the time, or unlikely while it is true more than half the time.

Output

cCopy
Loading…

The percentage is rounded half up to 1 decimal. Errors: branch NAME: hint must be likely, unlikely or none, branch NAME: bad outcome list, and penalty: must be >= 0.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Keep the source-level condition and the physical jump direction separate. The hint changes only the mapping between them.
2. Simulate each branch's predictor from its initial state for every layout.

Hidden tests cover a likely hint that is wrong, a pattern that defeats the 2-bit counter, custom penalties including a zero taken-jump cost (so only mispredictions matter), a single-outcome branch, and malformed outcome lists.