Will the native compiler ever optimize memory layout of compound types?

optimization

#1

Say I have the type int list option. As I understand the current operation of ocamlopt, a value such as Some [5] will have a memory layout like this:

  • First, there will be an on-heap variant instance (for the option part), which will indicate Some and contain a pointer to an int list instance,
  • and that int list instance will itself be represented as an on-heap variant indicating :: with two fields, one being the immediate integer 5 and the other being an immediate integer representing the empty list [].

So, in order to get the fist element in a non-None int list option, the generated code has to follow one pointer before ending up at an actual int list instance, but it need not be this way. What if, instead, the compiler had flattened the nested variants in int list option, resulting in a single variant of three cases:

  • Some (head :: tail)
  • Some []
  • None

Such a flattened variant would require only one on-heap instance, and would still contain the same amount of information. In particular, the current on-heap “array of pointers” representation could still be used, retaining compatibility with the garbage collector.

Now, I’m aware this isn’t exactly a trivial thing to do. For one, it requires that all compilation units agree on the unique (optimized) layout of each concrete type, while also making it substantially harder to meaningfully inspect OCaml objects from external C code. And maybe more critically, it would substantially complicate code generation for polymorphic functions, and give a high performance penalty to any non-specialized polymorphic code.

So yes, I’m very aware of the many reasons that one might not want to do these sorts of optimizations, but they’re nonetheless interesting to someone who would like to be able to write memory-efficient polymorphic code in pure OCaml. Is there, then, any interest among those working on the compiler to implement such optimizations in the future, or even any experimental work that has done so already?