Intermediate Examples

// learning/code/ex-28-cache-miss-stride-sweep/stride_sweep.c
// Example 28: sweep access stride 1..1024 elements and find the cache-line-size
// performance cliff on this machine (co-02, co-05).
#include <stdio.h>  // => co-25: printf -- reports the ns/access table and PASS/FAIL verdict
#include <stdlib.h> // => co-01: malloc/free -- the 256 MiB buffer under test
#include <time.h>   // => co-25: clock_gettime -- the wall-clock timer used below
 
#define BUF_MB 256UL // => co-05: 256 MiB buffer, far larger than any cache on this machine
#define ACCESSES \
    8000000L // => co-05: fixed access count per stride -- same work, only stride
             // varies
 
static double now_seconds(void) { // => co-25: wall-clock via clock_gettime, portable timer
    struct timespec ts;           // => co-25: POSIX timespec -- seconds + nanoseconds
    clock_gettime(CLOCK_MONOTONIC,
                  &ts);                                  // => co-25: monotonic clock -- immune to wall-clock adjustment
    return (double)ts.tv_sec + (double)ts.tv_nsec / 1e9; // => co-25: combine into one double-seconds value
}
 
int main(void) {
    // => co-02: the hypothesis under test -- consecutive small-stride accesses
    // => share a 128 B cache line and pay for only ONE miss among many touches,
    // => while a stride >= one line's worth of ints pays a fresh miss every time
    size_t n_ints = (BUF_MB * 1024UL * 1024UL) / sizeof(int); // => co-01: element count, a power of two by construction
    // => co-01: 256 MiB is far past this machine's 4 MiB L2, so a small stride's
    // => "fast" case below is genuinely spatial-locality inside one cache line,
    // => not the whole buffer secretly fitting in cache
    int *buf = malloc(n_ints * sizeof(int)); // => co-01: one big flat array -- the memory under test
    if (buf == NULL) {                       // => co-25: guard the 256 MiB allocation before touching it
        fprintf(stderr, "alloc failed\n");   // => co-25: reports to stderr, not stdout
        return 1;                            // => co-25: nonzero exit -- allocation failure is not this example's claim
    } // => co-25: fail loudly rather than measure garbage
    for (size_t i = 0; i < n_ints; i++) // => co-01: one pass over every element, ascending
        buf[i] = (int)i;                // => co-01: touch every page once so faults don't skew timing
 
    size_t mask = n_ints - 1;                                              // => co-02: n_ints is a power of two -- mask replaces slow modulo
    int strides[] = {1, 2, 4, 8, 16, 24, 32, 48, 64, 128, 256, 512, 1024}; // => co-02: elements per step,
                                                                           // sweeping past 32 (=128B/4B)
    int n_strides = (int)(sizeof(strides) / sizeof(strides[0]));           // => co-02: array length, computed
                                                                           // rather than hardcoded
 
    printf("cache line size on this machine: %d bytes (%d ints)\n", 128,
           128 / (int)sizeof(int)); // => co-02: known via sysctl
    printf("%8s %12s %10s\n", "stride", "ns/access",
           "elems/line"); // => co-25: column header for the table printed below
 
    double baseline_ns = 0.0;                        // => co-05: ns/access at the smallest stride -- the "all hits" floor
    double cliff_ns = 0.0;                           // => co-05: ns/access once stride exceeds the cache-line size
    for (int s = 0; s < n_strides; s++) {            // => co-02: one timed pass per candidate stride
        volatile long sum = 0;                       // => co-25: volatile sink -- forces the load to really happen
        size_t idx = 0;                              // => co-02: running index, wrapped with the power-of-two mask
        double t0 = now_seconds();                   // => co-25: start the clock for this stride's run
        for (long i = 0; i < ACCESSES; i++) {        // => co-05: fixed number of accesses, identical across strides
            idx = (idx + (size_t)strides[s]) & mask; // => co-02: advance by `stride` elements, wrap via mask
            sum += buf[idx];                         // => co-05: the actual memory access under measurement
        }
        double t1 = now_seconds();                                 // => co-25: stop the clock
        double ns_per_access = (t1 - t0) * 1e9 / (double)ACCESSES; // => co-25: normalize to a per-access cost
        printf("%8d %12.2f %10.1f\n", strides[s],
               ns_per_access,                               // => co-25: print this stride's real measured cost
               128.0 / (strides[s] * (double)sizeof(int))); // => co-02: how many strides fit in one 128 B line
        if (strides[s] == 1)
            baseline_ns = ns_per_access; // => co-05: smallest stride -- best-case,
                                         // all same-line hits
        if (strides[s] == 32)
            cliff_ns = ns_per_access; // => co-02: exactly one cache line (128B/4B) per step
        (void)sum;                    // => co-25: sum only exists to defeat dead-code elimination
    }
 
    double ratio = cliff_ns / baseline_ns; // => co-05: how much slower the one-miss-per-access case is
    printf("\nstride=1 baseline: %.2f ns/access\n",
           baseline_ns); // => co-25: restate the floor for the reader
    printf("stride=32 (one cache line/access): %.2f ns/access\n",
           cliff_ns); // => co-05: restate the cliff for the reader
    printf("cliff ratio: %.2fx -> %s\n",
           ratio,                                                                                  // => co-25: the program judges its OWN claim, not the reader
           ratio > 1.5 ? "PASS (clear cliff at the cache-line stride)" : "FAIL (no clear cliff)"); // => co-05: the assertion
    free(buf);                                                                                     // => co-01: release the 256 MiB buffer before exiting
    return ratio > 1.5 ? 0 : 1;                                                                    // => co-25: a real process exit code reflecting the PASS/FAIL
}

cache line size on this machine: 128 bytes (32 ints)
  stride    ns/access elems/line
       1         0.96       32.0
       2         0.96       16.0
       4         1.37        8.0
       8         1.92        4.0
      16         1.34        2.0
      24         1.64        1.3
      32         5.73        1.0
      48         6.83        0.7
      64         6.51        0.5
     128         6.46        0.2
     256         4.22        0.1
     512         3.29        0.1
    1024         4.32        0.0
 
stride=1 baseline: 0.96 ns/access
stride=32 (one cache line/access): 5.73 ns/access
cliff ratio: 5.96x -> PASS (clear cliff at the cache-line stride)

// learning/code/ex-29-matrix-traversal-ij-vs-ji/matrix_traversal.c
// Example 29: sum a large row-major int matrix [i][j] (sequential) vs [j][i]
// (strided) and verify [i][j] is measurably faster (co-03, co-17).
#include <stdio.h>  // => co-25: printf -- the timing/PASS report this program prints
#include <stdlib.h> // => co-17: malloc/free -- the one 64 MiB matrix both traversals share
#include <time.h>   // => co-25: clock_gettime -- the portable wall-clock timer used below
 
#define N \
    4096          // => co-17: 4096x4096 ints = 64 MiB -- far bigger than this machine's 4
                  // MiB L2
#define REPEATS 3 // => co-25: best-of-3 -- shared-machine noise smoothing (DD-20 step 2)
// => co-25: this program's own PASS/FAIL line is the assertion -- no external
// => test harness is needed to confirm the claim this example makes
 
static double now_seconds(void) {                        // => co-25: same portable clock_gettime timer used across this tier
    struct timespec ts;                                  // => co-25: POSIX timespec, seconds + nanoseconds fields
    clock_gettime(CLOCK_MONOTONIC, &ts);                 // => co-25: monotonic -- immune to
                                                         // NTP/wall-clock adjustment mid-run
    return (double)ts.tv_sec + (double)ts.tv_nsec / 1e9; // => co-25: combined into one double-seconds
                                                         // value for subtraction
}
 
static long sum_row_major(int (*m)[N]) { // => co-17: m[i][j] is the pointer-to-array-of-N-ints layout
                                         // C actually uses
    // => co-03: "row-major" means row 0's N ints, then row 1's N ints, etc,
    // => laid out back to back -- C guarantees this for a plain 2-D array
    long total = 0;                   // => co-03: accumulator -- summed in the SAME order memory is laid out
    for (int i = 0; i < N; i++) {     // => co-03: outer loop over rows -- each row is N contiguous ints
        for (int j = 0; j < N; j++) { // => co-03: inner loop walks j sequentially WITHIN one row
            total += m[i][j];         // => co-03: address = base + i*N*4 + j*4 -- j+1 is the
                                      // VERY next int
        }
    }
    return total; // => co-03: identical mathematical sum to sum_col_major below
}
 
static long sum_col_major(int (*m)[N]) { // => co-17: SAME matrix, SAME memory layout --
                                         // only the loop nesting flips
    // => co-17: this is the classic "algorithm looks identical, performance
    // => doesn't" trap -- big-O is O(N^2) either way, but the constant differs
    // hugely
    long total = 0;                   // => co-17: accumulator -- summed in COLUMN order, against the grain
    for (int j = 0; j < N; j++) {     // => co-17: outer loop over columns now
        for (int i = 0; i < N; i++) { // => co-17: inner loop walks i -- each step jumps N*4 = 16 KiB
            total += m[i][j];         // => co-17: address = base + i*N*4 + j*4 -- i+1 skips a
                                      // whole row
        }
    }
    return total; // => co-17: same total as sum_row_major -- correctness is
                  // unaffected
}
 
