缓存无关算法：重排二维数组遍历以榨干 CPU 缓存行

通过 Go 测试框架验证行优先/列优先访问的性能差异，并实现递归分块遍历（cache oblivious），对比 SIMD 等效优化。 · 难度：入门 · +10XP

缓存无关算法：重排二维数组遍历以榨干 CPU 缓存行

大多数教程只告诉你“行优先更快”。本教程实测缓存未命中代价，并编写递归分块（morton order）遍历，使得任何缓存大小都能自动利用。你将使用 perf 或 bcc 观察 L1 未命中，并用 Go 的 testing.Benchmark 量化差异。还会讨论 Go 编译器自动向量化的限制。

func TraverseBlocks(arr [][]int, x0, y0, x1, y1 int) {
    if x1-x0 <= 16 && y1-y0 <= 16 {
        for i := x0; i < x1; i++ {
            for j := y0; j < y1; j++ {
                _ = arr[i][j]
            }
        }
        return
    }
    mx, my := (x0+x1)/2, (y0+y1)/2
    // 四块递归
    TraverseBlocks(arr, x0, y0, mx, my)
    TraverseBlocks(arr, x0, my, mx, y1)
    TraverseBlocks(arr, mx, y0, x1, my)
    TraverseBlocks(arr, mx, my, x1, y1)
}