优化纳秒级操作：当CPU缓存成为关键变量

性能分析器会告诉你时间花在哪里。人们很容易把这当成一种承诺：删掉它指出的那 29 秒，你就能拿回 29 秒。本文讲述的是一个该承诺并不成立的案例。我们移除的检查确实很昂贵，但它的一部分开销悄无声息地转移到了我们从未改动过的一行代码上。

场景是一个热循环，其中单个操作大约耗时 200 纳秒。在这个尺度上，CPU 缓存不再只是一个细节，而开始决定你的代码成本；一个操作可能为另一个操作产生的开销买单。

让我们一起优化一次图遍历：一步一步来，并测量每一步。我们从最简单的版本开始。

任务

Maven Central 给了我们一个可供探索的大型自然图。作为示例任务，让我们一次性解析每个 Apache 项目的类路径：compile、runtime 和 test（仅最新版本）。2025 年 4 月的 Goblin 快照包含 1620 万个 release 和 1.36 亿条边——这将成为我们在一台笔记本电脑上、内存中的图。org.apache.* 为我们带来 30,889 个根 × 3 个 scope。

令人惊讶的是，正确的依赖解析本身就是一个 NP 完全问题（Russ Cox，“Version SAT”）。我们将使用 Go 简单得多的规则——最小版本选择（Minimal Version Selection）：请求的最高版本胜出。输出会经过校验：优化中的每一步都必须打印出完全相同的结果。

朴素版本

解析一个类路径需要三次遍历。select 收集所有可达项。reach 再次从根开始遍历，只沿着最高版本前进，从而跳过那些只能通过较低版本到达的分支。via 从每个直接依赖重复执行 reach，以判断每个条目是由哪一个直接依赖引入的。

这是任何人一开始都会采用的实现：将 release 表示为 group:artifact:version 字符串，将图表示为 HashMap<String, List<Dependency>>，使用带有已访问 release 的 HashSet 的广度优先搜索，根被拆分到并行线程中。

// 遍历访问到的每个 release：要跟随它的哪些依赖。
private fun passedOn(release: Release): List<Dependency> {
    val scopes = if (release == root) kind.rootScopes else kind.transitiveScopes
    // 查找 1：该 release 的依赖
    return graph.dependencies.getValue(release)
        .filter {
            // compile、runtime 或 test
            it.scope in scopes &&
                    // 不是根自身，无论哪个版本
                    it.artifact != rootArtifact &&
                    // 查找 2：目标是否存在？
                    graph.existsOnCentral(it.artifact, it.version)
        }
}

Maven Central 有一个陷阱：它不检查某个 release 的依赖是否存在。一个 POM 可能指向来自另一个仓库的 artifact（androidx 位于 Google 的仓库）、一个版本范围，或一个 -SNAPSHOT。在我们的遍历中，0.75% 的边指向了不在图中的 release；如果缺少这项检查，30,889 个 compile 类路径中有 13,155 个会失败。因此，每条边都会被检查：

// "g:a:v" 是否是图中的 release，即是否发布在 Central 上？
fun existsOnCentral(artifact: Artifact, version: Version): Boolean =
    // 构造 "g:a:v"，使用同一个 1600 万条目的 map
    dependencies.containsKey(releaseOf(artifact, version))

性能分析

为了对代码做性能分析，我们将使用 TickSnick，这是我自己的分析器。它的主要优势在于，它测量的是你命名的操作，而不是这些操作恰好经过的方法。你可以用 op(...) 包裹每个操作：

private fun passedOn(release: Release): List<Dependency> = op(PASSED_ON) {
    val scopes = if (release == root) kind.rootScopes else kind.transitiveScopes
    op(DEPENDENCIES) { graph.dependencies.getValue(release) }
        .filter {
            it.scope in scopes &&
                    it.artifact != rootArtifact &&
                    op(ON_CENTRAL) { graph.existsOnCentral(it.artifact, it.version) }
        }
}

报告会给出每个操作的时间、调用次数，以及由此得出的每次调用时间，即使某个操作只耗时 100 ns。而且随着代码变化，标签保持不变，因此两个版本的 profile 可以逐行进行 diff。（我为什么构建它：火焰图错了 57 倍。）

