指针访存优化

下面这个循环，把 *b 的值填满数组 a：

void func(int *a, int *b, int n) {
    for (int i = 0; i < n; ++i) {
        a[i] = *b;
    }
}

*b 在循环里从来没被赋值过，按理读一次就够。GCC 13 -O2 编出来却是每轮都读：

.L3:
    movl  (%rsi), %eax      # 每轮读一次 *b
    addq  $4, %rdi
    movl  %eax, -4(%rdi)    # 写 a[i]
    cmpq  %rdx, %rdi
    jne   .L3

原因是 b 可能就指向 a 里的某一格，写 a[i] 可能把 *b 改掉，编译器不能假设它没变。这篇讲三件事：怎么让编译器敢少读内存；数据怎么存得更省，链里的“下一个”用几个字节，指针和几个 ID 怎么压进一个整数；大块写和写设备时用什么指令。汇编是 GCC 13.3、x86-64 的真实输出，周期数是帮助理解的范围，没有计时。

1. `__restrict`：向编译器保证两个指针不重叠

1.1 别名（aliasing）：两个指针可能指向同一块内存

两个指针指向同一块内存，叫它们互为别名。上面的循环就是别名挡住了优化。给参数加上 __restrict：

void func_restrict(int *__restrict a, int *__restrict b, int n) {
    for (int i = 0; i < n; ++i) {
        a[i] = *b;
    }
}

意思是“在这个函数里，通过这个指针访问的内存，不会通过别的指针访问”。编译器就把 movl (%rsi), %eax 提到循环外只读一次，循环里只剩写，还顺手展开成每轮写 2 个。

1.2 `-O3`：编译器自己在运行时检查一遍

-O3 下，不带 __restrict 的 func 也向量化了。编译器生成了两个版本的循环，开头先比地址：b 不落在 a[0..n) 里，就走一次写 16 B 的向量版；落在里面，就走每轮重读 *b 的逐个版。这叫循环多版本（loop versioning）。所以 -O3 下 __restrict 省的是开头这几条比较和那份备用代码；-O2 下，或者别名关系复杂到编译器不愿生成检查时，差别才大。

1.3 代价：这是你的承诺，编译器不检查

违反了就是未定义行为。 写了 __restrict，调用时又传了重叠的指针，编译器照样按“不重叠”优化，结果静默算错，没有任何报错。
它只影响编译器，CPU 看不见。 机器码里没有“restrict”，它的效果全在“编译器生成了哪些指令”。CPU 照样检查每个读和前面的写是否同址。
不是标准 C++。 C99 有 restrict，C++ 没有；GCC、Clang、MSVC 都支持 __restrict 扩展。
类型不同时本来就不用写。 int* 和 float* 按严格别名规则（strict aliasing）默认不重叠；__restrict 管的是同一种类型的两个指针。参数写成 const T* 也代替不了它：const 只说你不通过它改，别的指针照样能改（const 和 constexpr）。

2. 链式结构里“下一个”存多宽

2.1 前提：pointer chasing 每一步都要等上一步

链表、订单簿的价位链、对象池的空闲链，都是“读出下一个在哪，再去读它”。下一次读的地址，要等这一次读完才知道，所以这种 pointer chasing 没法提前发读（内存延迟与带宽），每一步都付满一次访存延迟：L1 约 1 ns（4–5 个周期），L2 约 3–5 ns，L3 约 10–30 ns，内存约 70–120 ns。链全在 L1 里时，一步只要几个周期，多一条指令就看得出来；链落到内存，每一步都是一次完整的内存延迟，多几条指令无关紧要，要紧的是链能不能小到落进更近的一层。所以链快不快只看两件事：每一步的指令要多久，整条链有多大。“下一个”存多宽，同时影响这两件事。

2.2 下标还是指针：寻址方式差 1 个周期，大小差 1 倍

“下一个”可以存成 4 字节下标（k = q[k]），也可以存成 8 字节指针（k = k->ptr）。编出来每步各是一条指令：

