On 17/09/10 09:55, Pedro Ferreira wrote:> As I understand it, LLVM simply gives you support for garbage collectors > that you have to implement yourself and link into the final binary, > similar to what C's malloc does (it's a library call). The issue with > GC's is that they need to be provided info about the stack, thats where > LLVM's support comes in.Are there any standalone accurate garbage collectors that I could use in my project, rather than having to write me own (or use libgc, which is what I'm doing now)? Garbage collectors are subtle and very tricky and I really don't want to have to do one myself, as I know I'll just get it wrong. -- ┌─── dg@cowlark.com ───── http://www.cowlark.com ───── │ │ life←{ ↑1 ⍵∨.^3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵ } │ --- Conway's Game Of Life, in one line of APL -------------- next part -------------- A non-text attachment was scrubbed... Name: signature.asc Type: application/pgp-signature Size: 262 bytes Desc: OpenPGP digital signature URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20100917/3ab035fa/attachment.sig>
I don't know of any precise and efficient GC that you can take as-is, you often need to specialize them by, eg, providing an object model, multi-threading interface. In VMKit, I use MMTk (http://jikesrvm.org/MMTk), which is "unfortunately" written in Java. However I am able to generate a .so file out of it that can link with C code. So if you are prepared to play with vmkit's Java ahead of time compiler, and to understand MMTk's interface to object model and multi-threading, using MMTk might be a solution for you. Cheers, Nicolas On Fri, Sep 17, 2010 at 1:16 PM, David Given <dg at cowlark.com> wrote:> On 17/09/10 09:55, Pedro Ferreira wrote: > > As I understand it, LLVM simply gives you support for garbage collectors > > that you have to implement yourself and link into the final binary, > > similar to what C's malloc does (it's a library call). The issue with > > GC's is that they need to be provided info about the stack, thats where > > LLVM's support comes in. > > Are there any standalone accurate garbage collectors that I could use in > my project, rather than having to write me own (or use libgc, which is > what I'm doing now)? Garbage collectors are subtle and very tricky and I > really don't want to have to do one myself, as I know I'll just get it > wrong. > > -- > ┌─── dg@cowlark.com ───── http://www.cowlark.com ───── > │ > │ life←{ ↑1 ⍵∨.^3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵ } > │ --- Conway's Game Of Life, in one line of APL > > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20100917/b853dd2c/attachment.html>
On Fri, 2010-09-17 at 12:16 +0100, David Given wrote:> On 17/09/10 09:55, Pedro Ferreira wrote: > > As I understand it, LLVM simply gives you support for garbage collectors > > that you have to implement yourself and link into the final binary, > > similar to what C's malloc does (it's a library call). The issue with > > GC's is that they need to be provided info about the stack, thats where > > LLVM's support comes in. > > Are there any standalone accurate garbage collectors that I could use in > my project, rather than having to write me own (or use libgc, which is > what I'm doing now)? Garbage collectors are subtle and very tricky and I > really don't want to have to do one myself, as I know I'll just get it > wrong. > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdevYou can try Hans Bohem Garbage collector. http://www.hpl.hp.com/personal/Hans_Boehm/gc/
> > > You can try Hans Bohem Garbage collector. > http://www.hpl.hp.com/personal/Hans_Boehm/gc/ > >This GC is not precise. Cheers, Nicolas -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20100917/d13d6d2a/attachment.html>
He said that he's already using it. Eugene On Fri, Sep 17, 2010 at 1:01 PM, Pedro Ferreira <pedro.ferreira at imgtec.com> wrote:> On Fri, 2010-09-17 at 12:16 +0100, David Given wrote: >> On 17/09/10 09:55, Pedro Ferreira wrote: >> > As I understand it, LLVM simply gives you support for garbage collectors >> > that you have to implement yourself and link into the final binary, >> > similar to what C's malloc does (it's a library call). The issue with >> > GC's is that they need to be provided info about the stack, thats where >> > LLVM's support comes in. >> >> Are there any standalone accurate garbage collectors that I could use in >> my project, rather than having to write me own (or use libgc, which is >> what I'm doing now)? Garbage collectors are subtle and very tricky and I >> really don't want to have to do one myself, as I know I'll just get it >> wrong. >> >> _______________________________________________ >> LLVM Developers mailing list >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > > You can try Hans Bohem Garbage collector. > http://www.hpl.hp.com/personal/Hans_Boehm/gc/ > > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >
David Given wrote:> Are there any standalone accurate garbage collectors that I could use in my > project, rather than having to write me own (or use libgc, which is what I'm > doing now)? Garbage collectors are subtle and very tricky and I really don't want > to have to do one myself, as I know I'll just get it wrong.On the contrary, writing your own GC is both easy and enlightening. You'll need: 1. Your own shadow stack: an array of pointers to blocks in the heap (those that are directly reachable). 2. The allocated blocks: another array of pointers to heap blocks (all those that have been allocated). 3. A visit stack: yet another array of pointers to heap blocks (those waiting to be marked). 4. The set of marked heap blocks. Maintain your own shadow stack by: 1. Pushing values upon a) allocation, b) reading references from the heap or c) obtaining references as the result of a function call. 2. Resetting your shadow stack pointer at all return points of all functions to the value it had upon entry to the function. At regular intervals, check if the heap size has exceeded its quota and, if so, run a GC cycle. To run a GC cycle: 1. Starting with an empty set of marked heap blocks, mark the global roots (global variables and everything on the shadow stack) and then keep marking heap blocks from the visit stack until it is empty. 2. Do a sliding compaction on the allocated list, calling free() on anything unmarked and copying the rest over the top of it in the allocated list. To mark a heap block: 1. Add it to the set of marked heap blocks. 2. Push any heap blocks that it references onto the visit stack. That's it. You can do this in ~100 lines of code. Cheers, Jon.
Am 16.12.2011 21:06, schrieb Jon Harrop:> At regular intervals, check if the heap size has exceeded its quota > and, if so, run a GC cycle.I have seen people recommend doing this kind of check whenever hitting a malloc call. I think it nicely scales with the level of heap activity for most programs.