int main(void) {                             // => co-25: single self-contained process -- both traversals
                                             // run in it
    int (*m)[N] = malloc(sizeof(int[N][N])); // => co-17: one 64 MiB row-major allocation,
                                             // shared by BOTH traversals
    if (m == NULL) {
        fprintf(stderr, "alloc failed\n");
        return 1;
    } // => co-25: fail loudly rather than time a null pointer
    for (int i = 0; i < N; i++)          // => co-01: fill once so page faults don't skew either timed pass
        for (int j = 0; j < N; j++)      // => co-01: touches every one of the 16M ints exactly once
            m[i][j] = (i * 31 + j) % 97; // => co-01: arbitrary deterministic values
                                         // -- content doesn't matter here
 
    double best_row = 1e18,
           best_col = 1e18;        // => co-25: track the FASTEST of REPEATS runs per
                                   // traversal, not the average
    long row_sum = 0, col_sum = 0; // => co-03: captured to prove both traversals
                                   // compute the SAME answer
    // => co-25: both traversals do the EXACT same 16M additions -- only the
    // => memory ACCESS PATTERN differs, isolating the layout effect from work
    // done
    for (int r = 0; r < REPEATS; r++) { // => co-25: re-run to confirm the result
                                        // reproduces, not a lucky sample
        double t0 = now_seconds();      // => co-25: time ONLY the traversal, not the setup above
        row_sum = sum_row_major(m);     // => co-03: the cache-friendly, sequential-access traversal
        double t1 = now_seconds();      // => co-25: stop the clock for the row-major pass
        if (t1 - t0 < best_row)
            best_row = t1 - t0; // => co-25: keep the best (least noisy) row-major timing so far
 
        double t2 = now_seconds();  // => co-25: start the clock for the column-major pass
        col_sum = sum_col_major(m); // => co-17: the SAME matrix, strided-access traversal
        double t3 = now_seconds();  // => co-25: stop the clock for the column-major pass
        if (t3 - t2 < best_col)
            best_col = t3 - t2; // => co-25: keep the best (least noisy) column-major
                                // timing so far
    }
 
    printf("row-major [i][j] sum: %ld, best of %d: %.4f s\n", row_sum, REPEATS,
           best_row); // => co-25: methodology stated in the output
    printf("col-major [j][i] sum: %ld, best of %d: %.4f s\n", col_sum, REPEATS,
           best_col);                     // => co-17: methodology stated in the output
    double speedup = best_col / best_row; // => co-03: how many times slower the
                                          // strided traversal really was
    printf("row-major is %.2fx faster -> %s\n",
           speedup,                                // => co-25: prints the ratio the reader should verify against
                                                   // below
           (row_sum == col_sum && speedup > 1.2) ? // => co-03: correctness (equal sums) AND speed both gate the PASS
               "PASS (identical sums, [i][j] measurably faster)"
                                                 :        // => co-25: the program judges its own claim, per DD-20
               "FAIL");                                   // => co-25: an honest FAIL label if either condition fails
    free(m);                                              // => co-17: release the 64 MiB matrix before exiting
    return (row_sum == col_sum && speedup > 1.2) ? 0 : 1; // => co-25: a real process exit code reflecting the PASS/FAIL
}

row-major [i][j] sum: 805306468, best of 3: 0.0014 s
col-major [j][i] sum: 805306468, best of 3: 0.0713 s
row-major is 50.70x faster -> PASS (identical sums, [i][j] measurably faster)

// learning/code/ex-30-aos-vs-soa-hot-loop/aos_vs_soa.c
// Example 30: sum ONE hot field across a large array-of-structs (AoS) vs the
// same data as a struct-of-arrays (SoA) -- verify SoA wins the hot-only sum
// (co-17).
#include <stdio.h>  // => co-17: printf -- the timing/PASS report this program prints
#include <stdlib.h> // => co-17: malloc/free -- both layouts under test are heap-allocated
#include <time.h>   // => co-17: clock_gettime -- the portable wall-clock timer used below
 
#define N \
    8000000       // => co-17: 8M elements -- each AoS struct is 64 B, so AoS = 512 MiB
                  // total
#define REPEATS 3 // => co-25: best-of-3 -- shared-machine noise smoothing (DD-20 step 2)
// => co-17: cold[15] simulates the OTHER 15 fields a real record carries
// => (name, timestamps, flags, ...) that a hot loop never touches per iteration
 
typedef struct {  // => co-17: array-of-structs -- ONE struct per element, fields
                  // interleaved
    int hot;      // => co-17: the ONLY field the hot loop below actually reads
    int cold[15]; // => co-17: 15 unused ints -- simulates a "real" record's other
                  // fields
} AosRecord;      // => co-16: sizeof(AosRecord) == 64 B (16 ints * 4 B), no padding
                  // needed here
 
static double now_seconds(void) { // => co-25: same portable clock_gettime timer used across this tier
    struct timespec ts;           // => co-25: POSIX timespec, seconds + nanoseconds fields
    clock_gettime(CLOCK_MONOTONIC,
                  &ts);                                  // => co-25: monotonic -- immune to wall-clock adjustment mid-run
    return (double)ts.tv_sec + (double)ts.tv_nsec / 1e9; // => co-25: combined into one double-seconds value
}
 
static long sum_hot_aos(const AosRecord *records,
                        int n) {  // => co-17: reads records[i].hot, skipping
                                  // records[i].cold every time
    long total = 0;               // => co-17: accumulator over the hot field only
    for (int i = 0; i < n; i++) { // => co-17: one iteration per record -- N total
        total += records[i].hot;  // => co-17: pulls in the WHOLE 64 B struct's cache
                                  // line for 4 B of data
    }
    return total; // => co-17: same mathematical sum as sum_hot_soa below
}
 
static long sum_hot_soa(const int *hot,
                        int n) {  // => co-17: reads hot[i] directly -- cold
                                  // fields live in a SEPARATE array
    long total = 0;               // => co-17: accumulator over the SAME hot values, different layout
    for (int i = 0; i < n; i++) { // => co-17: one iteration per element -- N total, identical work
        total += hot[i];          // => co-17: every fetched cache line is 100% hot data, 0%
                                  // wasted
    }
    return total; // => co-17: same mathematical sum as sum_hot_aos above
}
 
int main(void) { // => co-25: single self-contained process -- both layouts run in it
    // => co-17: two layouts of the SAME logical data -- one struct per record
    // (AoS)
    // => vs one flat array of just the hot field (SoA) -- correctness must match
    AosRecord *aos = malloc((size_t)N * sizeof(AosRecord)); // => co-17: 512 MiB -- N structs,
                                                            // hot+cold interleaved per record
    int *soa_hot = malloc((size_t)N * sizeof(int));         // => co-17: 32 MiB -- N ints, ONLY the
                                                            // hot field, tightly packed
    if (aos == NULL || soa_hot == NULL) {
        fprintf(stderr, "alloc failed\n");
        return 1;
    } // => co-25: fail loudly, never time a null pointer
 
    for (int i = 0; i < N; i++) {      // => co-01: fill both layouts with the SAME hot values once
        int value = (i * 7919) % 1009; // => co-01: arbitrary deterministic value --
                                       // content doesn't matter
        aos[i].hot = value;            // => co-17: same value written into the AoS record's hot field
        soa_hot[i] = value;            // => co-17: same value written into the SoA hot-only array
    }
 
    double best_aos = 1e18,
           best_soa = 1e18;        // => co-25: track the FASTEST of REPEATS runs per layout
    long aos_sum = 0, soa_sum = 0; // => co-17: captured to prove both layouts
                                   // compute the SAME answer
    // => co-17: both loops read exactly N ints of real data -- only the STRIDE
    // => between successive hot values (64 B in AoS, 4 B in SoA) differs
    for (int r = 0; r < REPEATS; r++) { // => co-25: re-run to confirm the result reproduces
        double t0 = now_seconds();      // => co-25: start the clock for this AoS pass
        aos_sum = sum_hot_aos(aos,
                              N);  // => co-17: the cache-hostile layout -- 15/16 of each line wasted
        double t1 = now_seconds(); // => co-25: stop the clock for this AoS pass
        if (t1 - t0 < best_aos)
            best_aos = t1 - t0; // => co-25: keep the best AoS timing so far
 
        double t2 = now_seconds(); // => co-25: start the clock for this SoA pass
        soa_sum = sum_hot_soa(soa_hot,
                              N);  // => co-17: the cache-friendly layout -- every fetched byte used
        double t3 = now_seconds(); // => co-25: stop the clock for this SoA pass
        if (t3 - t2 < best_soa)
            best_soa = t3 - t2; // => co-25: keep the best SoA timing so far
    }
 
    printf("AoS hot-field sum: %ld, best of %d: %.4f s\n", aos_sum, REPEATS,
           best_aos); // => co-17: methodology stated in output
    printf("SoA hot-field sum: %ld, best of %d: %.4f s\n", soa_sum, REPEATS,
           best_soa);                     // => co-17: methodology stated in output
    double speedup = best_aos / best_soa; // => co-17: how many times slower the
                                          // interleaved layout really was
    printf("SoA is %.2fx faster -> %s\n",
           speedup,                                // => co-25: prints the ratio the reader should verify against
                                                   // below
           (aos_sum == soa_sum && speedup > 1.2) ? // => co-17: correctness (equal sums) AND speed both gate the PASS
               "PASS (identical sums, SoA measurably faster for hot-only sum)"
                                                 :        // => co-25: the program judges its own claim
               "FAIL");                                   // => co-25: an honest FAIL label if either condition fails
    free(aos);                                            // => co-17: release the 512 MiB AoS buffer
    free(soa_hot);                                        // => co-17: release the 32 MiB SoA buffer
    return (aos_sum == soa_sum && speedup > 1.2) ? 0 : 1; // => co-25: real process exit code reflecting the PASS/FAIL
}

AoS hot-field sum: 4031998889, best of 3: 0.0102 s
SoA hot-field sum: 4031998889, best of 3: 0.0006 s
SoA is 16.63x faster -> PASS (identical sums, SoA measurably faster for hot-only sum)

// learning/code/ex-31-working-set-cache-cliffs/working_set_cliffs.c
// Example 31: pointer-chase through working sets crossing L1 (64 KiB) and L2
// (4 MiB) on this machine -- report the REAL observed cliffs, honestly (co-01,
// co-05).
#include <stdio.h>  // => co-01: printf -- the per-size latency table this program prints
#include <stdlib.h> // => co-01: malloc/free/rand -- buffer allocation and permutation shuffling
#include <time.h>   // => co-25: clock_gettime -- the portable wall-clock timer used below
 
#define N_SIZES 12     // => co-01: number of working-set sizes swept, 16 KiB .. 32 MiB
#define STEPS 4000000L // => co-05: pointer-chase steps timed per working-set size
// => co-25: this example REPORTS whatever cliffs actually appear on THIS
// => machine/run rather than asserting the textbook L1=64 KiB/L2=4 MiB numbers
 
static double now_seconds(void) { // => co-25: same portable clock_gettime timer used across this tier
    struct timespec ts;           // => co-25: POSIX timespec, seconds + nanoseconds fields
    clock_gettime(CLOCK_MONOTONIC,
                  &ts);                                  // => co-25: monotonic -- immune to wall-clock adjustment mid-run
    return (double)ts.tv_sec + (double)ts.tv_nsec / 1e9; // => co-25: combined into one double-seconds value
}
 
