The core and the operating system

What do branch prediction, SIMD, NUMA, the TLB and the kernel each charge, and when?

Branch prediction

A modern CPU is pipelined, like an assembly line: it works on many instructions at different stages at the same time. With a 15–20 stage pipeline, the CPU must decide which instruction to fetch next about 15 cycles before it knows the result of an if. It cannot wait, so it guesses and continues.

• Modern predictors (TAGE-class) are right 95–99% of the time on normal code.
• The cost is asymmetric: a correct guess is free, a wrong guess costs a full pipeline flush of 15–20 cycles.

The bad case is a branch on unpredictable data. if (value >= 128) on random values is a coin flip: 50% accuracy, ~10 cycles of penalty per item on average.

long sum = 0;
for (int i = 0; i < N; i++)
    if (data[i] >= 128)        // random data → mispredicts about half the time
        sum += data[i];

After sorting data, the same loop is 3–6× faster, although sorting added work, because the branch becomes "no, no, no … yes, yes, yes": perfectly predictable. This is Meera's second odd finding, and the clearest demonstration in systems programming that predictability beats the amount of work.

Branchless code reduces variance, not average cost

sum += (data[i] >= 128) * data[i];   // arithmetic instead of a jump

Branchless code does a small amount of guaranteed extra work for every item and removes the variable, large cost of mispredictions. On predictable data the branchy version wins; on unpredictable data the branchless one wins. This is why query engines use branchless selection vectors and bitmaps: predicate results on real data are unpredictable.

SIMD and the vectorization ceiling

SIMD (Single Instruction, Multiple Data) means one instruction works on a whole vector of values. Example: add 8 pairs of numbers with one instruction.

• SIMD is fixed-cost amortization applied to the instruction itself. Fetching, decoding, scheduling and finishing an instruction cost the same for 1 element or 16, so widening the data path is cheap compared with widening the whole core. SSE 128-bit → AVX2 256-bit → AVX-512 / SVE 512-bit: 4 / 8 / 16 integers of 32 bits per instruction.
• The limit is not the register width. The wider you go, the faster you run out of memory bandwidth. 16 lanes of arithmetic on data that arrives at one operation per byte just means 16 idle lanes instead of 1. Vectorization helps only when arithmetic intensity is high enough (the roofline model, next).
• Other limits:
  • Horizontal operations (sums or shuffles across lanes) are slow compared with lane-by-lane operations. So the data layout must suit lanes: SoA (Structure of Arrays), not AoS (Array of Structures). AoS = [{x,y,z}, {x,y,z}, …]; SoA = {x:[…], y:[…], z:[…]}. SoA is the same idea as columnar storage.
  • Downclocking: AVX-512 lowers the clock speed on many Intel CPUs, so wide code can slow the rest of the program.
  • Vectorization is a data layout decision that happens to use special instructions.
• Vectorized query engines win for two reasons that people often mix up. (1) Less interpretation overhead per batch: the older Volcano model processes one row at a time with a function call per row, while vectorized engines process, for example, 1,024 values per call. (2) SIMD lanes. The first is usually the bigger gain. Keep them separate when you judge claims.

The bandwidth wall and the roofline model

• You can hide latency with concurrency. You cannot hide bandwidth. It is a fixed throughput shared by all cores. DRAM bandwidth is ~50–200 GB/s per socket, while the total compute of the cores is in the teraFLOP range (trillions of floating-point operations per second). Bytes available per operation have been falling for decades.
• The roofline model shows this clearly. Plot achievable performance (y) against arithmetic intensity (x) = FLOPs done per byte loaded from DRAM.
  • Left of the ridge point you are on the sloped memory roof: performance = intensity × bandwidth. Only moving fewer bytes helps.
  • Right of it you are on the flat compute roof.
• Almost every data-engineering operation is memory-bound. Scans, filters, hash joins and aggregations have ~0.1–1 FLOP/byte. Ridge points are ~5–15 FLOP/byte. You are far from the compute roof and cannot reach it.

• The strategic result: the only way to speed up a memory-bound workload is to move fewer bytes. That means:

  • compression — use the idle arithmetic units to save bandwidth. This is why light schemes (dictionary, run-length encoding, bit-packing) beat heavy ones such as gzip in query engines;
  • columnar layout — read only the columns you need;
  • late materialization — build full rows only after filtering;
  • predicate pushdown — filter as early as possible, near the data;
  • cache blocking — process data in cache-sized pieces.

  All of these are the same move.

NUMA

NUMA (Non-Uniform Memory Access): on a server with several CPU sockets, each socket has memory attached directly to it. Reading your own socket's memory is local and fast. Reading another socket's memory is remote and goes through an interconnect (UPI on Intel, Infinity Fabric on AMD).

• This is Cause 1 at socket scale. Remote access costs ~1.5–2.2× the latency with much less bandwidth, and the interconnect itself can become saturated.
• Where a page lands is a placement policy, decided by the thread that first touches it: that is memory management's subject, with the bug and the designs it forces.
• Modern single-socket CPUs are also NUMA inside (chiplets, sub-NUMA clustering), so this is no longer only a two-socket problem.

TLB and huge pages

• Virtual memory is an indirection layer, and it has its own cache. Programs use virtual addresses. Hardware translates them to physical addresses through page tables (a tree of lookup tables). A full lookup (a page-table walk) needs 4–5 memory reads that depend on each other, so the CPU caches recent translations in the TLB (Translation Lookaside Buffer).
• The arithmetic: 1,536 L2-TLB entries × 4 KB pages = ~6 MB of "reach". L3 cache is often 32 MB and your working set may be 10 GB. You can leave the TLB's coverage while still fitting in cache, which gives a confusing profile: data "in cache" but slow code.
• A TLB miss costs ~20–100 cycles, and it is a dependent load: the walk must finish before the real access starts, so it cannot overlap with other work. Random access over a large heap can spend 10–30% of its cycles walking page tables.
• Huge pages (2 MB) multiply reach by 512× to ~3 GB. This is a Cause 2 move (coarser units to amortize a fixed cost) with the usual price: wasted space inside big pages and, for transparent huge pages (THP), latency spikes when the kernel background process khugepaged compacts memory. That is why Redis and MongoDB advice is to disable THP while HPC (scientific computing) advice is to enable it: same mechanism, different tolerance for tail latency.

Syscalls, context switches and copies

• A syscall is not a function call. It crosses a privilege boundary. Your program asks the operating-system kernel to do something (read a file, send a packet). The direct cost is ~50–150 ns. The larger cost is pollution: the kernel evicts your L1/L2 and TLB entries, so your next several hundred instructions run slower. Spectre/Meltdown security fixes (KPTI, IBRS) made this 2–3× worse in some cases.
• A context switch (the OS pauses one thread and runs another) costs ~1–5 µs directly and 10–50 µs in practice, once cache and TLB are refilled. This is why one thread per request designs fail at high concurrency, and why event loops, green threads and io_uring exist.
• Copies are a pure bandwidth tax. The classic path from file to network (file → kernel buffer → user buffer → kernel socket buffer → network card) makes ~4 copies and ~4 mode switches. sendfile, splice and io_uring reduce this to 0–2 copies (zero-copy). At 10 GB/s, copying 1 GB costs 100 ms of waste, plus the cache it destroyed.
• The common idea: this is the NVMe finding from Storage media, seen from the other side. When the work per operation falls to ~1 µs, a 3–10 µs kernel path becomes the fixed cost. Cause 3 does not care whether the mechanism is a disk arm or a privilege switch.