用时间量一量局部性
目标
亲自测量：即使读取相同数据、读取次数也完全一样，仅仅改变读取顺序，耗时就会相差数倍。完成步幅、行优先与列优先、分块三组实验后，局部性将不再是抽象概念，而会成为清晰可见的数字。
为什么重要
内存层级建立在程序具有局部性这一假设上。违背这个假设的代码无法获得硬件提供的任何帮助。缓存以 64 字节的缓存行为单位取数；预取器会提前读取按固定间隔前进的访问；TLB 则记住最近访问页面的地址转换。随着步幅增大，这三者会依次失效。
这里测量的不是 Python 的速度。Python 虽然慢，但其开销会同样附着在每个实验上；只要固定读取次数，剩下的差异就来自内存。这几乎就是本实验的全部设计。
绝对数值因机器而异。评分也不检查绝对值，只看哪一侧慢、慢了多少。
步骤
- 确认运行此 Pod 的 CPU 缓存行大小和缓存层级，保存到
/root/mem/01-cache.txt。 - 创建
/root/mem/stride.py。它接收步幅参数，并只输出一行表示单次读取纳秒数的数字。 - 测量步幅 1、16、65536，把三行结果保存到
/root/mem/03-stride.txt。 - 为
stride.py增加rand分支，分别测量顺序访问与随机访问，把两行结果保存到/root/mem/04-random.txt。 - 创建
/root/mem/matrix.py。它接收N与遍历方向参数，并输出每个元素的纳秒数。 - 将
N设为 2048，测量行优先与列优先，把两行结果保存到/root/mem/06-order.txt。 - 为
matrix.py增加block分支，测量列优先与分块访问，把两行结果保存到/root/mem/07-block.txt。 - 分别用一句话总结三个实验，保存到
/root/mem/08-notes.md。
参考
- 所有产物都放在
/root/mem/下。请先执行mkdir -p /root/mem。 - 使用
time.perf_counter()计时；time.time()的分辨率不足。 - 测量前先预读约 1,000 次进行预热。首次访问会混入创建数组和页面错误的开销。
- 常见错误 1：数组太小。如果整个数组能放进缓存，无论怎样改变步幅都不会产生明显差异。
- 常见错误 2：不同分支使用不同的索引公式。如果只在一侧去掉乘法，测量中就会混入运算成本，无法判断测的是内存还是算术。
- 数组约为 96MB。Pod 有 2Gi 内存，空间充足，但不要同时运行多个程序。
读取本机缓存层级
确认运行此 Pod 的 CPU 缓存行大小和缓存层级（L1/L2/L3），保存到 /root/mem/01-cache.txt。同时计算一行能容纳多少个 int32。
缓存行大小位于 /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size，读取同一目录中的 level、type、size 可以看到层级。int32 占 4 字节，因此用缓存行大小除以 4，即可得到每行容纳的元素数。这个数字是后续选择步幅的依据。
制作可改变步幅的测量工具
创建 /root/mem/stride.py。通过 python3 /root/mem/stride.py <보폭> 调用时，创建包含 24,000,001 个 int32 的数组（约 96MB），读取 500,000 次，并以一位小数、仅一行数字的形式输出每次读取的纳秒数。
关键是让读取次数不受步幅影响并保持固定，这样 Python 本身的慢速开销会在两侧同样抵消，只留下内存差异。
预先生成索引列表，计时区间内只遍历该列表。下一个索引通过 i = (i + 보폭) % 배열길이 移动。数组长度为奇数，因此即使步幅很大，也不会很快反复访问同一位置。
测量前先预读约 1,000 次进行预热。第一次运行会混入创建数组的成本。
以 1、16、65536 三种步幅测量
使用第 2 步的工具分别测量步幅 1、16、65536，并在 /root/mem/03-stride.txt 中按 보폭 나노초 格式保存三行。
可以像 for s in 1 16 65536; do echo "$s $(python3 /root/mem/stride.py $s)"; done 这样一次得到三行。
对于 int32，步幅 16 恰好跨过一个缓存行；步幅 65536 为 256KB，远远超出页面边界和预取器可跟随的范围。预取器无法跨越页面边界，因此这里的数值会显著升高。
保持大小不变，只改变访问顺序
修改 /root/mem/stride.py，使其在参数为 rand 时按随机顺序读取。随后分别测量顺序访问（步幅 1）和随机访问，在 /root/mem/04-random.txt 中保存 seq 나노초、rand 나노초 两行。
本步骤的要点是保持数组大小和读取次数不变，只改变读取顺序。由于容量相同，差异不能归因于容量，剩下的解释只有空间局部性。
请在计时前预先生成随机索引。使用 random.Random(1) 之类的固定种子，可确保每次运行得到相同顺序。
制作按两个方向遍历矩阵的工具
创建 /root/mem/matrix.py。通过 python3 /root/mem/matrix.py <N> <row|col|block> 调用时，把 int32 N×N 存入一个扁平数组（a[i * N + j]），按指定方向遍历全部元素，并以一位小数、仅一行数字的形式输出每个元素的纳秒数。
row 以 i 为外层、j 为内层；col 则相反。两个分支的索引表达式都必须完全相同，都用 a[i * N + j]。如果只在一侧省去乘法，Python 运算成本会混入差值，最终无法判断测量的究竟是什么。
block 将在第 7 步使用。现在只实现 row 和 col 也能通过本步骤。
测量行优先与列优先的差异
将 N 设为 2048，分别测量行优先与列优先，并在 /root/mem/06-order.txt 中保存 row 나노초、col 나노초 两行。
读取的元素和次数完全相同，只有顺序不同，但列优先仍会慢数倍。N 为 2048 时，列方向相邻元素相隔 8KB，超过一个页面（4KB）的距离。
如果差异不明显，可增大 N。矩阵能够放进缓存时，两个方向的速度会接近。
通过分块减少列优先的损失
为 matrix.py 增加 block 分支。保持列优先顺序，但每次只在 64×64 的小块内遍历。随后将 N 设为 2048，分别测量列优先和分块访问，并在 /root/mem/07-block.txt 中保存 col 나노초、block 나노초 两行。
外层两重循环移动小块的起始坐标，内层两重循环在块内按列优先遍历。一个 64 行 × 64 列的小块触及约 16KB 的缓存行，可以放进 L1。
读取相同元素、次数也相同，却能加速，是因为在丢弃已取回的缓存行之前充分利用了它。矩阵乘法使用分块的原因也是如此。
分别用一句话总结三个实验
在 /root/mem/08-notes.md 中至少写三行，分别说明增大步幅为何变慢、列优先遍历为何吃亏，以及分块恢复了什么。
三个实验从不同角度讲的是同一件事：内存以缓存行为单位移动，取回一行却没有使用就丢弃，会付出相应代价。
正文中必须包含 보폭、열 우선、타일。