read the source · cache/05_mlp_prefetch.c
#include "../tools/bench.h"
#define BYTES (128ull << 20)
#define NODES (BYTES / 16) /* node = {next, ahead}: 16 bytes, both in one line */
static void sattolo(uint64_t *nxt, size_t n, uint64_t *seed) {
for (size_t i = 0; i < n; i++) nxt[i] = i;
for (size_t i = n - 1; i > 0; i--) { size_t j = (size_t)(bench_rand(seed) % i); uint64_t t = nxt[i]; nxt[i] = nxt[j]; nxt[j] = t; }
}
/* K independent chains started at K different points of the same cycle. */
__attribute__((noinline)) static uint64_t chase(const uint64_t *p, int k, uint64_t steps) {
uint64_t idx[16]; for (int c = 0; c < k; c++) idx[c] = (uint64_t)c * (NODES / 17);
for (uint64_t s = 0; s < steps; s++) for (int c = 0; c < k; c++) idx[c] = p[2 * idx[c]];
uint64_t r = 0; for (int c = 0; c < k; c++) r += idx[c]; return r;
}
/* ONE chain, but each node also stores the node D steps ahead ("jump pointer"), so we can prefetch it. */
__attribute__((noinline)) static uint64_t chase_jump(const uint64_t *p, uint64_t steps, int use_prefetch) {
uint64_t idx = 0;
for (uint64_t s = 0; s < steps; s++) {
if (use_prefetch) __builtin_prefetch(&p[2 * p[2 * idx + 1]], 0, 0); /* address known NOW, needed D steps later */
idx = p[2 * idx];
}
return idx;
}
/* Independent loads with addresses known in advance (an index array): does prefetch help here? */
__attribute__((noinline)) static uint64_t gather(const uint64_t *p, const uint32_t *ix, uint64_t n, int dist) {
uint64_t s = 0;
for (uint64_t i = 0; i < n; i++) { if (dist) __builtin_prefetch(&p[2 * ix[i + dist]], 0, 0); s += p[2 * ix[i]]; }
return s;
}
int main(int argc, char **argv) {
int D = argc > 1 ? atoi(argv[1]) : 8;
uint64_t seed = 7; uint64_t *nxt = malloc(NODES * 8); sattolo(nxt, NODES, &seed);
uint64_t *p = malloc(BYTES); /* p[2i] = next, p[2i+1] = D steps ahead */
uint64_t *order = malloc(NODES * 8); /* walk the cycle once to know who is D ahead */
uint64_t cur = 0; for (uint64_t k = 0; k < NODES; k++) { order[k] = cur; cur = nxt[cur]; }
for (uint64_t k = 0; k < NODES; k++) { uint64_t i = order[k]; p[2 * i] = nxt[i]; p[2 * i + 1] = order[(k + (uint64_t)D) % NODES]; }
free(order); free(nxt);
uint64_t steps = 4000000;
printf("== 1: K independent dependent chains over 128 MB (steps per chain = %llu) ==\n", (unsigned long long)steps);
printf("%8s %12s\n", "chains", "ns/load");
for (int k = 1; k <= 16; k *= 2) {
uint64_t t0 = bench_ns(); uint64_t r = chase(p, k, steps); BENCH_KEEP(r);
printf("%8d %12.1f\n", k, (double)(bench_ns() - t0) / (double)(steps * (uint64_t)k));
}
printf("\n== 2: ONE chain with jump pointers (D=%d): prefetch the node D steps ahead ==\n", D);
uint64_t t0 = bench_ns(); uint64_t r = chase_jump(p, steps, 0); BENCH_KEEP(r);
printf("%-22s %8.1f ns/load\n", "no prefetch", (double)(bench_ns() - t0) / (double)steps);
t0 = bench_ns(); r = chase_jump(p, steps, 1); BENCH_KEEP(r);
printf("%-22s %8.1f ns/load\n", "prefetch(ahead)", (double)(bench_ns() - t0) / (double)steps);
uint64_t n = 8000000; uint32_t *ix = malloc((n + 64) * 4);
for (uint64_t i = 0; i < n + 64; i++) ix[i] = (uint32_t)(bench_rand(&seed) % NODES);
printf("\n== 3: independent loads with addresses in an index array: prefetch distance ==\n");
printf("%9s %12s\n", "distance", "ns/load");
int dists[] = {0, 4, 16, 64};
for (size_t d = 0; d < sizeof dists / sizeof *dists; d++) {
t0 = bench_ns(); r = gather(p, ix, n, dists[d]); BENCH_KEEP(r);
printf("%9d %12.1f\n", dists[d], (double)(bench_ns() - t0) / (double)n);
}
return 0;
}