<p>In a <a href="https://en.wikipedia.org/wiki/Structural_type_system" rel="noreferrer">structural type system</a>, a type can be assignable to another type without this relationship necessarily being declared. For example, in Typescript <code>{x: number, y: string}</code> is assignable to <code>{y: string}</code> because it has all of the required fields.</p>
<p>This raises a question of how a field access like <code>obj.y</code> 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 <a href="https://mathiasbynens.be/notes/shapes-ics" rel="noreferrer">inline caches</a> 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 &quot;slow path&quot; 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.</p>
<p>In contrast, <a href="https://en.wikipedia.org/wiki/Nominal_type_system" rel="noreferrer">nominal type systems</a> with single inheritance can avoid this problem since the access <code>obj.y</code> can only be performed on an object of some known type which declares the field <code>y</code>, 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.</p>
<p>Is it possible for an ahead-of-time compiler to avoid runtime lookups of field offsets by name, in a structural type system?</p>

<compilers><polymorphism><structural-types>
How can polymorphism in a structural type system be compiled?
<p>OCaml uses a <a href="https://sympa.inria.fr/sympa/arc/caml-list/2008-01/msg00183.html" rel="nofollow noreferrer">hybrid approach</a>: 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.</p>
<pre><code># object method azdwbie = 1 end;;
- : &lt; azdwbie : int &gt; = &lt;obj&gt;
# object method c7diagq = 2 end;;
- : &lt; c7diagq : int &gt; = &lt;obj&gt;
# object method azdwbie = 1 method c7diagq = 2 end;;
Error: Method labels `azdwbie' and `c7diagq' are incompatible.
       Change one of them.
</code></pre>
<p>The same restriction applies to variant names in polymorphic variants, i.e. tag names for union types with nominal typing.</p>
<pre><code># if true then `azdwbie else `c7diagq;;
Error: Variant tags `azdwbie and `c7diagq have the same hash value.
       Change one of them.
</code></pre>
<p>In practice most programmers never find out.</p>
<p>There are various ways this hash-based approach could be modified to avoid rejecting programs with colliding method names, but they all have downsides.</p>
<ul>
<li>If the compiler can know all the methods of a program before generating code, it can calculate a <a href="https://en.wikipedia.org/wiki/Perfect_hash_function" rel="nofollow noreferrer">perfect hash function</a> for that set of method names, so that no collisions will happen. But this rules out separate compilation, which OCaml supports.</li>
<li>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).</li>
<li>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.</li>
</ul>

CC BY-SA 4.0
2023-05-20T21:41:14.717Z
2023-05-21T19:53:09.350Z
2023-05-21T19:53:09.350Z
Gilles 'SO- stop being evil'
CC BY-SA 4.0
2023-05-21T07:30:13.800Z
Interesting! Wouldn't it be possible to change the hash function in order to avoid collisions, though?
kaya3
CC BY-SA 4.0
2023-05-21T09:56:37.817Z
@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).
Gilles 'SO- stop being evil'
CC BY-SA 4.0
2023-05-21T10:12:42.883Z
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?
kaya3
CC BY-SA 4.0
2023-05-21T10:34:06.473Z
@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.
Gilles 'SO- stop being evil'
CC BY-SA 4.0
2023-05-21T10:35:03.163Z
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.
kaya3
CC BY-SA 4.0
2023-05-21T19:12:50.967Z
@kaya3 But then the hashes aren't known at compile time, which adds complexity and code size to object construction. There are solutions, but they don't come for free.
Gilles 'SO- stop being evil'
CC BY-SA 4.0
2023-05-21T19:15:39.433Z
I'm really not following you. If the compiler knows all of the names in the program then it can choose a hash function with no collisions on those names, and it can compute their hashes at compile-time.
kaya3
CC BY-SA 4.0
2023-05-21T19:18:14.520Z
@kaya3 You're forgetting about separate compilation. Not to mention dynamic loading.
Gilles 'SO- stop being evil'
CC BY-SA 4.0
2023-05-21T19:21:07.163Z
I'm not forgetting about those things ─ I asked, *"Or do you mean the hashes have to be consistent across different compilation jobs?"* ─ but I didn't get a clear answer. It would help if you added these to your answer as reasons that OCaml does it this way.
kaya3
CC BY-SA 4.0
2023-05-21T19:54:17.120Z
@kaya3 I've expanded on some potential solutions that could apply to other languages.
Gilles 'SO- stop being evil'
<p>When compiling a single program in a closed world, whole-program analysis can identify</p>
<ol>
<li>every structural type referred to anywhere in the program</li>
<li>every shape of object that can be constructed</li>
</ol>
<p>With this information, <strong>structural typing can be reduced to nominal typing</strong>: in Java terms, every structural type becomes a nominal interface, and every object implements all the relevant interfaces.</p>
<p>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.</p>
<p>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.</p>
<hr />
<p>Another approach is to make every structural type real: for each type, define a widening conversion for <em>every possible supertype</em>. This conversion will produce <strong>a new object conforming exactly to the type, with no surplus slots</strong>, 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.</p>
<p>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.</p>

