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

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

On Mon, Jan 27, 2014 at 11:18:23AM -0500, Yotam Barnoy wrote:
> >
> > 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.
> >
> >
> It wouldn't be too hard to add a word of metadata to the stack to tell the
> GC what's a pointer and what isn't. Haskell does this for function calls
> (in fact, if the metadata doesn't fit in a word, it allocates a separate
> metadata structure), and F# has this from the .NET runtime which has full
> type metadata for everything.

You can do that. It's called BOXING.

Even if you create just a single box for the whole stackframe of the
function it is still a box.

See the other thread about changing the in memory represenation of
ocaml for how to improve having boxed with mixed content so
int32/int64/float don't need extra boxing on their own.
 
> Problem is that a value is a fixed size and fits in a register. A
> > tuple does not. (int * float) even takes the space of 3 values on
> > 32bit. You can unbox that in the optimizer for local use but in memory
> > and in function calls you need to pass this as box. Otherwise
> > polymorphic functions break.
> >
> > Putting larger structures into an array without boxing also only works
> > for immutable objects and by copying them every time they are passed
> > around. You can't copy a mutable and you can't pass a pointer to the
> > middle of an array to another function or the GC might freak out.
> >
> 
> Leaving it to the optimizer is problematic because it might cause a lot of
> unneeded boxing and unboxing.
> Haskell has the {- #UNPACK -} pragma to unbox types. You have to be really
> careful in haskell with this, because you're also changing the evaluation
> semantics to be strict. This makes for really ugly optimized haskell code,
> but maybe we can do something similar (but not as ugly). F# inherits .NET's
> struct types, which are similarly limited, but also useful. Of course, once
> you unbox, all parametric polymorphism is lost, but because you have
> control over it, you can decide where it's worthwhile.
> 
> An example of unpack usage in haskell:
> 
> data T = T {-# UNPACK #-} !(Int,Int)
> 
> which would be equivalent to something like
> type t = (int * int) [@u]
> 
> Note that the whole tuple is unboxed.
> 
> In haskell, you can now do
> 
> f :: T -> Int
> f (T(i1,i2)) = i1 + i2
> 
> and in ocaml you'd do
> 
> let f : t -> int = fun (i1,i2) = i1 + i2
> 
> Of course, this would require more metadata for the stack. For the heap,
> you'd probably want to just use a new tag or the custom tag. For ocaml
> you'd also probably have to stipulate that polymorphic marshalling cannot
> be performed on this type, and neither can polymorphic comparison -- you'd
> have to have specific marshalling/comparison functions, which aren't too
> difficult to generate automatically.
> 
> -Yotam

Consider this:

type ['a] tt = ('a * 'a) [@u]
let ff : 'a tt -> ('a -> int) -> int = fun (t1, t2) f = f t2
let x = ff ((1, 2), (3, 4)) f

The ff function is tail recursive so f is called with the arguments of
ff no longer registered with the GC. And f is passed a pointer to the
middle of the tt type. Now lets assume the GC will run inside f.

*BOOM*

The tt type is no longer reachable so it would be freed. f has a
pointer pointing to the middle of a block causing the GC to parse the
t1 part of tt type as metadata.

Overall verry bad. Boxed and UNPACKed types would have to be
incompatible in ocaml.

MfG
	Goswin