关闭 Turbo，18 GB 堆，每次运行三个测量批次，每个版本运行四次，交替进行。TickSnick 的报告，朴素实现，第 1 次运行，共 4 次（列和行有裁剪）：

粗粒度操作——墙钟时间，包含式，按运行时的嵌套关系
runBatch                      82.0 s
  resolveRoot                 82.0 s   100%
    resolve                   82.0 s   100%
      select                  42.5 s    52%
        - merge        自身    14.6 s    34%
        - onCentral    自身    12.2 s    29%   总计 29.2 s，分布在 4 个操作下
      via                     28.1 s    34%
        - onCentral    自身    11.8 s    42%
      reach                   10.1 s    12%
        - onCentral    自身    5.21 s    52%

粗粒度和细粒度操作——自身时间

最大遍历中耗时最高的一行是 merge，14.6 s。但 onCentral——Central 检查——出现在全部三次遍历中：总计 29.2 s，5.69 亿次调用，每次 205 ns。而且它的答案从不改变：g:a:v 是否存在只取决于这条边，而不取决于哪次遍历。

这立刻提示了一个优化：Central 检查只做一次。

centralEdges

centralEdges 会删除所有指向不存在 release 的边——占图中所有边的 4.2%——只做一次，且在任何遍历之前完成。遍历中只保留 scope 和根检查：

override fun prepare(graph: Graph): Graph {
    val dependencies = HashMap<Release, List<Dependency>>(graph.dependencies.size * 4 / 3 + 1)
    for ((release, list) in graph.dependencies)
        dependencies[release] = list.filter { graph.existsOnCentral(it.artifact, it.version) }
    return Graph(dependencies)
}

profile 显示这项检查耗时 29.2 s，所以这就是我们预期能节省的时间。让我们运行它。

差异

让我们看看 TickSnick 对每个版本全部四次运行所做的 diff：

Diff          朴素（4 次运行）-> centralEdges（4 次运行）
...
runBatch        82.4 s -> 58.1 s     -29%   +-1.3%  更快

成功：82 s -> 58 s！

三个批次从 82.4 s 变为 58.1 s：节省了 24.3 s。四次运行证实了这一点：TickSnick 报告了 95% 置信区间，±1.3%。

但 profile 说这项检查耗时 29.2 s。另外 4.9 s 去哪儿了？

我们怎么查明？同一个 diff 也能回答这个问题：它按名称匹配两个版本中的每个操作，并显示每个操作发生了什么变化。

啊哈，找到了：dependencies 慢了 86%。这是 passedOn 中查找 1 的标签，即 graph.dependencies.getValue(release)——从同一个 1600 万条目的 map 中获取该 release 的依赖列表。一行我们从未改动过的代码。同样是 2.22 亿次调用——只是每次调用都更久了。为什么一个未改动的查找会变慢？

这其实非常有趣。再说一次，我们没有碰那行代码，但它却慢了很多——就好像它接管了 onCentral 的一部分开销。这种情况什么时候会发生？当一部分在帮助另一部分时。但怎么帮的？通过缓存！

我们删掉的 onCentral 检查会在同一个 1600 万条目的 map 中查找 g:a:v，查找的正是遍历接下来要获取的那个 release。它承担了访问主内存的开销，而遍历的查找则在缓存中找到了该条目。没有这项检查后，这个查找现在会直接访问主内存。

我们能证明这个猜想吗？如果它是对的，那么只把检查放回去就应该让查找重新变快。于是有了：centralEdgesRecheck，即把检查放回剪枝后的图——现在它总是通过，所以它所做的只是触碰内存。每个版本运行三次，单独一组：

是的：从 185 ns 回到 99.9 ns，大约回到了朴素版本中的水平。## 结论

性能分析告诉了我们什么： 时间花在了哪里。一个答案永远不会改变的检查耗费了 29.2 秒。我们把它移出遍历后，节省了 24.3 秒。

它无法告诉我们什么： 这次优化究竟能省下多少。该检查的一部分开销来自一次内存访问，而这次访问并没有消失——下一行需要同一条目的代码为它付出了代价。

所以，每完成一步之后， 不仅要看哪些地方变得更便宜了，还要看哪些地方变得更贵了。相同的调用，每一次却更慢——那就是某一行在替别人买单。

接下来：merge 现在位居首位，194 纳秒处的查找直指内存布局本身。从这里开始只会越来越有意思。敬请期待。