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

["Jon Harrop" <jon@ffconsultancy.com>]

On 24.01.2014 08:34, Andreas Rossberg wrote:
> On Jan 24, 2014, at 09:22 , Jon Harrop <jon@ffconsultancy.com> wrote:
>> With value types you can almost completely avoid the garbage 
>> collector by replacing pointers with indices into an array of value 
>> types that acts as a pool allocator. This can be useful for avoiding 
>> GC latency and for optimizing for collections that violate the 
>> generational hypothesis (e.g.
>> long-lived Sets and Maps).
>
> As you well know, though, pervasive unboxing as for value types is 
> incompatible with a uniform representation approach like used by 
> OCaml. And non-uniform representation requires either static 
> monomorphisation (not possible in OCaml, because of first-class 
> polymorphism and separate compilation), or dynamic monomorphisation 
> (not possible without just-in-time compilation), or runtime type 
> passing and switching (expensive).

I think there are halfway houses as well...

Options could keep the same uniform representation when on the heap but be
unboxed when they are stored locally (arguments, local variables and return
values). You could either carry the pointer to the original option (if any)
or re-allocate when it was needed.

If run-time type passing and switching is expensive because of virtual
dispatch then you could replace the dynamic jump with a test to see if the
location is the same as it was for the last jump and, if so, use a static
jump and then update just the static jump using JIT compilation. 
That requires JIT compilation but, perhaps, so little JIT compilation that
the technique is of interest?

The required run-time type information could just be the number of
(uniformly-represented) words in each value and the "switch" could be a loop
(that usually does only one iteration). For example, the "A of 'a | B of 'b
* 'b | C" could be represented using 3 words per value instead of one: one
for the tag A=1|B=2|C=3 and two for the two potential arguments.

On a related note, doesn't OCaml box multiple return values as well? Could
it use sret form and elide the write barrier instead?

Even if such approaches don't improve overall performance they should shift
the burden off the GC and onto the generated code which would make it easier
to obtain good performance for alternative GC implementations (like OC4MC).

Cheers,
Jon.