Performance and Memory Layout

1The memory hierarchy

A main-memory access costs roughly two hundred cycles — enough time to execute several hundred arithmetic instructions. On modern hardware, the question is rarely how many operations you perform; it is how often you wait for memory.

Cache lines

Memory is not fetched a byte at a time. The hardware transfers a whole cache line, almost universally 64 bytes. Read one int and the sixteen around it arrive for free.

That single fact explains week 32's result. Walking an array touches consecutive addresses, so one miss serves sixteen elements. Walking a linked list follows pointers to scattered allocations, so nearly every step is a fresh miss — sixteen times the memory traffic for the same arithmetic.

The hardware also prefetches: detecting a sequential pattern, it fetches ahead so the data has arrived before you ask. Prefetchers recognize forward and backward strides. They cannot predict pointer chasing.

2Data layout

Loop order

/* fast: sequential in memory */
for (size_t r = 0; r < ROWS; r++)
    for (size_t c = 0; c < COLS; c++)
        sum += m[r][c];

/* slow: strides a whole row per step */
for (size_t c = 0; c < COLS; c++)
    for (size_t r = 0; r < ROWS; r++)
        sum += m[r][c];

Identical results, identical operation count. Week 12 explained row-major layout; this is where it costs you. On a large matrix the difference is commonly five- to tenfold.

Structure of arrays

When a loop touches one field of many records, the other fields still occupy the cache lines:

/* array of structures — the conventional layout */
typedef struct { int id; char name[32]; double score; } Student;
Student students[N];
for (size_t i = 0; i < N; i++) total += students[i].score;
/* each 64-byte line carries one score and 40 bytes you did not want */

/* structure of arrays — one array per field */
typedef struct {
    int    *id;
    char  (*name)[32];
    double *score;
} Students;
for (size_t i = 0; i < N; i++) total += s.score[i];
/* each line carries eight scores */

This is the standard transformation in numerical and game code. It is also less readable and harder to maintain, so apply it where a profiler says it matters — not everywhere.

Field ordering

Week 22 showed that declaring members largest-first eliminates padding. The same change helps here: a smaller structure means more records per cache line.

3Optimization levels

An unoptimized build is commonly three to ten times slower than -O2. Never benchmark at -O0: you are measuring the compiler's debugging output, not your program.

4Reading the generated assembly

You do not need to write assembly to benefit from reading it. The question is usually just "did the compiler do what I hoped?"

gcc -O2 -S -masm=intel prog.c -o prog.s     # generate assembly
objdump -d --demangle prog.o | less          # disassemble an object file

Compiler Explorer — linked in the course resources — shows source and assembly side by side with the correspondence colour-coded, which is far easier for learning.

Four things worth checking:

This is how week 15 demonstrated that index and pointer traversal compile identically, and how you confirm that a restrict annotation actually changed anything in week 38.

5Profiling

Programmers are reliably wrong about where time goes. Measure.

# perf — Linux, sampling, no recompilation, very low overhead
perf stat ./prog
perf record -g ./prog && perf report

# gprof — portable, needs instrumentation
gcc -pg -O2 prog.c -o prog && ./prog && gprof ./prog gmon.out | head -30

# callgrind — exact instruction counts, ~50x slower
valgrind --tool=callgrind ./prog && callgrind_annotate callgrind.out.*

perf stat is the first command to run. Beyond the elapsed time it reports cache-misses and instructions per cycle — and those two numbers usually identify whether you have a computation problem or a memory problem before you look at anything else.

Timing correctly

struct timespec t0, t1;
clock_gettime(CLOCK_MONOTONIC, &t0);
work();
clock_gettime(CLOCK_MONOTONIC, &t1);
double secs = (double)(t1.tv_sec - t0.tv_sec)
            + (double)(t1.tv_nsec - t0.tv_nsec) / 1e9;

CLOCK_MONOTONIC, not the wall clock, because the wall clock can step backwards. Run each measurement several times and take the minimum — the minimum is the run least disturbed by other activity, and is more stable than the mean.

Beware the compiler deleting your benchmark: if a result is unused, the whole computation can be removed. Print it, or accumulate into a volatile.

6Worked example: the same loop, made three times faster

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define SIZE 1024
#define REPS 20
#define RECORDS 2000000

static double now(void)
{
    struct timespec t;
    clock_gettime(CLOCK_MONOTONIC, &t);
    return (double)t.tv_sec + (double)t.tv_nsec / 1e9;
}

/* ---------- 1. loop order over a matrix ---------- */

static double sum_row_major(const double *m)
{
    double total = 0.0;
    for (int rep = 0; rep < REPS; rep++)
        for (size_t r = 0; r < SIZE; r++)
            for (size_t c = 0; c < SIZE; c++)
                total += m[r * SIZE + c];         /* sequential */
    return total;
}

static double sum_column_major(const double *m)
{
    double total = 0.0;
    for (int rep = 0; rep < REPS; rep++)
        for (size_t c = 0; c < SIZE; c++)
            for (size_t r = 0; r < SIZE; r++)
                total += m[r * SIZE + c];         /* strides 8 KB per step */
    return total;
}

/* ---------- 2. array of structures versus structure of arrays ---------- */

typedef struct {
    int    id;
    char   name[32];
    double score;
} Record;                       /* 48 bytes; we want 8 of them */

typedef struct {
    int    *id;
    char  (*name)[32];
    double *score;
} Columns;

