Why GADTs matter for performance (2015)

Summary

When GADTs (Generalized Algebraic Data Types) landed in OCaml, I wasn’t particularly happy about it. I assumed that it was the kind of nonsense you get when you let compiler writers design your programming language. Which is to say that the standard GADT examples all seem to be about the kinds of things that compiler writers do, like embed domain-specific languages or build typed abstract-syntax trees. But it didn’t seem particularly relevant for the kind of systems programming that I think about. But it became apparent pretty quickly that I was wrong. In particular, since GADTs have landed, at Jane Street we’ve found lots of examples where GADTs are important for performance, of all things. The theme in these examples is that GADTs enable you to tweak your memory representations in ways that would otherwise be painful or impossible to do safely in OCaml. The Problem of Polymorphism I’d like to walk through a simple example that illustrates this aspect of GADTs, but first, a few words about OCaml’s memory representation. OCaml’s polymorphism is in an important way backed on that memory representation. In particular, consider a simple polymorphic function like List.iter, which has the following type: val iter: 'a list -> f:('a -> unit) -> unit The polymorphic type tells you that List.iter can operate on lists of any type, and in OCaml, this is achieved with a single compiled version of the code. This is possible because the memory representation of the elements of a list are uniform: you can always refer to an OCaml value in a single word, either as a pointer to a heap-allocated value, or as an immediate that fits inside that word. That means that some OCaml datatypes are less efficient space-wise than you might imagine. Arrays, for example, take the same amount of space per element whether those elements are bytes, 32-bit ints, or 64-bit ints. (There’s actually some special magic in the compiler for float arrays, though this is probably more trouble than it’s worth,...