Joachim Breitner: A mostly allocation-free optional type
The Motoko programming language has a built-in data type for optional values, named ?t with values null and ?v (for v : t); this is the equivalent of Haskell s Maybe, Ocaml s option or Rust s Option. In this post, I explain how Motoko represents such optional values (almost) without allocation.
I neither claim nor expect that any of this is novel; I just hope it s interesting.
Uniform representation
The Motoko programming language, designed by Andreas Rossberg and implemented by a pretty cool team at DFINITY is a high-level language with strict semantics and a strong, structural, equi-recursive type system that compiles down to WebAssembly.
Because the type system supports polymorphism, it represents all values uniformly. Simplified for the purpose of this blog post, they are always pointers into a heap object where the first word of the heap object, the heap tag, contains information about the value:
tag
The tag is something like array, int64, blob, variant, record, , and it has two purposes:
- The garbage collector uses it to understand what kind of object it is looking at, so that it can move it around and follow pointers therein. Variable size objects such as arrays include the object size in a subsequent word of the heap object.
- Some types have values that may have different shapes on the heap. For example, the ropes used in our text representation can either be a plain
blob, or a concatenation node of two blobs. For these types, the tag of the heap object is inspected.
The optional type, naively
The optional type (?t) is another example of such a type: Its values can either be null, or ?v for some value v of type t, and the primitive operations on this type are the two introduction forms, an analysis function, and a projection for non-null values:
null : () -> ?t
some : t -> ?t
is_some : ?t -> bool
project : ?t -> t // must only be used if is_some holds
It is natural to use the heap tag to distinguish the two kind of values:
- The
null value is a simple one-word heap object with just a tag that says that this is null:
null
- The other values are represented by a two-word object: The tag
some, indicating that it is a ?v, and then the payload, which is the pointer that represents the value v:
some payload
With this, the four operations can be implemented as follows:
def null():
ptr <- alloc(1)
ptr[0] = NULL_TAG
return ptr
def some(v):
ptr <- alloc(2)
ptr[0] = SOME_TAG
ptr[1] = v
return ptr
def is_some(p):
return p[0] == SOME_TAG
def project(p):
return p[1]
The problem with this implementation is that null() and some(v) both allocate memory. This is bad if they are used very often, and very liberally, and this is the case in Motoko: For example the iterators used for the for (x in e) construct have type
type Iter<T> = next : () -> ?T
and would unavoidably allocate a few words on each iteration. Can we avoid this?
Static values
It is quite simple to avoid this for for null: Just statically create a single null value and use it every time:
static_null = [NULL_TAG]
def null():
return static_null
This way, at least null() doesn t allocate. But we gain more: Now every null value is represented by the same pointer, and since the pointer points to static memory, it does not change even with a moving garbage collector, so we can speed up is_some:
def is_some(p):
return p != static_null
This is not a very surprising change so far, and most compilers out there can and will do at least the static allocation of such singleton constructors.
For example, in Haskell, there is only a single empty list ([]) and a single Nothing value in your program, as you can see in my videos exploring the Haskell heap.
But can we get rid of the allocation in some(v) too?
Unwrapped optional values
If we don t want to allocate in some(v), what can we do? How about simply
def some(v):
return v
That does not allocate! But it is also broken. At type ??Int, the values null, ?null and ??null are distinct values, but here this breaks.
Or, more formally, the following laws should hold for our four primitive operations:
is_some(null()) = false-
v. is_some(some(v)) = true
-
p. project(some(p)) = p
But with the new definition of some, we d get is_some(some(null())) = false. Not good!
But note that we only have a problem if we are wrapping a value that is null or some(v). So maybe take the shortcut only then, and write the following:
def some(v):
if v == static_null v[0] == SOME_TAG:
ptr <- alloc(2)
ptr[0] = SOME_TAG
ptr[1] = v
return ptr
else:
return v
The definition of is_some can stay as it is: It is still the case that all null values are represented by static_null. But the some values are now no longer all of the same shape, so we have to change project():
def project(p):
if p[0] == SOME_TAG:
return p[1]
else:
return p
Now things fall into place: A value ?v can, in many cases, be represented the same way as v, and no allocation is needed. Only when v is null or ?null or ??null or ???null etc. we need to use the some heap object, and thus have to allocate.
In fact, it doesn t cost much to avoid allocation even for ?null:
static_some_null = [SOME_TAG, static_null]
def some(v):
if v == static_null:
return static_some_null
else if v[0] == SOME_TAG:
ptr <- alloc(2)
ptr[0] = SOME_TAG
ptr[1] = v
return ptr
else:
return v
So unless one nests the ? type two levels deep, there is no allocation whatsoever, and the only cost is a bit more branching in some and project.
That wasn t hard, but quite rewarding, as one can now use idioms like the iterator shown above with greater ease.
Examples
The following tables shows the representation of various values before and after. Here [ ] is a pointed-to dynamically allocated heap object, a statically allocated heap object, N = NULL_TAG and S = SOME_TAG.
tag
blob, or a concatenation node of two blobs. For these types, the tag of the heap object is inspected.?t) is another example of such a type: Its values can either be null, or ?v for some value v of type t, and the primitive operations on this type are the two introduction forms, an analysis function, and a projection for non-null values:
null : () -> ?t
some : t -> ?t
is_some : ?t -> bool
project : ?t -> t // must only be used if is_some holds- The
nullvalue is a simple one-word heap object with just a tag that says that this isnull:null - The other values are represented by a two-word object: The tag
some, indicating that it is a?v, and then the payload, which is the pointer that represents the valuev:some payload
def null():
ptr <- alloc(1)
ptr[0] = NULL_TAG
return ptr
def some(v):
ptr <- alloc(2)
ptr[0] = SOME_TAG
ptr[1] = v
return ptr
def is_some(p):
return p[0] == SOME_TAG
def project(p):
return p[1]null() and some(v) both allocate memory. This is bad if they are used very often, and very liberally, and this is the case in Motoko: For example the iterators used for the for (x in e) construct have type
type Iter<T> = next : () -> ?T Static values
It is quite simple to avoid this for for null: Just statically create a single null value and use it every time:
static_null = [NULL_TAG]
def null():
return static_null
This way, at least null() doesn t allocate. But we gain more: Now every null value is represented by the same pointer, and since the pointer points to static memory, it does not change even with a moving garbage collector, so we can speed up is_some:
def is_some(p):
return p != static_null
This is not a very surprising change so far, and most compilers out there can and will do at least the static allocation of such singleton constructors.
For example, in Haskell, there is only a single empty list ([]) and a single Nothing value in your program, as you can see in my videos exploring the Haskell heap.
But can we get rid of the allocation in some(v) too?
Unwrapped optional values
If we don t want to allocate in some(v), what can we do? How about simply
def some(v):
return v
That does not allocate! But it is also broken. At type ??Int, the values null, ?null and ??null are distinct values, but here this breaks.
Or, more formally, the following laws should hold for our four primitive operations:
is_some(null()) = false-
v. is_some(some(v)) = true
-
p. project(some(p)) = p
But with the new definition of some, we d get is_some(some(null())) = false. Not good!
But note that we only have a problem if we are wrapping a value that is null or some(v). So maybe take the shortcut only then, and write the following:
def some(v):
if v == static_null v[0] == SOME_TAG:
ptr <- alloc(2)
ptr[0] = SOME_TAG
ptr[1] = v
return ptr
else:
return v
The definition of is_some can stay as it is: It is still the case that all null values are represented by static_null. But the some values are now no longer all of the same shape, so we have to change project():
def project(p):
if p[0] == SOME_TAG:
return p[1]
else:
return p
Now things fall into place: A value ?v can, in many cases, be represented the same way as v, and no allocation is needed. Only when v is null or ?null or ??null or ???null etc. we need to use the some heap object, and thus have to allocate.
In fact, it doesn t cost much to avoid allocation even for ?null:
static_some_null = [SOME_TAG, static_null]
def some(v):
if v == static_null:
return static_some_null
else if v[0] == SOME_TAG:
ptr <- alloc(2)
ptr[0] = SOME_TAG
ptr[1] = v
return ptr
else:
return v
So unless one nests the ? type two levels deep, there is no allocation whatsoever, and the only cost is a bit more branching in some and project.
That wasn t hard, but quite rewarding, as one can now use idioms like the iterator shown above with greater ease.
Examples
The following tables shows the representation of various values before and after. Here [ ] is a pointed-to dynamically allocated heap object, a statically allocated heap object, N = NULL_TAG and S = SOME_TAG.
static_null = [NULL_TAG]
def null():
return static_nulldef is_some(p):
return p != static_nullsome(v), what can we do? How about simply
def some(v):
return v??Int, the values null, ?null and ??null are distinct values, but here this breaks.
Or, more formally, the following laws should hold for our four primitive operations:
is_some(null()) = false-
v.is_some(some(v)) = true -
p.project(some(p)) = p
some, we d get is_some(some(null())) = false. Not good!
But note that we only have a problem if we are wrapping a value that is null or some(v). So maybe take the shortcut only then, and write the following:
def some(v):
if v == static_null v[0] == SOME_TAG:
ptr <- alloc(2)
ptr[0] = SOME_TAG
ptr[1] = v
return ptr
else:
return vis_some can stay as it is: It is still the case that all null values are represented by static_null. But the some values are now no longer all of the same shape, so we have to change project():
def project(p):
if p[0] == SOME_TAG:
return p[1]
else:
return p?v can, in many cases, be represented the same way as v, and no allocation is needed. Only when v is null or ?null or ??null or ???null etc. we need to use the some heap object, and thus have to allocate.
In fact, it doesn t cost much to avoid allocation even for ?null:
static_some_null = [SOME_TAG, static_null]
def some(v):
if v == static_null:
return static_some_null
else if v[0] == SOME_TAG:
ptr <- alloc(2)
ptr[0] = SOME_TAG
ptr[1] = v
return ptr
else:
return v? type two levels deep, there is no allocation whatsoever, and the only cost is a bit more branching in some and project.
That wasn t hard, but quite rewarding, as one can now use idioms like the iterator shown above with greater ease.
Examples
The following tables shows the representation of various values before and after. Here [ ] is a pointed-to dynamically allocated heap object, a statically allocated heap object, N = NULL_TAG and S = SOME_TAG.
| type | value | before | after |
|---|---|---|---|
Null |
null |
N |
N |
?Int |
null |
N |
N |
?Int |
?23 |
[S,23] |
23 |
??Int |
null |
N |
N |
??Int |
?null |
[S, N ] |
S, N |
??Int |
??23 |
[S,[S,23]] |
23 |
???Int |
null |
N |
N |
???Int |
?null |
[S, N ] |
S, N |
???Int |
??null |
[S,[S, N ]] |
[S, S, N ] |
???Int |
???23 |
[S,[S,[S,23]]] |
23 |
Concluding remarks
- If you know what parametric polymorphism is, and wonder how this encoding can work in a language that has that, note that this representation is on the low-level of the untyped run-time value representation: We don t need to know the type of
v in some(v), merely its heap representation.
- The uniform representation in Motoko is a bit more involved: The pointers are tagged (by subtracting 1) and some scalar values are represented directly in place (shifted left by 1 bit). But this is luckily orthogonal to what I showed here.
- Could Haskell do this for its
Maybe type? Not so easily:
- The
Maybe type is not built-in, but rather a standard library-defined algebraic data type. But the compiler could feasible detect that this is option-like?
- Haskell is lazy, so at runtime, the type
Maybe could be Nothing, or Just v, or, and this is crucial, a yet to be evaluated expression, also called a thunk. And one definitely needs to distinguish between a thunk t :: Maybe a that may evaluate to Nothing, and a value Just t :: Maybe a that definitely is Just, but contains a value, which may be a thunk.
Something like this may work for a strict Maybe type or unlifted sums like (# (# #) a #), but may clash with other ticks in GHC, such as pointer tagging.
- As I said above, I don t expect this to be novel, and I am happy to add references to prior art here.
- Given that a heap object with tag
SOME_TAG now always encodes a tower ? null for n>0, one could try to optimize that even more by just storing the n:
some n
But that seems unadvisable: It is only a win if you have deep towers, which is probably rare. Worse, now the project function would have to return such a heap object with n decremented, so now projection might have to allocate, which goes against the cost model expected by the programmer.
- If you rather want to see code than blog posts, feel free to check out Motoko PR #2115.
- Does this kind of stuff excite you? Motoko is open source, so your contributions may be welcome!
v in some(v), merely its heap representation.Maybe type? Not so easily:
- The
Maybetype is not built-in, but rather a standard library-defined algebraic data type. But the compiler could feasible detect that this is option-like? - Haskell is lazy, so at runtime, the type
Maybecould beNothing, orJust v, or, and this is crucial, a yet to be evaluated expression, also called a thunk. And one definitely needs to distinguish between a thunkt :: Maybe athat may evaluate toNothing, and a valueJust t :: Maybe athat definitely isJust, but contains a value, which may be a thunk.
(# (# #) a #), but may clash with other ticks in GHC, such as pointer tagging.SOME_TAG now always encodes a tower ? null for n>0, one could try to optimize that even more by just storing the n:
some n
project function would have to return such a heap object with n decremented, so now projection might have to allocate, which goes against the cost model expected by the programmer.
I have uploaded most of my Machine Learning lecture to YouTube.
The slides are in English, but the audio is in German.
Some very basic contents (e.g., a demo of standard k-means clustering) were left out from this advanced class,
and instead only a link to recordings from an earlier class were given. In this class, I wanted to focus
on the improved (accelerated) algorithms instead. These are not included here (yet).
I believe there are some contents covered in this class you will find nowhere else (yet).
The first unit is pretty long (I did not split it further yet). The later units are shorter recordings.
ML F1: Principles in Machine Learning
Because 
