Memory Latency: What It Is and Why Your CPU Isn’t Running at 100%

⏱️ Reading time: 14 min

A monitor showing CPU at 100% almost never tells the full truth: that number measures busy time, not useful work. The most common cause of the gap is memory latency, the time the processor loses waiting for data that isn’t in its caches.

For anyone tuning a SQL query, a data pipeline, or a production service, understanding this difference changes what should be optimized first. This article explains how the CPU cache hierarchy works, why a GROUP BY with millions of keys becomes slow, and how to measure the problem on your own machine with perf stat.

TL;DR

• Memory latency explains why a CPU at 100% can deliver 400 to 800 times less throughput than expected
• L1 responds in ~1 ns, L3 in ~10-15 ns, and RAM takes 50-100 ns: each hop costs hundreds of lost instructions
• A GROUP BY with 17 million unique keys turns every HashMap access into a direct trip to RAM
• perf stat with the backend_bound_memory metric measures how much CPU time is lost waiting for data instead of computing
• Partitioning data so each chunk fits in the L2 or L3 cache is the core technique behind engines like Pivot

What Is Memory Latency?

Memory latency is the time it takes a processor to fetch data that isn’t available in its internal caches and must be requested from RAM. It’s measured in nanoseconds, usually ranging between 50 and 100 ns on modern hardware, and determines how many instructions sit frozen waiting for that response.

That wait isn’t a minor detail: on a modern CPU capable of executing 4 to 8 instructions per nanosecond, every trip to RAM is equivalent to skipping between 400 and 800 instructions the processor could have executed. That’s the underlying reason behind the figure cited in Pivot’s blog: a CPU can appear busy in the operating system’s monitor while actually spending a large part of its time stalled, waiting.

Why It Matters for Developers

The operating system considers a CPU busy if there’s any task (in Linux terms) assigned to that core, regardless of whether that task is making progress or just waiting for a memory response. That’s why two processes showing 100% CPU usage can be doing completely different amounts of actual work.

This affects everyday engineering decisions: choosing a data structure, deciding how many threads to launch, or diagnosing why a SQL query takes longer than expected even though the server doesn’t appear saturated according to standard metrics. Ignoring the CPU cache hierarchy leads to optimizing the wrong thing, like adding more cores to a problem that’s actually limited by how many times the processor has to reach out to RAM.

How the CPU Cache Hierarchy Works

To avoid paying the full cost of every RAM access, modern processors interleave several levels of memory, each progressively faster and smaller, soldered directly onto the chip. The level closest to the core, the L1 cache, responds in just 1 nanosecond but has a tiny size (around 64 KB). The following levels, L2 and L3, are larger but also slower.

flowchart TD
    A["CPU Core"] --> B["L1 Cache ~1 ns, ~64 KB"]
    B --> C["L2 Cache ~3-4 ns, ~1 MB"]
    C --> D["L3 Cache ~10-15 ns, hundreds of MB"]
    D --> E[("DRAM ~50-100 ns, GBs")]

The table below summarizes the four levels using the values Pivot’s own team uses to reason about their engine’s performance:

The practical consequence is clear: a program that works with small data structures and accesses them predictably can stay almost entirely within L1 or L2. A program that jumps erratically across a memory space much larger than L3 will end up paying the full cost of the cache hierarchy on every access.

Practical Examples: From a Dictionary to Random Access in C

The simplest example of a GROUP BY is a dictionary that accumulates totals by key. In Python:

from collections import defaultdict

sales = [("ana", 120), ("luis", 75), ("ana", 30), ("luis", 10), ("ana", 5)]
totals = defaultdict(int)
for user, amount in sales:
    totals[user] += amount

print(dict(totals))

This code groups sales by user and sums the amounts, exactly what SELECT SUM(amount) FROM sales GROUP BY user does in SQL. The output is deterministic:

{'ana': 155, 'luis': 85}

With five rows and two keys, the entire dictionary comfortably lives in the L1 cache. The problem appears when cardinality grows: with millions of unique keys, that same defaultdict stops fitting in any cache, and every totals[user] += amount becomes a potential jump to RAM.

To see the effect in a controlled way, this C program sums 50 million integers two different ways: accessing them in order, and accessing them following a fixed stride that visits the same positions but in a scattered order.

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    long n = 50000000;
    long *data = malloc(n * sizeof(long));
    for (long i = 0; i < n; i++) data[i] = i;

    long sequential_sum = 0;
    for (long i = 0; i < n; i++) {
        sequential_sum += data[i];
    }

    long scattered_sum = 0;
    for (long i = 0; i < n; i++) {
        long idx = (i * 7919L) % n;
        scattered_sum += data[idx];
    }

    printf("sequential=%ld scattered=%ld\n", sequential_sum, scattered_sum);
    free(data);
    return 0;
}

