← Labscache-02Memory hierarchy●●○○

Working set — measure L1, L2, L3, DRAM and the TLB yourself

cache/02_working_set.cneeds: tools/bench.h, tools/pin.sh1 steps

0/1 steps

what this lab teaches

The classic pointer-chasing experiment: follow a random cyclic permutation through an array of size S, so every load depends on the previous one (no overlap, no prefetching), and plot ns per load against S. The steps in the curve ARE the memory hierarchy of this machine, and one of the steps is not a cache at all. WHY A RANDOM CYCLE (Sattolo's algorithm): a single cycle visiting every slot once, in random order. Sequential order would let the prefetcher hide everything; independent random loads would let out-of-order execution overlap them (lab 05). Dependent random loads measure LATENCY.

evidence to leave with

Staircase 2.4 / 4-12 / 24-82 / 128-184 ns matched to lscpu; the 8-16 MB step identified as page walks

first, get the code

run this

$ git clone https://github.com/adit4443ya/debug_labs.git && cd debug_labs

then build it

run this

$ cd cache && ./build.sh

produces bin/02_working_set

walk it, one step at a time

run this

$ ../tools/pin.sh -q ./bin/02_working_set

what it printed on the machine that wrote this lab

     bytes    slots    ns/load   P-core: L1d 48K, L2 1.25M, L3 18M (shared); dTLB ~96 entries, STLB 2048 = 8 MB reach
      4096      512       4.41   L1
      8192     1024       2.47   L1
     16384     2048       2.40   L1
     32768     4096       2.48   L1
     65536     8192       3.83   L2
    131072    16384       5.69   L2
    262144    32768       6.54   L2
    524288    65536       7.88   L2
   1048576   131072      11.89   L2
   2097152   262144      24.25   L3
   4194304   524288      40.83   L3
   8388608  1048576      82.39   L3
  16777216  2097152     119.32   L3 + page walks (beyond STLB reach)
  33554432  4194304     127.53   DRAM + page walks
  67108864  8388608     134.91   DRAM + page walks
 134217728 16777216     137.89   DRAM + page walks
 268435456 33554432     151.57   DRAM + page walks
 536870912 67108864     183.67   DRAM + page walks

how to read it

- 8 KiB..32 KiB: 2.4 ns = 5 cycles at ~2.1 GHz. L1 hit latency. (4 KiB shows 4.4 ns: a 512-slot cycle is so short the loop overhead and the first-iteration effects dominate; ignore the smallest point.) - 64 KiB..1 MiB: 3.8 -> 11.9 ns. L2 (1.25 MB on a P-core here). The rise inside L2 is the L1 dTLB running out (~96 entries x 4 KiB = 384 KB) and part of the accesses paying an L2 TLB lookup. - 2..8 MiB: 24 -> 82 ns. L3 latency is ~40-50 cycles (~20-25 ns), and you can see that at 2 MiB. Beyond that the number climbs far above any L3 latency because the STLB (2048 entries x 4 KiB = 8 MB of reach) is exhausted: every load now ALSO walks the page table, and the page-table entries themselves compete for cache. That is the step that is not a cache: it is virtual memory. - 32 MiB+: 128 -> 184 ns. DRAM latency (~100 ns) plus page walks that increasingly miss in cache too. The 512 MB point is the honest cost of a random dependent access in a large table on this laptop. Compare with `lscpu` / `getconf -a | grep CACHE`: L1d 48 KiB and L2 1.25 MB per P-core (getconf reports the E-core's 32 KiB / 2 MB cluster; lscpu sums both kinds), L3 18 MB shared. The curve found them without documentation. That is the point: you can characterize an unknown machine (a cloud instance, a phone SoC) in a minute with this program.

the rules

W1. "Fits in cache" is per level and per core; know your machine's numbers (run this on every new box before believing any benchmark). W2. A dependent random access costs ~130-180 ns here. Design structures so that the common path does one such access, not five (open addressing, flat arrays, B-trees over binary trees). W3. Beyond ~8 MB of random reach, 4 KiB pages cost a page walk per access; huge pages move that cliff to gigabytes (lab 06).

take it further

1. Pin to an E-core (`-c 8`) and rerun: different L1/L2 sizes appear. 2. `perf stat -e dTLB-load-misses:u,L1-dcache-load-misses:u,LLC-load-misses:u` at 1 MiB, 8 MiB and 64 MiB. Match each counter to a step of the curve. 3. Add `madvise(MADV_HUGEPAGE)` on the array (THP is `madvise` here) and watch the 16 MiB point drop toward true L3 latency. ============================================================

read the source · cache/02_working_set.c

#include "../tools/bench.h"
/* Build a random cyclic permutation over n 8-byte slots (Sattolo), then follow it. */
static void sattolo(uint64_t *p, size_t n, uint64_t *seed) {
    for (size_t i = 0; i < n; i++) p[i] = i;
    for (size_t i = n - 1; i > 0; i--) {
        size_t j = (size_t)(bench_rand(seed) % i);          /* j < i: guarantees ONE cycle */
        uint64_t t = p[i]; p[i] = p[j]; p[j] = t;
    }
}
int main(int argc, char **argv) {
    uint64_t loads = argc > 1 ? strtoull(argv[1], 0, 10) : 20000000ull;
    uint64_t seed = 0x1234567ull;
    printf("%10s %8s %10s   %s\n", "bytes", "slots", "ns/load", "P-core: L1d 48K, L2 1.25M, L3 18M (shared); dTLB ~96 entries, STLB 2048 = 8 MB reach");
    for (size_t bytes = 4096; bytes <= (512ull << 20); bytes *= 2) {
        size_t n = bytes / 8;
        uint64_t *p = (uint64_t *)malloc(bytes);
        sattolo(p, n, &seed);
        uint64_t idx = 0;
        for (uint64_t i = 0; i < n; i++) idx = p[idx];                /* warm the chain once */
        uint64_t t0 = bench_ns();
        for (uint64_t i = 0; i < loads; i++) idx = p[idx];
        uint64_t dt = bench_ns() - t0;
        BENCH_KEEP(idx);
        double ns = (double)dt / (double)loads;
        const char *lvl = bytes <= 49152 ? "L1" : bytes <= (1280u << 10) ? "L2" : bytes <= (8u << 20) ? "L3" : bytes <= (18u << 20) ? "L3 + page walks (beyond STLB reach)" : "DRAM + page walks";
        printf("%10zu %8zu %10.2f   %s\n", bytes, n, ns, lvl);
        free(p);
    }
    return 0;
}

◇

Finish the lab: write the evidence note

A lab is done when you can say what it showed on your machine — not when you have read it.