// => co-05: Sattolo's algorithm -- builds ONE single cycle over all n indices
// => (no short sub-cycles), so pointer-chasing it truly wanders the ENTIRE
// => working set instead of bouncing inside a small, easily cached loop
static void sattolo_shuffle(int *arr,
                            int n) { // => co-05: builds the pointer-chase path
                                     // -- read this BEFORE chase_ns_per_access
    for (int i = 0; i < n; i++)
        arr[i] = i;                   // => co-05: start as the identity permutation
    for (int i = n - 1; i > 0; i--) { // => co-05: Sattolo's variant of
                                      // Fisher-Yates -- guarantees one big cycle
        int j = rand() % i;           // => co-05: j strictly < i (never swaps an element with itself)
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp; // => co-05: swap -- builds the single-cycle permutation in place
    } // => co-05: after this loop, arr is one n-length cycle:
      // 0->arr[0]->arr[arr[0]]->...
}
 
// => co-05: chases arr[idx] STEPS times -- each load depends on the PREVIOUS
// => load's result, so out-of-order execution cannot hide the memory latency;
// => this measures real latency, not throughput
static double chase_ns_per_access(int *arr, int n, long steps) {
    volatile int idx = 0;              // => co-25: volatile -- forces every dependent load to really happen
    double t0 = now_seconds();         // => co-25: start the clock right before the timed
                                       // dependent-load loop
    for (long i = 0; i < steps; i++) { // => co-05: STEPS sequential, data-dependent loads
        idx = arr[idx];                // => co-05: the next index to visit -- unknown until THIS
                                       // load returns
    }
    double t1 = now_seconds();              // => co-25: stop the clock right after the loop
    (void)n;                                // => co-25: n only used by the caller for the printed table, not here
    return (t1 - t0) * 1e9 / (double)steps; // => co-25: normalized to nanoseconds
                                            // per pointer-chase step
}
 
int main(void) {
    srand(42);                                                                                     // => co-05: fixed seed -- the SAME permutation shape every run
    size_t sizes_kib[N_SIZES] = {16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768}; // => co-01: KiB working sets
    int max_elems = (int)((sizes_kib[N_SIZES - 1] * 1024UL) / sizeof(int));                        // => co-01: largest size drives the one shared buffer
    int *buf = malloc((size_t)max_elems * sizeof(int));                                            // => co-01: one 32 MiB buffer, reused
                                                                                                   // (re-shuffled) at each smaller size
    if (buf == NULL) {
        fprintf(stderr, "alloc failed\n");
        return 1;
    } // => co-25: fail loudly, never time a null pointer
 
    printf("L1d=64 KiB, L2=4 MiB on this machine (sysctl "
           "hw.l1dcachesize/hw.l2cachesize)\n"); // => co-01: known boundaries,
                                                 // stated up front
    printf("%10s %14s\n", "size(KiB)",
           "ns/access");                                      // => co-01: table header for the sweep below
    double prev_ns = 0.0;                                     // => co-05: previous size's latency, for computing the jump ratio
    int printed_first = 0;                                    // => co-05: skip the ratio print on the very first (smallest) size
    for (int s = 0; s < N_SIZES; s++) {                       // => co-01: one timed pointer-chase per working-set size
        int n = (int)((sizes_kib[s] * 1024UL) / sizeof(int)); // => co-01: element count for THIS size, within
                                                              // the shared buffer
        sattolo_shuffle(buf, n);                              // => co-05: a fresh single-cycle permutation
                                                              // confined to the first n ints
        double ns = chase_ns_per_access(buf, n,
                                        STEPS); // => co-05: the real measured latency for this working-set size
        printf("%10zu %14.2f", sizes_kib[s],
               ns);                      // => co-05: prints the REAL measured ns/access, never a guessed
                                         // number
        if (printed_first) {             // => co-05: report the jump ratio vs the PREVIOUS
                                         // (smaller) size
            double ratio = ns / prev_ns; // => co-05: how much slower THIS size is
                                         // than the one before it
            printf("   (%.2fx vs prior size)",
                   ratio); // => co-05: prints the real ratio, not an assumed textbook
                           // number
            if (ratio > 1.4)
                printf("  <-- CLIFF"); // => co-05: flag a real, measured jump -- not
                                       // asserted, OBSERVED
        }
        printf("\n");      // => co-05: end this size's table row
        prev_ns = ns;      // => co-05: remember this size's latency for the NEXT ratio
        printed_first = 1; // => co-05: every size after the first prints a ratio
    }
    free(buf); // => co-01: release the 32 MiB shared buffer
    printf("\nObserved cliffs are reported above as measured, not assumed -- see "
           "the\n"
           "prose discussion for which sizes crossed L1/L2 on THIS run.\n"); // =>
                                                                             // co-25:
                                                                             // honesty
                                                                             // statement
                                                                             // per
                                                                             // DD-20
    return 0;                                                                // => co-25: this example reports observations -- no PASS/FAIL
                                                                             // threshold
}

L1d=64 KiB, L2=4 MiB on this machine (sysctl hw.l1dcachesize/hw.l2cachesize)
 size(KiB)      ns/access
        16           3.59
        32           2.66   (0.74x vs prior size)
        64           2.82   (1.06x vs prior size)
       128           3.00   (1.07x vs prior size)
       256           5.93   (1.97x vs prior size)  <-- CLIFF
       512           7.37   (1.24x vs prior size)
      1024           7.59   (1.03x vs prior size)
      2048           7.85   (1.03x vs prior size)
      4096           8.10   (1.03x vs prior size)
      8192           9.92   (1.22x vs prior size)
     16384          18.92   (1.91x vs prior size)  <-- CLIFF
     32768          84.70   (4.48x vs prior size)  <-- CLIFF
 
Observed cliffs are reported above as measured, not assumed -- see the
prose discussion for which sizes crossed L1/L2 on THIS run.

// learning/code/ex-32-cache-blocking-matmul/blocked_matmul.c
// Example 32: naive triple-loop matmul vs a cache-blocked/tiled version --
// verify identical results and the tiled version measurably faster (co-03,
// co-25).
#include <stdio.h>  // => co-25: printf -- the timing/PASS report this program prints
#include <stdlib.h> // => co-03: malloc/free -- all three N x N matrices are heap-allocated
#include <time.h>   // => co-25: clock_gettime -- the portable wall-clock timer used below
 
#define N \
    512 // => co-03: 512x512 doubles = 2 MiB per matrix -- A+B+C don't fit in L2
        // (4 MiB)
#define BLOCK \
    64            // => co-03: tile edge -- a 64x64 double tile is 32 KiB, fits comfortably
                  // in L1d
#define REPEATS 3 // => co-25: best-of-3 -- shared-machine noise smoothing (DD-20 step 2)
 
static double now_seconds(void) { // => co-25: same portable clock_gettime timer used across this tier
    struct timespec ts;           // => co-25: POSIX timespec, seconds + nanoseconds fields
    clock_gettime(CLOCK_MONOTONIC,
                  &ts);                                  // => co-25: monotonic -- immune to wall-clock adjustment mid-run
    return (double)ts.tv_sec + (double)ts.tv_nsec / 1e9; // => co-25: combined into one double-seconds value
}
 
// => co-03: naive C[i][j] = sum_k A[i][k]*B[k][j] -- for FIXED i,j the inner k
// => loop strides through B COLUMN-wise, touching a new cache line almost every
// step
static void matmul_naive(const double *a, const double *b, double *c,
                         int n) {                   // defines matmul_naive(): helper function used by this example
    for (int i = 0; i < n; i++) {                   // => co-03: rows of A/C
        for (int j = 0; j < n; j++) {               // => co-03: columns of B/C
            double sum = 0.0;                       // => co-03: accumulator for C[i][j]
            for (int k = 0; k < n; k++) {           // => co-03: dot product of A's row i and B's column j
                sum += a[i * n + k] * b[k * n + j]; // => co-03: a[i][k] sequential,
                                                    // b[k][j] strided by n doubles
            } // => co-03: k=0..n-1 means b's column touches n DIFFERENT cache lines
            c[i * n + j] = sum; // => co-03: write the finished dot product into C
        } // => co-03: next column j -- b's whole n*n footprint is walked AGAIN
    }
}
 
// => co-03: same math, tiled into BLOCK x BLOCK sub-matrices so each tile of
// => A, B, and C stays resident in L1/L2 while it is being reused repeatedly
static void matmul_blocked(const double *a, const double *b, double *c,
                           int n) { // defines matmul_blocked(): helper function used by this example
    for (int i = 0; i < n; i++)     // => co-03: C must still be zeroed -- blocking
                                    // only reorders accumulation
        for (int j = 0; j < n; j++)
            c[i * n + j] = 0.0;                     // => co-03: start every output cell at zero before
                                                    // accumulating tiles
    for (int ii = 0; ii < n; ii += BLOCK) {         // => co-03: outer tile loop over row-blocks of A/C
        for (int jj = 0; jj < n; jj += BLOCK) {     // => co-03: outer tile loop over column-blocks of B/C
            for (int kk = 0; kk < n; kk += BLOCK) { // => co-03: outer tile loop over
                                                    // the shared reduction dimension
                // => co-03: this INNER triple loop is the same naive kernel, just
                // => confined to one BLOCK x BLOCK x BLOCK cube -- small enough to stay
                // cached
                for (int i = ii; i < ii + BLOCK; i++) {         // => co-03: within-tile row -- BLOCK=64 rows per outer tile
                                                                // step
                    for (int j = jj; j < jj + BLOCK; j++) {     // => co-03: within-tile column -- BLOCK=64 columns per
                                                                // outer tile step
                        double sum = c[i * n + j];              // => co-03: resume accumulating THIS cell across k-tiles
                        for (int k = kk; k < kk + BLOCK; k++) { // => co-03: within-tile reduction -- only BLOCK terms
                                                                // per (ii,jj,kk) pass
                            sum += a[i * n + k] * b[k * n + j]; // => co-03: identical arithmetic to the
                                                                // naive kernel, tile-local
                        } // => co-03: this k-tile's contribution to c[i][j] is now folded
                          // in
                        c[i * n + j] = sum; // => co-03: write back the partial sum for this k-tile
                    } // => co-03: next column within this (ii,jj,kk) tile
                } // => co-03: next row within this (ii,jj,kk) tile
            }
        }
    }
}
 
