The Useless If That Broke a Latency Chain

Most performance work is about algorithms, data layouts, or vectorization. Then there are the cases where the algorithm is already solid, the SIMD is tight, and the remaining loop still crawls because of a single data dependency the CPU cannot hide. That is exactly the situation a domain-specific compressor hit while choosing optimal encodings for input chunks: a trivial-looking walk over a precomputed table that was latency-bound for no good semantic reason.

The fix was an if that does nothing useful from the language's point of view. With the right hints it still cut the loop from 320 µs to 80 µs in a synthetic run (and roughly 2× in a more realistic one). The technique is narrow, data-dependent, and a little ugly. It is also a clean illustration of how modern CPUs actually run code, and why developers who own hot paths sometimes have to argue with both the compiler and the memory system at once.

The dependency the compiler cannot see past

The heavy lifting lived in a reverse-pass loop that filled an array next_j[n_symbols][8] with SSE2. That part was already well optimized: _mm_minpos_epu16, blends, packs, the usual dance. The follow-up that turned those references into an encoding sequence looked almost free:

uint8_t j = 0;
for (int i = 0; i < n_symbols; i++) {
    j = next_j[i][j];
    encoding[i] = j;
}

Excluding the store, the body is a single load. On paper that should be throughput-limited. In practice each iteration waits for the previous j before it can even form the address of the next load. Instruction-level parallelism exists, but it cannot start two dependent memory operations at the same time. Even L1 latency is enough to serialize the whole walk when every step threads a register through the loop.

This is not 1984. The front end and the execution ports can keep many independent instructions in flight; a carried dependency simply starves them. The loop counter and the store to encoding are cheap enough to hide. The chain on j is not.

Predicting that nothing changes

The data distribution saved the day. Chunks are relatively rare, so for most i the value of next_j[i][j] is simply j itself. If the CPU could be told to assume that, the dependency disappears on the common path and the loop becomes throughput-bound again. Address prediction is not under software control, but branch prediction is.

The rewritten form is deliberately branchy:

for (int i = 0; i < n_symbols; i++) {
    if (j != next_j[i][j]) {
        j = next_j[i][j];
    }
    encoding[i] = j;
}

When the predictor treats the body as cold, it simply ignores the store to j. Speculative execution proceeds as if j never changed. On the rare true path the misprediction recovery machinery undoes the wrong speculative work and restarts with the correct value. That is exactly the cost model you want when changes are infrequent: pay a predictable mispredict tax only when the encoding actually switches, and keep the pipeline full the rest of the time.

From the language abstract machine the if is pure noise. Common-subexpression elimination will happily delete it. Compilers are also biased toward branchless code for exactly this kind of assignment, because branchless form is usually faster when the branch would be unpredictable. Here the opposite is required: convert branchless into branchy so the predictor can do useful work.

Forcing the compiler's hand

Two portable-enough tricks survive the optimizers. The original approach cast the load through volatile:

if (j != next_j[i][j]) {
    j = *(uint8_t volatile *)&next_j[i][j];
}

That makes the load look like it can have side effects the compiler is not allowed to sink or eliminate, so the control dependence stays. Later observation showed that [[unlikely]] (or the older __builtin_expect(..., 0)) also keeps the branch alive under LLVM. volatile still produced better code in practice and worked with GCC as well, so it remains the more robust hammer.

Neither technique is a general recommendation. Both are local lies told to the optimizer because the data distribution is known and the loop is hot enough to matter. In this particular algorithm each next_j[i][j] can only be j or a value that depends only on i. That observation opens a cleaner encoding (store the alternate value plus a bitmask), but testing a variable bit is slower than a plain comparison on x86, so the "useless" if stayed the better trade-off.

What actually changes for working code

This pattern is worth recognizing, not cargo-culting. Reach for it only after a profiler has already pointed at a carried dependency inside a tight loop and you have measured that the value almost never changes. Typical candidates: state machines that stay in the same state for long runs, sparse transitions in table-driven decoders, or the final reconstruction pass of a dynamic-programming table like the one here.

The practical checklist is short:

• Confirm the dependency with a cycle-accurate view or at least with perf counters that show high load-use latency and low IPC on that loop.
• Measure the true frequency of the rare path on real data. A 4× win on synthetic input became a still-useful 2× on more realistic material, largely because LLVM's codegen was not ideal. If the branch is taken more than a few percent of the time the mispredict cost will dominate.
• Prefer [[unlikely]] first if you are already on a recent Clang; fall back to a carefully scoped volatile load when you need GCC as well or when the generated code is still wrong.
• Keep the alternative representation in mind. Sometimes making the branch semantically necessary (bitmask, optional, tagged union) removes the need for volatile tricks entirely and is easier to maintain.
• Document the assumption. The next reader will otherwise delete the "pointless" if and quietly lose the speedup.

It does not replace ordinary work: better algorithms, better locality, or vectorizing the reconstruction itself if the problem allows. It also does not help when the transition rate is high or when the table no longer fits in cache; then you are back to ordinary memory-bound analysis. Portability is imperfect (predictors and recovery costs differ across microarchitectures), so keep a branchless fallback behind a feature test if the same code must run well on multiple vendors.

A small, honest win

The numbers are modest in absolute terms (tens of microseconds per pass), yet the loop ran many times during compression, so the cumulative effect was real. More interesting than the 4× figure is the reasoning: modern cores are built around speculation, and sometimes the cheapest way to give them a free dependency chain is to insert a branch they can correctly predict as never taken.

Compilers have gotten very good at turning branches into conditional moves and at removing dead tests. They still cannot read the statistical structure of your input. When that structure is stable and extreme, a carefully placed "useless" if remains a legitimate, if slightly disreputable, tool. Use it sparingly, measure it, and leave a comment for the next person who will otherwise clean it up.

The rest of the time, write the obvious code and let the optimizer do its job. The 1 % of loops that actually matter will tell you when the obvious is no longer enough.