[LLVMdev] Stack roots and function parameters[MESSAGE NOT SCANNED]

Mark Shannon marks at dcs.gla.ac.uk
Wed Sep 22 11:08:25 PDT 2010


Talin wrote:

[snip]

> 
> Here's another way to think about the issue: Compare this whole approach 
> to stack roots to that of a conservative collector. Since we know 
> conservative collectors work, the whole reason for making an accurate 
> collector in the first place is efficiency, right? If we couldn't make 
> an accurate collector that was more efficient than a conservative 
> collector, then no one would bother because it's such a pain.
> 

One very important to use precise GC is to have a copying collector.
For generational GC, a copying collector is faster and makes the 
allocator much simpler and faster.

> However, looking strictly at stack frames, a conservative collector has 
> a much more compact stack layout. There's no need to copy anything to 
> local variables, because by the time you call into the collector proper, 
> everything - every register variable, every function parameter, and so 
> on - is already on the stack *somewhere*.

The typical stack is *tiny* compared with the typical heap.
Its pretty small compared with the nursery, so even for minor 
collections it won't matter.

> 
> The stack frame layout dictated by llvm.gcroot, by contrast, is much, 
> much fatter. In a typical deeply-nested call stack, there will be many 
> copies of the same value on the stack. Let's take the 'this' pointer as 
> an example. Say we have some method that calls itself recursively, and 
> we are currently 10 levels deep. That means that we have 20 copies of 
> the 'this' pointer on the stack: Because each invocation of the method 
> has to push the 'this' pointer on the stack as part of the calling 
> protocol (even if it's passed in registers, it still has to save the 
> prior value of the register somewhere), and in addition we also have to 
> save the 'this' pointer as a stack root. A conservative collector, on 
> the other hand, would be able to get by with only 10 copies of the 
> 'this' pointer.

If you're really worried about the extra roots, you could do liveness 
analysis. If its not live across a GC-safe point, then its not a root.
In fact, liveness analysis is important anyway. Retaining a dead object
will hurt your performance much more than tracing a live one twice.

> 
> As far as the issue of eliminating redundant stores, I'm pretty sure 
> that the optimizers cannot eliminate redundant /roots/. Figuring out the 
> minimal set of temporary roots needed for a function call is a 
> non-trivial problem (you don't want to just blindly make every pointer 
> argument to a function a temporary root, since that just bloats the size 
> of the call frame needlessly.)
> 
> My entire goal here is to get a GC that has high performance and 
> efficiency. I want my GC to be able to run on everything from a data 
> center to a beagle board, and use the minimum resources possible.
> 

You might want to have a look at my GC(s), its probably too
entangled with the rest of the toolkit to be useful directly,
but it might be of interest.

http://code.google.com/p/gvmt/

> -- 
> -- Talin
> 

Cheers,
Mark





More information about the llvm-dev mailing list