// ex-32: main() ties both kernels together -- allocate once, run both REPEATS
// times, diff their outputs for correctness, and only THEN compare timings, so
// a speed win never masks a wrong answer.
int main(void) {                                                // => co-25: single self-contained process -- both kernels run in it
    double *a = malloc((size_t)N * N * sizeof(double));         // => co-03: 2 MiB input matrix A
    double *b = malloc((size_t)N * N * sizeof(double));         // => co-03: 2 MiB input matrix B
    double *c_naive = malloc((size_t)N * N * sizeof(double));   // => co-03: 2 MiB output for the naive kernel
    double *c_blocked = malloc((size_t)N * N * sizeof(double)); // => co-03: 2 MiB output for the blocked kernel
    if (!a || !b || !c_naive || !c_blocked) {
        fprintf(stderr, "alloc failed\n");
        return 1;
    } // => co-25: fail loudly
 
    for (int i = 0; i < N * N; i++) {         // => co-01: fill A and B once with deterministic values
        a[i] = (double)((i * 7) % 13) - 6.0;  // => co-01: arbitrary but deterministic -- content doesn't matter
        b[i] = (double)((i * 11) % 17) - 8.0; // => co-01: different formula so A != B
    } // => co-01: both matrices fully touched once, before any timed pass
 
    double best_naive = 1e18,
           best_blocked = 1e18;         // => co-25: track the FASTEST of REPEATS runs per kernel
    for (int r = 0; r < REPEATS; r++) { // => co-25: re-run to confirm the result reproduces
        double t0 = now_seconds();      // => co-25: start the clock for this naive pass
        matmul_naive(a, b, c_naive,
                     N);           // => co-03: the cache-hostile, unblocked kernel
        double t1 = now_seconds(); // => co-25: stop the clock for this naive pass
        if (t1 - t0 < best_naive)
            best_naive = t1 - t0; // => co-25: keep the best naive timing so far
 
        double t2 = now_seconds(); // => co-25: start the clock for this blocked pass
        matmul_blocked(a, b, c_blocked,
                       N);         // => co-03: the SAME math, tiled for cache reuse
        double t3 = now_seconds(); // => co-25: stop the clock for this blocked pass
        if (t3 - t2 < best_blocked)
            best_blocked = t3 - t2; // => co-25: keep the best blocked timing so far
    }
 
    double max_diff = 0.0;                       // => co-03: largest per-cell difference between the
                                                 // two kernels' outputs
    for (int i = 0; i < N * N; i++) {            // => co-03: scan every one of the N*N result cells
        double diff = c_naive[i] - c_blocked[i]; // => co-03: exact double arithmetic --
                                                 // blocking changes ORDER, not values here
        if (diff < 0)
            diff = -diff; // => co-03: absolute difference
        if (diff > max_diff)
            max_diff = diff; // => co-03: track the worst-case mismatch across all cells
    } // => co-03: max_diff over all N*N cells is this run's correctness verdict
 
    printf("naive:   best of %d: %.4f s\n", REPEATS,
           best_naive); // => co-25: methodology stated in the output
    printf("blocked: best of %d: %.4f s\n", REPEATS,
           best_blocked); // => co-25: methodology stated in the output
    printf("max |naive - blocked| difference: %.2e\n",
           max_diff);                           // => co-03: near-zero proves the tiling didn't change the
                                                // answer
    double speedup = best_naive / best_blocked; // => co-03: how many times faster
                                                // the tiled version really was
    int correct = max_diff < 1e-9;              // => co-03: both use double, same summation
                                                // order per cell -- expect exact match
    printf("blocked is %.2fx faster -> %s\n",
           speedup,                     // => co-25: prints the ratio the reader should verify against
                                        // below
           (correct && speedup > 1.1) ? // => co-03: correctness (near-zero diff) AND speed both gate the
                                        // PASS
               "PASS (identical results, blocking measurably faster)"
                                      : // => co-25: the program judges its own claim, per DD-20
               "FAIL");                 // => co-25: an honest FAIL label if either condition fails
    free(a);
    free(b);
    free(c_naive);
    free(c_blocked);                           // => co-03: release all four 2 MiB matrices before exiting
    return (correct && speedup > 1.1) ? 0 : 1; // => co-25: real process exit code reflecting the PASS/FAIL
}

naive:   best of 3: 0.1563 s
blocked: best of 3: 0.1070 s
max |naive - blocked| difference: 0.00e+00
blocked is 1.46x faster -> PASS (identical results, blocking measurably faster)

// learning/code/ex-33-false-sharing-demo/false_sharing.c
/* Example 33: two threads increment adjacent longs sharing one 128 B cache
   line vs longs placed on separate cache lines -- verify a real, measured
   slowdown from false sharing (co-02, co-24). */
#include <pthread.h> // => co-24: pthread_create/join -- the two concurrent writer threads under test
#include <stdio.h>   // => printf -- the timing/PASS report this program prints
#include <stdlib.h>  // => calloc/free -- the shared buffer both counter pairs live inside
#include <time.h>    // => clock_gettime -- the portable wall-clock timer used below
 
#define ITERS \
    100000000L          // => co-24: 100M increments/thread -- large enough for a stable
                        // timing signal
#define STRIDE_LONGS 32 // => co-02: 32 * 8 B = 256 B -- guarantees two DIFFERENT 128 B cache lines
 
// co-24: a pair of pointers, not two named fields -- lets run_pair() reuse ONE
// thread body for both the "same line" and "different line" experiments below,
// varying only which addresses inside one shared buffer the two threads are
// told to hammer.
typedef struct {
    volatile long *a; // => co-24: volatile is load-bearing here -- without it
                      // clang can prove no other
    volatile long *b; //    thread observes intermediate values and collapse the
                      //    loop to `*a += ITERS`
} Pair;               //    once, which would silently delete the false-sharing traffic this
                      //    measures
 
static void *inc_a(void *arg) { // => co-24: thread body -- increments *only* a
    Pair *p = (Pair *)arg;      // => co-24: recover the shared pointer pair
    for (long i = 0; i < ITERS; i++)
        (*p->a)++; // => co-24: real load+add+store every iteration --
    return NULL;   //    contended by thread B's writes if a/b share a line
}
static void *inc_b(void *arg) { // => co-24: thread body -- increments *only* b
    Pair *p = (Pair *)arg;      // => co-24: same struct, opposite field
    for (long i = 0; i < ITERS; i++)
        (*p->b)++; // => co-24: identical work to inc_a, mirrored
    return NULL;
}
 
static double now_seconds(void) { // => co-25: shared wall-clock helper, this topic's standard pattern
    struct timespec ts;           // => POSIX timespec: seconds + nanoseconds
    clock_gettime(CLOCK_MONOTONIC,
                  &ts);                                  // => monotonic -- immune to wall-clock adjustment mid-run
    return (double)ts.tv_sec + (double)ts.tv_nsec / 1e9; // => combined into one double-seconds value
}
 
// co-24: spins up both writer threads on the SAME pair of addresses, times
// wall-clock from before creation to after both joins -- the two-core
// contention IS the measurement.
static double run_pair(volatile long *a, volatile long *b) {
    Pair p = {a, b}; // => co-24: bundle both target addresses once
    pthread_t t1,
        t2;                               // => co-24: two OS threads -- real concurrency, not simulated
    double t0 = now_seconds();            // => co-25: start the clock before either thread exists
    pthread_create(&t1, NULL, inc_a, &p); // => co-24: thread 1 hammers *a
    pthread_create(&t2, NULL, inc_b,
                   &p); // => co-24: thread 2 hammers *b, concurrently
    pthread_join(t1,
                 NULL); // => co-24: block until thread 1's 100M increments finish
    pthread_join(t2,
                 NULL);        // => co-24: block until thread 2's 100M increments finish
    return now_seconds() - t0; // => co-25: total wall-clock for both threads combined
}
 
int main(void) {
    // co-02: one big buffer -- WE control offsets directly instead of trusting
    // malloc's internal placement, so the "same line" vs "different line" claim
    // is exact, not assumed.
    long *buf = calloc(1024, sizeof(long)); // => 8 KB buffer, zero-initialized counters
    if (!buf) {
        fprintf(stderr, "alloc failed\n");
        return 1;
    } // => fail loudly, never time a null pointer
 
    // co-02: offsets 0 and 1 are 8 bytes apart -- both land inside the SAME 128 B
    // line
    double t_adjacent = run_pair((volatile long *)&buf[0], (volatile long *)&buf[1]);
    // co-02: offsets 0 and STRIDE_LONGS are 256 bytes apart -- two DIFFERENT 128
    // B lines
    double t_separate = run_pair((volatile long *)&buf[0], (volatile long *)&buf[STRIDE_LONGS]);
 
    printf("adjacent (false-sharing) pair:     %.4f s\n",
           t_adjacent); // => co-24: same-line timing
    printf("separate (independent-line) pair:  %.4f s\n",
           t_separate);                        // => co-24: different-line timing
    double slowdown = t_adjacent / t_separate; // => co-24: how many times slower sharing a line was
    printf("false-sharing slowdown: %.2fx -> %s\n", slowdown,
           slowdown > 1.3 ? "PASS (adjacent measurably slower)" : "FAIL"); // => co-25: program judges its own claim
    free(buf);                                                             // => release the 8 KB shared buffer
    return slowdown > 1.3 ? 0 : 1;                                         // => real process exit code reflecting the PASS/FAIL
}

adjacent (false-sharing) pair:     0.1481 s
separate (independent-line) pair:  0.0357 s
false-sharing slowdown: 4.14x -> PASS (adjacent measurably slower)

// learning/code/ex-34-padding-fixes-false-sharing/padded_counters.c
/* Example 34: pad two counters onto separate 128 B cache lines -- verify
   ex-33's false-sharing slowdown disappears once each counter owns its own
   line (co-02, co-24). */
#include <pthread.h> // => co-24: pthread_create/join -- the two concurrent writer threads under test
#include <stdio.h>   // => printf -- the sizeof/timing/PASS report this program prints
#include <stdlib.h>  // => calloc/free -- both counter layouts under test are heap-allocated
#include <time.h>    // => clock_gettime -- the portable wall-clock timer used below
 
#define ITERS \
    100000000L // => co-24: same iteration count as ex-33 -- an apples-to-apples
               // rerun
