03 · cache 与数据布局

// c03_order.cpp
// g++ -O2 -std=c++17 c03_order.cpp -o c03_order
#include <cstdio>
#include <vector>
#include <chrono>

using Clock = std::chrono::steady_clock;
static double ms_since(Clock::time_point t) {
    return std::chrono::duration<double, std::milli>(Clock::now() - t).count();
}

int main() {
    const int N = 4096;                       // 4096 x 4096 个 double = 128 MB
    std::vector<double> m((size_t)N * N, 1.0);

    // ① 一行一行走：内存里挨着的元素，挨着访问
    auto t = Clock::now();
    double s1 = 0;
    for (int r = 0; r < N; ++r)
        for (int c = 0; c < N; ++c)
            s1 += m[(size_t)r * N + c];
    double t_row = ms_since(t);

    // ② 一列一列走：每次跳 N 个 double = 32768 字节
    t = Clock::now();
    double s2 = 0;
    for (int c = 0; c < N; ++c)
        for (int r = 0; r < N; ++r)
            s2 += m[(size_t)r * N + c];
    double t_col = ms_since(t);

    std::printf("矩阵 %d x %d double = %.0f MB\n", N, N, (double)N*N*8/1048576.0);
    std::printf("① 按行走: %8.2f ms   和 = %.0f\n", t_row, s1);
    std::printf("② 按列走: %8.2f ms   和 = %.0f\n", t_col, s2);
    std::printf("   慢了   : %8.2f 倍   (两个和一样吗: %s)\n",
                t_col / t_row, s1 == s2 ? "一样" : "不一样");
    return 0;
}

// c03_probe.cpp
// g++ -O2 -std=c++17 c03_probe.cpp -o c03_probe
#include <cstdio>
#include <new>

int main() {
#ifdef __cpp_lib_hardware_interference_size
    std::printf("hardware_destructive_interference_size = %zu\n",
                std::hardware_destructive_interference_size);
#else
    std::printf("(标准库没提供这个常量)\n");
#endif
    return 0;
}

hardware_destructive_interference_size = 64

// c03_line.cpp
// g++ -O2 -std=c++17 c03_line.cpp -o c03_line
#include <cstdio>
#include <vector>
#include <chrono>

using Clock = std::chrono::steady_clock;
static double ms_since(Clock::time_point t) {
    return std::chrono::duration<double, std::milli>(Clock::now() - t).count();
}

int main() {
    const size_t BYTES = 128u << 20;             // ⭐ 摸的范围固定 128 MB，比任何一级缓存都大
    const size_t N = BYTES / sizeof(int);
    std::vector<int> a(N, 1);
    const int REP = 5;                           // 每种间隔量 5 遍取最快的一遍

    std::printf("固定摸完同样的 %zu MB，只改「隔几个 int 取一个」\n", BYTES >> 20);
    std::printf("  间隔(字节)      取了多少个   总耗时(ms)\n");

    for (size_t k = 1; k <= 64; k *= 2) {
        double best = 1e18;
        long long s = 0;
        for (int r = 0; r < REP; ++r) {
            auto t = Clock::now();
            s = 0;
            for (size_t i = 0; i < N; i += k) s += a[i];
            double ms = ms_since(t);
            if (ms < best) best = ms;
        }
        std::printf("  %8zu   %12lld   %10.2f\n", k * sizeof(int), s, best);
    }
    return 0;
}

// c03_ws.cpp
// g++ -O2 -std=c++17 c03_ws.cpp -o c03_ws
#include <cstdio>
#include <vector>
#include <chrono>
#include <numeric>
#include <random>
#include <algorithm>

using Clock = std::chrono::steady_clock;

int main() {
    std::printf("  数据量      每次跳一步的平均耗时(ns)\n");
    for (size_t kb = 8; kb <= 65536; kb *= 4) {
        size_t n = kb * 1024 / sizeof(int);          // 这么多个 int
        std::vector<int> next(n);
        // 造一条走遍所有格子的随机环：next[i] 是下一个要去的格子
        std::vector<int> perm(n);
        std::iota(perm.begin(), perm.end(), 0);
        std::mt19937 rng(12345);
        std::shuffle(perm.begin(), perm.end(), rng);
        for (size_t i = 0; i + 1 < n; ++i) next[perm[i]] = perm[i + 1];
        next[perm[n - 1]] = perm[0];

        const long long STEPS = 20'000'000;
        int p = 0;
        for (long long i = 0; i < (long long)n; ++i) p = next[p];   // 预热
        auto t = Clock::now();
        for (long long i = 0; i < STEPS; ++i) p = next[p];          // ⭐ 一步都不能提前预测
        double ns = std::chrono::duration<double, std::nano>(Clock::now() - t).count() / STEPS;
        std::printf("  %6zu KB    %8.2f     (p=%d)\n", kb, ns, p);
    }
    return 0;
}

