Re: [Caml-list] How much optimized is the 'a option type ?

[Alain Frisch <alain@frisch.fr>]

On 01/17/2014 10:10 AM, Gabriel Scherer wrote:
> There have been recurrent discussions of optimizing `'a option` to
> avoid allocation in some cases, which is interesting when it is used
> as a default value for example. (The nice recent blog post by Thomas
> Leonard also seems to assume that `'a option` is somehow optimized.)
>
> My strictly personal opinion is that I doubt this would be a good
> idea, because I expect a fair share of the programming practice that
> currently use ('a option) to move to something like (('a,
> error-description) either) later in their lifetime, and I wouldn't
> want people to avoid to do that for performance concerns.
> Historically, we've rather come to see special-case representation
> optimizations (eg. array of floats) as a mistake -- but on the other
> hand there is not much downside to record of floats.

It could be argued the role of option types is important enough to 
justify a special treatment for them.  But maybe one could think (just 
for the fun of it) about a more general optimized representation for sum 
types where one constructor should behave (mostly) as the identity at 
runtime.

To take an example, consider a type:

   type ('a, 'b) t =
      | A of 'a
      | B of 'b * 'b
      | C

with some marker to tell the compiler to optimize the representation of A.

If one wants the constructor A to be the identity at runtime (in most 
cases), we still need to distinguish C from A C, A (A C), A (A (A C)), 
etc,  and B (x, y) from A (B (x, y)), A (A (B (x, y))), etc.  Here is 
one possible implementation:  let's allocate a fresh value to represent 
the identity of the t type:

   id_t = 0:(0)

that is, a block of size 1, tag 0, with a single 0 field (equivalent to: 
id_t = ref ()).  (This value would be generated by the compiler and 
passed along in modules which re-export the type t.)

The value (B (x, y)) would be represented as a block b0 = 1:(id_t, 0, x, 
y)  (block with tag 1 and 4 fields).  Applying the A constructor to such 
a block b0 would return a new block b1 = 1:(id_t, b0).  Applying again 
the A constructor to b1 would return b2 = 1:(id_t, b1).

Similarly, the value C would be represented as a block c0 = 2:(id_t, 0). 
  Applying A to such a value would return a block c1 = 1:(id_t, c0), and 
then c2 = 1:(id_t, c1).

So, in general, applying the A constructor to a value x requires to 
check if its argument is a block whose first field is equal to id_t, and 
in this case, it returns a new block with the same tag and the two 
fields id_t and x.  In other cases, the constructors simply returns its 
argument.

With this representation, it is not difficult to deconstruct the three 
constructors.  For a value of type t:

  - If the value is a block whose first field is equal to id_t and its 
second field is 0, then the value comes from the B or C constructor 
(according to the block tag) and the arguments can be found in the block.

  - If the value is a block whose first first is equal to id_t and its 
second field is not 0, then the value comes from the A constructor, and 
the argument is the second field of the block.

  - Otherwise, the value comes from the A constructor and its argument 
is represented by the same value.


There is one correctness problem with this representation, though: 
applying the A constructor to a float value cannot be the identity, 
because of the specific representation for float arrays (which is 
triggered by checking if the value is a float block).  This means we 
must also have a special representation for A x, A (A x), etc, where x 
is a float.  The scheme above extends naturally to support this 
representation:  a0 = 0:(id_t, 0, x), a1 = 0:(id_t, a0), etc.


Another drawback is related to the use of the id_t block, which does not 
work well with the generic marshaling, and requires extra plumbing to 
make this value available where the type t can be constructed or 
deconstructed.  It's possible to do better for a type with a "global name".


In case of a constant constructor such as C, one can of course 
pre-allocate the block c0 = 2:(id_t, 0).  To avoid passing an extra 
value around, one could store it within id_t itself (id_t = 0:(c0) 
instead of id_t = 0:(0)).

Another optimization is to avoid the allocation when applying the A 
constructor several times to the same B or C value.  This can be done by 
memoization.  One can add an extra field to all the blocks described 
above, initialized to 0, and updated to point to the "next" application 
of A when requested.

So, we would have:

   c0 = 2:(id_t, 0, 0)

When applying A to it, one create c1

   c1 = 2:(id_t, c0, 0)

and update the last field of c0 to be c1:

   c0 = 2:(id_t, 0, c1)

If one needs to apply A again to c0, one can reuse the existing value. 
The same applies to non-constant constructors as well.



-- Alain