Re: [Caml-list] Proposal: re-design of ocaml headers

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

On Fri, Oct 11, 2013 at 11:48:52AM -0400, Yotam Barnoy wrote:
> I had an idea based on (or actually copied from) something Goswin mentioned
> earlier in our discussion. What if the bits can be used to indicate
> embedded values? An embedded value would have a header inside the body of
> the parent value, making it possible to get rid of all pointers within that
> parent. This would represent a potentially large saving for the GC, as well
> as reducing random jumps around memory which are very cache-stressing.

Embedded values would be something like this:

type p2 = { x : int; y : int; }
type p3 = { xy : embedded p2; z : int; }

The type p3 would still be a single block and p3.xy.x would not need
an extra indirection.

Right?


I'm not sure this would be too usefull overall. In the above example
it would be far better to have a row type like in objects. Something
like

type p3 = { p2 with z : int; }

That would even allow using p3.x instead of p3.xy.x.

It would also allow passing a p3 record to a function expecting a p2
record. With embedded types that would not be possible. An embedded
type would have to be passed to other functions as pointer to the
begining of the parent and offset within.


Another thing is, as recently mentioned, that the compiler aparently
aggregates allocations. So if you write

let p2 = { x = 1; y = 2; } in
let p3 = { xy = p2; z = 3; } in

that results in a single allocation and p2 and p3 will be cache local.
I think they will even stay next to each other during compression.
Right?

Embedding would get rid of the xy pointer and indirection but would it
help so much? Would it be used widely?

Given that embedded and not embedded types are incompatible I think
this would rather be limited to stay within modules and never cross
the module boundary. For example an internal hashtable would make use
of it. And why have extra headers for the embedded values? Incorporate
them into the main header directly and make

type p3 = { xy : embedded p2; z : int; }

equivalent to

type p3 = { xy.x : int; xy.y: int; z : int; }

A block containing 3 values. Embedding extra headers would only be
usefull when embedding largish float arrays (which don't need a bit
for every member) into large records. And then why not use the
indifection? Given then size it probably will be negible. And for
small structures use the individual bits to mark every float member
independently.

So overally I'm doubtfull the added complexity to recurse into
embedded headers is worth it.

MfG
	Goswin