chase_int:   movslq (%rcx,%rax,4), %rax     # 基址 + 下标 × 4，读 4 字节并扩成 64 位
chase_ptr:   movq   (%rax), %rax            # 直接按指针读 8 字节

下标版并没有多一条乘法：× 4 是 x86 寻址方式的一部分（scale）。两者的差别在寻址方式本身：很多 x86 核上，只有“一个寄存器（加一个小偏移）”的简单寻址，L1 命中时约 4 个周期出结果；带下标的寻址约 5 个周期。所以全在 L1 时，指针链每步快约 1 个周期。

反过来，指针是 8 字节，下标是 4 字节，同样多的节点，指针链大一倍。1024 个节点是 8 KiB 对 4 KiB，都在 L1 里，指针快；100 万个节点是 8 MiB 对 4 MiB，下标版可能还在 L3、指针版已经要读内存，那一步差的就是 10–30 ns 对 70–120 ns，1 个周期的寻址优势完全不算数。链小时看指令，链大时看字节数。

2.3 “32 位指针”：64 位程序里通常就是下标

指针快在寻址，下标赢在大小，自然会想两头都要：让指针本身只占 4 字节，拿来就能直接读。这就是常说的“32 位指针”。

64 位程序里一般做不到，因为 4 字节装不下地址。4 字节最多表示到 4 GiB（0xffffffff），而 64 位程序的地址一般远在这之上，Linux 上常见 0x7ffd5a3c1e80 这样的。把地址直接转成 uint32_t，g++ 会报错（cast ... loses precision，意思是转了会丢信息）；硬转（先转成 uintptr_t 再截成 uint32_t）能编过，但高位被扔掉，转回指针就指到别处了。

4 字节能存下的，只有“下一个在数组里排第几”（或者离数组开头多少字节）。要跳过去，得先算“数组起点 + 第几个 × 节点大小”，这就是上面的下标版，那 1 个周期照样要付。所以“32 位指针”多数时候只是下标换了个叫法，指针和下标之间的取舍还是绕不开。

例外有两种：节点本来就放在 4 GiB 以下（比如 Linux 上用 mmap 加 MAP_32BIT 申请的内存，落在最低的 2 GiB 里），这时 4 字节存的就是完整地址，可以直接读；或者整个程序换成 4 字节指针的编法（编成 32 位程序 -m32，或者很少有人用的 x32 -mx32）。

2.4 24 位紧凑下标：省 25% 空间，每步多几条指令

下标版的链如果只比某一层缓存大一点，还可以再压一压：每个元素只占 3 字节，比 4 字节下标省 25%。代价是每走一步要读 3 个字节再拼起来：

int chase_24(const uint8_t* q, int k, int steps) {   // k 是字节偏移 = 下标 × 3
    for (int i = 0; i < steps; i++) {
        int next_val = q[k] | (q[k + 1] << 8) | (q[k + 2] << 16);
        k = next_val & ((1 << 24) - 1);
    }
    return k;
}

编出来每步是 3 次读、2 次移位、2 次或，还有几条算地址、扩展符号的指令，而它们都在依赖链上。全在 L1 时它比 4 字节下标慢；只有省下的 25% 正好让整条链从下一层缓存“掉回”上一层，才划算。

容量也要算对：这里存的是字节偏移（下标 × 3），24 位最大 $2^{24} - 1$，所以最多约 $2^{24} / 3 \approx 559$ 万个元素，不是 $2^{24}$ 个。想要约 1600 万个，就存下标本身，每步再乘 3（一条 lea）。

3. 指针压缩：存偏移，不存地址

下标能用，前提是池子里每个元素一样大：第 k 个就在“起点 + k × 元素大小”。对象大小不一，或者几种类型混放在同一块内存里（订单和价位节点挤在一块 arena 里，长短不一的消息排在一块缓冲区里），就没有“第几个”可言，只能记字节位置：离池子开头多远。

