[LLVMdev] More Garbage Collection Questions

[Talin]

Gordon Henriksen wrote:
> On 2007-09-15, at 23:55, Talin wrote:
>
>> Gordon Henriksen wrote:
>>
>>> Can you be more specific the algorithm for which you need type 
>>> metadata in a write barrier? No algorithms I am aware of perform any 
>>> tracing from a write barrier.
>>
>> This one does:
>>
>> http://citeseer.ist.psu.edu/cache/papers/cs2/442/http:zSzzSzwww.cs.technion.ac.ilzSz~erezzSzPaperszSzms-sliding-views.pdf/an-on-the-fly.pdf 
>>
>>
>>> Write barriers are commonly used to record references from 
>>> old-generation objects to new-generation ones, either by recording 
>>> the referencing object, the referencing field, or using a card 
>>> table. For these purposes, the addresses are sufficient.
>>
>> In the paper cited above, the write barrier checks to see if the 
>> object being mutated has been traced; If it hasn't, then it records 
>> the values of all pointers contained in the object into a buffer - 
>> for which you need the location of the pointers.
>
> Okay. If you're implementing this algorithm with a tagless collector, 
> we may need to extend the intrinsics.
More accurately, what I am trying to do is not only create a collector, 
but also create a framework for implementing different collector 
algorithms. I don't intend to be the person that creates the 
best/fastest collector, I just want to create something that people can 
build on.

There are a lot of algorithms out there that require similar underlying 
data structures - an efficient heap, lock-free work queues, and so on. I 
figure if I can provide those along with a working example, it may help 
to stimulate further development.

I chose this particular algorithm to start with because it seemed fairly 
easy to implement.

Eventually I want to do a multi-generation design - most of the research 
papers out there seem to settle on a per-thread copying collector for 
young generations, and a heap-based mark and sweep for older 
generations. However,  tracking references to young generation objects 
belonging to a different thread is quite involved, and I wanted to start 
off with something less challenging.

One thing I am missing is a way to test this in an LLVM context. Right 
now all my tests are just unit tests. I'd like to do a full integration 
test - to be able to actually write LLVM programs that work with my heap 
- but I don't want to have to write a whole language compiler to do it.

-- Talin