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 C implements an interface I, 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 yields “implements” calls that are equal to the product of the total number of concrete ($|C|$) and interface ($|I|$) types ($O(|C| × |I|$)). For large programs in languages with structural subtyping, such as Go, the RTA algorithm is less effective at rapidly finding these relationships, slowing callgraph 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; furthermore, we employ lock-free data structures to ensure scalability.

We evaluate Kumo on an industry-scale corpus of 732 Go services at Neptune. The method index alone yields up to 4× speedup over Go’s standard-library RTA; combined with fine-grained parallelism using 64 workers, Kumo achieves a peak speedup of 30× with median exceeding 16×. Kumo is being used in Neptune’s CI systems on every code diff, and the speedups translate to reducing the most expensive graph construction step from 30+ minutes to ~70 seconds on large programs. While evaluated on Go, the technique applies to any language with structural subtyping.