直接存字节偏移，4 字节只能管 4 GiB。可对象一般按 $2^s$ 字节对齐，每个对象的起点都是 $2^s$ 的倍数，偏移的低 $s$ 位永远是 0，存它们纯属浪费。把偏移右移 $s$ 位再存，用的时候左移回来：

$$ \text{编码} = \frac{\text{地址} - \text{基址}}{2^{s}}, \qquad \text{地址} = \text{基址} + \text{编码} \times 2^{s} $$

比如按 16 字节对齐（$s = 4$），对象在离池子开头 0x1230 字节处，低 4 位是 0，只存 0x123；用的时候左移 4 位变回 0x1230，再加上池子的起点。同样 4 字节，能管的范围从 4 GiB 变成 $2^{32} \times 16$ B = 64 GiB。

这样看，下标其实是它的特例：对象一样大、大小正好是 $2^s$ 时，右移 $s$ 位的偏移就是下标。两者只是单位不同：下标以“一个元素”为单位，压缩指针以“对齐粒度 $2^s$”为单位。正因为单位是对齐粒度，它能指向池子里任何一个对齐的对象，不管什么类型、多大。容量上它并不比下标强：同样 4 字节，下标能管 $2^{32}$ 个元素，元素越大，管的字节越多（64 字节的节点就是 256 GiB）。

代价也和下标一样，落在每走一步上：解码是一次移位加一次加法。移 0–3 位时（乘 1、2、4、8），x86 的寻址方式能把这一步和读合成一条指令，和下标版一样约 5 个周期；移 4 位就要先单独移一次，多约 1 个周期。换来的是节点里每个指针从 8 字节变 4 字节。订单簿、侵入式链表这种一个节点里有好几个指针的结构，每个指针都省一半，节点能小一截，一条缓存行装得更多。JVM 的 compressed oops 就是这么做的：32 位编码、按 8 字节对齐移 3 位，管 32 GB 的堆。

一个容易写错的地方：空指针通常编成 0，而池子里第一个对象的偏移也是 0。指针编成了小整数，“没有”和“第一个”就撞在一起：按“偏移就是编码”写，压缩 &pool[0] 再解压，得到的是 nullptr。所以把 0 留给空指针，其余编码在原来的基础上加 1：

template <typename T>
struct Compressed32 {
    T* base;
    uint32_t shift;                                         // log2(alignof(T))
    uint32_t pack(const T* p) const {
        if (!p) return 0;
        return uint32_t(((reinterpret_cast<uintptr_t>(p) - reinterpret_cast<uintptr_t>(base)) >> shift) + 1);
    }
    T* unpack(uint32_t c) const {
        if (c == 0) return nullptr;
        return reinterpret_cast<T*>(reinterpret_cast<uintptr_t>(base) + (uintptr_t(c - 1) << shift));
    }
};

解码里的 $-1$ 不用真减：把基址提前换成 $\text{基址} - 2^s$，它就并进了那次加法。也可以另找一个值（比如 UINT32_MAX）表示空。另外两条要守住：池子不能超过编码能表示的范围；对象地址必须真的按 $2^s$ 对齐，否则移掉的低位就丢了。

4. 复合索引：几个 ID 拼成一个 64 位整数

持仓、风控这类记录，常要按几个 ID 一起查。几个字段分开存，比较要比好几次，哈希要把几个值揉在一起。把客户 ID（32 位）、会员 ID（12 位）、合约 ID（20 位）拼成一个 uint64_t，就能当一个整数做哈希表的键、排序、一条指令比较：

struct CompositeIndex {
    uint64_t client : 32;
    uint64_t member : 12;
    uint64_t contract : 20;
};
uint64_t encode(CompositeIndex idx) {
    return uint64_t(idx.client) | (uint64_t(idx.member) << 32) | (uint64_t(idx.contract) << 44);
}
CompositeIndex decode(uint64_t val) {
    return {
        .client = val & 0xFFFFFFFF,
        .member = (val >> 32) & 0xFFF,
        .contract = (val >> 44) & 0xFFFFF
    };
}

