Re: Fat references

Jon Harrop <>
Mon, 04 Jan 2010 03:12:15 +0000

          From comp.compilers

Related articles
[14 earlier articles]
Re: Fat references (Robert A Duff) (2010-01-02)
Re: Fat references (Jon Harrop) (2010-01-03)
Re: Fat references (Hans-Peter Diettrich) (2010-01-03)
Re: Fat references (Ray) (2010-01-03)
Re: Fat references (2010-01-03)
Re: Fat references (glen herrmannsfeldt) (2010-01-03)
Re: Fat references (Jon Harrop) (2010-01-04)
Re: Fat references (Kaz Kylheku) (2010-01-04)
Re: Fat references (BGB / cr88192) (2010-01-03)
Re: Fat references (Robert A Duff) (2010-01-04)
Re: Fat references (2010-01-04)
Re: Fat references (Kaz Kylheku) (2010-01-04)
Re: Fat references (Jon Harrop) (2010-01-05)
[8 later articles]
| List of all articles for this month |

From: Jon Harrop <>
Newsgroups: comp.compilers
Date: Mon, 04 Jan 2010 03:12:15 +0000
Organization: Flying Frog Consultancy Ltd.
References: 09-12-045 09-12-050 09-12-056 10-01-010
Keywords: storage, GC
Posted-Date: 04 Jan 2010 11:21:53 EST

Robert A Duff wrote:
> Jon Harrop <> writes:
>> Robert A Duff wrote:
>>> Are you saying all pointers are fat (4
>>> words per pointer!?)? Or just pointers to arrays?
>> Yes, all pointers. Every single reference in the heap now occupies a
>> quadword. I even blindly load and store entire quadwords when reading and
>> writing references.
> For pointer-heavy data structures, I'd be concerned about using
> fat pointers all over -- damages cache behavior by making
> everything bigger.

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.

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. 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.

>>> Under what circumstances are you worried about an extra copy?
>> Extra copy of what?
> In your original message, you said, "...because that would require C
> arrays to be copied just to add this header." I was asking what
> you mean. I guess you mean C code passes you an address,
> and an array length, or something like that, and you want to avoid
> putting your meta-data before the array data, because then you'd
> have to copy that data.

I see. Yes, that is exactly what I meant.

>>> By the way, if you're interested in GC, you should join the
>>> GC list, which our esteemed moderator set up some years ago.
>> I'd love to. Where is it?
> I was hoping our esteemed moderator would point to it.
> I don't have it handy, hmm.... let's see, google points
> me here:
> It's pretty low traffic these days.

I've subscribed.

>> HLVM has another unusual characteristic in that it defines a high-level
>> language (e.g. with tuples and tail call elimination) that is not only
>> the target language but also the language the GC is written in.
> Interesting.

I just made HLVM multicore friendly (the GC allows threads to run in
parallel) and I'm thinking that it has huge potential...

Dr Jon D Harrop, Flying Frog Consultancy Ltd.

Post a followup to this message

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