Re: Fat references

Jon Harrop <jon@ffconsultancy.com> writes:


> Locality is different but not necessarily worse. For example,
> computing the number of elements in a hash table represented as a
> spine array of bucket arrays requires you to sum the lengths of the
> bucket arrays. In HLVM's representation, those are stored in the spine
> so you'll get 4 lengths per 64-byte cache line rather than only 1 =>
> locality can be better with HLVM.


OK.


> Memory consumption is only increased for duplicated references
> (i.e. when two or more references in the heap point to the same value)
> but I believe that is comparatively rare.


That's a good point.


But don't forget to count 'null' pointers. For example, consider
a balanced binary tree of depth 3. You've got 7 nodes and
7 non-null pointers to them (one from outside the tree).
But you've also got 8 null pointers stored in the leaf
nodes. As I understand it, those 8 null pointers are
going to be 4 words each, in HLVM.


You can think of 'null' as being a pointer to a single
dummy object -- and there are typically lots of duplicates!


If you're talking about something like OCaml, you don't
have null (which is a Good Thing!) but you have the
equivalent issue.


Also, why you do say "in the heap" above? I'd say "Memory consumption
is only increased for duplicated references (i.e. when two or more
references point to the same value)." Doesn't matter whether those
pointers are in the heap, or on the stack (or in a register -- four
registers! -- for that matter).


Anyway, if you've got good measurements, they trump my
speculation.


>...Indeed, a lot of literature on reference counting says that this
> is so and, hence, 1-bit reference counts that saturate can still be
> useful.


Yes, I've read that. There are lots of GC schemes that take
advantage of that.


- Bob

Return to the comp.compilers page.
Search the comp.compilers archives again.