encode 里的 uint64_t(...) 不能省。12 位、20 位的位域在运算前会先提升成 int（int 装得下它的所有值），直接写 idx.member << 32，就是对 32 位的 int 左移 32 位，未定义行为。实测 GCC 13 只给一个 -Wshift-count-overflow 警告，结果里 member、contract 全丢了；Clang 18 干脆返回 0。另外，位域在内存里怎么排是实现定义的，要稳定的编码就像 encode 这样显式移位，不要直接把结构体的字节当整数用。

5. 大块写和写设备

5.1 Non-temporal store：不读回、不进缓存

普通写碰到不在缓存里的行，先整条读回（RFO），之后再写回，一条行在总线上走两趟。流式写（non-temporal store，_mm256_stream_si256 这类）在 WC 缓冲（写合并缓冲）里凑满 64 B 直接写内存，只走一趟，带宽上限最多翻倍（机制见内存延迟与带宽的流式写一节）。用的时候要守几条规矩：

只用在大块、近期不再读的数据上。 写完数据不在缓存里，马上要读就得从内存读回来。块比缓存小时，普通写反而更快。
地址要对齐。 _mm256_stream_si256 要求 32 字节对齐，不对齐直接崩溃。
它是弱序的。 流式写不遵守普通写之间的先后顺序：写完数据再写“就绪”标志，别的核可能先看到标志、后看到数据。发布之前要先 _mm_sfence()。
memset / memcpy 已经会用。 glibc 在块大到和共享缓存（L3）同一个量级时，自己就切换成流式写。手写的价值在于明确控制阈值，或者在 glibc 不会用的场景里用。

5.2 写 PCIe / MMIO：用 8 字节整块写，别用通用 `memcpy`

网卡、FPGA 的寄存器和描述符区被映射进进程地址空间（MMIO），常设成 WC（写合并）类型。对它的每一次写，最终都变成 PCIe 总线上的写事务。通用 memcpy 为了处理各种长度和对齐，可能拆成 1 字节、2 字节的碎写，每一笔都可能变成一个单独的事务。用对齐的 8 字节整块写，相邻的写更容易在 WC 缓冲里合并成更少的事务：

inline void copy_u64_blocks(volatile void* dst, const void* src, size_t nbytes) {
    // nbytes 须为 8 的倍数；dst/src 建议 8 字节对齐
    auto* d = static_cast<volatile uint64_t*>(dst);
    const auto* s = static_cast<const uint64_t*>(src);
    const size_t n = nbytes / sizeof(uint64_t);
    for (size_t i = 0; i < n; ++i) {
        d[i] = s[i];
    }
}

目标用 volatile 指针，是为了不让编译器把这些写合并、重排或删掉；写完要求设备一定看到时，再补一条 sfence。这一条只针对设备内存，普通内存上的 memcpy 已经高度优化，不要替换。

应用

第 1 节的 __restrict 和别名，在实际优化里对应“B4 漏 restrict”这张卡片：在汇编里看到什么、怎么改、怎么验证。

B4 漏 restrict
适用：只适用于 C。
信号：循环前有一段指针相减、比较、跳转的重叠检查；同一个循环编出向量和标量两个版本；或者一个没有依赖、没有分支的简单循环完全没向量化。
原因：编译器不敢假设输出指针和输入不重叠，只能加运行时检查（10–20 条指令，外加两份循环），或者干脆放弃向量化。
修法：只读输入写成 const float * restrict，输出写成 float * restrict。C++ 没有标准的 restrict，只有 GCC/Clang 的 __restrict__。
坑：restrict 是对编译器的承诺。调用方真传了重叠指针就是未定义行为，不只是变慢。故意原地处理的参数不能加。
验证：gcc -O2 -S 前后对比，检查段消失。加了以后测试挂了，说明调用方在传重叠指针，要去掉 restrict、改调用方。
原理：#10 第 1 节 __restrict：两个指针为什么可能指向同一块内存，见 1.1；编译器在运行时自己检查一遍，见 1.2。

1. __restrict：向编译器保证两个指针不重叠