#define LINE \
    128 // => co-02: THIS machine's real cache line size (128 B on Apple Silicon)
        // --
        //    hardcoding the common 64 B x86 number here would silently under-pad
 
// co-02: reproduces ex-33's failing case in THIS file too, so ex-34 stays
// self-contained -- two counters with no padding between them, guaranteed to
// share one 128 B line.
typedef struct {              // struct layout definition
    volatile long unpadded_a; // => co-24: volatile -- same collapse-prevention
                              // reasoning as ex-33
    volatile long unpadded_b; // => co-02: 8 bytes after unpadded_a -- same cache
                              // line, by construction
} Unpadded;                   // supporting statement for this example
 
// co-02: the FIX -- one real counter plus enough padding bytes to fill out a
// whole 128 B line, so that in an ARRAY of these structs, element [1] starts on
// the NEXT cache line instead of a few bytes into element [0]'s line.
typedef struct {                   // struct layout definition
    volatile long value;           // => co-24: the one real counter this struct holds
    char pad[LINE - sizeof(long)]; // => co-16: deliberate, performance-motivated
                                   // struct padding --
} PaddedCounter;                   //    120 filler bytes so sizeof(PaddedCounter) == 128 exactly
 
static void *inc_long(void *arg) {           // => co-24: one shared thread body for BOTH experiments
    volatile long *p = (volatile long *)arg; // => co-24: works on any single volatile long address
    for (long i = 0; i < ITERS; i++)
        (*p)++;  // => co-24: real load+add+store every iteration
    return NULL; // returns the computed result
}
 
static double now_seconds(void) {                        // => co-25: shared wall-clock helper, this topic's standard pattern
    struct timespec ts;                                  // supporting statement for this example
    clock_gettime(CLOCK_MONOTONIC, &ts);                 // calls clock_gettime(...)
    return (double)ts.tv_sec + (double)ts.tv_nsec / 1e9; // returns the computed result
}
 
static double run_two(volatile long *a,
                      volatile long *b) { // => co-24: times two threads
                                          // hammering a/b concurrently
    pthread_t t1, t2;                     // declares t1
    double t0 = now_seconds();            // declares t0
    pthread_create(&t1, NULL, inc_long,
                   (void *)a); // => co-24: thread 1 increments *a
    pthread_create(&t2, NULL, inc_long,
                   (void *)b); // => co-24: thread 2 increments *b, concurrently
    pthread_join(t1, NULL);    // calls pthread_join(...)
    pthread_join(t2, NULL);    // calls pthread_join(...)
    return now_seconds() - t0; // => co-25: total wall-clock for both threads combined
}
 
int main(void) {                                                                  // program entry point
    printf("sizeof(PaddedCounter) = %zu bytes (padded to one %d B cache line)\n", // prints a report line
           sizeof(PaddedCounter),
           LINE); // => co-16: prove the padding actually landed at 128
 
    Unpadded *u = calloc(1, sizeof(Unpadded)); // => co-02: false-sharing baseline, reproduced here
    if (!u) {
        fprintf(stderr, "alloc failed\n");
        return 1;
    } // prints a report line
    double t_unpadded = run_two(&u->unpadded_a, &u->unpadded_b); // => co-24: ex-33's slow case, rerun
 
    PaddedCounter *p = calloc(2,
                              sizeof(PaddedCounter)); // => co-02: array of 2 -- p[1] starts a WHOLE line
    if (!p) {
        fprintf(stderr, "alloc failed\n");
        return 1;
    } //    after p[0], by the padding above
    double t_padded = run_two(&p[0].value,
                              &p[1].value); // => co-24: the FIXED case -- no shared line at all
 
    printf("unpadded (false-sharing) pair: %.4f s\n",
           t_unpadded); // => co-24: reproduces ex-33's slow number
    printf("padded (own cache line each):  %.4f s\n",
           t_padded);                                                           // => co-24: the fixed, fast number
    double speedup = t_unpadded / t_padded;                                     // => co-24: how much the padding fix recovered
    printf("padding speedup: %.2fx -> %s\n", speedup,                           // prints a report line
           speedup > 1.3 ? "PASS (padding fix removes the slowdown)" : "FAIL"); // => co-25: self-judged PASS/FAIL
    free(u);                                                                    // => release the false-sharing baseline struct
    free(p);                                                                    // => release the padded-counter array
    return speedup > 1.3 ? 0 : 1;                                               // => real process exit code reflecting the PASS/FAIL
}

sizeof(PaddedCounter) = 128 bytes (padded to one 128 B cache line)
unpadded (false-sharing) pair: 0.1325 s
padded (own cache line each):  0.0340 s
padding speedup: 3.89x -> PASS (padding fix removes the slowdown)

// learning/code/ex-35-prefetch-hint/prefetch_hint.c
/* Example 35: add a __builtin_prefetch hint to a random-index (gather)
   summation -- measure its REAL effect on this machine, honestly, rather
   than assume the textbook win (co-03, co-25). */
#include <stdio.h>  // => printf -- the timing/finding report this program prints
#include <stdlib.h> // => malloc/free/rand -- the data array and its random permutation
#include <time.h>   // => clock_gettime -- the portable wall-clock timer used below
 
#define N \
    100000000 // => co-03: 100M ints = 400 MB -- far bigger than this machine's 4
              // MiB L2,
              //    so every access below is a real DRAM-latency miss
#define BLOCK \
    64 // => co-03: prefetch a whole 64-element BLOCK ahead at once, not one
       //    element at a time -- the block-ahead shape used in real
       //    prefetch-tuned kernels (tried first: per-element prefetch;
       //    block-ahead measured the same)
#define BLOCK_AHEAD \
    256          // => co-03: how many elements AHEAD (in the permutation's visiting order)
                 //    the block of prefetches targets
#define TRIALS 4 // => co-25: best-of-4 -- shared-machine noise smoothing
 
static double now_seconds(void) {                        // => co-25: shared wall-clock helper, this topic's standard pattern
    struct timespec ts;                                  // supporting statement for this example
    clock_gettime(CLOCK_MONOTONIC, &ts);                 // calls clock_gettime(...)
    return (double)ts.tv_sec + (double)ts.tv_nsec / 1e9; // returns the computed result
}
 
// co-03: Fisher-Yates -- a genuinely random VISITING ORDER (not a dependent
// pointer chase), so each element's target address is unpredictable to a
// hardware STRIDE prefetcher, but fully knowable BLOCK_AHEAD steps in advance
// from the array alone -- exactly the shape software prefetching is designed to
// exploit.
static void shuffle(int *perm,
                    int n) { // defines shuffle(): helper function used by this example
    for (int i = 0; i < n; i++)
        perm[i] = i;                  // => start as the identity order
    for (int i = n - 1; i > 0; i--) { // => standard Fisher-Yates from the back
        int j = rand() % (i + 1);     // declares j
        int tmp = perm[i];
        perm[i] = perm[j];
        perm[j] = tmp; // => swap -- builds one random permutation
    }
}
 
// co-03: no hint -- the CPU only discovers `data[perm[i]]` is needed when the
// load actually issues; this machine's out-of-order engine still overlaps many
// INDEPENDENT loads on its own (co-22), which is exactly what this example
// measures.
static long sum_no_prefetch(const int *data, const int *perm,
                            int n) { // defines sum_no_prefetch(): helper function used by this example
    long total = 0;                  // declares total
    for (int i = 0; i < n; i++) {    // loop header controlling the sweep below
        total += data[perm[i]];      // => co-05: an unpredicted-address gather load
    }
    return total; // returns the computed result
}
 
// co-03: WITH the hint -- __builtin_prefetch tells the CPU "you will want this
// address soon", issued for a whole BLOCK_AHEAD-elements-ahead block before
// that block is consumed, hoping the fetch lands in cache before the real load
// needs it.
static long sum_with_prefetch(const int *data, const int *perm,
                              int n) {        // defines sum_with_prefetch(): helper
                                              // function used by this example
    long total = 0;                           // declares total
    int i = 0;                                // declares i
    for (; i + BLOCK <= n; i += BLOCK) {      // => co-03: process one BLOCK of elements at a time
        int fbase = i + BLOCK_AHEAD;          // => co-03: this block's prefetch TARGETS start here
        if (fbase + BLOCK <= n) {             // conditional check
            for (int k = 0; k < BLOCK; k++) { // loop header controlling the sweep below
                __builtin_prefetch(&data[perm[fbase + k]], 0,
                                   1); // => co-03: read hint, low locality (used once)
            }
        }
        for (int k = 0; k < BLOCK; k++)
            total += data[perm[i + k]]; // => co-05: the real, consumed loads
    }
    for (; i < n; i++)
        total += data[perm[i]]; // => co-03: scalar tail for n not a multiple of BLOCK
    return total;               // returns the computed result
}
 
