15
$\begingroup$

In a structural type system, a type can be assignable to another type without this relationship necessarily being declared. For example, in Typescript {x: number, y: string} is assignable to {y: string} because it has all of the required fields.

This raises a question of how a field access like obj.y could be compiled ahead-of-time. An interpreter can implement objects as hashtables, and look up their fields by name at runtime. A JIT compiler can use inline caches to avoid repeating these lookups, but in order to fill in the cache, the field's offset in the object must still be looked up at least once at runtime, and this "slow path" must be followed in case the object has a different shape than the one that was cached. Either way, these approaches require the object's shape to be represented at runtime, and for names to be looked up dynamically.

In contrast, nominal type systems with single inheritance can avoid this problem since the access obj.y can only be performed on an object of some known type which declares the field y, and this field will have the same offset in all subtypes. This allows the field access to be compiled to a simple read at that known offset, and there is no need for the field's offset to ever be computed at runtime.

Is it possible for an ahead-of-time compiler to avoid runtime lookups of field offsets by name, in a structural type system?

$\endgroup$
0

4 Answers 4

9
$\begingroup$

In Extensible Records with Scoped Labels, the paper that introduced the now-popular technique for typechecking row-polymorphic records and variants, Daan Leijen describes the approach to compiling polymorphic records used in his research language at the time, Morrow. Namely, if a function takes a polymorphic record parameter, and the concrete type can’t be determined at compile time, then the offset of each field is added as an extra parameter. This is an “evidence-passing” translation which is basically the same idea as the “dictionary passing style” used to implement typeclasses and other forms of implicit parameters.

Here’s an example from the paper:

$$ \begin{align} & \mathrm{dist} :: \forall \, r. \{ x :: \mathrm{Int}, y :: \mathrm{Int} \mid r \} \to \mathrm{Int} \\ & \mathrm{dist} \: r = r\mathrm{.}x + r \mathrm{.}y \end{align} $$

This is compiled into an outer “wrapper” function containing the lookups, and an inner “worker” that takes the integer field offsets as arguments:

$$ \begin{align} & \mathrm{dist} \: r = \mathrm{dist\_work} \: (\mathbf{lookup} \: r \: x) \: (\mathbf{lookup} \: r \: y) \: r \\ & \mathrm{dist\_work} \: i \: j \: r = \mathbf{select} \: r \: i + \mathbf{select} \: r \: j \end{align} $$

The idea is that these offsets are likely to be known at the call site of the wrapper, supposing that it’s inlined. It goes on to give a brief description of how to float the lookup operations out of expressions, including offset adjustments for record-extension expressions.

Calling this function on a subtype of its parameter type, like so:

dist { w = 0, x = 10, y = 20, z = 30 }

Would compile to something like this (C99):

struct R { int w, x, y, z; };
dist_work(
  offsetof(struct R, x),
  offsetof(struct R, y),
  &(struct R) { .w = 0, .x = 10, .y = 20, .z = 30 }
)
$\endgroup$
7
$\begingroup$

OCaml uses a hybrid approach: names are hashed to an integer, and records contain a table of (hash, method address) pairs ordered by hash (on which the runtime does a binary search). More precisely, in OCaml, this applies to methods of objects (structure types have nominal typing, and object fields are private, but object methods are public and have structural typing). If there is any attempt to construct an object where two method names have the same hash, the compiler rejects the program.

# object method azdwbie = 1 end;;
- : < azdwbie : int > = <obj>
# object method c7diagq = 2 end;;
- : < c7diagq : int > = <obj>
# object method azdwbie = 1 method c7diagq = 2 end;;
Error: Method labels `azdwbie' and `c7diagq' are incompatible.
       Change one of them.

The same restriction applies to variant names in polymorphic variants, i.e. tag names for union types with nominal typing.

# if true then `azdwbie else `c7diagq;;
Error: Variant tags `azdwbie and `c7diagq have the same hash value.
       Change one of them.

In practice most programmers never find out.

