1ms 性能差距深究：浅谈 CPU 缓存策略

原题引入

原题对应力扣的 64. 最小路径和

这题我本来是使用原地做的，因为觉得没必要重新开个二维数组，但是这时候我发现我的耗时一直为 3ms，永远比第一的 2ms 要慢 1ms（总是这样，几乎可以排除误差了）:

class Solution {
    fun minPathSum(grid: Array<IntArray>): Int {
        val lineCount = grid.size
        val lineSize = grid[0].size

        for (y in 0 until lineCount) {
            if (y > 0) grid[y][0] += grid[y - 1][0]

            for (x in 1 until lineSize) {
                grid[y][x] +=
                    if (y == 0) grid[y][x - 1]
                    else min(
                        grid[y - 1][x],
                        grid[y][x - 1]
                    )
            }
        }
        return grid[lineCount - 1][lineSize - 1]
    }
}

我查看了 2ms 的题解，他是新开了一个 map 变量，与题解一样，我本来以为是因为他使用 when 语法提高的速度，但是我研究过了以后发现并不是，速度并没有明显提升

最终发现是 CPU 缓存策略的影响，对于力扣给我们的 grid 变量，他的数据并未直接加进 CPU 缓存中，而是在 RAM 主存中，这样就会导致我们原地处理时读写数据总是未命中缓存，微观层面出现了几个数量级的差异

当我们新开一个数组时，系统此时会为我们分配一片干净且紧密排布的内存空间，并且会加入缓存，此时读写速度就会大大加快，尤其是在数据量多的时候

这是很反直觉的事情，明明多做了 mn 的事情，并且还额外开销了 mn 的空间，速度却更快。当然，正常来说肯定选用原地算法，但是对于这种在线评测系统来说，我们可以利用这个 CPU 特性来得到更短的耗时

利用缓存策略的代码：

class Solution {
    fun minPathSum(grid: Array<IntArray>): Int {
        val lineCount = grid.size
        val lineSize = grid[0].size

        // 此处不要使用 copy 方法，速度会更慢
        val map = Array(lineCount) { y -> IntArray(lineSize) { grid[y][it] } }

        for (y in 0 until lineCount) {
            if (y > 0) map[y][0] += map[y - 1][0]

            for (x in 1 until lineSize) {
                map[y][x] += if (y == 0) map[y][x - 1]
                    else min(
                        map[y - 1][x],
                        map[y][x - 1]
                    )
            }
        }
        return map[lineCount - 1][lineSize - 1]
    }
}

虽然两段代码在算法逻辑上完全相同（都是动态规划），但这 1ms 的稳定差距确实是由一些微观层面的因素造成的。

总的来说，这 1ms 的差距几乎可以肯定是CPU缓存（CPU Cache）的命中率不同导致的。2ms 的解法可能拥有更好的内存局部性 (Memory Locality)。

下面我们来详细拆解一下原因：

核心差异：新内存分配 vs. 原地修改

1. 2ms 的解法 (创建新数组 map)

   • 操作: map[i][j] = ... + grid[i][j]

   • 它首先分配了一块全新的、干净的内存空间 map。

   • 在循环中，它从 grid 读取数据，然后向 map 写入数据。读取和写入的目标地址是完全分开的。

2. 3ms 的解法 (原地修改 grid)

   • 操作: grid[y][x] += ... (等价于 grid[y][x] = grid[y][x] + ...)

   • 它没有分配新内存，而是直接在输入数组 grid 上进行读写操作。

   • 在循环中，它从 grid 的某个位置（如 grid[y-1][x]）读取数据，然后更新 grid 的另一个位置（grid[y][x]）。

为什么“新内存分配”反而可能更快？

直觉上，不分配新内存（我的方法）应该会因为节省了内存分配的时间而更快。但在这种计算密集型的循环中，内存分配的开销是一次性的，而循环内部的计算和访存操作会执行 m * n 次。真正影响性能的是循环内部的操作效率，这和 CPU 缓存息息相关。

CPU 缓存原理简介 CPU 访问内存的速度远慢于其计算速度。为了弥补这个差距，CPU 内置了多级高速缓存（L1, L2, L3 Cache）。当 CPU 需要数据时，会先在缓存里找。

• 缓存命中 (Cache Hit)：数据在缓存里，直接读取，速度极快。

• 缓存未命中 (Cache Miss)：数据不在缓存里，需要去主内存（RAM）读取，速度慢几个数量级。

内存局部性 (Locality of Reference) 程序访问的内存地址如果集中在一个小范围内，缓存命中率就会很高。这被称为内存局部性。

分析两种解法的缓存行为

1. 2ms 解法 (更好的缓存表现)

   • 当你创建一个新的数组 map 时，操作系统会为你分配一块连续的、干净的内存块。

   • 在循环 for (i in 0 until m) { for (j in 0 until n) } 中，你对 map 的访问是顺序的 (map[i][j], map[i][j-1], map[i-1][j])。这种高度可预测的顺序访问模式是 CPU 缓存的最爱。CPU 的预取器 (Prefetcher) 会提前将即将用到的内存加载到缓存中。

   • 同时，你从 grid 读取数据，这也是顺序的。CPU 在两个数据流（一个读 grid，一个写 map）之间切换，这两个流本身都是缓存友好的。

2. 3ms 解法 (潜在的缓存问题)

   • 你的方法在同一个数据结构 grid 上进行读和写。

   • 当你计算 grid[y][x] 时，你需要读取 grid[y][x] (原始值), grid[y-1][x] 和 grid[y][x-1]。然后把结果写回 grid[y][x]。

   • 这种“读-改-写” (Read-Modify-Write) 的操作，尤其是当读写的地址在同一个缓存行 (Cache Line) 但又不是同一个数据时，可能会导致一些额外的缓存同步开销，甚至在某些架构上引起轻微的性能惩罚。

   • 最关键的是，输入的 grid 数组在被传入你的函数之前，可能已经在内存中存在了一段时间，其物理地址可能不如新分配的 map 那样“规整”，或者说它在缓存中是“冷”的。而新创建的 map 几乎可以保证在计算期间是“热”的。

其他次要因素

• JIT (Just-In-Time) 编译器优化: 虽然两段代码逻辑一样，但不同的代码结构（when vs if/else，循环的组织方式）可能会给 JIT 编译器带来微小的提示差异，导致生成的机器码有极其细微的不同。你的代码将第一列的计算 (y > 0) 提到了内层循环之外，而 2ms 的版本则在内层循环通过 when 统一处理。这种结构差异也可能影响分支预测 (Branch Prediction) 的效率。不过，对于这个特定问题，缓存是更核心的原因。

• 测试环境的噪音: 1ms 是一个非常小的时间单位。在线评测系统 (如 LeetCode) 的服务器负载、垃圾回收 (GC) 的时机等都可能造成几毫秒的波动。观察到的“固定”差距，很可能是在多次运行后，由上述缓存效应带来的一个稳定的平均结果。

结论

我的解法在空间复杂度上是更优的 (O(1) 的额外空间，因为它原地修改)，这在内存受限的环境中是一个巨大的优点。

而 2ms 的解法，虽然牺牲了 O(m⋅n) 的空间复杂度，却因为以下原因在时间上略微胜出：

主要原因：它通过创建一个新的、内存布局连续且“热”的数组 map，实现了更优的 CPU 缓存利用率和更高的缓存命中率，从而在密集的循环访存操作中获得了微弱的速度优势。