int main(void) {                                 // program entry point
    srand(7);                                    // => co-25: fixed seed -- reproducible permutation
    int *data = malloc((size_t)N * sizeof(int)); // => the 400 MB array being summed
    int *perm = malloc((size_t)N * sizeof(int)); // => the random visiting order over that array
    if (!data || !perm) {
        fprintf(stderr, "alloc failed\n");
        return 1;
    } // prints a report line
    for (int i = 0; i < N; i++)
        data[i] = (i * 2654435761u) % 1000u; // => deterministic filler values
    shuffle(perm, N);                        // => one random permutation, reused by BOTH runs
 
    double best_no_pf = 1e18, best_pf = 1e18;   // declares best_no_pf
    long sum_a = 0, sum_b = 0;                  // declares sum_a
    for (int t = 0; t < TRIALS; t++) {          // => co-25: best-of-N -- keep the fastest clean run
        double t0 = now_seconds();              // declares t0
        sum_a = sum_no_prefetch(data, perm, N); // assigns sum_a
        double t1 = now_seconds();              // declares t1
        if (t1 - t0 < best_no_pf)
            best_no_pf = t1 - t0; // conditional check
 
        double t2 = now_seconds();                // declares t2
        sum_b = sum_with_prefetch(data, perm, N); // assigns sum_b
        double t3 = now_seconds();                // declares t3
        if (t3 - t2 < best_pf)
            best_pf = t3 - t2; // conditional check
    }
 
    printf("N=%d ints (%.0f MB), block=%d, block_ahead=%d, best of %d\n",
           N, // prints a report line
           (double)(N * sizeof(int)) / (1024.0 * 1024.0), BLOCK, BLOCK_AHEAD,
           TRIALS); // continues the printf(...) call above
    printf("no prefetch:   sum=%ld, %.4f s (%.2f ns/elem)\n", sum_a,
           best_no_pf,            // prints a report line
           best_no_pf * 1e9 / N); // continues the printf(...) call above
    printf("with prefetch: sum=%ld, %.4f s (%.2f ns/elem)\n", sum_b, best_pf,
           best_pf * 1e9 / N);           // prints a report line
    double ratio = best_no_pf / best_pf; // => co-03: >1.0 would mean prefetch helped
    printf("prefetch ratio: %.2fx, correctness: %s\n", ratio,
           (sum_a == sum_b) ? "identical sums" : "MISMATCH -- BUG"); // prints a report line
    printf(                                                          // prints a report line
        "OBSERVED FINDING (measured, not assumed, per co-25): on THIS machine's "
        "deep\n" // continues the printf(...) call above
        "out-of-order core, %s -- see prose for why (co-22's memory-level "
        "parallelism\n"                                                                                      // continues the printf(...) call above
        "already overlaps independent gather loads without help here).\n",                                   // continues
                                                                                                             // the
                                                                                                             // printf(...)
                                                                                                             // call
                                                                                                             // above
        ratio > 1.03 ? "the prefetch hint measurably helped" : "the prefetch hint did NOT measurably help"); // continues the
                                                                                                             // printf(...) call
                                                                                                             // above
    free(data);                                                                                              // releases data's heap memory
    free(perm);                                                                                              // releases perm's heap memory
    return (sum_a == sum_b) ? 0 : 1;                                                                         // => correctness is the only hard gate here --
} //    this example's point is the MEASUREMENT itself

N=100000000 ints (381 MB), block=64, block_ahead=256, best of 4
no prefetch:   sum=49949981688, 0.4066 s (4.07 ns/elem)
with prefetch: sum=49949981688, 0.5629 s (5.63 ns/elem)
prefetch ratio: 0.72x, correctness: identical sums
OBSERVED FINDING (measured, not assumed, per co-25): on THIS machine's deep
out-of-order core, the prefetch hint did NOT measurably help -- see prose for why (co-22's memory-level parallelism
already overlaps independent gather loads without help here).

// learning/code/ex-36-branch-predictable-vs-random/branch_predict.c
/* Example 36: sum-if-positive over sorted vs shuffled data -- verify the
   sorted (predictable) pass runs faster than the shuffled (random) one
   (co-21). */
#include <stdio.h>  // => printf -- the timing/PASS report this program prints
#include <stdlib.h> // => malloc/free/rand/qsort -- data generation, sorting, and shuffling
#include <time.h>   // => clock_gettime -- the portable wall-clock timer used below
 
#define N \
    1000000 // => co-21: 1M elements, 4 MB -- fits inside this machine's 4 MiB L2,
            // so
            //    the loop is BRANCH/compute-bound, not memory-bandwidth-bound (a
            //    50M-element streaming array hid the mispredict cost behind DRAM
            //    bandwidth -- verified by first trying that shape and seeing no
            //    effect)
#define PASSES \
    200          // => co-21: repeat the full-array pass this many times -- builds a
                 // stable,
                 //    multi-millisecond signal out of a small, cache-resident array
#define TRIALS 3 // => co-25: best-of-3 -- shared-machine noise smoothing
 
static double now_seconds(void) {                        // => co-25: shared wall-clock helper, this topic's standard pattern
    struct timespec ts;                                  // supporting statement for this example
    clock_gettime(CLOCK_MONOTONIC, &ts);                 // calls clock_gettime(...)
    return (double)ts.tv_sec + (double)ts.tv_nsec / 1e9; // returns the computed result
}
 
// co-21: EVERY iteration hits this branch -- with sorted input, the outcome is
// the same ("no") for a long run then the same ("yes") for a long run, so the
// branch predictor's history table learns the pattern almost perfectly. With
// shuffled input, the outcome flips unpredictably, defeating the predictor on
// roughly half the iterations -- each mispredict flushes the pipeline (co-20)
// for tens of cycles. VERIFIED CAVEAT (found while building this example):
// clang -O2 on arm64 recognizes `if (x>=0) sum+=x;` as equivalent to `sum +=
// max(x,0)` and silently rewrites it into a branchless `bic/asr` bit-trick on
// its OWN (disassembly confirmed zero branch instructions survived plain code,
// even with vectorize(disable)). The `"+r"(v)` per-value asm barrier below is
// the same "DoNotOptimize" idiom used in ex-37: it pins each candidate value
// through an opaque register operation so LLVM can no longer prove the two arms
// are equivalent and cannot fold them back into one branchless selection.
static long sum_if_positive(const int *arr,
                            int n) {        // defines sum_if_positive(): helper function used by this example
    long total = 0;                         // declares total
    for (int i = 0; i < n; i++) {           // loop header controlling the sweep below
        if (arr[i] >= 0) {                  // => co-21: the data-dependent branch under test --
            int v = arr[i];                 //    two value-pinned arms so clang cannot merge
            __asm__ volatile("" : "+r"(v)); //    them back into a single bic/asr bit-trick
            total += v;                     // => taken only when the (unpredictable) sign says so
        } else {                            // alternate branch
            int v = 0;                      //    the "skip" arm, equally value-pinned
            __asm__ volatile("" : "+r"(v)); // supporting statement for this example
            total += v;                     // updates total
        }
    }
    return total; // returns the computed result
}
 
// co-21: repeats the pass PASSES times so a small, cache-resident array still
// produces a measurable multi-millisecond total, keeping the branch (not memory
// bandwidth) as the bottleneck this example is isolating.
static long sum_if_positive_repeated(const int *arr, int n,
                                     int passes) { // defines sum_if_positive_repeated():
                                                   // helper function used by this example
    long total = 0;                                // declares total
    for (int p = 0; p < passes; p++) {             // loop header controlling the sweep below
        total += sum_if_positive(arr, n);          // => co-21: identical work every pass, same data
    }
    return total; // returns the computed result
}
 
static int cmp_int(const void *a,
                   const void *b) {                 // defines cmp_int(): helper function used by this example
    int ia = *(const int *)a, ib = *(const int *)b; // declares ia
    return (ia > ib) - (ia < ib);                   // => standard three-way qsort comparator
}
 
int main(void) {                                     // program entry point
    srand(99);                                       // => co-25: fixed seed -- reproducible dataset
    int *sorted = malloc((size_t)N * sizeof(int));   // heap-allocates memory for sorted
    int *shuffled = malloc((size_t)N * sizeof(int)); // heap-allocates memory for shuffled
    if (!sorted || !shuffled) {
        fprintf(stderr, "alloc failed\n");
        return 1;
    } // prints a report line
 
    for (int i = 0; i < N; i++) {            // loop header controlling the sweep below
        int v = (int)(rand() % 2001) - 1000; // => values in [-1000, 1000] -- roughly half negative
        sorted[i] = v;                       // assigns sorted[i]
        shuffled[i] = v;                     // => SAME multiset of values in both arrays
    }
    qsort(sorted, N, sizeof(int),
          cmp_int); // => co-21: sorted -> long predictable runs of sign
    // shuffled stays in its original random order -- co-21: sign flips
    // unpredictably
 
    double best_sorted = 1e18, best_shuffled = 1e18;              // declares best_sorted
    long sum_sorted = 0, sum_shuffled = 0;                        // declares sum_sorted
    for (int t = 0; t < TRIALS; t++) {                            // => co-25: best-of-N -- keep the fastest clean run
        double t0 = now_seconds();                                // declares t0
        sum_sorted = sum_if_positive_repeated(sorted, N, PASSES); // assigns sum_sorted
        double t1 = now_seconds();                                // declares t1
        if (t1 - t0 < best_sorted)
            best_sorted = t1 - t0; // conditional check
 
        double t2 = now_seconds();                                    // declares t2
        sum_shuffled = sum_if_positive_repeated(shuffled, N, PASSES); // assigns sum_shuffled
        double t3 = now_seconds();                                    // declares t3
        if (t3 - t2 < best_shuffled)
            best_shuffled = t3 - t2; // conditional check
    }
 
    printf("N=%d elements x %d passes (4 MB array, L2-resident)\n", N,
           PASSES); // prints a report line
    printf("sorted   sum=%ld, best of %d: %.4f s\n", sum_sorted, TRIALS,
           best_sorted); // prints a report line
    printf("shuffled sum=%ld, best of %d: %.4f s\n", sum_shuffled, TRIALS,
           best_shuffled);                                         // prints a report line
    double speedup = best_shuffled / best_sorted;                  // => co-21: how much slower the mispredicting pass was
    printf("sorted is %.2fx faster -> %s\n", speedup,              // prints a report line
           (sum_sorted == sum_shuffled && speedup > 1.2)           // continues the printf(...) call above
               ? "PASS (identical sums, sorted measurably faster)" // continues the
                                                                   // printf(...)
                                                                   // call above
               : "FAIL");                                          // continues the printf(...) call above
    free(sorted);                                                  // releases sorted's heap memory
    free(shuffled);                                                // releases shuffled's heap memory
    return (sum_sorted == sum_shuffled && speedup > 1.2) ? 0 : 1;  // returns the computed result
}

N=1000000 elements x 200 passes (4 MB array, L2-resident)
sorted   sum=49982168800, best of 3: 0.1292 s
shuffled sum=49982168800, best of 3: 0.6692 s
sorted is 5.18x faster -> PASS (identical sums, sorted measurably faster)

// learning/code/ex-37-branchless-max/branchless_max.c
/* Example 37: replace a conditional max with a branchless bit-trick --
   verify identical output and a speedup on unpredictable (random) data
   (co-21). */
#include <stdio.h>  // => printf -- the timing/PASS report this program prints
#include <stdlib.h> // => malloc/free/rand -- the random input arrays
#include <time.h>   // => clock_gettime -- the portable wall-clock timer used below
 
#define N \
    50000000     // => co-21: 50M random pairs -- enough to average out predictor
                 // noise
#define TRIALS 3 // => co-25: best-of-3 -- shared-machine noise smoothing
 
static double now_seconds(void) {                        // => co-25: shared wall-clock helper, this topic's standard pattern
    struct timespec ts;                                  // supporting statement for this example
    clock_gettime(CLOCK_MONOTONIC, &ts);                 // calls clock_gettime(...)
    return (double)ts.tv_sec + (double)ts.tv_nsec / 1e9; // returns the computed result
}
 
