Caches, cache lines and false sharing

matrix.c adds up the same 16,777,216 numbers twice and gets the same total both times, yet on an Apple silicon Mac under macOS, best of five trials each, the column-by-column walk took many times as long as the row-by-row one. Nothing differs but the order of the loads. A cachecache: A small, fast memory near a core that keeps copies of recently used memory, so that later loads of the same or nearby addresses need no trip to main memory. keeps recently used memory close to the core, and it brings memory in whole cache linescache line: The fixed-size, aligned block in which a cache stores and moves memory. Sizes differ between processors and cache levels: Intel gives 64 bytes for its Core processors. A miss brings in the whole line.: a load that walks memory in order uses every byte it brought in, and one that jumps uses a sliver of each line.

Threads feel the same unit. Two threads that write different variables in one line slow each other down, which is called false sharingfalse sharing: A slowdown in which threads write different variables that happen to lie in the same cache line, so the line moves between their cores although no variable is shared.: only one core at a time may write a line, so the line moves back and forth between their cores. Every run below is native.

A cache moves memory in whole lines, and the system reports their size

Each cache moves memory in cache lines of its own fixed size. macOS reports one line size and the cache sizes through sysctl, which Apple documents for exactly this:

"""Asks macOS for the cache line size and the cache sizes of the two kinds of core."""

import pathlib
import sys

sys.path.insert(0, str(pathlib.Path(__file__).parent / "sessions"))
import session  # noqa: E402

session.run("""
# The line size, the L1 data cache of each kind of core (perflevel0 is the faster kind, perflevel1 the other),
# and the L2 cache of the perflevel0 cores, all in bytes
/usr/sbin/sysctl hw.cachelinesize hw.perflevel0.l1dcachesize hw.perflevel1.l1dcachesize hw.perflevel0.l2cachesize
""")

# The line size, the L1 data cache of each kind of core (perflevel0 is the faster kind, perflevel1 the other),
# and the L2 cache of the perflevel0 cores, all in bytes
$ /usr/sbin/sysctl hw.cachelinesize hw.perflevel0.l1dcachesize hw.perflevel1.l1dcachesize hw.perflevel0.l2cachesize
hw.cachelinesize: 128
hw.perflevel0.l1dcachesize: 131072
hw.perflevel1.l1dcachesize: 65536
hw.perflevel0.l2cachesize: 16777216

hw.cachelinesize is 128, the size Apple calls the system cache line: on a miss, a cache with lines of that size fetches the aligned 128 bytes around the address, not just the 4 or 8 the load asked for. Apple’s open-source kernel reads that number from the cache beyond the L1, and lists 64-byte lines for the L1 data caches of the cores it names. Apple numbers the host’s two kinds of core from the fastest: a perflevel0 core has a 131,072-byte L1 data cache, a perflevel1 core half that, and the L2 of the perflevel0 cores holds 16,777,216 bytes. Intel’s manual gives 64-byte lines for the L1 and L2 caches of its Core and Atom processors.

A walk in memory order uses every byte of each line

matrix.c fills a 4096 x 4096 matrix of int, 64 MiB, and sums it both ways at -O1, so that neither loop is vectorized and each does the same work per element. C stores a matrix row by row, so m[i][j] and m[i][j + 1] are 4 bytes apart while m[i][j] and m[i + 1][j] are 16,384 bytes apart:

// matrix.c: sums one 4096 x 4096 matrix of int twice, row by row and column by column, and times each walk.
// Both walks add the same 16,777,216 numbers, so they print the same sum; only the order of the loads differs.
// Built with -O1, so neither loop is vectorized and the two loops do the same work per element.
#include <stdio.h>
#include <time.h>

#define N 4096

static int m[N][N];  // 64 MiB, four times the largest cache the host reports

static double now_ms(void) {
    struct timespec t;
    clock_gettime(CLOCK_MONOTONIC, &t);
    return t.tv_sec * 1e3 + t.tv_nsec / 1e6;
}

// Consecutive elements: m[i][j] and m[i][j + 1] are 4 bytes apart.
static long by_rows(void) {
    long sum = 0;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) sum += m[i][j];
    return sum;
}

// One element per row: m[i][j] and m[i + 1][j] are 4096 x 4 = 16,384 bytes apart.
static long by_columns(void) {
    long sum = 0;
    for (int j = 0; j < N; j++)
        for (int i = 0; i < N; i++) sum += m[i][j];
    return sum;
}

