访存、计费粒度与并行度：性能优化通用方法论
本文刻意写成与项目无关的形式，供后续开发与其他语言参考。
怎么用这份文档
- 接手新模块 / 发现热点 → 走 §3 的五个审计与决策树
- 写代码评审意见 → 对照 §5 反模式清单
- 怀疑”是不是内存问题” → 先看附录 B 的判定方法，别凭直觉
- 想找同类案例 → 附录 A 的八条，每条都标注了它违反哪条判据
0. 结论先行
性能问题的根源极少是”访问顺序”，而是 ①每元素摊销的访存次数、②访存之间的依赖关系、③每个付费单位的工作量。 顺序访问之所以常常有效，是因为它同时改善这三者；但如果热表能装进 L1、且访存彼此独立，随机查表同样快，甚至更快。
一句话操作原则：让访存可预测、批量、且彼此独立。做不到时，改算法，而不是改循环。
1. 三条判据（+ 一条补充）
判据 1：访存地址是否提前可知（可预测性）
| 不可预测 | 可预测 | |
|---|---|---|
| 形态 | 链表 / 树 / 哈希链 / next 指针 | 数组下标、由寄存器算出的偏移 |
| 硬件预取器 | 无所适从 | 顺序流可预取；表在 L1 则无需预取 |
| 后果 | 只能等 | 可以提前发射 |
判据 2：访存之间是否互相独立（并行度 / MLP）
延迟本身不是问题，串行延迟才是。
串行链（延迟受限）： load(a) → 由 a 算出 b → load(b) → 由 b 算出 c → load(c) … 总耗时 = 链长 × 单次访存延迟
独立访存（吞吐受限）： load(t[i1])、load(t[i2])、load(t[i3]) … // 下标之间无依赖 总耗时 ≈ 访存数 × 吞吐 / 并行度乱序执行能重叠独立访存，但对依赖链无能为力。这条解释了两类典型问题：
- 数据结构引入的串行：
unordered_map的”桶数组 → 节点”是两级依赖访存；树/链表逐节点跳同理。 - 算法本身串行：流密码的 CFB 模式每块密文依赖上一块，天然串行；CTR 模式的密钥流块彼此独立，可以整批交给硬件。这是换算法暴露并行度，不是换访存方式。
判据 3：每个”付费单位”做了多少有效工作（计费粒度）
看热循环的趟数按什么单位计费，以及能否提高一档：
比特 → 符号 → CPU 字 → 缓存行 → 批次 → 系统调用 / 跨模块调用| 反例 | 趟数 | 正例 | 趟数 |
|---|---|---|---|
| 每比特一次移位合并 | 8 趟/符号 | 每符号一次 64 位合并 | 1 趟/符号 |
| 每字节一次函数调用 | 16 次/轮 | 一条 SIMD 指令处理 16 字节 | 1 次/轮 |
| 每 16 字节一次系统/库调用 | 52 万次/8MB | 每 256KB 一次 | 32 次/8MB |
提高计费档位几乎总是免费收益，而且跨语言普适：Python 里”把循环推给 numpy”、SQL 里”别写 N+1 查询”、JS 里”别在回调里做重活”，都是同一条。
补充判据 4：热数据总量 vs 缓存层级
| 工作集 | 归属 | 策略 |
|---|---|---|
| ≤ ~32 KB | L1 | 平坦表直接随机查 |
| ≤ ~1 MB | L2 | 平坦表仍可，注意冲突 |
| 数 MB | L3 | 分块（tiling）提升时间局部性，或改顺序流 |
| ≫ L3 | 内存 / 磁盘 | 顺序流 + 预取是唯一出路 |
判据 4 是下一节”什么时候该用顺序访问”的答案所在。
2. 什么时候该用顺序（流式）访问
满足以下全部条件时，顺序访问是默认选择
- 数据总量 ≫ 缓存（必须反复从内存/磁盘搬）
- 每个元素恰好处理一次（一趟扫描出结果）
- 元素之间不需要串行依赖
典型场景：压缩/解压、哈希、解析、扫描、过滤、聚合、拷贝、编解码、ETL。
以下情况，平坦随机访问优于顺序访问
| 情况 | 原因 |
|---|---|
| 热表能常驻 L1/L2 | 索引一次就够；顺序扫一遍反而增加总访存量 |
| 访问位置由已就绪的寄存器值决定 | 访存独立，可重叠 |
| ”少量元素被反复访问” | 时间局部性 > 空间局部性（如高频符号的短码） |
所以不要把结论记成”要用顺序访问”。准确的表述是：让访存可预测、批量、且彼此独立；做不到时改算法。
3. 通用方法论：五个审计 + 一棵决策树
这套审计语言无关 —— 它问的是”数据放在哪、怎么走”，而不是”用什么语法”。
审计 A — 计费单位
这个热循环按什么单位付费？能否提高一档？
自查：内层循环趟数 = O(什么)？有没有”每元素一次函数调用 / 虚调用 / 边界检查 / 加锁 / 分配 / 系统调用”？
审计 B — 依赖距离
下一次访存的地址，是否要等上一次访存的结果？
- 要等 → 拉长依赖距离（循环展开、多流交错、预计算地址），或换算法暴露并行度
- 不用等 → 提高并行度（展开、SIMD、多累加器）
附带的反模式：多个逻辑流写到同一个地址会造成伪串行。例如频率统计若对所有输入只自增一个计数器，就退化成 load-modify-store 的串行链；多累加器分桶再合并可以打破它。
审计 C — 工作集
热数据总量多少？L1 / L2 / L3 装得下吗？
装得下 → 平坦表直接查；装不下 → 分块（tiling）或顺序流。
审计 D — 间接层数
一次逻辑操作要解几次指针？
unordered_map / map / 链表 / 树 / vector<vector<T>> / vector<unique_ptr<T>> / 引用数组 —— 每一个至少多一跳。目标：一次逻辑操作一跳到位。
审计 E — 批处理
有没有”每元素一次昂贵操作”可以升格为”每批一次”？
系统调用、加锁、分配、跨模块调用、IPC、网络往返、数据库查询，全部适用。
决策树
热循环里依次问：① 我按什么单位付费？ —— 能升档吗？（比特 → 符号 → 批）② 下次访存地址依赖上次结果吗？ 依赖 → 拉长依赖距离 / 换算法暴露并行 不依赖 → 提高并行度（unroll / SIMD / 多流）③ 热数据 vs L1/L2？ 装得下 → 平坦表随机查（别强行顺序） 装不下 → 分块 or 顺序流 + 预取④ 一次逻辑操作解几次指针？≥2 → 改平坦数组 / SoA⑤ 有没有每元素一次调用/锁/分配？能批处理吗？4. 跨语言映射：哪些构造会偷偷引入间接层
原理相同，差别只在”你能控制到什么程度”和”哪些语法糖在背后加跳”。
| 语言 | 顺序/平坦的好形态 | 会偷偷加跳的构造 |
|---|---|---|
| C/C++ | 平坦数组、SoA、std::array、连续 vector | unordered_map/map、链表、vector<unique_ptr<T>>、虚调用、shared_ptr 控制块 |
| Rust | Vec<T>、&[T]、切片迭代器（优化后即顺序流）、SoA | Box<dyn Trait>、Rc<RefCell<T>>、HashMap、Vec<Box<T>>；链式 iterator 若中途 collect 会额外分配 |
| C# / .NET | T[]（值类型）、Span<T>、Memory<T>、stackalloc | List<Class>（引用数组 = 指针追逐）、Dictionary<K,V>、LINQ 链的重复枚举、装箱 |
| Java | int[]/byte[]、原始类型数组、ByteBuffer | HashMap、ArrayList<Object>、Stream 装箱、引用跳转 |
| Go | []T（值语义连续）、[]byte 流式 | map、[]*T、interface{} 装箱、channel 逐元素传递 |
| JS / TS | TypedArray、ArrayBuffer、平坦数值数组 | 对象数组、Map、megamorphic 属性访问（引擎无法内联 → 等价于指针追逐） |
| Python | numpy / array / memoryview + 向量化 | 逐元素 for、dict、对象列表（每个元素都是一个 PyObject 指针） |
| SQL / ORM | 集合操作、批量 INSERT、JOIN | N+1 查询、逐行 round-trip |
Python 那一行值得单独注意：解释器开销远超访存，所以”提高计费档位”的单位从 CPU 字变成了整个数组 —— 但原理完全相同。方法论能跨语言，是因为它讨论的量（摊销到每个元素的访存次数与间接层数）在任何语言里都是同一个。
同理，“批处理”在各语言里的形态：C/C++ 的 SIMD 与块缓冲、C# 的 Span 批处理、Python 的向量化、SQL 的批量写、网络层的请求合并 —— 都是同一原理的不同外观。
5. 反模式清单（代码评审可直接对照）
| # | 反模式 | 违反 | 替代 |
|---|---|---|---|
| 1 | 热循环里用哈希容器按整数/枚举键查表 | D | 平坦数组直接索引 |
| 2 | 结构体里放 vector/string 作为”值”，热循环逐元素取 | D | 定宽整数（uint32/64）或 SoA |
| 3 | 内层循环按比特 / 字符推进 | A | 按符号 / 字 / 批量推进 |
| 4 | 每个元素一次函数调用（尤其跨编译单元、虚函数） | A、E | 内联 / LTO / 批量接口 |
| 5 | 每个元素一次系统调用、加锁、分配 | E | 攒批、池化、一次调用处理一批 |
| 6 | 逐元素链表 / 树 / next 指针遍历 | B | 扁平化 + 索引数组；或改算法 |
| 7 | 多个逻辑流争抢同一地址自增 | B | 多累加器分桶 |
| 8 | 用”看起来顺序”的 API 但底层每次随机（如逐行查询） | E、D | 批量接口 |
| 9 | 先改代码再测 | — | 先量瓶颈，改完重新量（瓶颈会转移） |
6. 边界：什么时候不该改
- 工作集本来就在 L1 里 → 强行顺序化可能增加总访存量。当每符号的固定开销大于原逐位走树的成本时，查表反而回退。
- 瓶颈会转移 → 加密内核提速一个数量级后，瓶颈会变成密钥流计数器生成与异或遍历，再优化密码本体已无意义。
- 抽象代价 → SoA / 平坦表会让 API 更难用、更易错。收益不显著时别做。
- 过早优化 → 必须先量，再改，改完再量。
7. 落地清单（贴在手边）
热循环自查（10 秒版）□ 内层循环按什么单位跑？能升一档吗？□ 下次访存地址依赖上次结果吗？—— 依赖 = 延迟受限，优先解决它□ 热数据多大？装得进 L1 就平坦表，装不进就分块 / 流式□ 一次逻辑操作解几次指针？≥2 就扁平化□ 有没有"每元素一次调用 / 锁 / 分配"？能批处理吗？□ 改完瓶颈跑哪去了？（重新测）附录 A：八个反模式与正解的对照
八个案例没有任何一个是”把随机访问改成顺序访问” —— 全部落在审计 A/B/D/E 上。这正说明为什么不能把结论简化成”用顺序访问”。
| # | 反模式 | 违反判据 | 正解 | 实测倍数 |
|---|---|---|---|---|
| 1 | 用 unordered_map<unsigned char, T> 按字节值查编码 | D，桶→节点 2 跳加堆分配第 3 跳 | 平坦 code[256] + len[256]，一跳 | 1.86× |
| 2 | 结构体值里放 std::vector<uint8_t> 存码字，逐符号堆指针追逐 | D | 定宽 uint64 码字 | 累计至 2.63× |
| 3 | 位合并逐位移位 | A，按比特计费 | 64 位位缓冲整码字合并 | 累计至 13.87× |
| 4 | 频率统计用 unordered_map[c].freq++ | D 加 B，同址自增伪串行 | 平坦 freq[c]++ | 均匀数据 657 → 4022 MB/s；偏斜数据因同址自增只到 866 MB/s，正是判据 B 的体现 |
| 5 | 解码逐位走树 | B 串行依赖链加 A | 换算法：canonical 码 + 12 位查表 | 2.07× |
| 6 | 解码时每字节把位展开成 8 元素容器 | A 加内存放大 8 倍 | 64 位位缓冲按字节冲刷 | 含在 #5 内 |
| 7 | 自研分组密码：逐字节函数调用加模运算，且无 SIMD 路径 | A 加 D 加无硬件路径 | 换算法与换实现：CTR 暴露并行，交由硬件批量 | 20.1× 与 20.6× |
| 8 | 热点函数定义在另一编译单元，无 LTO | E，每符号一次跨 TU 调用 | -flto 内联 | 编码 +44% |
端到端提升通常远小于内核级提升（编码 7.5×、加密 20×，端到端只有 2 倍上下）。因为完整流程里还有目录枚举、逐文件读写、队列同步这些不随内核加速的串行端点 —— 这是 Amdahl 定律。优化内核之后必须重新测端到端，否则会高估收益。
附录 B：先判定你是哪一类瓶颈
不做判定就套方法论，等于猜。三类瓶颈的解法完全不同：
| 类型 | 特征指标 | 解法 |
|---|---|---|
| 延迟受限 | IPC 低、stalled-cycles 高、cache-miss 高、依赖链长 | 判据 1/2：扁平化、拉长依赖距离、换算法 |
| 带宽受限 | 访存吞吐接近硬件上限、IPC 尚可 | 减少总访存量（提高计费档位、避免重复读）、分块 |
| 计算受限 | IPC 高、访存不饱和 | 判据 3：SIMD、更少指令、换算法 |
快速判定法：
- 数一数热循环每个元素访问了几次内存、几个缓存行 → 乘以元素数，与硬件带宽比较。差距大 → 带宽不是瓶颈。
- 检查是否单条依赖链 → 若是，无论带宽多大都受限。
- 做消融实验：只改一件事，测增量。这比读指标更直接，附录 A 的实测倍数就是这么来的。
工具：Linux perf stat / perf c2c、Intel VTune、AMD uProf、llvm-mca（静态估算）、编译器的 -Rpass-analysis / -fopt-info。Windows 上可用 ETW / WPA、Visual Studio 的 CPU 与内存分析器。
最可靠的判据仍是消融实验：把怀疑的那一项单独改掉，其他不动，前后对比。
部分信息可能已经过时
粤公网安备44011102484817号