// co-21: the OBVIOUS implementation -- a data-dependent branch that the CPU
// must predict every iteration. On uniformly random a/b, "a > b" is true about
// half the time with NO pattern, so the branch predictor is wrong roughly half
// the time -- every mispredict flushes the in-flight pipeline (co-20). VERIFIED
// CAVEAT (found while building this example): clang -O2 on arm64 aggressively
// converts a plain
// `(a>b)?a:b` into a branchless `cmp+csel` on its OWN -- disassembly confirmed
// no branch survived, even behind a memory-only asm barrier (that barrier
// doesn't pin the VALUE, only memory ordering, so if-conversion still merged
// the two arms). The `"+r"(v)` per-value asm barrier below is the standard
// "DoNotOptimize" idiom (as used by Google Benchmark): it forces the SPECIFIC
// register holding each candidate value through an opaque no-op instruction, so
// LLVM can no longer prove the two arms compute equivalent values and cannot
// fold them into one csel.
static long sum_branchy_max(const int *a, const int *b,
                            int n) {        // defines sum_branchy_max(): helper function used by this example
    long total = 0;                         // declares total
    for (int i = 0; i < n; i++) {           // loop header controlling the sweep below
        if (a[i] > b[i]) {                  // => co-21: a REAL conditional branch (cmp+b.le) --
            int v = a[i];                   //    two value-pinned arms so clang cannot merge
            __asm__ volatile("" : "+r"(v)); //    them back into a single conditional-select
            total += v;                     // updates total
        } else {                            // alternate branch
            int v = b[i];                   //    same value-pinning trick on the other arm
            __asm__ volatile("" : "+r"(v)); // supporting statement for this example
            total += v;                     // updates total
        }
    }
    return total; // returns the computed result
}
 
// co-21: the BRANCHLESS trick -- computes max(a,b) with pure arithmetic/bitwise
// ops, no conditional jump at all, so there is nothing for the branch predictor
// to get wrong: diff = a-b; mask = diff's sign bit smeared across all 32 bits
// (all 1s if a<b, all 0s if a>=b); result = a - (diff & mask) -- selects a or b
// without a jump. vectorize(disable) keeps this scalar so the comparison
// isolates the branch-vs-branchless difference, not a scalar-vs-SIMD difference
// (that's ex-47's and ex-48's job, not this one's).
static long sum_branchless_max(const int *a, const int *b,
                               int n) {                   // defines sum_branchless_max(): helper
                                                          // function used by this example
    long total = 0;                                       // declares total
#pragma clang loop vectorize(disable) interleave(disable) // supporting statement for this example
    for (int i = 0; i < n; i++) {                         // loop header controlling the sweep below
        int diff = a[i] - b[i];                           // => co-21: negative iff a[i] < b[i]
        int mask = diff >> 31;                            // => co-21: arithmetic shift smears the sign bit --
                                                          //    all-1s (mask=-1) if diff<0, all-0s if diff>=0
        int m = a[i] - (diff & mask);                     // => co-21: mask=0 -> m=a[i]-0=a[i]; mask=-1 ->
        total += m;                                       //    m=a[i]-diff=a[i]-(a[i]-b[i])=b[i] -- zero branches
    }
    return total; // returns the computed result
}
 
int main(void) {                              // program entry point
    srand(2024);                              // => co-25: fixed seed -- reproducible dataset
    int *a = malloc((size_t)N * sizeof(int)); // heap-allocates memory for a
    int *b = malloc((size_t)N * sizeof(int)); // heap-allocates memory for b
    if (!a || !b) {
        fprintf(stderr, "alloc failed\n");
        return 1;
    } // prints a report line
    for (int i = 0; i < N; i++) {               // => uniformly random pairs -- no exploitable pattern
        a[i] = (int)(rand() % 200001) - 100000; // assigns a[i]
        b[i] = (int)(rand() % 200001) - 100000; // assigns b[i]
    }
 
    double best_branchy = 1e18, best_branchless = 1e18; // declares best_branchy
    long sum_branchy = 0, sum_branchless = 0;           // declares sum_branchy
    for (int t = 0; t < TRIALS; t++) {                  // => co-25: best-of-N -- keep the fastest clean run
        double t0 = now_seconds();                      // declares t0
        sum_branchy = sum_branchy_max(a, b, N);         // assigns sum_branchy
        double t1 = now_seconds();                      // declares t1
        if (t1 - t0 < best_branchy)
            best_branchy = t1 - t0; // conditional check
 
        double t2 = now_seconds();                    // declares t2
        sum_branchless = sum_branchless_max(a, b, N); // assigns sum_branchless
        double t3 = now_seconds();                    // declares t3
        if (t3 - t2 < best_branchless)
            best_branchless = t3 - t2; // conditional check
    }
 
    printf("branchy    sum=%ld, best of %d: %.4f s\n", sum_branchy, TRIALS,
           best_branchy); // prints a report line
    printf("branchless sum=%ld, best of %d: %.4f s\n", sum_branchless, TRIALS,
           best_branchless);                                // prints a report line
    double speedup = best_branchy / best_branchless;        // => co-21: how much the branchless rewrite recovered
    printf("branchless is %.2fx faster -> %s\n", speedup,   // prints a report line
           (sum_branchy == sum_branchless && speedup > 1.1) // continues the printf(...) call above
               ? "PASS (identical output, branchless measurably faster on random "
                 "data)"                                             // continues the printf(...) call above
               : "FAIL");                                            // continues the printf(...) call above
    free(a);                                                         // releases a's heap memory
    free(b);                                                         // releases b's heap memory
    return (sum_branchy == sum_branchless && speedup > 1.1) ? 0 : 1; // returns the computed result
}

branchy    sum=1666530063850, best of 3: 0.2236 s
branchless sum=1666530063850, best of 3: 0.0322 s
branchless is 6.94x faster -> PASS (identical output, branchless measurably faster on random data)

// learning/code/ex-38-pipeline-dependency-chain/dependency_chain.c
/* Example 38: time a serial dependent add chain vs 4 independent add chains --
   verify the independent version is faster (co-20, co-22). */
#include <stdio.h> // => printf -- the timing/PASS report this program prints
#include <time.h>  // => clock_gettime -- the portable wall-clock timer used below
 
#define OPS \
    400000000L // => co-20: 400M total increments in EITHER version -- equal total
               // work
 
static double now_seconds(void) {                        // => co-25: shared wall-clock helper, this topic's standard pattern
    struct timespec ts;                                  // supporting statement for this example
    clock_gettime(CLOCK_MONOTONIC, &ts);                 // calls clock_gettime(...)
    return (double)ts.tv_sec + (double)ts.tv_nsec / 1e9; // returns the computed result
}
 
// co-20: a pure SERIAL dependency chain -- iteration i+1's `x = x + 1` cannot
// even START until iteration i's result is committed, because it reads the
// value iteration i just wrote. `volatile` forces a real store+load every step
// (not a register-only loop the compiler could fold to `x=OPS`), so this
// exposes the CPU's add latency chained OPS times with NO opportunity for the
// pipeline to overlap independent work.
static long dependent_chain(long ops) { // defines dependent_chain(): helper
                                        // function used by this example
    volatile long x = 0;                // => co-20: volatile -- forces a real memory round-trip
    for (long i = 0; i < ops; i++) {    // loop header controlling the sweep below
        x = x + 1;                      // => co-20: this step depends on the PREVIOUS step's x
    }
    return x; // returns the computed result
}
 
// co-22: FOUR independent chains, interleaved in ONE loop -- x0..x3 have no
// data dependency on each other, so a superscalar out-of-order core can
// dispatch and execute all four adds for one loop iteration concurrently
// instead of serializing them; each individual chain is still
// `volatile`-serialized against ITSELF, but the four chains overlap with each
// other, cutting the exposed critical-path length ~4x.
static long independent_chains(long ops) { // defines independent_chains(): helper function
                                           // used by this example
    volatile long x0 = 0, x1 = 0, x2 = 0,
                  x3 = 0;                // => co-22: four separate accumulators, no cross-deps
    for (long i = 0; i < ops / 4; i++) { // => co-22: ops/4 iterations * 4 chains = same total OPS
        x0 = x0 + 1;                     // => co-22: these four statements are mutually
        x1 = x1 + 1;                     //    independent -- the CPU can run them in parallel
        x2 = x2 + 1;                     // assigns x2
        x3 = x3 + 1;                     // assigns x3
    }
    return x0 + x1 + x2 + x3; // => co-22: combined only ONCE, at the very end
}
 
int main(void) {                               // program entry point
    double t0 = now_seconds();                 // declares t0
    long dep_result = dependent_chain(OPS);    // => co-20: the latency-bound baseline
    double t1 = now_seconds();                 // declares t1
    long ilp_result = independent_chains(OPS); // => co-22: the throughput-bound, overlapped version
    double t2 = now_seconds();                 // declares t2
 
    double secs_dep = t1 - t0; // declares secs_dep
    double secs_ilp = t2 - t1; // declares secs_ilp
    printf("OPS=%ld total increments in each version\n",
           OPS); // prints a report line
    printf("dependent chain (1 accumulator):    result=%ld, %.4f s\n", dep_result,
           secs_dep);                                                                          // prints a report line
    printf("independent chains (4 accumulators): result=%ld, %.4f s\n", ilp_result, secs_ilp); // prints a report line
    double speedup = secs_dep / secs_ilp;                                                      // => co-22: how much overlap the 4 independent chains bought
    printf("independent chains are %.2fx faster -> %s\n",
           speedup,                                                              // prints a report line
           (dep_result == ilp_result && speedup > 1.1)                           // continues the printf(...) call above
               ? "PASS (identical result, independent chains measurably faster)" // continues the printf(...) call above
               : "FAIL");                                                        // continues the printf(...) call above
    return (dep_result == ilp_result && speedup > 1.1) ? 0 : 1;                  // returns the computed result
}

OPS=400000000 total increments in each version
dependent chain (1 accumulator):    result=400000000, 0.1387 s
independent chains (4 accumulators): result=400000000, 0.0657 s
independent chains are 2.11x faster -> PASS (identical result, independent chains measurably faster)

