CHAPTER 29 / 架构、性能与并行
CPU cache、缓存一致性与 SIMD
同样读八个整数，为什么地址布局会改变需要接触的缓存行数？
这一章要弄清楚
- 计算访问地址对应的缓存行
- 区分一致性、局部性与伪共享
- 用向量宽度和尾部处理理解 SIMD
先备知识：拥有一组数据：array、vector与string / 虚拟内存、页表与 mmap
C++20 / macOS 与 Linux；本章的硬件模型只推演逻辑，不代表设备性能。
搬来的是一行，不是一个整数
程序读一个四字节整数时，CPU 通常按缓存行（cache line）在层级间搬运一段连续数据。缓存行大小由具体硬件决定；本章模型选择 64 字节，只为方便手算。若数组起点对齐到缓存行边界，连续读取八个四字节整数只涉及一行；若每次跨过十六个整数，八次读取就涉及八行。运算次数相同，但潜在的数据搬运量不同。
第一例只计算地址属于哪些行，没有模拟真实 cache。真实命中率还依赖容量、相联度、替换策略、预取器、其他线程、写策略及先前访问历史。八行地址不等于八次 DRAM 请求：数据可能已经在 L1、L2 或更远的缓存中。报告结果时用“涉及行数”而不是假造“本机 miss 次数”。
时间局部性与空间局部性
空间局部性表示访问了一个地址以后，很快会使用附近字节。时间局部性表示同一数据不久后又会使用。顺序遍历帮助利用一行中的多个元素；分块（blocking）则把会反复使用的工作集限制在较小范围。数组的 AoS 和 SoA 布局也会影响有效字节比例：若只扫描每个对象的一个字段，紧邻存放该字段的 SoA 往往便于连续加载，但完整对象处理、接口和缓存污染也要一起衡量。
缓存一致性（coherence）负责让多个核心对同一内存位置的缓存副本保持协议允许的一致关系。它与 C++ 的 data race 安全不是一回事：硬件有一致性协议，不会让未经同步的普通并发写变成合法 C++。语言层必须先用锁或原子建立正确协议，再讨论硬件如何执行。
伪共享为何没有“共享变量”
假设线程甲频繁写计数器 x，线程乙写计数器 y。两个变量互不依赖，却恰好位于同一缓存行。各自写入可能触发该行所有权反复转移，拖慢彼此，这叫伪共享（false sharing）。修复可以是局部累积、分离布局、适度 padding，而不是给两个无关变量再加一把全局锁。对齐提示需要与实际目标匹配；随意填充会浪费内存，也可能破坏更有利的局部性。
SIMD 不是多开几个线程
SIMD 指一条向量指令处理多个数据通道。用宽度四计算五个元素的点积，前四个可视为一个批次，第五个是尾部。第二例用普通 C++ 循环表现这种分组和尾部，不发出特定 ISA 指令，也不保证编译器实际向量化。向量化能否发生，取决于别名、依赖、数据类型、分支、对齐和编译选项。检查优化报告或汇编，再讨论真实向量指令。
尾部处理是正确性问题，不只是优化细节。不能为了凑满四个通道而越界读后面的内存；可以用标量尾循环、掩码加载，或确保额外存储及对应合同。浮点归约向量化还可能改变运算顺序，需要在数值合同允许范围内衡量。
把布局假设写进实验
比较连续和跨步访问时，固定元素数与类型，记录对齐、步长、总工作集和访问方式。分别测小于缓存与远大于缓存的规模，先用正确性检查保证没有索引错误。数据访问与整数计算只是整个处理器性能的一部分，别把一个行数模型直接扩展成所有 CPU 的加速结论。面试中先从字节地址推理，再提出能够检验推理的计数器和实验。
动手改变 · 观察因果
从字节地址找到缓存行
下一次 4B 访问会碰到新的一行吗？
每行假设 64B，每次访问 4B。结果是地址涉及行数，不是 cache miss、DRAM 请求或实测时间。偏移非 4 的倍数也按字节覆盖计算。 对应 例题 25-a；图中的代码行是步骤提示，完整可编译源码见例题。
改输入后从第一步重新推演。Tab 选择控件，Enter／空格操作按钮；图内方向键平移，手机可横向滑动。
先预测，再前进一步
下一次 4B 访问会碰到新的一行吗？
输入、边界、状态变化完整文字推演与当前数据
静态推演与完整文字（便于对照、打印）
64B 行中的地址分布
地址 0、4、8、12 都在第 0 行。
地址 16、20、24、28 仍在同一行。
地址每次增加 64，八个元素涉及八行。
阅读完整推演文字
- 连续前四项
地址：0 4 8 12；行号：0 0 0 0；去重行数：1
地址 0、4、8、12 都在第 0 行。
- 连续后四项
地址：16 20 24 28；行号：0 0 0 0；累计行数：1
地址 16、20、24、28 仍在同一行。
- 改成跨步十六
地址：0 64 … 448；行号：0 1 … 7；累计行数：8
地址每次增加 64，八个元素涉及八行。
跟着例子，走完一遍
连续与跨步访问涉及多少行
模型行大小 64B、元素 4B、首地址 0，读取 8 个元素；步长分别为 1 和 16。
- 第 i 次地址为 i×stride×4。
- 用地址除以 64 得到行号。
- 集合去重计数，并检查零元素输入。
#include <cstddef>
#include <iostream>
#include <set>
#include <stdexcept>
std::size_t lines(std::size_t count,std::size_t stride) {
std::set<std::size_t> touched;
for(std::size_t i=0;i<count;++i) touched.insert((i*stride*4)/64);
return touched.size();
}
int main() {
if(lines(0,1)!=0 || lines(8,1)!=1 || lines(8,16)!=8 || lines(17,1)!=2)
throw std::runtime_error("line model");
std::cout<<"contiguous_lines="<<lines(8,1)<<" strided_lines="<<lines(8,16)<<'\n';
}contiguous_lines=1 strided_lines=8
这是地址覆盖模型；没有测量本机 cache miss。
在本机运行这个例子
下载后，在文件所在目录执行。需要支持 C++20 的编译器；POSIX 示例还需要章节说明中的系统条件。
clang++ -std=c++20 -Wall -Wextra -Wpedantic -Werror -pthread 25-a.cpp -o example && ./example预期标准输出：
contiguous_lines=1 strided_lines=8
宽度四的逻辑分组与尾部
a=[1,2,3,4,5]，b=[2,3,4,5,6]；点积结果应为 70。
- 完整批次覆盖下标 0..3。
- 尾循环覆盖下标 4。
- 检查长度不一致、空数组和 0..9 个元素。
#include <cstddef>
#include <iostream>
#include <numeric>
#include <stdexcept>
#include <vector>
long long dot(const std::vector<int>& a,const std::vector<int>& b) {
if(a.size()!=b.size()) throw std::invalid_argument("shape");
long long sum=0; std::size_t i=0;
for(;a.size()-i>=4;i+=4)
for(std::size_t lane=0;lane<4;++lane) sum+=static_cast<long long>(a[i+lane])*b[i+lane];
for(;i<a.size();++i) sum+=static_cast<long long>(a[i])*b[i];
return sum;
}
int main() {
for(std::size_t n=0;n<=9;++n) {
std::vector<int> a(n,2),b(n,3);
if(dot(a,b)!=static_cast<long long>(n)*6) throw std::runtime_error("tail");
}
bool rejected=false;
try {
const auto unexpected=dot({1},{});
std::cout<<"unexpected mismatched dot="<<unexpected<<'\n';
return 1;
} catch(const std::invalid_argument&){rejected=true;}
if(!rejected || dot({1,2,3,4,5},{2,3,4,5,6})!=70) throw std::runtime_error("dot");
std::cout<<"dot=70 tail=1\n";
}dot=70 tail=1
分组逻辑用普通 C++ 表达，不能据此声称已使用硬件 SIMD。
在本机运行这个例子
下载后，在文件所在目录执行。需要支持 C++20 的编译器；POSIX 示例还需要章节说明中的系统条件。
clang++ -std=c++20 -Wall -Wextra -Wpedantic -Werror -pthread 25-b.cpp -o example && ./example预期标准输出：
dot=70 tail=1
把缓存一致性当作线程安全
认为多核能看到同一 RAM，因此两个线程普通写同一个变量不会有问题。
修正思路：先满足 C++ 同步规则，再用硬件一致性和局部性解释性能；两层合同不能互相替代。
轮到你动手
先写预测或代码，再按需打开提示。完整答案用于对照自己的推理。
练习 1
数组起点改为字节地址 60，连续读取两个四字节整数，会涉及几行？
给我一点提示
- 地址分别是 60 和 64。
- 按行号去重。
查看答案与推理
两个元素分别落在行 0 和行 1，共两行。起点对齐改变了边界，不能只用元素总字节数除以行大小向上取整来推断任意地址范围。
练习 2
两个独立原子计数器可能伪共享。提出两个修复方案及各自代价。
给我一点提示
- 尽量少写共享位置。
- padding 不是零成本。
查看答案与推理
方案一每线程局部计数，定期合并，代价是统计不再每次实时更新；方案二把计数器分离到适当缓存行，代价是内存增加且应按目标平台验证。先测原始布局，再测修改后的吞吐。
把理解说出来
先用中文讲清因果，再用英文回答。问题依据技能主题编写，并非公司内部题库。
空间与时间局部性有什么区别？
参考回答 / English answer
空间局部性复用附近字节，时间局部性复用之前的数据。连续遍历与适当分块分别帮助它们。
Spatial locality uses nearby addresses. Temporal locality reuses data that was accessed recently.本章涉及八行，是否证明八次 DRAM miss？
参考回答 / English answer
不是，行可能已在缓存中；模型只统计地址覆盖，没有容量、替换或层级状态。
No. The model counts distinct line addresses, not memory misses or DRAM transactions.伪共享为什么叫伪？
参考回答 / English answer
线程不共享同一个逻辑变量，却共享硬件一致性粒度的一行，写入互相影响。
The threads modify different logical objects. They still contend because coherence operates at cache-line granularity.SIMD 宽度四而 n=5，直接执行两组完整加载安全吗？
参考回答 / English answer
若没有额外有效存储与明确合同，会越界。需标量尾部或正确掩码访问。
The second full-width load can access beyond the valid range. I use a tail loop or a properly masked operation.普通循环长得像 SIMD，如何确认实际向量化？
参考回答 / English answer
检查目标编译配置、向量化报告和汇编，再测完整程序。源码分组不能证明发出了向量指令。
I inspect compiler vectorization diagnostics and generated instructions. Source-level grouping alone is not evidence of SIMD execution.为什么 SoA 有时优于 AoS？
参考回答 / English answer
只使用少数字段时，SoA 让有效数据连续，减少无用搬运并利于向量化；完整对象访问可能偏向 AoS。
SoA can pack the fields a loop actually uses into contiguous memory. The best layout depends on the access pattern, not a universal rule.继续查证
- CS149：Parallel Computing ↗
课程中的 memory hierarchy、cache coherence 与 SIMD 讲次
- AMD HIP：Performance guidelines ↗
Memory throughput；作为后续 GPU 局部性对照
公开资料用于查证；本章图解和例题是独立教学内容。CPU 逻辑模型不能证明设备性能。