Since 7919 is prime and doesn’t divide 50,000,000, the second loop visits exactly the same 50 million positions, just in an order that constantly jumps from page to page. The mathematical result is identical in both cases:

sequential=1249999975000000 scattered=1249999975000000

Same sum, same data, but the second loop forces the CPU to request scattered data across all of memory instead of taking advantage of the hardware prefetcher, the circuit that guesses the next block to load when it detects a sequential pattern. Measuring the difference between both loops with perf stat is exactly what the next section does.

The Real Case: a GROUP BY over 99 Million Rows

The Pivot team brought this exact problem to production. They took the public “hits” dataset from ClickBench (99 million rows) and ran this query with a naive GROUP BY implementation, a HashMap that grows with no locality optimization at all:

SELECT count(*), UserID FROM hits GROUP BY UserID

With 17 million unique UserID values, the query took 3.9 seconds on the first run and 3.6 seconds on the second, once all the data was already in the operating system’s page cache. To understand why, they ran perf stat pinning the process to a specific core with taskset and measuring what percentage of the CPU’s execution slots were lost waiting on memory:

Performance counter stats for 'CPU(s) 3':

 8364109137 ex_no_retire.load_not_complete    # 50.1 % backend_bound_memory
 38233214040 de_no_dispatch_per_slot.backend_stalls
 8977647849 ex_no_retire.not_complete
 11861387798 ls_not_halted_cyc

The 50.1% backend_bound_memory means that, for half the execution time, the CPU had work assigned (and the resource monitor showed it as busy) but wasn’t completing any instructions: it was stalled, waiting for RAM to return the next UserID value. With 17 million keys scattered across a HashMap, almost no access lands within L1, L2, or L3.

sequenceDiagram
    participant CPU as CPU
    participant L1 as L1 Cache
    participant L2 as L2 Cache
    participant L3 as L3 Cache
    participant RAM as DRAM
    CPU->>L1: requests UserID at address X
    L1-->>CPU: miss
    CPU->>L2: requests address X
    L2-->>CPU: miss
    CPU->>L3: requests address X
    L3-->>CPU: miss
    CPU->>RAM: requests address X
    RAM-->>CPU: data, 50-100 ns later
    Note over CPU,RAM: data is copied back to L1, L2, and L3 on return

Getting Started: Measuring Memory Latency with perf on Linux

Dependencies on Ubuntu or Debian: the linux-tools-common package and the kernel-specific version, linux-tools-$(uname -r). On Arch Linux or Fedora, the package is simply called perf. On macOS the equivalent tool is Instruments (included with Xcode); on Windows, Windows Performance Recorder (WPR).

sudo apt install linux-tools-common linux-tools-$(uname -r)

Save the program from the previous section as latency.c, compile it with optimizations (without -O2 the compiler may behave differently), and run perf stat on the binary:

gcc -O2 -o latency latency.c
perf stat -M backend_bound_memory,retiring -- ./latency

You’ll see two numbers: backend_bound_memory (percentage of slots waiting on memory) and retiring (percentage of slots that actually completed an instruction). If your kernel blocks unprivileged access to hardware counters, you’ll need sudo or you’ll need to temporarily set /proc/sys/kernel/perf_event_paranoid to -1.

💡 Tip: There’s no universal good number for backend_bound_memory: what matters is comparing the same program across two versions, like the sequential loop against the scattered one from the earlier example. If your optimized version didn’t lower that percentage, you didn’t fix the memory problem, you just hid it.

Real-World Use Cases in Database Engines

Columnar engines like ClickHouse or DuckDB don’t use a single giant HashMap for a GROUP BY. Instead, they split the work into two phases: a local, batched aggregation, vectorized with SIMD instructions and small enough to fit entirely in L1 or L2, and a global merge at the end, once there are far fewer values left to combine. That’s essentially the technique Pivot describes to avoid the scenario of 50.1% backend_bound_memory: partitioning keys by hash into N buckets, so each bucket fits in an L2 or L3 cache instead of scattering across all of RAM.

The same principle shows up in very different systems: a sorted B+ tree index physically groups nearby keys so a lookup touches few memory pages, and a game engine that iterates an “array of structures” instead of a “structure of arrays” pays the same cache-miss cost as the naive HashMap in this article. The CPU cache hierarchy isn’t a database detail: it’s a physical constraint that runs through any program that moves enough data.

Common Mistakes and Best Practices

