CS Fundamentals Trainer · Guides
The memory hierarchy and Big-O in practice
Cache lines and locality, why the same O(n) loop can be 18 times slower, row against column order, struct layouts, linked lists, branch prediction and when the constant factor beats the exponent, with measured C experiments.
36 min read
Big-O notation says how the work grows with the input: a hash lookup is O(1), a sort is O(n log n), a linked-list traversal is O(n). It is the right tool for choosing between a quadratic and a linearithmic algorithm. It is the wrong tool for choosing between two algorithms of the same order, and it can mislead at small sizes, because it hides a constant factor and, more importantly today, the fact that not all memory accesses cost the same. A load from the L1 cache takes about a nanosecond; a load from main memory takes over a hundred times longer. In this guide I measured both effects with small C and Python programs (code in the appendix) and drew out the rules that follow.
The machine was a two-core virtual server (Xeon at 2.1 GHz, 64-byte cache lines, a 48 KB L1 data cache and 2 MB L2 per core). Every number in this guide is specific to that machine and to how I ran the test: the processor model and its cache sizes, the memory speed, the hypervisor and the neighbours on the same host, the compiler version and flags, the operating system and the moment. Different hardware gives different absolute times, different positions for the steps in the latency table, and different ratios (a desktop CPU with a larger L2, a phone chip, or a server with different prefetching will disagree with several of them). Treat the shape of the results as the lesson (what grows, what stays flat, in which direction each effect points), not any single figure. The section "How much to trust these numbers" says how repeatable they were here and how to measure on your own machine.
1. The memory hierarchy
A CPU can do a few operations per nanosecond, but main memory (DRAM) cannot deliver data that fast. Computers bridge the gap with caches: small, fast memories between the CPU and RAM that hold copies of recently used data.
Diagram: Each level is bigger and slower than the one above
The unit of transfer is a cache line (64 bytes on most CPUs today). Reading one byte brings its whole line into the cache; the next 63 bytes then cost almost nothing. Programs are fast when they have locality: temporal (the same data again soon) and spatial (data near what was just used). The hardware also prefetches: when it sees accesses moving through memory in a regular pattern, it starts loading the next lines before the program asks for them.
Measuring the hierarchy
To measure the latency of each level, I built a randomly shuffled cycle through an array and followed it: each load needs the previous one's result, so the CPU cannot overlap them or prefetch. The time per step, as the array grows:
| Array size | Time per dependent load | It fits in |
|---|---|---|
| 16 KB | 1.9 ns | L1 |
| 64 KB | 3.1 ns | between L1 and L2 |
| 256 KB | 5.5 ns | L2 |
| 1 MB | 8 ns | L2 |
| 4 MB | 24 ns | L3 |
| 16 MB | 48 ns | L3 |
| 64 MB | 135 ns | mostly main memory |
| 256 MB | 140 ns | main memory |
The steps in the table are the cache levels: each time the working set outgrows a level, the latency jumps. Reading from main memory was about 70 times slower than from L1. (The virtual machine reports a very large L3 (260 MB) shared with other tenants of the host, so the last step appears late, and the amount of L3 this program really gets depends on what the neighbours are doing. On your own computer the steps will be at different sizes.) The practical meaning is that the speed of a loop depends on the size of the data it touches as much as on how many steps it does.
2. Sequential against random: the same Big-O, 18 times apart
I summed 64 million integers (256 MB) twice. Both loops do exactly 64 million additions, so both are O(n):
| Access pattern | Time | Per element |
|---|---|---|
| in order | 43 ms | 0.64 ns |
| in a random order (through an index array) | 762 ms | 11.4 ns |
The random order was about 18 times slower for the same number of operations. In order, each cache line brought in serves 16 integers and the prefetcher stays ahead of the loop; at random, almost every access is a cache miss that has to wait for memory. The memory system can overlap several independent misses, which is why 11 ns is less than the 140 ns latency above, but it cannot hide them.
Stride: paying for the whole line
To see the cache line itself, I touched the same number of array elements with a growing step (stride), in a 256 MB array:
| Stride (ints) | 1 | 2 | 4 | 8 | 16 | 32 | 64 |
|---|---|---|---|---|---|---|---|
| Time per access | 1.6 ns | 1.8 ns | 2.6 ns | 4.2 ns | 6.4 ns | 9.2 ns | 11.1 ns |
At a stride of 1 the next access is almost always in a line already loaded. As the stride grows, more accesses need a new line, until at 16 ints (64 bytes) every access touches its own line. The cost continues to rise beyond that, because larger strides also cross pages and defeat the prefetcher and the address-translation cache (see operating systems on pages and the TLB). The point: using one int out of every cache line is paying for sixteen.
Step through a small cache, with an array laid out contiguously and with the same elements scattered, and watch which accesses hit:
Interactive animation: cache lines
With 64-byte lines holding 8 elements each, the 24 accesses in order had 3 misses (13%), one per line; in the scattered layout, all 24 missed. This is the whole story of this section in miniature.
3. Data layout is an algorithm choice
Row-major against column-major
A two-dimensional array in C, Go, Rust or Java is stored row after row. Walking along a row touches consecutive addresses; walking down a column jumps by a whole row each time. For a 4096 by 4096 matrix of integers (64 MB), the sum over rows first took 10 ms and over columns first 133 ms, 13 times as long, with identical arithmetic. Loop order is not a micro-optimisation: it can be the dominant cost. (Fortran, R and MATLAB store columns first, so the advice flips with the language.) Blocked or "tiled" algorithms for matrix multiplication and image processing exist for exactly this reason: they reorder the work so that a small block of data stays in the cache while it is reused.
Array of structs against struct of arrays
Suppose you have 8 million records of 64 bytes each and need to sum one 4-byte field:
| Layout | Time |
|---|---|
| array of 64-byte structs | 32.5 ms |
| a separate array holding only that field | 5.0 ms |
The struct layout loads 64 bytes (a whole line) for every 4 bytes it uses, so it moves 16 times as much data and takes about 6.5 times as long. A struct-of-arrays (columnar) layout keeps each field contiguous. It is the idea behind columnar databases and analytics formats such as Parquet, and behind entity-component systems in games: when queries touch a few columns of many rows, store columns together. When you read whole records one at a time, the row layout is better, which is the same trade-off as between row stores and column stores in databases.
Linked lists
A linked list is O(n) to traverse, and so is an array. I built a list of 4 million nodes (64 MB) and traversed it five times, with the nodes laid out in order in memory and then with the same list scattered:
| Layout in memory | Per node |
|---|---|
| nodes allocated in order | 3.4 ns |
| nodes scattered | 130 ns |
The scattered list was about 38 times slower, and each load waits for the previous one, which is the pointer-chasing case from the first table. A list built by allocating nodes one after another often happens to be in order at first and gets scattered as the program runs, deletes and reallocates. Even the ordered list was slower than the array sum (3.4 ns against 0.64 ns), because each node is 16 bytes with a pointer and the loop is serialised by the dependency. This is why the default sequence in most languages is a dynamic array (ArrayList, Vec, slice, std::vector), why LinkedList has so few uses, and why "insert in the middle is O(1) with a list but O(n) with an array" often loses in practice: finding the position costs a traversal anyway, and below some size shifting a contiguous block is cheaper than chasing pointers.
When contiguous data is not the answer
The measurements above are all about reading. Layout advice depends on how the data is used and, above all, how it changes:
- Inserting or deleting in the middle of a large array moves everything after it. I measured inserting at a random position of an
intarray withmemmove, and the same insertion in a linked list whose nodes are scattered in memory:
| Elements | Array: insert at a random position | List: walk to the position, then insert | List: insert after a node you already hold |
|---|---|---|---|
| 1,000 | 37 ns | 0.9 µs | 24 ns |
| 16,000 | 0.5 µs | 48 µs | 30 to 40 ns |
| 256,000 | 12 µs | 4.2 ms | 75 to 100 ns |
| 1,024,000 | 74 to 87 µs | 61 to 69 ms | 100 to 120 ns |
When you must find the position first, the array wins by a wide margin at every size (the memmove runs at memory bandwidth, the list walk is a chain of cache misses), which is why "O(1) insertion" in a list so rarely pays. But once the array reaches hundreds of thousands of elements, each insertion costs tens of microseconds and grows linearly, and when you already hold the node (an LRU cache, where a hash table gives you the entry and a doubly linked list moves it to the front; a scheduler's queue; an intrusive list in a kernel) the list's insertion stays at about 0.1 µs while the array's keeps growing. The right comparison is the whole operation with its real access pattern, at your sizes.
- Growing a contiguous block can move it. A dynamic array that doubles when full copies all its elements, and invalidates every pointer and reference into it. If other code holds addresses of elements (observers, graphs with edges, handles), you need stable storage: a list or a deque, a pool or an arena with indexes instead of pointers, or a chunked structure. Appends are amortised O(1), but one append can cost a full copy, which matters for latency-sensitive code.
- Ordered data with frequent inserts needs a structure, not a sorted array. A balanced tree, a skip list or a B-tree keeps keys ordered with O(log n) insertion; the B-tree is the compromise in this guide's own theme, with wide nodes holding sorted arrays so that each step reads a few cache lines. For keyed lookup without order, a hash table beats scanning an array once n is more than a few dozen.
- Struct-of-arrays has a cost on writes and on code. Updating or moving a whole record touches several arrays (several cache lines instead of one), adding or deleting a record means keeping every array in step, and the code is harder to read. Keep array-of-structs when you read and write whole records, or when records are few.
- Concurrent writers. Contiguous structures shared between threads suffer from false sharing (two threads writing different elements on the same cache line invalidate each other's cache) and from coarse locks; per-thread data, padding, or structures designed for concurrency can matter more than the layout of a single-threaded scan.
- Very large, sparse or variable-length data. A mostly-empty table, strings of many different lengths and nested documents are not served by a plain flat array; compressed, sparse or columnar-with-dictionary formats are, and some of the gain is in reading fewer bytes, not in contiguity.
- Small data. Under a few dozen elements the layout rarely matters; clarity wins.
4. Branches: the other hidden cost
Modern CPUs run ahead by predicting which way each if goes. A correct prediction is cheap, but not free: the branch still occupies an instruction slot and a place in the predictor's tables, a taken branch can limit how many instructions are fetched in a cycle, a hot loop with many branches can overflow the predictor so that different branches interfere with each other (aliasing), and the work done on the predicted path depends on speculation that the CPU must be able to track and, if it is wrong, undo. A wrong prediction throws away the work in progress and costs roughly 10 to 20 cycles (the exact figure depends on the CPU's pipeline). So the 5.6-fold difference below measures mispredictions; it does not mean that predictable branches cost nothing, and a branch-free formulation can be slightly faster even when the branch would be predicted well (and slower when it would not, since it does the work of both sides). I summed the bytes that are at least 128 over 32 million random bytes, four times, first on random data and then on the same data sorted:
| Data | Time |
|---|---|
| random order | 693 ms |
| sorted | 124 ms |
The sorted data was 5.6 times faster, with identical work, because the branch is then true for a long run and false for a long run, and the predictor is almost always right (still not free, only cheap); on random data it is wrong about half the time. (To make the test about branches, I forced the compiler to keep the branch with an empty asm statement. Without it, an optimising compiler would typically turn the condition into branch-free code and show no difference. This is a reminder that micro-benchmarks need care.) The consequence for design is mild but real: data-dependent branches in a hot loop of unpredictable data are expensive, and sorted, partitioned or batched data helps.
5. When Big-O and the constants disagree
Small inputs
For small n, the constant factor decides. I searched a sorted array of integers with a linear scan and with a binary search (O(n) against O(log n)), at random positions:
| n | Linear scan | Binary search |
|---|---|---|
| 4 | 9 ns | 14 ns |
| 16 | 15 ns | 27 ns |
| 64 | 30 ns | 41 ns |
| 256 | 77 ns | 57 ns |
| 1,024 | 206 ns | 77 ns |
| 16,384 | 3,043 ns | 102 ns |
| 262,144 | 52,484 ns | 157 ns |
| 1,048,576 | 215,391 ns | 245 ns |
Below roughly 100 elements the "worse" algorithm wins, because a linear scan has predictable branches and perfect locality, while binary search has an unpredictable branch at every step. Above a few hundred elements, the O(log n) algorithm wins by a growing margin: at a million elements it is nearly a thousand times faster. Standard libraries encode this knowledge: sort routines switch to insertion sort for small partitions, and B-trees use wide nodes searched linearly or with a small binary search inside the node, because a node is sized to fit a few cache lines (or a disk page).
The same effect in Python, where the interpreter overhead is large and the lookup is done in C: a k in list costs 35 ns for 2 elements and 360 ns for 64, while k in set stays at 30 to 40 ns for any size (500,000 ns for a list of 100,000 against 38 ns for the set). Building a set of 1,000 items costs 8.6 µs, about two scans of the list, so the set pays for itself after about two lookups. For a handful of items the list is fine; the lesson is not "always use a set" but "know how many lookups and how many elements".
Big-O hides the constant, the language and the layout
An algorithm with a better exponent can lose for realistic n if it has big constants or poor locality (fast matrix multiplication algorithms, many tree structures, hash maps with chaining against open addressing). And the language multiplies the constants: in the Python test, summing 10 million integers in a list took 63 ms and in an array('q') 111 ms, because the array has to create a Python integer for each element it yields; the array saves memory (it is 81 MB against 80 MB of pointers plus 28 bytes for every integer object, so a Python list of integers costs over 350 MB in total) but not time. The cache effects in this guide are measured in C because Python's overhead would mask them; in Python, the equivalent is to push loops into libraries written in C (NumPy, built-ins) which then enjoy the contiguous layout.
6. How much to trust these numbers
A single run of a benchmark gives one sample of a noisy quantity. To see how noisy, I ran the whole C program five times in a row on the same machine and compared the results:
| Quantity | Lowest | Median | Highest |
|---|---|---|---|
| Sequential against random sum, ratio | 15.6 | 19.0 | 20.6 |
| Row-first against column-first, ratio | 10.5 | 12.3 | 12.6 |
| Array of structs against one field array, ratio | 6.3 | 6.5 | 7.4 |
| Sorted against random branch data, ratio | 5.0 | 5.7 | 5.8 |
| Scattered against ordered list, ratio | 39.4 | 40.5 | 41.8 |
| Load from L1-sized array (16 KB), ns | 1.8 | 1.8 | 2.8 |
| Load from a 256 MB array, ns | 152 | 154 | 156 |
So the run-to-run spread on one machine was about 3% to 60% of the median depending on the measurement (the short L1 and sequential-sum measurements, which last only a few milliseconds, are the least stable), and the ratios in the text (18, 13, 6.5, 5.6, 38) are single runs that sit within or near these ranges but are not the medians. They would also move with a different machine, and the conclusions would not. A fair way to report the results is the median and the range over several runs, never one number.
How to benchmark so that the result means something
- Warm up, then measure. The first run pays for page faults on fresh memory (the operating systems guide shows 65,536 of them for 256 MB), cold caches and, in managed languages, JIT compilation (see compilers and runtimes). Run the work once or more before timing it, and report separately if the cold start is what you care about.
- Repeat and look at the spread. Run each measurement many times (at least 5 to 30, more when the variance is high), report the median or a percentile with the range, and discard nothing silently. Compare two variants with interleaved runs (A, B, A, B) so that a slow period of the machine affects both.
- State the compiler and its flags.
-O0,-O2,-O3,-march=native, link-time optimisation and the compiler version change the results, sometimes by removing the thing you wanted to measure (a loop whose result is unused, a branch turned into a conditional move, a computation moved out of the loop). Use the result (a checksum printed at the end), inspect the generated assembly (gcc -S, a disassembler) for the hot loop, and use barriers only when you have understood what they hide. My branch test deliberately forces the branch with an emptyasmstatement; without it the effect disappears. - Control the CPU. Frequency scaling and turbo boost make a CPU faster when it is cool and idle and slower when it is hot or busy, and the clock changes during a run. Where you control the machine, set the performance governor, disable turbo or note it, and let the machine warm up. On a virtual machine you cannot (my runs have no frequency control at all).
- Isolate the measurement. Pin the process to one core (
taskset), keep other work off it (and off its hyper-threading sibling), stop background jobs, and prefer a machine with a quiet neighbour; on shared cloud hosts the neighbours' cache and memory use is part of your result, which is one reason for the spread above. Disable address-space randomisation and fix the allocator only when you need exactly repeatable layouts. - Control the data. Use realistic sizes (the cache effects appear when the data outgrows each level), initialise memory before timing (untouched memory may all map to one zero page), keep alignment and the order of allocation in mind, and note whether transparent huge pages are on, since they change the address-translation cost.
- Check the explanation with counters. If you claim "cache misses", measure them:
perf stat -e cache-misses,branch-misses,instructions,cycleson Linux shows whether the hypothesis holds. A speed difference without the matching counter difference may have another cause. - Record the environment (CPU model, memory, kernel, compiler and flags, the date) next to the numbers, so that someone can tell later why they do not reproduce, and test the conclusion on the real workload and not only on a micro-benchmark: a loop that is 10 times faster in isolation matters only if it is a large share of the program's time.
7. Rules of thumb
- Choose the algorithm by Big-O first, then think about memory behaviour. An O(n²) approach on 100,000 elements will not be saved by cache friendliness.
- Prefer contiguous data for read-heavy and scan-heavy work: arrays and vectors over linked structures, columns over records when scanning a few fields, flat structures over pointer-heavy trees for hot paths. This is a default for traversal, not a law for every workload; "When contiguous data is not the answer" below says when the cost of changing the data, the need for stable references or the access pattern points elsewhere.
- Walk memory in order. Loop in the order the data is stored, process in blocks that fit in cache, and sort or group work so that accesses are near each other.
- Keep the hot data small. Smaller types, a
structwithout unused fields, an index ofint32whereint64is not needed: more records per cache line and more of them in cache. - Avoid unpredictable branches in the hottest loops when you can, by sorting, partitioning or using arithmetic in place of an
if, but only after you have measured that it matters. Predictable branches are cheap, not free, and a branch-free version is not always faster. - Do less work per element before doing it faster: batching, early exit and filtering before computing remove misses entirely.
- Measure. Use a profiler and hardware counters (
perf statshows cache misses and branch mispredictions on Linux), benchmark with realistic sizes and data, repeat runs, and beware compilers that optimise away what you wanted to measure.
The same ideas one level up
The hierarchy continues beyond the CPU: RAM to SSD is another factor of a thousand, and disk to network another. That is why the same principles show up in systems design: database indexes are B-trees with nodes sized to a disk page; caching strategies put hot data in a faster, smaller tier; the swap and page-cache behaviour in operating systems is the same working-set story; search indexes compress posting lists to read fewer bytes; and observability tells you which level is slow in production.
8. Common mistakes
- Stating complexity without saying what n is, or ignoring that the constant can dominate at the sizes you have.
- Replacing an array with a linked list "because insertion is O(1)".
- Iterating a 2D array in the wrong order, or a column store row by row.
- Optimising a loop that is not on the hot path; measure first.
- Benchmarking with data that fits in cache and then running on data that does not (or the reverse).
- Believing a micro-benchmark that the compiler may have deleted, or whose first run included loading the data.
- Treating hash maps as always O(1) with no cost: each lookup is typically at least one cache miss on a large table.
- Quoting one benchmark number as a fact, without the machine, the compiler flags, the number of runs and the spread.
- Turning every collection into a flat array without asking how it is modified: large middle insertions, stable references and concurrent writers can change the answer.
9. Things to mention in an interview
- That Big-O is about growth, not speed, and that the memory hierarchy adds a factor of 100 between L1 and RAM.
- Cache lines and locality (spatial and temporal), with the example of row-major against column-major traversal.
- Why arrays beat linked lists in practice, and when that changes.
- Array of structs against struct of arrays, and the link to columnar storage.
- Branch prediction and the sorted-array example.
- That small inputs can favour the "worse" algorithm, and that real libraries switch strategies by size.
- That you would profile before optimising, and what you would look at (cache misses, branch mispredictions).
- How you would benchmark properly: warm-up, repetitions with the median and the range, interleaved comparison, compiler flags and checked assembly, CPU frequency and isolation, counters to confirm the cause.
- When contiguous data is not the right choice (large insertions in the middle, stable pointers, ordered keys, concurrent writes) and that a correctly predicted branch is cheap, not free.
Quick recap
- A memory access costs from about 2 ns (L1) to about 140 ns (RAM) in the test, a factor of 70; cache lines of 64 bytes are what move.
- The same O(n) sum was 18 times slower in random order; a matrix walked column-first was 13 times slower; a scattered linked list was 38 times slower than an ordered one; a struct layout cost 6.5 times when only one field was needed.
- Predictable branches are cheap, not free, and mispredicted ones matter: sorted data ran 5.6 times faster for the same work.
- These are results from one virtual machine: five repeated runs gave ratios that varied by about 5% to 25% of their median, and other hardware will differ more. Report medians and ranges, and measure on your own machine and workload.
- Contiguous layouts win for scans and lookups, but not for every workload: inserting in the middle of a million-element array cost about 80 µs, against about 0.1 µs when you already hold a list node; stable references, ordered keys and concurrent writers can decide otherwise.
- For small n the simpler algorithm wins (linear scan beat binary search up to roughly 100 elements); for large n the better Big-O wins by orders of magnitude.
- Use Big-O to choose the algorithm and the memory hierarchy to choose the layout, and measure before optimising.
Appendix: the experiment code
The C program was compiled with gcc -O2 and run on a small two-core virtual server; it takes about half a minute and needs about 800 MB of memory. The tables in this guide come from single runs; five repeated runs (section 6) varied from a few percent to about 60 percent of the median depending on the measurement, and the results differ a lot between machines, so the table values above are rounded and the ratios are the lesson. The program does not pin the process to a core, control the CPU frequency or report its own variance, so these controls are exactly what you should add when you rerun it. Two details matter for a fair test: the arrays are written before they are read (memory that has only been allocated may all map to one shared zero page, which makes every access fast), and the branch test uses an empty asm statement to stop the compiler from replacing the branch with branch-free code. The Python script measures the interpreter, where the cache effects are mostly hidden by the interpreter's own overhead.
Cache levels, access order, layout and branches (C)
// gcc -O2 -o mem mem.c
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>
static double now(void) { struct timespec t; clock_gettime(CLOCK_MONOTONIC, &t); return t.tv_sec + t.tv_nsec * 1e-9; }
static uint64_t rng = 88172645463325252ULL;
static uint64_t xr(void) { rng ^= rng << 13; rng ^= rng >> 7; rng ^= rng << 17; return rng; }
// 1. pointer chasing through a random cycle: every load depends on the previous one
static double chase(size_t bytes) {
size_t n = bytes / sizeof(size_t);
size_t *next = malloc(n * sizeof(size_t)), *perm = malloc(n * sizeof(size_t));
for (size_t i = 0; i < n; i++) perm[i] = i;
for (size_t i = n - 1; i > 0; i--) { size_t j = xr() % (i + 1); size_t t = perm[i]; perm[i] = perm[j]; perm[j] = t; }
for (size_t i = 0; i < n; i++) next[perm[i]] = perm[(i + 1) % n]; // one cycle through all slots
size_t steps = 20000000, p = 0; double t0 = now();
for (size_t i = 0; i < steps; i++) p = next[p];
double dt = now() - t0; volatile size_t sink = p; (void)sink; free(next); free(perm);
return dt / steps * 1e9;
}
// 2. summing 64M ints: in order, or in a random order
static void seq_vs_random(void) {
size_t n = 64u << 20; int *a = malloc(n * sizeof(int)); size_t *idx = malloc(n * sizeof(size_t));
for (size_t i = 0; i < n; i++) { a[i] = (int)i; idx[i] = i; }
for (size_t i = n - 1; i > 0; i--) { size_t j = xr() % (i + 1); size_t t = idx[i]; idx[i] = idx[j]; idx[j] = t; }
long s = 0; double t0 = now(); for (size_t i = 0; i < n; i++) s += a[i]; double t1 = now();
for (size_t i = 0; i < n; i++) s += a[idx[i]]; double t2 = now();
printf("sum of %zu ints (%zu MB): in order %.0f ms (%.2f ns each), random order %.0f ms (%.2f ns each), ratio %.1fx [%ld]\n",
n, n * 4 >> 20, (t1 - t0) * 1e3, (t1 - t0) / n * 1e9, (t2 - t1) * 1e3, (t2 - t1) / n * 1e9, (t2 - t1) / (t1 - t0), s % 7);
free(a); free(idx);
}
// 3. stride: touch every k-th int of a 256 MB array, the same number of touches each time
static void stride(void) {
size_t n = 64u << 20; int *a = malloc(n * sizeof(int)); for (size_t i = 0; i < n; i++) a[i] = (int)i; long s = 0; // written first: untouched calloc pages would all share one zero page
printf("stride (ints) : ");
for (size_t k = 1; k <= 256; k *= 2) {
size_t touches = 8u << 20; double t0 = now(); size_t i = 0;
for (size_t r = 0; r < touches; r++) { s += a[i]; i += k; if (i >= n) i -= n; }
printf("%zu:%.2fns ", k, (now() - t0) / touches * 1e9);
}
printf("[%ld]\n", s); free(a);
}
// 4. matrix: row by row against column by column
static void matrix(void) {
size_t N = 4096; int *m = malloc(N * N * sizeof(int)); for (size_t i = 0; i < N * N; i++) m[i] = 1; long s = 0;
double t0 = now(); for (size_t r = 0; r < N; r++) for (size_t c = 0; c < N; c++) s += m[r * N + c];
double t1 = now(); for (size_t c = 0; c < N; c++) for (size_t r = 0; r < N; r++) s += m[r * N + c];
double t2 = now();
printf("%zux%zu ints: row by row %.0f ms, column by column %.0f ms, ratio %.1fx [%ld]\n", N, N, (t1 - t0) * 1e3, (t2 - t1) * 1e3, (t2 - t1) / (t1 - t0), s % 7); free(m);
}
// 5. array of structs against struct of arrays, when only one field is needed
typedef struct { int id; int x; double pad[6]; } Rec; // 64 bytes per record
static void aos_soa(void) {
size_t n = 8u << 20; Rec *r = malloc(n * sizeof(Rec)); int *xs = malloc(n * sizeof(int));
for (size_t i = 0; i < n; i++) { r[i].id = (int)i; r[i].x = 1; xs[i] = 1; }
long s = 0; double t0 = now(); for (size_t i = 0; i < n; i++) s += r[i].x; double t1 = now();
for (size_t i = 0; i < n; i++) s += xs[i]; double t2 = now();
printf("sum one field of %zu records: array of 64-byte structs %.1f ms, separate int array %.1f ms, ratio %.1fx [%ld]\n", n, (t1 - t0) * 1e3, (t2 - t1) * 1e3, (t1 - t0) / (t2 - t1), s % 7);
}
// 6. a linked list laid out in memory order against the same list shuffled in memory
typedef struct Node { struct Node *next; long v; } Node;
static void lists(void) {
size_t n = 4u << 20; Node *pool = malloc(n * sizeof(Node)); size_t *ord = malloc(n * sizeof(size_t));
for (size_t i = 0; i < n; i++) ord[i] = i;
for (int shuffled = 0; shuffled < 2; shuffled++) {
if (shuffled) for (size_t i = n - 1; i > 0; i--) { size_t j = xr() % (i + 1); size_t t = ord[i]; ord[i] = ord[j]; ord[j] = t; }
for (size_t i = 0; i < n; i++) { pool[ord[i]].v = 1; pool[ord[i]].next = i + 1 < n ? &pool[ord[i + 1]] : NULL; }
long s = 0; double t0 = now(); for (int rep = 0; rep < 5; rep++) for (Node *p = &pool[ord[0]]; p; p = p->next) s += p->v;
double dt = now() - t0; printf("traverse a list of %zu nodes (%zu MB) x5: nodes %s in memory %.0f ms (%.2f ns per node) [%ld]\n", n, n * sizeof(Node) >> 20, shuffled ? "scattered" : "in order", dt * 1e3, dt / (5.0 * n) * 1e9, s % 7);
}
}
// 7. branch prediction: count values >= 128 in unsorted and in sorted data
static int cmp(const void *a, const void *b) { return *(const unsigned char *)a - *(const unsigned char *)b; }
static void branches(void) {
size_t n = 32u << 20; unsigned char *d = malloc(n); for (size_t i = 0; i < n; i++) d[i] = xr() & 255; long c = 0;
double t0 = now(); for (int r = 0; r < 4; r++) for (size_t i = 0; i < n; i++) { if (d[i] >= 128) { c += d[i]; asm volatile("" ::: "memory"); } }
double t1 = now(); qsort(d, n, 1, cmp); double t2 = now();
for (int r = 0; r < 4; r++) for (size_t i = 0; i < n; i++) { if (d[i] >= 128) { c += d[i]; asm volatile("" ::: "memory"); } }
double t3 = now(); printf("conditional sum over %zu random bytes x4: unsorted %.0f ms, sorted %.0f ms, ratio %.1fx [%ld]\n", n, (t1 - t0) * 1e3, (t3 - t2) * 1e3, (t1 - t0) / (t3 - t2), c % 7);
}
// 8. linear scan against binary search in a sorted array, by size
static int lin(const int *a, int n, int x) { int i = 0; while (i < n && a[i] < x) i++; return i; }
static int bin(const int *a, int n, int x) { int lo = 0, hi = n; while (lo < hi) { int m = (lo + hi) / 2; if (a[m] < x) lo = m + 1; else hi = m; } return lo; }
static void search(void) {
printf("search in sorted ints, ns per lookup (linear / binary): ");
for (int n = 4; n <= 1 << 20; n *= 4) {
int *a = malloc(n * sizeof(int)); for (int i = 0; i < n; i++) a[i] = 2 * i;
int q = 200000; int *k = malloc(q * sizeof(int)); for (int i = 0; i < q; i++) k[i] = (int)(xr() % (2 * n));
long s = 0; double t0 = now(); for (int i = 0; i < q; i++) s += lin(a, n, k[i]); double t1 = now();
for (int i = 0; i < q; i++) s += bin(a, n, k[i]); double t2 = now();
printf("n=%d: %.0f/%.0f ", n, (t1 - t0) / q * 1e9, (t2 - t1) / q * 1e9); if (s == 42) putchar(' '); free(a); free(k);
if (n >= 1 << 14) { }
}
printf("\n");
}
int main(void) {
printf("pointer chasing, ns per dependent load:\n");
size_t sizes[] = {16u<<10, 32u<<10, 64u<<10, 256u<<10, 1u<<20, 2u<<20, 4u<<20, 16u<<20, 64u<<20, 256u<<20};
for (int i = 0; i < 10; i++) printf(" %6zu KB: %6.2f ns\n", sizes[i] >> 10, chase(sizes[i]));
seq_vs_random(); stride(); matrix(); aos_soa(); lists(); branches(); search();
return 0;
}
Big-O against constant factors in Python
import timeit, random, bisect
# 1. membership: list (O(n)) against set (O(1) average), by size; the key is found at the end of the list
print("x in list / x in set, ns per lookup (key at the end of the list):")
for n in (2, 4, 8, 16, 64, 1000, 100000):
data = list(range(n)); s = set(data); k = n - 1
tl = min(timeit.repeat(lambda: k in data, number=20000, repeat=5)) / 20000 * 1e9
ts = min(timeit.repeat(lambda: k in s, number=20000, repeat=5)) / 20000 * 1e9
print(f" n={n:>6}: list {tl:>9.0f} set {ts:>5.0f}")
# 2. the cost of building the set: when a lookup structure pays off
n = 1000; data = list(range(n))
build = min(timeit.repeat(lambda: set(data), number=2000, repeat=5)) / 2000 * 1e6
scan = min(timeit.repeat(lambda: (n - 1) in data, number=2000, repeat=5)) / 2000 * 1e6
print(f"building a set of {n} items takes {build:.1f} us; one worst-case scan of the list takes {scan:.1f} us, so the set wins after about {build/scan:.0f} lookups")
# 3. the same sum over a list of Python ints and over a list of floats from an array: the constant factors of the language
import array, sys
n = 10_000_000; lst = list(range(n)); arr = array.array("q", range(n))
t1 = min(timeit.repeat(lambda: sum(lst), number=1, repeat=3)); t2 = min(timeit.repeat(lambda: sum(arr), number=1, repeat=3))
print(f"sum of {n} ints: list {t1*1e3:.0f} ms ({sys.getsizeof(lst)//1_000_000} MB of pointers plus {sys.getsizeof(5)} bytes per int object), array('q') {t2*1e3:.0f} ms ({sys.getsizeof(arr)//1_000_000} MB)")
Inserting in the middle: an array against a list (C)
// mutation.c: inserting in the middle: a contiguous array (memmove) against a linked list, as the collection grows.
// gcc -O2 -o mutation mutation.c
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>
static double now(void) { struct timespec t; clock_gettime(CLOCK_MONOTONIC, &t); return t.tv_sec + t.tv_nsec * 1e-9; }
static uint64_t rng = 88172645463325252ULL;
static uint64_t xr(void) { rng ^= rng << 13; rng ^= rng >> 7; rng ^= rng << 17; return rng; }
typedef struct Node { int v; struct Node *next; } Node;
int main(void) {
printf("%10s %28s %34s %30s\n", "n", "array: insert at random pos", "list: find pos by walking + insert", "list: insert at a known node");
for (size_t n = 1000; n <= 4000000; n *= 4) {
int *a = malloc((n + 1000) * sizeof(int)); for (size_t i = 0; i < n; i++) a[i] = (int)i;
int reps = n < 100000 ? 2000 : 200; size_t len = n;
double t0 = now();
for (int r = 0; r < reps; r++) { size_t p = xr() % len; memmove(a + p + 1, a + p, (len - p) * sizeof(int)); a[p] = -1; len++; if (len >= n + 1000) len = n; }
double ta = (now() - t0) / reps;
// a list whose nodes are scattered in memory (as after many allocations and frees)
Node **nodes = malloc(n * sizeof(Node *)); for (size_t i = 0; i < n; i++) nodes[i] = malloc(sizeof(Node));
for (size_t i = n - 1; i > 0; i--) { size_t j = xr() % (i + 1); Node *t = nodes[i]; nodes[i] = nodes[j]; nodes[j] = t; }
for (size_t i = 0; i < n; i++) { nodes[i]->v = (int)i; nodes[i]->next = i + 1 < n ? nodes[i + 1] : NULL; }
int lreps = n < 100000 ? 500 : 20;
t0 = now();
for (int r = 0; r < lreps; r++) { size_t p = xr() % n; Node *x = nodes[0]; for (size_t k = 0; k < p; k++) x = x->next; Node *nn = malloc(sizeof(Node)); nn->v = -1; nn->next = x->next; x->next = nn; }
double tl = (now() - t0) / lreps;
t0 = now(); int kreps = 100000;
for (int r = 0; r < kreps; r++) { Node *x = nodes[xr() % n]; Node *nn = malloc(sizeof(Node)); nn->v = -1; nn->next = x->next; x->next = nn; }
double tk = (now() - t0) / kreps;
printf("%10zu %25.0f ns %31.0f ns %27.0f ns\n", n, ta * 1e9, tl * 1e9, tk * 1e9);
free(a);
}
return 0;
}
Compile with gcc -O2 -o mutation mutation.c. The times are per insertion, averaged over 20 to 100,000 insertions depending on the size, from two runs on the same virtual machine; they vary by several percent.
Sources
- Ulrich Drepper, What Every Programmer Should Know About Memory (2007), still the best long explanation of caches, TLBs and prefetching.
- Randal Bryant and David O'Hallaron, Computer Systems: A Programmer's Perspective, chapter 6 on the memory hierarchy and locality.
- John Hennessy and David Patterson, Computer Architecture: A Quantitative Approach, the chapters on memory hierarchy design.
- Jeff Dean's widely copied "latency numbers every programmer should know" list, and Colin Scott's interactive version over the years, for orders of magnitude; real values depend on the hardware.
- The Stack Overflow question Why is processing a sorted array faster than processing an unsorted array? for the branch-prediction experiment.
- Linux
perfdocumentation for measuring cache misses and branch mispredictions.
Practise this topic: CS Fundamentals