int main(void) {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) m[i][j] = (i + j) % 10;
    double best_rows = 1e30, best_columns = 1e30;
    long sum_rows = 0, sum_columns = 0;
    for (int trial = 0; trial < 5; trial++) {  // the best of 5 trials, as the machine is shared
        double t0 = now_ms();
        sum_rows = by_rows();
        double t1 = now_ms();
        sum_columns = by_columns();
        double t2 = now_ms();
        if (t1 - t0 < best_rows) best_rows = t1 - t0;
        if (t2 - t1 < best_columns) best_columns = t2 - t1;
    }
    printf("matrix: %d x %d int, %zu bytes\n", N, N, sizeof m);
    printf("row by row:       sum %ld, best of 5: %.1f ms\n", sum_rows, best_rows);
    printf("column by column: sum %ld, best of 5: %.1f ms\n", sum_columns, best_columns);
    printf("column by column took %.1f times as long\n", best_columns / best_rows);
    return 0;
}

"""Builds matrix.c without vectorization and times a row-by-row and a column-by-column sum of the same 64 MiB."""

import pathlib
import sys

sys.path.insert(0, str(pathlib.Path(__file__).parent / "sessions"))
import session  # noqa: E402

session.run("""
clang -O1 -o matrix matrix.c
./matrix
""")

$ clang -O1 -o matrix matrix.c
$ ./matrix
matrix: 4096 x 4096 int, 67108864 bytes
row by row:       sum 75497480, best of 5: 4.1 ms
column by column: sum 75497480, best of 5: 48.1 ms
column by column took 11.6 times as long

The row walk has spatial localityspatial locality: The tendency of a program to use memory near memory it has just used, such as the next element of a row. It lets one cache line serve many loads.: once a 128-byte line has come in, the next 31 loads find their ints in it. The column walk moves 16,384 bytes per load, so each load needs a new line, and one column touches 4,096 lines, 512 KiB, more than the 128 KiB L1 of a perflevel0 core can hold. Both walks need the same cache lines, but the column walk fetches each into the L1 many times over: by the time it returns for the next column, those lines have left the L1:

Three questions go further:

• False sharing slows threads that write separate variables in one line, and padding each variable to its own line removes it.
• A hardware prefetcherhardware prefetcher: A part of the processor that watches the addresses of a program's loads and fetches the lines it predicts will be needed next, before the loads ask for them. fetches lines ahead of a walk in memory order, which pointer chasingpointer chasing: Walking a data structure by loading an address from memory and then loading through that address, as a linked-list walk does at every node. More in “Structs, arrays and linked lists in assembly” through a shuffled list defeats.
• Each system reports the line size its own way: sysctl on macOS, sysfs on Linux, CPUID or CTR_EL0 on the processor.

Practise

Three tasks on matrix.c. Build with clang -O1 -o matrix matrix.c and run ./matrix.

1. Change int to long long in the matrix and in nothing else. Work out how many elements now share a 128-byte line, predict whether the gap between the walks grows or shrinks, then run it.
2. Swap the two loops of by_columns so that it walks row by row, and check that its time falls to the row walk’s.
3. Work out how many lines one column of a 4096 x 4096 matrix of char touches, and whether they fit in a perflevel0 core’s L1.

False sharing measured, and the padding that removes it Pro: opens with a Pro, Premium or Ultimate pass

Prefetchers and pointer chasing, measured on the same nodes Pro: opens with a Pro, Premium or Ultimate pass

Finding the cache line size on each system, and the read that macOS refuses Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Why does summing a large C matrix row by row run faster than column by column?

C stores a matrix row by row, so the elements of a row are next to each other in memory, and the elements of a column are a whole row apart. A cache brings memory in whole lines, 64 bytes on many x86-64 processors and 128, as macOS reports it, on the Apple silicon host of the runs above, so a row walk uses every element of each line it fetches: for 4-byte ints, one miss serves 32 loads on a 128-byte line. A column walk jumps a row’s length on every load, so each load needs a line of its own, and in a large matrix those lines have left the cache before the walk comes back for the next column. Both walks do the same additions and give the same sum.

Three harder questions build on this one: counters that refuse to scale, a list against an array of the same records, and padding chosen for two kinds of processor.

Key takeaways

• Caches move memory in whole lines, and macOS reports the system line through sysctl: 128 bytes on the host of the runs.
• A loop whose consecutive loads fall in the same line uses all of each fetch; a loop that jumps a row per load needs a new line for every element.
• The order of the loads, not the number of additions, set the cost of the two walks of matrix.c.