wingolog

Today, a very quick note on dynamic instance type checks in virtual machines with single inheritance.

The problem is that given an object o whose type is t, you want to check if o actually is of some more specific type u. To my knowledge, there are two sensible ways to implement these type checks.

if the set of types is fixed: dfs numbering

Consider a set of types T := {t, u, ...} and a set of edges S := {<t|ε, u>, ...} indicating that t is the direct supertype of u, or ε if u is a top type. S should not contain cycles and is thus a direct acyclic graph rooted at ε.

First, compute a pre-order and post-order numbering for each t in the graph by doing a depth-first search over S from ε. Something like this:

def visit(t, counter):
    t.pre_order = counter
    counter = counter + 1
    for u in S[t]:
        counter = visit(u, counter)
    t.post_order = counter
    return counter

Then at run-time, when making an object of type t, you arrange to store the type’s pre-order number (its tag) in the object itself. To test if the object is of type u, you extract the tag from the object and check if tag–u.pre_order mod 2ⁿ < u.post_order–u.pre_order.

Two notes, probably obvious but anyway: one, you know the numbering for u at compile-time and so can embed those variables as immediates. Also, if the type has no subtypes, it can be a simple equality check.

Note that this approach applies only if the set of types T is fixed. This is the case when statically compiling a WebAssembly module in a system that doesn’t allow modules to be instantiated at run-time, like Wastrel. Interestingly, it can also be the case in JIT compilers, when modeling types inside the optimizer.

if the set of types is unbounded: the display hack

If types may be added to a system at run-time, maintaining a sorted set of type tags may be too much to ask. In that case, the standard solution is something I learned of as the display hack, but whose name is apparently ungooglable. It is described in a 4-page technical note by Norman H. Cohen, from 1991: Type-Extension Type Tests Can Be Performed In Constant Time.

The basic idea is that each type t should have an associated sorted array of supertypes, starting with its top type and ending with t itself. Each t also has a depth, indicating the number of edges between it and its top type. A type u is a subtype of t if u[t.depth]=t, if u.depth <= t.depth.

There are some tricks one can do to optimize out the depth check, but it’s probably a wash given the check performs a memory access or two on the way. But the essence of the whole thing is in Cohen’s paper; go take a look!

Jan Vitek notes in a followup paper (Efficient Type Inclusion Tests) that Christian Queinnec discovered the technique around the same time. Vitek also mentions the DFS technique, but as prior art, apparently already deployed in DEC Modula-3 systems. The term “display” was bouncing around in the 80s to describe some uses of arrays; I learned it from Dybvig’s implementation of flat closures, who learned it from Cardelli. I don’t know though where “display hack” comes from.

That’s it! If you know of any other standard techniques for type checks with single-inheritance subtyping, do let me know in the comments. Until next time, happy hacking!