Prevalence of duplicate references in the heap

Prevalence of duplicate references in the heap

[Jon Harrop]

I took an odd design decision with HLVM and made references a struct of 
run-time type, metadata (e.g. array length), pointer to mark state and 
pointer to data. So every reference consumes 4x32=128 bits rather than the 
usual 32 bits but heap-allocated values no longer require a header.

My performance results really surprised me. For example, the "gc" benchmark in 
the HLVM test suite fills a hash table that is represented by an array spine 
containing references to array buckets. Despite having (fat) references 
everywhere, HLVM is 2.2x faster than OCaml on x86.

The main disadvantage of HLVM's approach is probably that every duplicate 
reference now duplicates the header information, wasting 96 bits. However, I 
do not believe references are duplicated in the heap very often. Both trees 
and hash tables contain many references but none are duplicated.

So I'm wondering if anyone has studied the makeup of heaps in idiomatic OCaml 
code and could point me to data on the proportion of the heap typically 
consumed by duplicate references, i.e. how much space is HLVM likely to 
waste?

Many thanks,
-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e