CC BY-SA 4.0
2023-05-20T09:12:23.593Z
2023-05-20T09:12:23.593Z
Michael Homer
CC BY-SA 4.0
2023-08-17T17:31:05.767Z
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.
feldentm
CC BY-SA 4.0
2023-08-17T18:38:20.970Z
What you’re seeing is explicitly what the answer says, yes.
Michael Homer
CC BY-SA 4.0
2023-08-11T16:51:52.643Z
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.
feldentm
CC BY-SA 4.0
2023-08-16T03:15:45.203Z
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.
Michael Homer
CC BY-SA 4.0
2023-08-16T15:50:05.557Z
You need the layout to generate code, because the CPU has to do something when accessing data, right?
feldentm
CC BY-SA 4.0
2023-08-16T18:41:22.467Z
Every value has *a* layout that you generate, but there’s no requirement that they have anything in common with one another.
Michael Homer
<h2>Consistent packing</h2>
<p>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.</p>
<p>Consider these structs:</p>
<pre class="lang-rs prettyprint-override"><code>struct A {
    delta: u32,
    epsilon: u32
}

struct B {
    delta: u32,
    gamma: u64
}

struct C {
    delta: u32
    gamma: u64,
    epsilon: u32
}
</code></pre>
<p>We create this list of attributes, consider attributes with different types in binary different. Pointers are the same, but primitives are different from eachother:</p>
<div class="s-table-container">
<table class="s-table">
<thead>
<tr>
<th>Name</th>
<th>Size</th>
<th>Occurrences</th>
</tr>
</thead>
<tbody>
<tr>
<td>gamma</td>
<td>8</td>
<td>2</td>
</tr>
<tr>
<td>epsilon</td>
<td>4</td>
<td>2</td>
</tr>
<tr>
<td>delta</td>
<td>4</td>
<td>3</td>
</tr>
</tbody>
</table>
</div>
<p>Now we sort first by most occurrences then by lowest size to get them in this order:</p>
<ul>
<li>epsilon</li>
<li>delta</li>
<li>gamma</li>
</ul>
<p>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:</p>
<div class="s-table-container">
<table class="s-table">
<thead>
<tr>
<th>Attribute</th>
<th>Position</th>
</tr>
</thead>
<tbody>
<tr>
<td>gamma</td>
<td>0</td>
</tr>
<tr>
<td>epsilon</td>
<td>8</td>
</tr>
<tr>
<td>delta</td>
<td>4</td>
</tr>
</tbody>
</table>
</div>
<p>Now we can translate attribute accesses using this table:</p>
<div class="s-table-container">
<table class="s-table">
<thead>
<tr>
<th>Code</th>
<th>Translated form</th>
</tr>
</thead>
<tbody>
<tr>
<td>a.gamma</td>
<td><code>*a</code></td>
</tr>
<tr>
<td>a.epsilon</td>
<td><code>*(a+8)</code></td>
</tr>
<tr>
<td>a.delta</td>
<td><code>*(a+4)</code></td>
</tr>
</tbody>
</table>
</div>
<p>This leaves a 4 byte gap in struct <code>A</code>. 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.</p>
<p>Still it should be more performant than a hash map.</p>

