Beyond Nominality: Faster Rapid Type Analysis in the Presence of Structural Subtyping

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.