Re: Fat references

On 2010-01-04, Robert A Duff <bobduff@shell01.TheWorld.com> wrote:
> 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.


It seems these null pointers could be elided by using a different tree
node variant for leaf nodes, which simply has no pointers.


I.e. a tree is defined recursively as:


    - an empty tree, denoted by a null value
    - a leaf node record containing only a key and value
    - an inner node containing a key, value and two children that are trees.


A ``half inner'' node (a node with one null child pointer) still has
two pointers, but these could get a dedicated representation also, for
both the left and right leaning variants. Though it deserves to be
noted that in a maximally balanced tree of any size, there is at most
one of these nodes, whereas more than half of the nodes are leaves.


If you have fat pointers you already have a type field in the pointer,
which indicates the node variant, so that the node need not have a
type field for this. It almost seems silly not to take advantage in
this way, given that these fat pointers are carrying a word-wide type
field.


Without fat pointers, this same compression can still be done with spare bits
in a regular pointer.

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