CC BY-SA 4.0
2023-05-20T09:14:16.407Z
2023-05-20T09:56:25.173Z
2023-05-20T09:56:25.173Z
mousetail 'he-him'
<p>In <a href="https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/scopedlabels.pdf" rel="nofollow noreferrer">Extensible Records with Scoped Labels</a>, 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.</p>
<p>Here’s an example from the paper:</p>
<p><span class="math-container">$$
\begin{align}
&amp; \mathrm{dist} :: \forall \, r. \{ x :: \mathrm{Int}, y :: \mathrm{Int} \mid r \} \to \mathrm{Int} \\
&amp; \mathrm{dist} \: r = r\mathrm{.}x + r \mathrm{.}y
\end{align}
$$</span></p>
<p>This is compiled into an outer “wrapper” function containing the lookups, and an inner “worker” that takes the integer field offsets as arguments:</p>
<p><span class="math-container">$$
\begin{align}
&amp; \mathrm{dist} \: r = \mathrm{dist\_work} \: (\mathbf{lookup} \: r \: x) \: (\mathbf{lookup} \: r \: y) \: r \\
&amp; \mathrm{dist\_work} \: i \: j \: r = \mathbf{select} \: r \: i + \mathbf{select} \: r \: j
\end{align}
$$</span></p>
<p>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.</p>
<p>Calling this function on a subtype of its parameter type, like so:</p>
<pre><code>dist { w = 0, x = 10, y = 20, z = 30 }
</code></pre>
<p>Would compile to something like this (C99):</p>
<pre><code>struct R { int w, x, y, z; };
</code></pre>
<pre><code>dist_work(
  offsetof(struct R, x),
  offsetof(struct R, y),
  &amp;(struct R) { .w = 0, .x = 10, .y = 20, .z = 30 }
)
</code></pre>

CC BY-SA 4.0
2023-05-21T01:37:39.833Z
2023-08-11T05:31:08.180Z
2023-08-11T05:31:08.180Z
Jon Purdy
# How can polymorphism in a structural type system be compiled?
Posted by: username_0 on 2023-05-20
In a [structural type system](https://en.wikipedia.org/wiki/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](https://mathiasbynens.be/notes/shapes-ics) 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](https://en.wikipedia.org/wiki/Nominal_type_system) 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?
**Tags:** compilers polymorphism structural-types
---
## 4 answers
### Answer by username_5 on 2023-05-21. Score: 9 | Accepted answer
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 }
)
---
### Answer by username_1 on 2023-05-20. Score: 7
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 > = 
# object method c7diagq = 2 end;;
- : < c7diagq : int > = 
# 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.
> **Comments:**
> **username_0** (2023-05-21): Interesting! Wouldn't it be possible to change the hash function in order to avoid collisions, though?  
> **username_1** (2023-05-21): @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).  
> **username_0** (2023-05-21): 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?  
> **username_1** (2023-05-21): @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.  
> **username_0** (2023-05-21): 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.  
> **username_1** (2023-05-21): @kaya3 But then the hashes aren't known at compile time, which adds complexity and code size to object construction. There are solutions, but they don't come for free.  
> **username_0** (2023-05-21): I'm really not following you. If the compiler knows all of the names in the program then it can choose a hash function with no collisions on those names, and it can compute their hashes at compile-time.  
> **username_1** (2023-05-21): @kaya3 You're forgetting about separate compilation. Not to mention dynamic loading.  
> **username_0** (2023-05-21): I'm not forgetting about those things ─ I asked, *"Or do you mean the hashes have to be consistent across different compilation jobs?"* ─ but I didn't get a clear answer. It would help if you added these to your answer as reasons that OCaml does it this way.  
> **username_1** (2023-05-21): @kaya3 I've expanded on some potential solutions that could apply to other languages.  
---
### Answer by username_2 on 2023-05-20. Score: 5
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.
> **Comments:**
> **username_3** (2023-08-11): 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.  
> **username_2** (2023-08-16): 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.  
> **username_3** (2023-08-16): You need the layout to generate code, because the CPU has to do something when accessing data, right?  
> **username_2** (2023-08-16): Every value has *a* layout that you generate, but there’s no requirement that they have anything in common with one another.  
> **username_3** (2023-08-17): 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.  
> **username_2** (2023-08-17): What you’re seeing is explicitly what the answer says, yes.  
---
### Answer by username_4 on 2023-05-20. Score: 4
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.
---
