what this lab teaches

Memory does not move bytes; it moves 64-byte LINES. The same number of accesses costs 8x more when each access lands on a different line, and 4x more again when each lands on a different 4 KiB page. This lab walks a 256 MB array with strides from 1 byte to 8 KiB, doing the SAME number of loads (32M) each time, and reports ns per access.

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/01_stride

walk it, one step at a time

run this

$ ../tools/pin.sh -q ./bin/01_stride

what it printed on the machine that wrote this lab

    stride    ns/access line-traffic MB/s   note
         1        0.563           1777   several accesses per 64-byte line
         2        0.572           3494   several accesses per 64-byte line
         4        0.641           6236   several accesses per 64-byte line
         8        1.117           7162   several accesses per 64-byte line
        16        1.287          12435   several accesses per 64-byte line
        32        2.333          13719   several accesses per 64-byte line
        64        4.304          14869   one access per line
       128        7.963           8038   one access per line, prefetcher stride
       256        9.930           6445   one access per line, prefetcher stride
       512        8.480           7547   one access per line, prefetcher stride
      1024        8.265           7744   one access per line, prefetcher stride
      2048       10.748           5954   one access per line, prefetcher stride
      4096       17.658           3624   one access per 4 KiB page (TLB)
      8192       17.831           3589   one access per 4 KiB page (TLB)

HOW TO READ IT (three regimes):
  1. stride 1..32: 64/stride accesses share a line. Time per access grows
     slowly because most accesses hit the line that the previous access
     just pulled in. The loop is instruction-bound at stride 1 (0.56 ns is
     about one dependent add per access) and becomes line-bound by 32.
  2. stride 64..2048: every access is a new line, so time per access is
     the cost of streaming lines from DRAM: ~4.3 ns per line at stride 64 =
     14.9 GB/s of line traffic, which is this laptop's practical single-
     core bandwidth. From 128 on, fewer lines per page are touched and the
     L2 streamer prefetcher (which works within a 4 KiB page) has fewer
     lines to run ahead on, so per-line cost roughly doubles.
  3. stride >= 4096: every access is a new PAGE: a TLB miss and a page walk
     per access, and the prefetcher does not cross page boundaries. 17.7 ns
     per access, 4x the stride-64 cost, for the SAME number of loads.
  "line-traffic MB/s" = lines actually fetched x 64 bytes / time. It tells
  you how much of the memory system you are using; ns/access tells you
  what your loop pays. Both matter: the first is a ceiling, the second is
  your bill.

the rules

C1. Count LINES, not bytes. A struct field you don't need still costs a full line when it sits between two you do (lab 03). C2. Sequential within a page is the fast case; the prefetcher is your best friend and it stops at 4 KiB boundaries (huge pages extend it: lab 06). C3. Random access pays a line AND often a page per access. Reduce it with layout (sort, pack, index) before reaching for prefetch hints (lab 05).

take it further

1. Halve the array to 128 MB and to 16 MB: at 16 MB (fits L3) stride 64 gets much cheaper; stride 4096 stays expensive (still 4096 pages). 2. `perf stat -e dTLB-load-misses:u` at stride 64 vs 4096: predict the ratio before you run it. 3. Change the access to a store (`a[idx] = i`) and re-run: stores need the line too (read-for-ownership), plus write-back traffic. ============================================================

read the source · cache/01_stride.c

#include "../tools/bench.h"
#define BYTES (256ull << 20)
#define ACCESSES (32ull << 20)
int main(int argc, char **argv) {
    unsigned char *a = (unsigned char *)malloc(BYTES);
    for (size_t i = 0; i < BYTES; i += 64) a[i] = (unsigned char)i;      /* pre-fault */
    size_t mask = BYTES - 1;
    printf("%8s %12s %14s   %s\n", "stride", "ns/access", "line-traffic MB/s", "note");
    size_t strides[] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192};
    for (size_t s = 0; s < sizeof strides / sizeof *strides; s++) {
        size_t stride = strides[s];
        uint64_t sum = 0, best = UINT64_MAX;
        for (int rep = 0; rep < 3; rep++) {
            uint64_t t0 = bench_ns();
            size_t idx = 0;
            for (uint64_t i = 0; i < ACCESSES; i++) { sum += a[idx]; idx = (idx + stride) & mask; }
            uint64_t dt = bench_ns() - t0; if (dt < best) best = dt;
        }
        BENCH_KEEP(sum);
        double ns = (double)best / (double)ACCESSES;
        const char *note = stride < 64 ? "several accesses per 64-byte line" : stride == 64 ? "one access per line" : stride >= 4096 ? "one access per 4 KiB page (TLB)" : "one access per line, prefetcher stride";
        printf("%8zu %12.3f %14.0f   %s\n", stride, ns, (double)ACCESSES * 64.0 / (best / 1e9) / 1e6 * (stride >= 64 ? 1 : (double)stride / 64.0), note);
    }
    (void)argc; (void)argv;
    free(a);
    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.

Stride — the cache line is the unit of memory traffic

Which role are you preparing for?