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 sizeTime per dependent loadIt fits in
16 KB1.9 nsL1
64 KB3.1 nsbetween L1 and L2
256 KB5.5 nsL2
1 MB8 nsL2
4 MB24 nsL3
16 MB48 nsL3
64 MB135 nsmostly main memory
256 MB140 nsmain 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 patternTimePer element
in order43 ms0.64 ns
in a random order (through an index array)762 ms11.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)1248163264
Time per access1.6 ns1.8 ns2.6 ns4.2 ns6.4 ns9.2 ns11.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:

LayoutTime
array of 64-byte structs32.5 ms
a separate array holding only that field5.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 memoryPer node
nodes allocated in order3.4 ns
nodes scattered130 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:

ElementsArray: insert at a random positionList: walk to the position, then insertList: insert after a node you already hold
1,00037 ns0.9 µs24 ns
16,0000.5 µs48 µs30 to 40 ns
256,00012 µs4.2 ms75 to 100 ns
1,024,00074 to 87 µs61 to 69 ms100 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.

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:

DataTime
random order693 ms
sorted124 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:

nLinear scanBinary search
49 ns14 ns
1615 ns27 ns
6430 ns41 ns
25677 ns57 ns
1,024206 ns77 ns
16,3843,043 ns102 ns
262,14452,484 ns157 ns
1,048,576215,391 ns245 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:

QuantityLowestMedianHighest
Sequential against random sum, ratio15.619.020.6
Row-first against column-first, ratio10.512.312.6
Array of structs against one field array, ratio6.36.57.4
Sorted against random branch data, ratio5.05.75.8
Scattered against ordered list, ratio39.440.541.8
Load from L1-sized array (16 KB), ns1.81.82.8
Load from a 256 MB array, ns152154156

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

7. Rules of thumb

  1. 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.
  2. 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.
  3. 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.
  4. Keep the hot data small. Smaller types, a struct without unused fields, an index of int32 where int64 is not needed: more records per cache line and more of them in cache.
  5. 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.
  6. Do less work per element before doing it faster: batching, early exit and filtering before computing remove misses entirely.
  7. Measure. Use a profiler and hardware counters (perf stat shows 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

9. Things to mention in an interview

Quick recap

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

Practise this topic: CS Fundamentals

More guides