遍历顺序与循环分块

两个嵌套循环访问矩阵里完全相同的单元，仅仅因为哪个循环在内层，缓存缺失数就可能相差 七倍。本讲比较按行读和按列读，再把转置切成小块，让一块数据在被使用期间一直留在缓存里，并在一个由 SPY 收盘价构成的矩阵上测量这两者。

n 行 n 列的矩阵按行优先顺序存放。沿着一行前进（改变 j）的循环读到的是相邻的值；沿着一列向下走（改变 i）的循环每一步都要跳过整整一行。下面两个循环访问的是同样的单元，一个把 j 放在内层，一个把 i 放在内层。我们打印一个 4×4 的 float64 矩阵的前六个地址。

def row_major_trace(n):    return [(i * n + j) * 8 for i in range(n) for j in range(n)]def col_major_trace(n):    return [(i * n + j) * 8 for j in range(n) for i in range(n)]1print("row:", row_major_trace(4)[:6])print("col:", col_major_trace(4)[:6])

row: [0, 8, 16, 24, 32, 40]
col: [0, 32, 64, 96, 8, 40]

1. 1i 在内层时，下一次读取要往后一整行（这里是 4 个值 = 32 字节）。

按行读时地址每次增加 8 字节，也就是第一个主题里的步长，一条缓存行能服务八次读取。按列读时这里每次跳 32 字节，在更大的矩阵里则每次跳一整行的长度。现在我们在一个 4 KB 的小缓存里，对 16×16 到 73×73 的矩阵数出两种顺序的缺失。

for n in (16, 32, 48, 73):    print(n, "x", n, "row:", count_misses(row_major_trace(n)), "col:", count_misses(col_major_trace(n)))

16 x 16 row: 32 col: 32
32 x 32 row: 128 col: 1024
48 x 48 row: 288 col: 2304
73 x 73 row: 667 col: 4573

16×16 的矩阵只有 2 KB，装得进缓存，加载之后两种顺序都是 32 次缺失，一样。从 32×32 起矩阵就装不下了，按列的顺序每次读都未命中：1,024 次对 128 次，差八倍，正好是一条缓存行里的八个值。到 73×73 时差距接近七倍。循环的形状没变，变的是数据的大小。

有时任何循环顺序都帮不上忙。转置 B[j][i] = A[i][j] 读 A 写 B，循环若沿着 A 的行走，就会沿着 B 的列往下走。不论哪个循环在内层，两个矩阵里总有一个要以大步长被遍历。解决办法是循环分块：把矩阵分成小的方块来处理，让一块碰到的那几条行在被替换之前被多次使用。

1. 1
   选择块大小 t小到让 A 的一块和 B 的一块能同时装进缓存。
2. 2
   遍历各个块两层外循环，步长为 t：ii 和 jj 给出一个块的角。
3. 3
   在块内部处理两层内循环只访问这个块的 t×t 个单元，与之前一样。
4. 4
   进入下一个块到这时程序才丢下旧块的那些行。

下面的代码只列出 4×4 矩阵在不分块和用大小为 2 的块时各单元被访问的顺序。分块后，程序先把左上角 2×2 的块做完，才去碰别的单元。

def visit_order(n, tile=None):    step = n if tile is None else tile    order = []    for ii in range(0, n, step):1        for jj in range(0, n, step):            for i in range(ii, min(ii + step, n)):                for j in range(jj, min(jj + step, n)):                    order.append((i, j))    return orderprint("plain:", visit_order(4)[:8])print("tile 2:", visit_order(4, 2)[:8])

plain: [(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3)]
tile 2: [(0, 0), (0, 1), (1, 0), (1, 1), (0, 2), (0, 3), (1, 2), (1, 3)]

1. 1两层外循环遍历各个块，两层内循环遍历一个块的内部。

现在做真正的转置。我们写出读 A 和写 B 的轨迹（B 紧接着 A 存放），并对 73×73 的矩阵数出不分块和块大小为 4、8、16、32 时的缺失。

def transpose_trace(n, tile=None):    base_b = n * n * 8    step = n if tile is None else tile    trace = []    for ii in range(0, n, step):        for jj in range(0, n, step):            for i in range(ii, min(ii + step, n)):                for j in range(jj, min(jj + step, n)):                    trace.append((i * n + j) * 8)                    trace.append(base_b + (j * n + i) * 8)    return tracefor tile in (None, 4, 8, 16, 32):    print("tile", tile, "misses:", count_misses(transpose_trace(73, tile)))

tile None misses: 5996
tile 4 misses: 2603
tile 8 misses: 2036
tile 16 misses: 1960
tile 32 misses: 1714

不分块时转置缺失 5,996 次。块大小为 4 时就降到 2,603，块大小在 8 到 32 之间时保持在 2,036 到 1,714，大约少了三倍。块太小会浪费它加载的缓存行的边缘部分，所以收益随块变大而增长，直到块装不下为止。

实验沿着本讲走：两种读取顺序、可带可不带分块的转置轨迹、按顺序和按块大小的缺失计数、最佳块大小的选择，以及对 SPY 矩阵的研究。

• 函数 · 问题依赖
• row_major_trace(n)按行读会碰到哪些地址？简单算术
• col_major_trace(n)按列读呢？简单算术
• transpose_trace(n, tile=None)转置（分块或不分块）会碰到哪些地址？四层嵌套循环
• compare_orders(n)按列的顺序差多少？row_major_tracecol_major_trace
• misses_by_tile(n, tiles)分块如何改变转置的缺失数？transpose_trace
• best_tile(n, tiles)哪个块大小最好？misses_by_tile
• study(bars)对 SPY 收盘价矩阵，分块能赢多少？compare_ordersbest_tile

下一个主题：分块靠重用缓存行来掩盖缺失的延迟，预取则靠在需要之前就先请求缓存行来掩盖。在预取里，你要给缓存加一个步长检测器，看它能预测哪些访问模式，又有哪些（比如在表里随机游走）它预测不了。