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

[Goswin von Brederlow <goswin-v-b@web.de>]

On Fri, Jan 24, 2014 at 04:56:46PM -0000, Jon Harrop wrote:
> 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.

They should certainly be unboxed when in registers. So

let t = (23, 42.0) in

would basically become

let t_0 = 23 in   (* r0 *)
let t_1 = 42.0 in (* fpu0 *)

Unless the tuple escapes the scope (either up or down) it should never
be allocated.

But you can't just put a float 42.0 on the heap or even stack when the
GC might get called. That needs to be boxed in some way to avoid it
getting misread as pointer.
 
> 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?

Or compile code poly-monomorphic. Meaning for a function
taking/returning a tuple compile 2 (or more) flavours. One that
allocates the tuple and one that passes the tuple in registers.

Obviously higher level function would need a lot of flavours to cover
all combinations. And closure would need multiple flavours too. But
when there are too many cases, or when it is undecidable, the compiler
can simply use the base case of allocaating everything like it does
now. But all of this would be done static at compile time.
 
> 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?

There are never multiple return values. You can only return tuples.

let f x y z = (x, y, z)
let (x,y,z) = f 1 2 3

It would be nice not to allocate that tuple. Does ocaml allocate it?
Or does inlining optimize the tuple away?

> 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.

MfG
	Goswin