• Confusing CPU at 100% with CPU saturated with useful work: the operating system marks any core with an assigned task as busy, regardless of whether that task is progressing or stalled waiting on RAM.
• Measuring only with a wall clock: a stopwatch tells you something took longer, but not why. Without perf stat it’s impossible to tell a memory bottleneck apart from a pure CPU one.
• Choosing a data structure without considering cardinality: a HashMap is perfect with thousands of keys and a disaster with tens of millions, not because of the algorithm itself, but because it stops fitting in any cache.
• Ignoring false sharing in multithreaded code: two threads writing to different variables that happen to sit on the same 64-byte cache line invalidate each other’s cache on every write, even though they logically share no data.
• Not aligning critical structs: letting the compiler’s padding fragment a structure used in a hot loop can make it span two cache lines instead of one, doubling the required memory accesses.

Comparison of Aggregation Strategies

Going Deeper: What’s Behind backend_bound_memory

Modern processors don’t execute instructions strictly in source-code order: they use out-of-order execution, pushing forward instructions that don’t depend on the result still waiting on memory. When that pool of independent instructions runs dry and the core literally has nothing else to do while it waits, that’s where the backend_bound_memory Pivot measured shows up: the percentage of execution slots left empty due to lack of data, not lack of work.

Another factor that worsens the problem on multi-socket servers is NUMA, non-uniform memory access: if the missing data lives in the RAM bank connected to the other socket, latency climbs well above the 50-100 ns of a local access, because the request has to cross the interconnect between sockets. Pinning processes to a core close to their memory, which is what taskset does in Pivot’s example, is a simple way to avoid that extra cost.

The decision of how many hash bits to use for partitioning matters too: with too few partitions, each one is still larger than L3; with too many, the overhead of managing them (metadata, branching) outweighs the savings. The practical goal is for each partition’s working set, the keys and counters touched repeatedly, to fit in L2 (on the order of 1 MB) so most accesses in the hot loop resolve there instead of in L3 or RAM.

flowchart TD
    subgraph Naive["Naive aggregation"]
    A1["New row"] --> A2["Hash scattered across the entire HashMap"]
    A2 --> A3["RAM access on almost every row"]
    end
    subgraph Partitioned["Partitioned aggregation"]
    B1["New row"] --> B2["Hash mod N partitions"]
    B2 --> B3["Partition fits in L2 or L3"]
    B3 --> B4["Access mostly within cache"]
    end

⚠️ Watch out: Over-partitioning has a real cost: every extra partition adds metadata and conditional branches. If your dataset already fits in L3 without partitioning, adding partitions only adds complexity with no measurable gain.

Your next step: compile this article’s latency.c program, run perf stat -M backend_bound_memory,retiring -- ./latency twice (sequential loop and scattered loop), and compare both percentages on your own machine.

Frequently Asked Questions

Why doesn’t a CPU at 100% reflect real RAM access time?

Because the operating system measures occupancy, not progress: a core with an assigned task shows as 100% even if that task is stalled waiting for a memory response. Only tools like perf stat distinguish between cycles that complete work and cycles that wait.

What’s the difference between the CPU cache hierarchy and RAM?

The cache hierarchy consists of several small, fast memory levels (L1, L2, L3) soldered directly onto the processor chip; RAM is external memory, much larger but between 50 and 100 times slower to access than the L1 cache.

How do I measure memory access speed on Linux?

With perf stat, using metric groups like backend_bound_memory and retiring, which show what percentage of the CPU’s execution slots were lost waiting on memory versus the ones that completed an instruction.

What does backend_bound_memory mean in perf stat?

It’s the percentage of execution slots where the CPU had an instruction pending completion but couldn’t move forward because it was waiting on a memory access. A high value, like the 50.1% Pivot measured on their naive GROUP BY, indicates the bottleneck is memory, not compute.

Do memory wait cycles affect all databases equally?

Not equally: columnar engines like ClickHouse or DuckDB mitigate the problem with vectorized, partitioned aggregation, while a naive GROUP BY implementation over an unpartitioned HashMap pays the full cost with datasets containing millions of unique keys.

Can memory wait cycles be eliminated entirely?

Not entirely: the physics of DRAM impose a floor of 50-100 ns per access that no software can avoid. What can be done is reducing how many times the program needs to make that trip, keeping the working set within L1, L2, or L3 for as long as possible.

References

• Pivot blog: original benchmark of a naive GROUP BY over the ClickBench “hits” dataset, with the perf stat counters cited in this article.
• Wikipedia: CPU cache: general explanation of the L1, L2, and L3 cache levels and their role in the memory hierarchy.
• Perf Wiki (kernel.org): official documentation for the perf tool and its hardware events.
• ClickHouse Docs: documentation for the columnar engine that uses vectorized, partitioned aggregation for GROUP BY.

📱 Enjoying this content? Follow @programacion on Telegram for daily tech content in Spanish: quick summaries, fresh content every day. @programacion

Featured image: Foto de Óscar Salgado en Unsplash