1 Cache 深入要回答的问题
同样在 8 核处理器上处理 256 MiB 数据，为什么有的程序增加线程后接近按比例提速，有的却在 4 个线程时开始变慢？同样是读取内存，为什么顺序扫描数组与沿着指针跳转，耗时能相差很大？这些现象不能只用处理器主频解释。CPU 执行指令时，需要不断取得指令和数据；数据是否已经靠近执行核心，以及几个核心是否反复争用相同的数据块，都会改变等待时间。
Cache 是保存近期或邻近数据副本的高速存储。它通常比主内存小，也更靠近核心。可以用一个教学配置建立直觉：每核 32 KiB 的 L1 数据 Cache、每核 512 KiB 的 L2，以及多个核心共享的 16 MiB 末级 Cache。它们不是所有芯片的统一规格；真实设备可能采用不同容量、共享方式和行大小。读主板说明书时看到的 32 GiB DDR 内存，也不能当作 Cache 容量。内存条连接到内存通道，Cache 通常集成在处理器内部，软件访问时面对的却都是内存地址。
Cache 并不是按程序声明的变量逐个搬运数据，而是按固定大小的缓存行搬运。先假设行大小为 64 B：读取数组中的 8 B 整数，可能把同一行中的相邻整数也带入。随后访问这些整数，就可能不必再次走到更远的层级。这里既利用了时间局部性，也利用了空间局部性：近期访问的数据可能再被访问，邻近地址也可能很快被访问。是否真的受益，要看实际访问顺序，不能只看源代码中变量彼此是否相邻。
本课回答 4 个问题：地址怎样竞争有限的位置，缺失怎样转化为等待，多个核心为什么可能互相拖慢，以及怎样把这些观察写进数据结构选择。先把地址视为正常可访问的内存地址，不展开地址翻译与复杂的物理索引细节。也暂不研究预测式替换、内部队列和协议状态机；理解入门模型的边界，比记住某款芯片的内部参数更有迁移价值。
图中的 SSD 和网卡有助于辨清边界。服务器上的 NVMe SSD 可能通过 PCIe 连接，网卡也可能通过 PCIe 与主机交换数据；读盘或收包之后，CPU 仍然需要访问内存中的缓冲区。提高 SSD 带宽，并不自动消除处理缓冲区时的 Cache 缺失。板载低功耗处理器、台式机和双路机架服务器都存在这类问题，只是缓存规模、内存通道和跨插槽访问代价不同。后面的手算先限定在单个插槽内，让因果关系保持清楚。
2 组相联、替换与写策略
假设一个教学 Cache 的数据容量为 32 KiB，行大小为 64 B，关联度为 8 路。它有 512 条缓存行，每 8 条组成 1 个组，因此共有 64 个组。地址先确定对应哪条内存块，再由索引规则确定允许进入哪个组，最后在该组中比较标签，判断需要的数据是否已在其中。行内偏移确定这一行里的具体字节。标签负责区分映射到相同组的不同内存块，不能只凭组号判断命中。
“8 路”意味着一个内存块可以放入目标组中的 8 个位置之一，不意味着可以任意放入全部 512 个位置。直接映射可以看成每组只有 1 路；全相联则允许放入所有行中的任意位置。组相联在位置自由度与查找成本之间取折中。容量相同的 Cache，也可能因为关联度不同，面对相同访问序列时出现不同命中率。更多的路通常能缓解位置冲突，但硬件也要付出比较、选择和能耗成本。
在采用简单取模索引的教学模型里，32 KiB、64 B 行、8 路对应 64 个组。相隔 4096 B 的地址，其内存块编号相差 64，因此会落到相同组。若反复轮流访问 9 个这样的块，目标组只有 8 个位置，就可能不断替换。全体活跃数据只需要 576 B，仍然远小于 32 KiB，却不保证命中。这是理解冲突的关键。真实芯片可能使用更复杂的映射，不能把这个地址间隔当成所有机器的诊断公式。
组满之后，硬件要决定替换哪一行。最久未使用，也就是 LRU，是便于手算的策略：优先换出最长时间没有被访问的行。但实际 Cache 可能用近似 LRU 或其他策略。手算题必须明确替换规则，实验报告则应注明它只是解释模型。程序员通常不能直接为普通数组指定“替换这行”，可以调整的是工作集、遍历顺序和数据布局。
写操作还涉及写策略。写回策略先修改 Cache 中的行，并把它标成脏行；脏行被逐出时，需要向下一层提交更新。写直达策略则把写入继续传递到下一层，通常会配合缓冲机制。这里的“下一层”不必就是 DRAM，更不意味着立刻写入 SSD。Cache 的脏行与文件是否持久化是不同层次的问题，断电保存数据还涉及存储设备和软件的持久化流程。
写未命中时，还要决定是否把目标行分配进来。写分配会先取得该行，再在其中修改；不写分配则按相应路径把写入送向下一层。这是与写回、写直达相关但不同的选择维度。本课后续采用写回、写分配的教学假设。连续写入大缓冲区时，取得行与最终写回都可能消耗带宽，因此“代码里只有写，没有读”不等于硬件完全没有读取流量。
3 缺失类型与惩罚
Cache 缺失常用 3 类原因解释。首次缺失发生在数据第一次被带入时，也称强制缺失；容量缺失发生在需要保留的活跃数据超过缓存能力时；冲突缺失则来自有限的映射位置。这个分类帮助判断改善方向：首次访问往往无法凭替换策略消失，容量压力需要减少工作集或分块，冲突压力可能通过布局和访问间隔调整得到缓解。实际多核系统还存在与一致性有关的缺失，不能把所有额外等待都硬塞进这 3 类。
考虑扫描一个 64 MiB 的数组，每个元素为 8 B，行大小为 64 B。若起点对齐，每条行含 8 个元素；在理想的按需读取模型里，每行第一次访问缺失，其余 7 次访问命中。即使数组远大于 L1，顺序访问仍能获得空间局部性的收益。但再次从头扫描时，开头的数据可能早已离开 L1。讨论命中率时，必须说清是扫描过程中的相邻访问，还是整轮之间的数据复用。
缺失惩罚是一次缺失相对命中增加的时间。用单层模型写成：平均访问时间 = 命中时间 + 缺失率 × 缺失惩罚。假设命中时间为 1 ns，缺失后额外需要 50 ns，缺失率为 2%，平均为 2 ns；缺失率升到 10%，平均为 6 ns。这里的 50 ns 是额外时间，不是包含命中查找的总时间；若定义混用，就会重复计费。这些数值只是用于推导的教学参数，不能据此承诺某块主板的延迟。
多级 Cache 要区分局部缺失率与全局缺失率。假设 1000 次访问中，100 次未命中 L1，这 100 次里又有 20 次未命中 L2。L2 的局部缺失率为 20%，而穿过这 2 层的全局缺失率是 2%。报告中只写“L2 缺失率 20%”会造成误判，因为它可能只统计到达 L2 的请求。看性能计数器时，要核对分母是指令、加载请求、Cache 查找，还是某层收到的请求。
平均访问时间也不等于程序总耗时。硬件可能并行处理多个独立请求，预取也可能提前搬运数据；反过来，沿指针逐个访问时，后续地址依赖前次结果，等待更难隐藏。带宽描述单位时间能传多少数据，延迟描述一个请求多久返回，两者不能互换。服务器即使拥有较高的 DDR 总带宽，也可能在低并行度的随机访问中让核心长期等待。
还要区分缓存行流量和有用数据量。如果每次搬入 64 B，程序只使用其中 8 B 就跳到远处，有用字节比例只有 12.5%。这不是命中率的同义词，却能说明为什么链式结构或大步长访问消耗了大量带宽。优化目标应结合有用吞吐量，例如每秒处理多少个节点，而不能只追求漂亮的命中率数字。
4 动手：用简单计数估算命中率变化
先做一个能在纸上复核的小实验，不急于运行复杂基准。设 Cache 数据容量为 256 B，行大小为 64 B，采用 2 路组相联与 LRU 替换，初始为空。共有 4 条行、2 个组。我们只记录读访问，忽略预取、地址翻译和其他层级，用内存块编号表示地址除以 64 后的整数部分，组号为块编号对 2 取余。
第一段序列为 0、1、2、3、0、1、2、3。前 4 次分别把 4 个块装入，发生 4 次缺失；后 4 次访问仍在原位置，发生 4 次命中。总访问为 8 次，命中率是 50%，缺失率也是 50%。如果在不清空 Cache 的情况下继续重复后 4 个访问，命中会继续增加。把第一次填充的结果当成稳定运行状态，就会低估重复访问的收益。
第二段序列为 0、2、4、0、2、4，并把 Cache 重新置空。3 个块都映射到组 0，但该组只有 2 路。访问 0 和 2 后，访问 4 会换出 0；再访问 0 会换出 2，随后继续发生同样的轮换。在这个 LRU 模型中，6 次都是缺失。组 1 虽然空着，也无法接纳它们。总活跃数据只有 192 B，仍然发生连续缺失，所以仅看总容量不足以解释结果。
第3段保留相同的 256 B 容量与 64 B 行大小，把组织改为 4 路全相联。重新执行第二段序列，前 3 次缺失，后 3 次命中，命中率变为 50%。这是只改变关联度的受控对照。如果同时增大容量、改变行大小，再把变化全部归因于关联度，结论就不成立。纸上模型的价值正是能控制变量，并明确每次替换发生在哪个组。
记录时可以画出访问编号、块编号、组号、访问前的组内容、命中或缺失、被替换的块，共 6 列。每次访问后再更新 LRU 顺序，避免先替换再判断命中的错误。命中率为命中次数除以总次数；如果分母为 0，就不展示百分比。把 0、2、4 的顺序改成 0、0、2、2、4、4，再手算一次，可以看到访问顺序本身也会改变结果。
把模型带到真实机器时，先记下处理器型号、操作系统、Cache 公开规格、线程数和数据规模。让计算结果被实际使用，防止编译器删除整个循环；把内存初始化放在计时区间之外，预热与正式计时分开。分别测试连续访问和固定步长访问，并保持执行的有效操作数可比。使用可用的性能工具观察耗时和相关事件，但不要把真实事件名称或事件含义假定为跨平台统一。
如果实测与手算不同，先检查模型省略了什么：硬件预取是否生效，数据是否留在更低层 Cache，测量是否混入首次分配，以及地址是否符合假设的索引规则。差异本身不是模型失效的证明；它提醒我们，模型负责解释局部因果，真实计时负责检验目标机器上的整体效果。
5 假共享：同一缓存行上的独立变量
“伪共享”和“假共享”通常是 false sharing 的不同中文译法，本课把它们作为同一个概念，不强行分成 2 种故障。它描述的是：不同核心修改不同的逻辑变量，但这些变量位于同一条缓存行，硬件以行为单位协调访问，于是产生额外开销。程序没有共享同一个变量，并不代表底层没有共享缓存行。
假设 64 B 行内并排放着 8 个 8 B 计数器，线程 0 只增加计数器 0，线程 1 只增加计数器 1。逻辑上它们负责不同统计项，但如果运行在不同核心上，写入时仍可能争夺这条行的写权限。某个核心准备修改它时，其他核心中相应副本的可用状态需要改变。后续另一核心继续写，就可能再次触发协调。这里先理解“修改权限按行协调”，具体消息与状态留到 H24。
相反，如果多个线程都要更新同一个总计数器，那是真共享。把该变量周围填满空字节，也不能让同一个变量拥有互相独立的值。若算法允许，可改为每线程累计后再归并；若必须得到每次更新后的全局精确值，就需要承担相应同步和竞争成本。必须先确认业务语义，再决定是否能改变汇总时机。
假共享主要关注频繁写入或读写交错。多个核心只读同一条行，通常不需要像交替写入那样反复争夺写权限，因此不能把“同一行”直接等同于“性能一定差”。如果热写变量旁边还有其他核心经常读取的字段，读者也可能受影响。判断时应画出谁读、谁写、频率如何，以及它们实际落在哪条行上。
缓解办法包括让独立的热写字段分离到不同行、采用每线程数据区、在局部累积后批量归并。简单地在结构体末尾增加几个字节不保证成功：起始地址可能没有按行对齐，结构体数组的元素步长也可能让相邻元素继续挤在同一行。填充和对齐要共同考虑，还要核对语言、编译器与分配器对布局的保证。
这些办法也有成本。把每个 8 B 计数器都扩成 64 B，会增加数据占用，使更多缓存行参与扫描；每线程副本还需要归并，并改变读者获取新值的时机。对于写得很少、读得很多的对象，紧凑布局可能更好。Cache 优化不是“永远填充”，而是围绕访问模式选择合理的存储边界。
6 常见坑：只看容量忽视关联度与行大小
选处理器时只比较“末级 Cache 有多少 MiB”，容易遗漏影响性能的条件。容量回答能保留多少数据；关联度影响哪些块能同时留下；行大小决定一次搬运的粒度；层级和共享关系决定哪些核心在竞争资源。即使公开容量更大，应用也可能因为访问依赖、延迟、核心数或工作集变化而没有提速。单个规格不能替代对目标负载的测量。
行更大不总是更好。顺序读取紧凑数组时，较大的搬运粒度可能提高相邻数据利用；随机读取时，额外字节可能根本用不到，反而占据容量和带宽。对于多核热写数据，行还决定了独立变量是否被放在相同的协调单位内。比较行大小时必须固定数据量与访问模式，不能只凭“每次拿得更多”判断收益。
另一个常见误判是“工作集小于 Cache，所以应该全命中”。除了前面的组冲突，工作集还可能被低估：程序同时需要指令、索引、辅助数组和其他活跃数据，共享层还可能受到其他线程影响。结构体看起来只有几个字段，实际布局可能含有对齐空隙；指针指向的对象也应计入。计算时要覆盖真实访问的数据，而不只是容器本身的尺寸。
测量环境同样会制造假象。笔记本持续运行后可能改变频率，服务器上的其他任务可能争用共享 Cache，虚拟机还可能受到宿主机调度影响。单次短测的差异不能直接归因为缓存。应重复测量，报告数据分布与有效吞吐量，在条件允许时固定线程放置，并记录是否发生跨插槽访问。固定线程位置用于减少变量，不意味着所有生产负载都应机械地采用同样设置。
也不要把各种“缓存”混为一谈。操作系统的文件页缓存位于主内存，用于复用文件内容；CPU Cache 存放接近核心的内存数据副本；SSD 控制器内部也可能有缓存。文件读取第二次变快，不能单凭现象断定是 L1 命中。排查要先定位路径：时间花在设备等待、内存搬运、CPU 计算，还是线程同步，然后再选择对应指标。
最后，命中率提高也可能伴随总耗时上升。例如为了复用数据增加了大量判断和复制，或者填充布局导致内存占用显著膨胀。应该同时记录完成相同任务所需的时间、有效工作量和资源开销。若 Cache 指标改善而吞吐量下降，结果仍然需要解释，不能把计数器当成最终目标。
7 案例：一行共享变量拖垮多核
考虑一台单插槽 8 核服务器，装有 32 GiB DDR 内存和 1 块 PCIe 网卡。程序先把接收的数据放进内存缓冲区，再由 8 个工作线程解析。为了观察线程负载，开发者准备了一个包含 8 个计数器的数组，每个计数器为 8 B，每个线程每处理 1 条记录就增加自己的计数器。教学案例假设该数组恰好对齐并位于 1 条 64 B 缓存行内。
现象是：数据处理本身已经能并行，线程增加后 CPU 使用率很高，但吞吐量没有继续上升。这个现象不能独自证明假共享，因为锁竞争、内存带宽和网卡队列分配也可能产生类似结果。首先保留固定的内存输入，让相同数量的记录绕开实时收包重复执行，确认瓶颈是否仍存在。这样把设备供给波动与解析阶段的竞争分开。
接着审查热路径，发现每次解析都更新计数器。尽管源代码里每个线程使用不同下标，布局图却显示它们在同一行。若语言要求线程间同步读取这些计数器，应使用符合其内存模型的同步方式；不能为了提速把必要的原子操作随意删除，也不能把数据竞争导致的异常速度当作优化成果。原子更新保证相应操作的语义，但不能自动消除缓存行竞争。
设计 3 个可比较版本：原始紧凑计数器、按目标平台行边界分离的计数器、线程局部累计后每处理 1024 条记录发布一次的计数器。各版本必须处理相同输入、产生相同最终计数，并明确中间统计的及时性是否改变。第 3 个版本减少发布频率，适用于监控允许稍晚更新的场景；如果外部逻辑依赖每条记录后的精确可见值，它就不是语义等价的替换。
观察时记录线程数从 1 增到 2、4、8 后的吞吐量与耗时。如果紧凑版在多核时恶化，而分离版明显改善，且可用的行竞争相关证据也减少，就支持假共享的解释。还可以保留每次更新次数不变，仅改变布局，增强因果判断。这里不预设某个提速倍数，因为核心拓扑、编译结果和更新比例都会改变收益。
最终方案可能选择局部累计并定期归并，也可能只把几个高频写字段分开。若吞吐量依然受限，还要继续检查缓冲区访问是否随机、解析是否存在串行步骤，以及是否已经接近内存带宽。完成一次 Cache 修复，只说明排除了一个限制因素，并不意味着整台服务器的性能问题都已解决。
8 把 Cache 效应写进数据结构选型
数据结构选型应从“热操作会碰哪些字节”出发。假设每条记录占 64 B，其中只有 8 B 的状态字段用于频繁筛选，其余字段很少读取。按记录连续存放时，扫描状态也会把冷字段带入；把状态单独放成紧凑数组，可能提高每条行中的有用数据比例。反过来，如果每次都要处理完整记录，拆分数组可能增加地址流和管理成本。按对象组织还是按字段组织，要由主要访问路径决定。
连续数组通常便于顺序读取和预取，但中间插入、删除或扩大容量可能需要移动数据。链式结构便于某些局部连接修改，却常需要读取指针后才能知道下个地址，还可能搬入大量不用的字段。可以先用索引替代部分指针、把热节点放进连续存储，或者采用分块组织；这些都是候选方案，不能仅凭结构名称宣布数组永远胜出。
矩阵和批处理适合用分块说明工作集控制。若一次计算需要同时访问几片数据，就让当前块和必要的辅助信息尽量留在目标层级中，处理完再换下个块。估算块大小时需要留出余量，因为目标 Cache 不只服务这一片数据，关联度也限制块能否共存。块越小也不是越好：循环管理、边界处理和重复加载都可能增加。
多线程布局则要同时考虑读者和写者。只读数据适合共享，独立热写数据适合分区，低频汇总可以集中。给线程分配连续数据区，往往比让相邻元素由不同线程交错更新更容易控制假共享。但分区边界若落在同一条行内，边缘仍可能发生竞争；对齐边界和处理尾部都需要纳入实现。负载不均衡时，还要在减少竞争与均衡任务之间取舍。
工程记录至少写明对象数量、每个对象实际大小、热字段、读写比例、访问顺序、线程归属和更新频率。例如“8 个线程，每线程顺序处理连续区间，局部统计每 1024 条归并”，就比“采用 Cache 友好结构”更容易评审。还应记录增加了多少内存、是否引入复制，以及统计可见性发生了什么变化，让性能收益和功能约束放在同一份决策里。
上线前用代表性数据验证，小数据与大数据都要覆盖。小数据可能全部驻留 Cache，大数据可能暴露带宽压力；均匀输入可能掩盖真实业务里的热点。选型结论应写成条件句：在当前访问模式与机器规格下，这种布局改善了哪些指标。未来核心数、行大小或数据分布改变时，这些条件就是重新评估的入口。
9 从单核 Cache 走向一致性（H24）
单核模型里，我们主要关心数据能否留住、放在哪里、缺失要付出多少代价。进入多核之后，还要问：同一个内存位置在多个 Cache 中存在副本时，某个核心修改之后，其他核心怎样取得合适的数据？写回策略允许脏数据暂时留在 Cache，因此不能把“主内存里现在是什么”当作解释所有核心读值的唯一线索。
缓存一致性关注多个副本围绕同一内存位置如何协调，内存一致性模型则约束不同访问在程序与观察者眼中的顺序。两者相关，但不能互相替代。某平台能维护缓存一致性，并不意味着没有同步的多线程程序就可以随意共享变量。语言中的原子操作、锁等仍然承担相应的正确性责任；本课的布局优化只能在正确程序的基础上讨论。
回看假共享，线程修改的是不同变量，功能结果可能完全正确，性能却因为行粒度协调而下降。回看真共享，所有线程都更新同一个计数器，即使把它放在独占的行里，也仍需协调。这 2 个例子给 H24 提出不同问题：硬件怎样传递修改权限，以及软件怎样减少必须发生的共享。学习协议之前，先把共享的对象、粒度和频率说清楚。
到这里应能完成一个闭环：从访问序列计算命中与替换，用缺失率和惩罚估计等待方向，再以布局、线程数和计数证据验证解释。下一课再展开核心间副本如何协调。本课不要求背诵协议状态，而要求你在看到多核变慢时，能区分容量不足、映射冲突、访问低效与共享争用这些不同线索。
放进方案里
在硬件与数据结构方案中，为 Cache 单独保留一段可检验的说明。先列出目标设备形态，例如单插槽 8 核服务器、32 GiB DDR 内存、PCIe 网卡，并注明目标处理器公开的 Cache 容量、共享范围和行大小；未知参数明确写未知。内存容量与设备带宽分别记录，避免用它们代替核心访问数据的代价。若未来迁移到双插槽机器，再补充线程与内存位置的约束。
接着描述热路径：每条记录多大，实际读取哪些字段，访问是连续、固定步长还是指针跳转，哪些数据会再次使用。估算同时活跃的工作集，并说明该估算包含哪些辅助数组。对多线程写入，列出线程负责的字节范围与发布频率，检查相邻热写字段是否可能落在同一缓存行；同时区分真共享与假共享，避免把必要同步误判为单纯布局问题。
方案应给出原始布局与候选布局的对照，只改变足以验证假设的因素。例如先保持更新次数不变，将计数器按行分离；若统计允许延后，再评估局部累计与批量归并。写明新增内存、归并成本和可见性变化。填充不是默认要求，关联度与地址映射也不能凭猜测写成确定事实。
最后定义验收方式：使用相同输入和有效操作数，分别测量 1、2、4、8 个线程，记录吞吐量、耗时分布和可获得的 Cache 相关证据。预热、初始化与正式计时分开，记录编译配置和运行环境。对按行分离的方案，附上热字段地址、对齐方式与元素步长，核实不同线程的写入确实落在不同行；缺少行竞争事件时，用仅改变布局的对照支持判断，并注明证据边界。只有在结果正确、业务延迟达标且目标负载收益稳定时，才采用改动；保留原始数据与适用条件，便于硬件或负载变化后重新判断。
10 小结：下一步缓存一致性（H24）
Cache 效果取决于容量、关联度、行大小、访问顺序和线程行为。相同的数据量可能因组冲突不断缺失，不同变量也可能因共享缓存行而争用。先用明确的模型推导，再用受控对照观察目标机器，最后把收益、成本和语义条件写入方案。
自测时可以口头回答：为什么 192 B 数据可能在 256 B Cache 中不断缺失？为什么按行分离无法解决同一个全局计数器的真共享？为什么命中率提高不一定让程序更快？能说明这些原因，就可以进入 H24，继续学习多个核心如何协调各自保存的数据副本。