// learning/code/ex-39-loop-unrolling/loop_unroll.c
/* Example 39: unroll a single-accumulator reduction loop 8x -- verify higher
   throughput than the rolled loop (co-20, co-22). */
#include <stdio.h>  // => printf -- the timing/PASS report this program prints
#include <stdlib.h> // => malloc/free -- the array being reduced
#include <time.h>   // => clock_gettime -- the portable wall-clock timer used below
 
#define N \
    200000000    // => co-20: 200M elements -- N is a multiple of 8, no remainder
                 // handling needed
#define TRIALS 3 // => co-25: best-of-3 -- shared-machine noise smoothing
 
static double now_seconds(void) {                        // => co-25: shared wall-clock helper, this topic's standard pattern
    struct timespec ts;                                  // supporting statement for this example
    clock_gettime(CLOCK_MONOTONIC, &ts);                 // calls clock_gettime(...)
    return (double)ts.tv_sec + (double)ts.tv_nsec / 1e9; // returns the computed result
}
 
// co-20: the ROLLED loop -- one `cmp`, one conditional branch, one index
// increment, and one add PER element. `vectorize/unroll(disable)` stops clang's
// own optimizer from doing this example's job for it, so the measured gap below
// is really about OUR manual unrolling, not the auto-vectorizer (that
// comparison belongs to ex-47).
static long sum_rolled(const int *arr,
                       int n) {                       // defines sum_rolled(): helper function used by this example
    long sum = 0;                                     // declares sum
#pragma clang loop vectorize(disable) unroll(disable) // supporting statement for this example
    for (int i = 0; i < n; i++) {                     // loop header controlling the sweep below
        sum += arr[i];                                // => co-20: 1 add's worth of USEFUL work per iteration,
    } //    but paired with a full cmp+branch+increment
    return sum; // returns the computed result
}
 
// co-20: manually UNROLLED 8x, still ONE accumulator (the dependency chain is
// NOT broken -- each `sum +=` still depends on the previous one) -- the only
// thing that changes is the loop-control overhead: one cmp+branch+increment now
// covers EIGHT adds instead of one, so co-22's superscalar front-end has less
// bookkeeping to issue per unit of useful work, even though the adds themselves
// stay serialized.
static long sum_unrolled8(const int *arr,
                          int n) {                    // defines sum_unrolled8(): helper function used by this example
    long sum = 0;                                     // declares sum
#pragma clang loop vectorize(disable) unroll(disable) // supporting statement for this example
    for (int i = 0; i < n; i += 8) {                  // => co-20: ONE cmp+branch+increment per 8 elements
        sum += arr[i];                                // => co-20: still a single serial chain of 8 adds --
        sum += arr[i + 1];                            //    ONLY the loop-control cost shrank, not the
        sum += arr[i + 2];                            //    per-add latency (that's ex-40's job, not this one)
        sum += arr[i + 3];                            // updates sum
        sum += arr[i + 4];                            // updates sum
        sum += arr[i + 5];                            // updates sum
        sum += arr[i + 6];                            // updates sum
        sum += arr[i + 7];                            // updates sum
    }
    return sum; // returns the computed result
}
 
int main(void) {                                // program entry point
    int *arr = malloc((size_t)N * sizeof(int)); // heap-allocates memory for arr
    if (!arr) {
        fprintf(stderr, "alloc failed\n");
        return 1;
    } // prints a report line
    for (int i = 0; i < N; i++)
        arr[i] = (i % 7) - 3; // => small deterministic values, no overflow risk
 
    double best_rolled = 1e18, best_unrolled = 1e18; // declares best_rolled
    long sum_r = 0, sum_u = 0;                       // declares sum_r
    for (int t = 0; t < TRIALS; t++) {               // => co-25: best-of-N -- keep the fastest clean run
        double t0 = now_seconds();                   // declares t0
        sum_r = sum_rolled(arr, N);                  // assigns sum_r
        double t1 = now_seconds();                   // declares t1
        if (t1 - t0 < best_rolled)
            best_rolled = t1 - t0; // conditional check
 
        double t2 = now_seconds();     // declares t2
        sum_u = sum_unrolled8(arr, N); // assigns sum_u
        double t3 = now_seconds();     // declares t3
        if (t3 - t2 < best_unrolled)
            best_unrolled = t3 - t2; // conditional check
    }
 
    printf("rolled   sum=%ld, best of %d: %.4f s\n", sum_r, TRIALS,
           best_rolled); // prints a report line
    printf("unrolled sum=%ld, best of %d: %.4f s\n", sum_u, TRIALS,
           best_unrolled);                                                      // prints a report line
    double speedup = best_rolled / best_unrolled;                               // => co-20: how much the reduced loop overhead bought
    printf("unrolled is %.2fx faster -> %s\n", speedup,                         // prints a report line
           (sum_r == sum_u && speedup > 1.05)                                   // continues the printf(...) call above
               ? "PASS (identical sums, unrolled measurably higher throughput)" // continues
                                                                                // the
                                                                                // printf(...)
                                                                                // call
                                                                                // above
               : "FAIL");                                                       // continues the printf(...) call above
    free(arr);                                                                  // releases arr's heap memory
    return (sum_r == sum_u && speedup > 1.05) ? 0 : 1;                          // returns the computed result
}

rolled   sum=-6, best of 3: 0.0803 s
unrolled sum=-6, best of 3: 0.0146 s
unrolled is 5.50x faster -> PASS (identical sums, unrolled measurably higher throughput)

// learning/code/ex-40-ilp-multiple-accumulators/ilp_accumulators.c
/* Example 40: sum a large array with 1 accumulator vs 4 accumulators --
   verify the 4-accumulator version is faster because it breaks the
   dependency chain (co-22). */
#include <stdio.h>  // => printf -- the timing/PASS report this program prints
#include <stdlib.h> // => malloc/free -- the array being reduced
#include <time.h>   // => clock_gettime -- the portable wall-clock timer used below
 
#define N \
    200000000    // => co-22: 200M elements, a multiple of 4 -- no remainder handling
                 // needed
#define TRIALS 3 // => co-25: best-of-3 -- shared-machine noise smoothing
 
static double now_seconds(void) {                        // => co-25: shared wall-clock helper, this topic's standard pattern
    struct timespec ts;                                  // supporting statement for this example
    clock_gettime(CLOCK_MONOTONIC, &ts);                 // calls clock_gettime(...)
    return (double)ts.tv_sec + (double)ts.tv_nsec / 1e9; // returns the computed result
}
 
// co-22: ONE accumulator over a REAL array -- every `sum += arr[i]` must wait
// for the previous one to finish (co-20's dependency chain), so the add's
// latency (not its throughput) is the bottleneck, no matter how many execution
// ports this superscalar core has. `vectorize/unroll(disable)` isolates the ILP
// effect this example is about from clang's own auto-optimizations
// (ex-39/ex-47's job).
static long sum_1acc(const int *arr,
                     int n) {                         // defines sum_1acc(): helper function used by this example
    long sum = 0;                                     // declares sum
#pragma clang loop vectorize(disable) unroll(disable) // supporting statement for this example
    for (int i = 0; i < n; i++) {                     // loop header controlling the sweep below
        sum += arr[i];                                // => co-20: strictly serial -- add i+1 waits on add i
    }
    return sum; // returns the computed result
}
 
// co-22: FOUR accumulators over the SAME array -- sum0..sum3 have no dependency
// on each other, so a superscalar out-of-order core can execute several of
// these adds per cycle instead of waiting on one serial chain; only combined
// into one total at the very end, after the loop.
static long sum_4acc(const int *arr,
                     int n) { // defines sum_4acc(): helper function used by this example
    long sum0 = 0, sum1 = 0, sum2 = 0,
         sum3 = 0;                                    // => co-22: four independent partial sums
#pragma clang loop vectorize(disable) unroll(disable) // supporting statement for this example
    for (int i = 0; i < n; i += 4) {                  // => co-22: n/4 iterations, 4 elements consumed each
        sum0 += arr[i];                               // => co-22: these four adds are mutually independent --
        sum1 += arr[i + 1];                           //    the CPU can execute them concurrently
        sum2 += arr[i + 2];                           // updates sum2
        sum3 += arr[i + 3];                           // updates sum3
    }
    return sum0 + sum1 + sum2 + sum3; // => co-22: combined ONCE, after all chains finish
}
 
int main(void) {                                // program entry point
    int *arr = malloc((size_t)N * sizeof(int)); // heap-allocates memory for arr
    if (!arr) {
        fprintf(stderr, "alloc failed\n");
        return 1;
    } // prints a report line
    for (int i = 0; i < N; i++)
        arr[i] = (i % 5) - 2; // => small deterministic values, no overflow risk
 
    double best_1acc = 1e18, best_4acc = 1e18; // declares best_1acc
    long sum_1 = 0, sum_4 = 0;                 // declares sum_1
    for (int t = 0; t < TRIALS; t++) {         // => co-25: best-of-N -- keep the fastest clean run
        double t0 = now_seconds();             // declares t0
        sum_1 = sum_1acc(arr, N);              // assigns sum_1
        double t1 = now_seconds();             // declares t1
        if (t1 - t0 < best_1acc)
            best_1acc = t1 - t0; // conditional check
 
        double t2 = now_seconds(); // declares t2
        sum_4 = sum_4acc(arr, N);  // assigns sum_4
        double t3 = now_seconds(); // declares t3
        if (t3 - t2 < best_4acc)
            best_4acc = t3 - t2; // conditional check
    }
 
    printf("1 accumulator sum=%ld, best of %d: %.4f s\n", sum_1, TRIALS,
           best_1acc); // prints a report line
    printf("4 accumulator sum=%ld, best of %d: %.4f s\n", sum_4, TRIALS,
           best_4acc);                                                     // prints a report line
    double speedup = best_1acc / best_4acc;                                // => co-22: how much breaking the dependency bought
    printf("4-accumulator is %.2fx faster -> %s\n", speedup,               // prints a report line
           (sum_1 == sum_4 && speedup > 1.2)                               // continues the printf(...) call above
               ? "PASS (identical sums, 4 accumulators measurably faster)" // continues
                                                                           // the
                                                                           // printf(...)
                                                                           // call
                                                                           // above
               : "FAIL");                                                  // continues the printf(...) call above
    free(arr);                                                             // releases arr's heap memory
    return (sum_1 == sum_4 && speedup > 1.2) ? 0 : 1;                      // returns the computed result
}