一句话：提出 Kumo，用方法索引与并行化加速结构子类型语言中的 RTA 调用图构建，Uber Go 服务中位加速 116×。
RTA 在名义子类型下可常数时间判定“具体类型 C 是否实现接口 I”，但结构子类型（如 Go）中子类型关系隐式，需比较方法集合。RTA 增量发现类型，朴素做法将新类型与已发现类型两两比较，导致 O(|C|×|I|) 次 implements 检查，拖慢大型程序调用图构建。本文提出 Kumo：利用“匹配类型至少共享一个方法名”这一必要条件构建方法索引，将检查限制在少量候选；并并行化 RTA 的不动点迭代，以事件排序与细粒度同步保证正确性和可扩展性。在 Uber 969 个 Go 服务上，64 worker 下相对标准库 RTA 中位加速超 116×、峰值 268×，最昂贵图构建步骤从 40 分钟降至 15 秒内，已用于 Uber CI。
Rapid Type Analysis (RTA) is an important algorithm used in constructing whole-program call graphs. RTA occupies a special middle ground between precision and speed, making it an algorithm of choice for many industry-scale downstream program analysis tasks. RTA’s core subtyping query, which asks whether a concrete type 𝐶 implements an interface 𝐼, is cheap under nominal subtyping: the implements relation is syntactically expressed and hence resolved in constant time. Under structural subtyping, however, the hierarchy is implicit and must be computed by comparing method sets. RTA discovers types incrementally during its fixed-point iteration, and the naive approach checks each newly discovered concrete type (interface type) against all known interface types (concrete types) so far. The resulting analysis performs a number of “implements” calls equal to the product of the total number of concrete (|𝐶|) and interface (|𝐼|) types (𝑂(|𝐶|×|𝐼|)). For large programs in languages with structural subtyping, such as Go, the RTA algorithm is less effective at rapidly finding these relationships, slowing call graph construction. We present Kumo, an improvement to the RTA algorithm that addresses its weaknesses in structurally typed languages. With Kumo, we solve the aforementioned problem with two techniques: first, we reduce the work overhead of discovering subtypes using a purpose-built method index technique, and second, we efficiently parallelize the algorithm to achieve high speedups. The method index exploits a necessary condition of structural subtyping—matching types must share at least one method name—to restrict each implements check to a small set of plausible candidates, reducing the check count to near-linear in practice. The parallelization exploits the fixed-point iteration of RTA while guaranteeing correctness via a subtle event ordering; fine-grained synchronization ensures scalability. We evaluate Kumo on an industrial corpus of 969 Go services at Uber. Relative to Go’s unmodified standard-library RTA, Kumo achieves a median speedup exceeding 116×with peaks reaching 268×, using 64 workers. Kumo is being used in Uber’s CI systems on every code diff, and the speedups translate to reducing the most expensive graph construction step from 40 minutes to under 15 seconds using 64 parallel workers on large programs. While evaluated on Go, the technique applies to any language with structural subtyping.
@article{paperbot12129,
title = {Beyond Nominality: Faster Rapid Type Analysis in the Presence of Structural Subtyping},
author = {Elton Pinto and Milind Chabbi},
journal = {Proceedings of the ACM on Programming Languages},
volume = {10},
number = {OOPSLA2},
year = {2026},
doi = {10.1145/3839455}
}