/*
 * p4lib.c —— 前置讲 P4 的 C 函数：测量存储层次的延迟与带宽
 * =====================================================================
 *
 * 【为什么要用 C】
 *   想测"读一次内存要多久"（几纳秒到上百纳秒），Python 每做一步就要几十纳秒的解释器开销，
 *   会把要测的东西完全淹没。所以把最内层的循环写成 C，由 Python 通过 ctypes 调用。
 *
 * 【指针追逐 pointer chasing】
 *   next[] 是一个随机的环：从 0 出发，i = next[i] 一直走，会把每个位置都访问一遍。
 *   每一次读取的地址都取决于上一次读到的值，CPU 无法提前预取、也无法同时发出多个读取，
 *   于是"每一步的平均时间"就是一次内存访问的延迟。数组越大，越装不进各级缓存，延迟越高。
 */

#include <stddef.h>

/* 沿着 next 数组走 steps 步，返回最后停在哪里（返回它是为了防止编译器把循环优化掉） */
long chase(const long* next, long steps) {
    long i = 0;
    for (long s = 0; s < steps; s++) {
        i = next[i];
    }
    return i;
}

/* 以步长 stride 读取 a 里的元素并求和：读取的元素个数 = n / stride。
 * 用 8 个互相独立的累加器：每次加法不必等上一次的结果（打破 P1 §1.3 说的"依赖链"），
 * 这样循环的速度才由"读内存"决定，而不是由"加法的延迟"决定。 */
double sum_stride(const float* a, long n, long stride) {
    double s0 = 0, s1 = 0, s2 = 0, s3 = 0, s4 = 0, s5 = 0, s6 = 0, s7 = 0;
    long i = 0;
    for (; i + 7 * stride < n; i += 8 * stride) {
        s0 += a[i];
        s1 += a[i + stride];
        s2 += a[i + 2 * stride];
        s3 += a[i + 3 * stride];
        s4 += a[i + 4 * stride];
        s5 += a[i + 5 * stride];
        s6 += a[i + 6 * stride];
        s7 += a[i + 7 * stride];
    }
    for (; i < n; i += stride) {
        s0 += a[i];
    }
    return s0 + s1 + s2 + s3 + s4 + s5 + s6 + s7;
}