// c03_pad.cpp
// g++ -O2 -std=c++17 c03_pad.cpp -o c03_pad
#include <cstdio>
#include <cstdint>
#include <cstddef>

struct Bad  { char  flag; double value; char  tag; int32_t id; };   // 随手写的顺序
struct Good { double value; int32_t id; char  flag; char  tag; };   // 从大到小排

int main() {
    std::printf("字段本身加起来: 1 + 8 + 1 + 4 = %d 字节\n\n",
                (int)(sizeof(char) + sizeof(double) + sizeof(char) + sizeof(int32_t)));

    std::printf("Bad  实际占 %zu 字节  (对齐要求 %zu)\n", sizeof(Bad),  alignof(Bad));
    std::printf("  flag  在偏移 %zu\n", offsetof(Bad, flag));
    std::printf("  value 在偏移 %zu   <- 前面被塞了 7 字节空洞\n", offsetof(Bad, value));
    std::printf("  tag   在偏移 %zu\n", offsetof(Bad, tag));
    std::printf("  id    在偏移 %zu   <- 又塞了 3 字节\n\n", offsetof(Bad, id));

    std::printf("Good 实际占 %zu 字节  (对齐要求 %zu)\n", sizeof(Good), alignof(Good));
    std::printf("  value 在偏移 %zu\n", offsetof(Good, value));
    std::printf("  id    在偏移 %zu\n", offsetof(Good, id));
    std::printf("  flag  在偏移 %zu\n", offsetof(Good, flag));
    std::printf("  tag   在偏移 %zu\n\n", offsetof(Good, tag));

    std::printf("⭐ 同样四个字段，只换了声明顺序: %zu -> %zu 字节，省了 %.0f%%\n",
                sizeof(Bad), sizeof(Good),
                100.0 * (sizeof(Bad) - sizeof(Good)) / sizeof(Bad));
    std::printf("   一条 64 字节的 cache line 能装几个: Bad %zu 个 / Good %zu 个\n",
                64 / sizeof(Bad), 64 / sizeof(Good));
    return 0;
}

// c03_aos.cpp
// g++ -O2 -std=c++17 c03_aos.cpp -o c03_aos
#include <cstdio>
#include <vector>
#include <chrono>

using Clock = std::chrono::steady_clock;
static double ms_since(Clock::time_point t) {
    return std::chrono::duration<double, std::milli>(Clock::now() - t).count();
}

struct Particle {                 // 一个粒子的全部属性摆在一起
    float x, y, z;
    float vx, vy, vz;
    float mass, charge;
};                                // 8 个 float = 32 字节

int main() {
    const size_t N = 8'000'000;
    const int    REP = 5;

    // ① AoS：一个装着「结构体」的数组
    std::vector<Particle> aos(N);
    for (size_t i = 0; i < N; ++i) { aos[i].x = 1.0f; aos[i].mass = 2.0f; }

    // ② SoA：每个属性一个自己的数组
    std::vector<float> sx(N, 1.0f), sy(N), sz(N),
                       svx(N), svy(N), svz(N),
                       smass(N, 2.0f), scharge(N);

    double best_aos = 1e18, best_soa = 1e18;
    float r1 = 0, r2 = 0;

    for (int r = 0; r < REP; ++r) {                 // 只用 x 这一个字段
        auto t = Clock::now();
        float s = 0;
        for (size_t i = 0; i < N; ++i) s += aos[i].x;
        double ms = ms_since(t);
        if (ms < best_aos) { best_aos = ms; r1 = s; }
    }
    for (int r = 0; r < REP; ++r) {
        auto t = Clock::now();
        float s = 0;
        for (size_t i = 0; i < N; ++i) s += sx[i];
        double ms = ms_since(t);
        if (ms < best_soa) { best_soa = ms; r2 = s; }
    }

    std::printf("sizeof(Particle) = %zu 字节，%zu 个粒子共 %.0f MB\n",
                sizeof(Particle), N, (double)N * sizeof(Particle) / 1048576.0);
    std::printf("只求和 x 这一个字段（%zu MB 的有效数据）:\n",
                (size_t)(N * sizeof(float) / 1048576));
    std::printf("  ① AoS  结构体数组: %8.2f ms   (和 %.0f)\n", best_aos, r1);
    std::printf("  ② SoA  数组的结构: %8.2f ms   (和 %.0f)\n", best_soa, r2);
    std::printf("  AoS / SoA        : %8.2f 倍\n", best_aos / best_soa);
    std::printf("⭐ AoS 每搬一条 64 字节的 cache line，只用得上其中 %zu 字节\n",
                64 / sizeof(Particle) * sizeof(float));
    return 0;
}