static double sum_aos(const Record *r, size_t n)
{
    double total = 0.0;
    for (int rep = 0; rep < 20; rep++)
        for (size_t i = 0; i < n; i++)
            total += r[i].score;
    return total;
}

static double sum_soa(const Columns *c, size_t n)
{
    double total = 0.0;
    for (int rep = 0; rep < 20; rep++)
        for (size_t i = 0; i < n; i++)
            total += c->score[i];
    return total;
}

/* ---------- 3. what the optimizer can and cannot see ---------- */

static long sum_to(long n)
{
    long total = 0;
    for (long i = 1; i <= n; i++) total += i;
    return total;
}

int main(void)
{
    puts("== 1. loop order ==");
    double *m = malloc((size_t)SIZE * SIZE * sizeof *m);
    if (m == NULL) return EXIT_FAILURE;
    for (size_t i = 0; i < (size_t)SIZE * SIZE; i++) m[i] = 1.0;
    printf("  matrix is %zu MB, cache lines hold %zu doubles\n",
           (size_t)SIZE * SIZE * sizeof *m / (1024 * 1024), 64 / sizeof(double));

    double t = now();
    double a = sum_row_major(m);
    double row_secs = now() - t;

    t = now();
    double b = sum_column_major(m);
    double col_secs = now() - t;

    printf("  row-major    : %.4f s  (sum %.0f)\n", row_secs, a);
    printf("  column-major : %.4f s  (sum %.0f)\n", col_secs, b);
    printf("  same result, same operation count, %.1fx difference\n",
           col_secs / row_secs);
    free(m);

    puts("\n== 2. array of structures versus structure of arrays ==");
    Record *recs = malloc(RECORDS * sizeof *recs);
    Columns cols = {
        .id    = malloc(RECORDS * sizeof *cols.id),
        .name  = malloc(RECORDS * sizeof *cols.name),
        .score = malloc(RECORDS * sizeof *cols.score)
    };
    if (recs == NULL || cols.id == NULL || cols.name == NULL || cols.score == NULL)
        return EXIT_FAILURE;

    for (size_t i = 0; i < RECORDS; i++) {
        recs[i].id = (int)i;  recs[i].score = 1.0;
        cols.id[i] = (int)i;  cols.score[i] = 1.0;
    }

    t = now();  double s1 = sum_aos(recs, RECORDS);  double aos_secs = now() - t;
    t = now();  double s2 = sum_soa(&cols, RECORDS); double soa_secs = now() - t;

    printf("  sizeof(Record) = %zu, so a 64-byte line holds %.1f scores\n",
           sizeof(Record), 64.0 / (double)sizeof(Record));
    printf("  array of structures : %.4f s  (sum %.0f)\n", aos_secs, s1);
    printf("  structure of arrays : %.4f s  (sum %.0f)\n", soa_secs, s2);
    printf("  %.1fx, purely from how much of each line is useful\n",
           aos_secs / soa_secs);

    free(recs); free(cols.id); free(cols.name); free(cols.score);

    puts("\n== 3. what the optimizer does ==");
    t = now();
    long total = sum_to(100000000L);
    double loop_secs = now() - t;
    printf("  sum 1..100000000 = %ld in %.4f s\n", total, loop_secs);
    puts("  compile at -O2 and inspect the assembly:");
    puts("    gcc -O2 -S perf.c -o perf.s && grep -A20 'sum_to:' perf.s");
    puts("  the loop may have become a closed-form multiplication");

    return EXIT_SUCCESS;
}

gcc -std=c17 -Wall -Wextra -O2 -o perf perf.c
./perf

Typical results

Confirm the diagnosis rather than assuming it:

perf stat -e cache-misses,cache-references,instructions,cycles ./perf

The column-major phase shows a cache-miss rate an order of magnitude higher than the row-major phase, at essentially the same instruction count. That is the entire explanation, visible as two numbers.

Look at the assembly

gcc -O2 -S perf.c -o perf.s
sed -n '/^sum_to:/,/ret/p' perf.s

Depending on the version, GCC may recognize the summation and emit the closed form n(n+1)/2 — replacing a hundred million iterations with three instructions. Compare against -O0:

gcc -O0 -S perf.c -o perf0.s
sed -n '/^sum_to:/,/ret/p' perf0.s      # a literal loop, everything in memory

Then time both builds. A benchmark run at -O0 measures none of this.

Profile before optimizing

perf record -g ./perf
perf report --stdio | head -20

The report ranks functions by the share of samples they consumed. Optimize the top entry; everything below it is noise. Amdahl's law is the arithmetic behind that advice: making a function that takes 5% of the runtime twice as fast improves the program by 2.5%, while the same effort on a function taking 60% is worth ten times more.

When to stop

Four questions, in order. Is it actually too slow — measured against a requirement, not a feeling? Does the profiler agree with your guess about where the time goes? Is there a better algorithm, which usually beats any amount of micro-optimization? And is the speedup worth the loss of clarity, given that the code must be maintained for years?

Most C is fast enough when it is straightforward and compiled at -O2 with sensible data layout. The layout is the part worth thinking about in advance, because it is the part that is hard to change later.

7Common mistakes

9Where this leads

Week 35 turns from making code fast to keeping it correct: debugging with GDB, unit tests and coverage, static analysis, and a continuous integration configuration that runs the sanitizers on every change. The warning profile assembled in week 29 becomes an enforced gate there.