A 1989 Paper Doubled Dynamic Language Speed by Guessing Types

Every procedure in the program can end up compiled several times over, each copy specialized to one receiver type it sees. That is the central move in a 1989 paper on compiling Self, a dynamically-typed object-oriented language. The problem it attacked has not aged: dynamically-typed languages keep pleasing programmers, and the missing static type information is what their performance pays for.

The paper’s answer is a bet with a receipt: pull static type information out of a declaration-free program. The compiler predicts types that are statically unknown but likely, and inserts run-time type tests to verify its predictions. It compiles several copies of a given procedure, each customized for one receiver type, so that “the type of the receiver is bound at compile time.” Calls are split as well, with a copy compiled on each control path and optimized to the types expected there.

Compile-time message lookup, aggressive procedure inlining, and traditional optimizations do the rest. Together the techniques doubled the performance of dynamically-typed object-oriented languages. What I like is that the guess is not hidden: the compiler writes down how to check it, and the program pays when the check fails. That is a more honest trade than most performance writing I read now, which presents specialization as though the check cost nothing and the type were known in advance.

Strip the 1989 vocabulary and the optimizers I run today look familiar: a fast path for the receiver a call site usually sees, a slower path for the rest, a branch between them. The copies carry a limit, though. One copy per receiver type is a good deal when a call site sees a few types and a poor deal when it sees many. Nothing sets a threshold, and none is needed: the technique is a wager on a distribution, and the distribution is what deserves measuring before trusting the trick.

Read it if you build or tune a language runtime; call splitting is where the copies multiply and where the inlining rules get spelled out. Anyone hoping for a shortcut to making a slow dynamic service fast should look elsewhere, since the reported doubling is a 1989 number and the method is the part that lasted. Picture the compiled method table, one entry matching the common case and one test standing guard beside it. Then open the slowest call in your profiler output and count the receiver types that really arrive.