// c03_false.cpp
// g++ -O2 -std=c++17 -pthread c03_false.cpp -o c03_false
#include <cstdio>
#include <thread>
#include <vector>
#include <chrono>
#include <atomic>

using Clock = std::chrono::steady_clock;
static double ms_since(Clock::time_point t) {
    return std::chrono::duration<double, std::milli>(Clock::now() - t).count();
}

struct Packed  { std::atomic<long long> v; };              // 4 个挤在一起
struct Spread  { std::atomic<long long> v; char pad[56]; };// ⭐ 撑到 64 字节，各占一条 cache line

template <class Slot>
double run(int nthreads, long long iters) {
    std::vector<Slot> slots(nthreads);
    for (auto& s : slots) s.v.store(0, std::memory_order_relaxed);
    std::vector<std::thread> ts;
    auto t = Clock::now();
    for (int k = 0; k < nthreads; ++k)
        ts.emplace_back([&slots, k, iters] {
            for (long long i = 0; i < iters; ++i)
                slots[k].v.fetch_add(1, std::memory_order_relaxed);
        });
    for (auto& th : ts) th.join();
    return ms_since(t);
}

int main() {
    const int  T = 4;
    const long long ITER = 20'000'000;
    std::printf("硬件线程数: %u\n", std::thread::hardware_concurrency());
    std::printf("sizeof(Packed)=%zu  sizeof(Spread)=%zu\n\n",
                sizeof(Packed), sizeof(Spread));
    std::printf("%d 个线程，各自给【自己的】计数器加 %lld 次（互不相干的变量）\n", T, ITER);

    for (int r = 0; r < 3; ++r) {
        double a = run<Packed>(T, ITER);
        double b = run<Spread>(T, ITER);
        std::printf("  第%d次:  挤在一起 %8.2f ms   隔开 %8.2f ms   慢 %.2f 倍\n",
                    r + 1, a, b, a / b);
    }
    return 0;
}

# c03_pyscatter.py
import random, time, array

N = 2_000_000

# ① 一次性造出来的对象，地址大体是挨着的
objs = [float(i) for i in range(N)]
gaps = [abs(id(objs[i + 1]) - id(objs[i])) for i in range(1000)]
print("① 顺序造出来的 float 对象，相邻两个的地址差（前 1000 个的中位数）:",
      sorted(gaps)[len(gaps) // 2], "字节")

# ② 把列表打乱：对象本身没动，但「访问顺序」和「内存顺序」错开了
shuffled = objs[:]
random.seed(0)
random.shuffle(shuffled)
gaps2 = [abs(id(shuffled[i + 1]) - id(shuffled[i])) for i in range(1000)]
print("② 打乱之后，相邻两个的地址差（中位数）:",
      sorted(gaps2)[len(gaps2) // 2], "字节")

def timed(f, rep=5):
    best = 1e18
    for _ in range(rep):
        t = time.perf_counter()
        r = f()
        best = min(best, (time.perf_counter() - t) * 1000)
    return best, r

t1, s1 = timed(lambda: sum(objs))
t2, s2 = timed(lambda: sum(shuffled))
arr = array.array('d', objs)
t3, s3 = timed(lambda: sum(arr))

print(f"③ 顺序列表求和  : {t1:8.1f} ms")
print(f"   打乱列表求和  : {t2:8.1f} ms   (慢 {t2/t1:.2f} 倍)")
print(f"   array('d') 求和: {t3:8.1f} ms   (对顺序列表 {t1/t3:.2f} 倍)")
print("   三个和一样吗:", s1 == s2 == s3)