There are various ways this hash-based approach could be modified to avoid rejecting programs with colliding method names, but they all have downsides.

  • If the compiler can know all the methods of a program before generating code, it can calculate a perfect hash function for that set of method names, so that no collisions will happen. But this rules out separate compilation, which OCaml supports.
  • You could have the linker, or the loader, calculate the perfect hash. This allows separate compilation. However this adds complexity to object construction and reduces what the compiler can do and how it can optimizes it, which reduces the benefits of separate compilation. And this rules out dynamic loading, which OCaml supports (or at least it would restrict dynamic loading to code that doesn't add new method names).
  • You could have a secondary table containing actual method names. But how do you know when to consult that secondary table? If you consult it all the time, the hash optimization is completely bypassed. If you want to only consult it in the likely case of an object without collisions, you have to implement some form of runtime analysis (sometimes but not always optimizable at compile time) to validate the absence of collisions. This analysis has to run whenever an object is constructed through inheritance, and with the polymorphism present in OCaml a given call site can inherit from multiple classes with different sets of potentially clashing methods (hence the impossibility of a pure compile-time analysis). I don't know if this approach has been prototyped and benchmark in OCaml.
$\endgroup$
10
  • $\begingroup$ Interesting! Wouldn't it be possible to change the hash function in order to avoid collisions, though? $\endgroup$
    – kaya3
    May 21, 2023 at 7:30
  • $\begingroup$ @kaya3 Any hash function is going to have collisions. (Unless it's a cryptographic hash, but then the hash doesn't fit in a machine (sub-)word, which defeats its purpose.) Keep in mind that the hash is in the compiler source code. It's not like choosing a perfect hash after you know all the method names that people have ever written (and will ever write). $\endgroup$ May 21, 2023 at 9:56
  • $\begingroup$ The compiler can choose between different hash functions once it knows the names, though. Or do you mean the hashes have to be consistent across different compilation jobs? $\endgroup$
    – kaya3
    May 21, 2023 at 10:12
  • $\begingroup$ @kaya3 If different objects have different hash functions, it complicates inheritance. And that doesn't actually resolve the problem since there's no guarantee that at least one of the functions will give unique results. So it doesn't resolve the general problem, and it doesn't help in practice because collisions basically don't arise accidentally. $\endgroup$ May 21, 2023 at 10:34
  • $\begingroup$ I don't mean different hash functions for different objects; I mean the compiler can look at the whole program and then choose one hash function which has no collisions on the names used in that program. $\endgroup$
    – kaya3
    May 21, 2023 at 10:35
5
$\begingroup$

When compiling a single program in a closed world, whole-program analysis can identify

  1. every structural type referred to anywhere in the program
  2. every shape of object that can be constructed

With this information, structural typing can be reduced to nominal typing: in Java terms, every structural type becomes a nominal interface, and every object implements all the relevant interfaces.

This can be accomplished with fixed numeric indices for each type across the program, and there aren't generally so many structural types in the program for this to be unreasonable. There is still a layer of indirection here, which isn't quite as good as the single-inheritance fixed-offset case, but much better than dynamic lookup by name (it's roughly equivalent to precalculating the cache). There are time-space tradeoffs available to remove some indirection in favour of more empty slots in each object.

In an open-world scenario with separate compilation this approach is harder to pull off, but it can sometimes be possible to canonicalise types such that they have shared identities across modules.


Another approach is to make every structural type real: for each type, define a widening conversion for every possible supertype. This conversion will produce a new object conforming exactly to the type, with no surplus slots, and copy in the relevant field values. Whenever a value of type A is put into a variable of type B, the A-to-B conversion is used to create a new object just of type B. The subsequent code can then follow the fixed-offset nominal approach from the question when it accesses that variable.

This approach doesn't preserve object identity or handle aliases to mutable objects. That won't matter for a functional language or values without identity. It can be mitigated for object-oriented languages without reference aliasing at least, and the values copied back when the reference goes out of scope.

$\endgroup$
6
  • $\begingroup$ You cannot assume that closed world will allow you to know an exact layout for every use of structural typing. The result of your analysis can still be that there is no common layout at some location. $\endgroup$
    – feldentm
    Aug 11, 2023 at 16:51
  • $\begingroup$ You don't need a common layout anywhere; that's what the indirection is for. You can try to find one and skip some indirection when you do, but that's extra. $\endgroup$
    – Michael Homer
    Aug 16, 2023 at 3:15
  • $\begingroup$ You need the layout to generate code, because the CPU has to do something when accessing data, right? $\endgroup$
    – feldentm
    Aug 16, 2023 at 15:50
  • $\begingroup$ Every value has a layout that you generate, but there’s no requirement that they have anything in common with one another. $\endgroup$
    – Michael Homer
    Aug 16, 2023 at 18:41
  • $\begingroup$ The only way I see to get your proposal to work is to introduce an interface per structural type and have every matching actual type implement it. That would result in a massive overhead on interface operations at runtime. $\endgroup$
    – feldentm
    Aug 17, 2023 at 17:31
4
$\begingroup$

Consistent packing

We want every struct that has a attribute with the same name packed at the same position. First, we need to build a list of all attributes used in our application.

Consider these structs:

struct A {
    delta: u32,
    epsilon: u32
}

struct B {
    delta: u32,
    gamma: u64
}

struct C {
    delta: u32
    gamma: u64,
    epsilon: u32
}

We create this list of attributes, consider attributes with different types in binary different. Pointers are the same, but primitives are different from eachother:

Name Size Occurrences
gamma 8 2
epsilon 4 2
delta 4 3

Now we sort first by most occurrences then by lowest size to get them in this order:

  • epsilon
  • delta
  • gamma

Now we can position each structured attribute. We store the current length of each struct starting at 0. For every attribute, we position it at the first position where it does not overlap with any other attribute already positioned. So we'd get this:

Attribute Position
gamma 0
epsilon 8
delta 4

Now we can translate attribute accesses using this table:

Code Translated form
a.gamma *a
a.epsilon *(a+8)
a.delta *(a+4)

This leaves a 4 byte gap in struct A. This algorithm was designed to minimize the size of the gaps but it's not perfect, especially it might give one struct a large gap to reduce the gap of some other structs, but if those others are used less that might not actually be desirable.

Still it should be more performant than a hash map.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .