การทำนายสาขาและการทำงานแบบคาดการณ์ล่วงหน้า

Modern CPUs are deeply pipelined, fetching and decoding many instructions ahead. But a conditional branch is a fork: the CPU does not yet know which path to fetch. Stalling would waste the whole pipeline.

To avoid stalls the CPU predicts which way a branch will go and keeps fetching. If correct, no time is lost. If wrong, the pipeline is flushed — a costly misprediction penalty of 15-20+ cycles.

The Branch Target Buffer and history tables record past outcomes. A simple 2-bit saturating counter remembers whether a branch was recently taken, predicting that loops keep looping.

Beyond predicting, the CPU speculatively executes the predicted path before the condition resolves. If the guess holds, results are committed; if not, they are discarded as if they never ran — architecturally.

You help the predictor by making branches consistent. A branch that is almost always taken predicts well; a random branch defeats prediction. Sorting data before a conditional loop can dramatically speed it up.

This C program shows the dramatic effect of sorted vs unsorted data on a branch-heavy loop. Run it and compare timings.

You can sometimes eliminate a branch entirely with arithmetic or conditional-move instructions (cmov), so the CPU never needs to predict.

Compilers expose hints like __builtin_expect (the source of likely()/unlikely() macros) so hot paths fall through and cold paths jump away, improving instruction-cache layout.

Speculative results are discarded architecturally — but they leave traces in the cache. Speculatively loaded data warms cache lines, and that timing difference can be measured. This is the basis of side-channel leaks.

Spectre tricks the predictor into speculatively reading memory it should not, then leaks the value through a cache timing side channel. The reads never commit, so they bypass normal bounds checks during the speculation window.

Defenses include serializing instructions (lfence) to stop speculation past a bounds check, retpolines for indirect branches, and microcode updates. They trade some performance for safety.

You learned how CPUs hide branch latency:

• Branch prediction guesses the path; mispredicts cost a pipeline flush
• Speculative execution runs the predicted path early
• Predictable branches, cmov, and likely/unlikely hints boost speed
• Speculation leaves cache side effects exploited by Spectre; lfence and retpolines mitigate it