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.> In concurrent collectors—by which I mean those that run > asynchronously of the mutator—write barriers may be used to mark the > written object pointer. Even byte arrays as you describe require an > object header in which to store mark bits, else the collector cannot > know whether the object has been marked (mark-sweep collectors) or > copied (copying collectors). >In my design, the mark bits are maintained by the allocator as part of the allocation header of each memory block. In other words, I'm trying to maintain a strict separation between the allocator/collector and the actual objects stored in the heap. The allocator/collector "owns" all of the bits that are before the start address of the object, while the language-specific type system owns all of the bits after the start address. As a result the collector isn't tied to a specific language. -- Talin
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.>> In concurrent collectors—by which I mean those that run >> asynchronously of the mutator—write barriers may be used to mark >> the written object pointer. Even byte arrays as you describe >> require an object header in which to store mark bits, else the >> collector cannot know whether the object has been marked (mark- >> sweep collectors) or copied (copying collectors). > > In my design, the mark bits are maintained by the allocator as part > of the allocation header of each memory block. > > In other words, I'm trying to maintain a strict separation between > the allocator/collector and the actual objects stored in the heap. > The allocator/collector "owns" all of the bits that are before the > start address of the object, while the language-specific type > system owns all of the bits after the start address. As a result > the collector isn't tied to a specific language.Sure. So by design, type metadata is never necessary to access the mark bits. — Gordon -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20070916/6a38e052/attachment.html>
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