On Fri, Dec 4, 2009 at 5:52 AM, Allison Randal <[email protected]> wrote: > I've wondered for a long time if we're using an incredibly stupid > tree-traversal algorithm during the mark phase. But, to look at the problem > more abstractly, any tree-traversal algorithm is going to have a cost > relative to n, where n is the number of elements in the tree. No matter what > traversal algorithm we use, the biggest gain will be reducing the number of > elements we traverse in a mark. Which means: > > A) Create a short-lived object pool that's marked/swept frequently, and only > use it for call signatures, contexts, etc. We can do this right now without > implementing full generational GC using the same strategy we use for > constant PMCs: call a separate function pmc_new_adonis that allocates from > the "fast dying pool". We can also use a function pmc_new_methuselah for > objects we know are created at interpreter startup that will live until > interpreter death (there's no reason to run GC on those during operation at > all). Like constants, we require that all children of adonis or methuselah > PMCs must be allocated from the same pool(s). Splitting off adonis and > methuselah PMC pools will mean far fewer mark runs on the ordinary GC pools. > (Names chosen for illustration purposes.)
So you're thinking like a generational scheme but with the ability to explicitly declare which generation to use when we allocate an object? I think we're going to want at least three explicit groups: Items that are rapidly recycled, items that are stable but mortal, and items which are absolutely immortal. On top of that, we're going to want just a normal allocation where we don't know the lifespan ahead of time and all the system to migrate the items depending on how many mark phases they survive. I'm also becoming very enamored with the idea of allowing stack-based allocations for items that have very finite lifespans (think about where we use constant_pmc_new now). Some macros to allocate simple, short-lived PMCs and their attributes on the stack would take off a lot of GC pressure in these cases. We wouldn't even need to call VTABLE_destroy in most cases. I suspect that a relatively large number of PMC allocations could be transformed in this way for a major performance savings. > B) Create fewer PMCs: Merge CallSignature/Context/RetContinuation/etc. Avoid > boxing until absolutely necessary (chromatic's changes to make CallSignature > a typed array should have taken care of that for positional arguments, but > we still need typed storage for named arguments). Explicitly merging PMCs is a good idea, but I also am liking the idea of implicitly merging them into "super objects". If we can take a PMC and lump it together into a memory block with the complete tree of all it's delegate PMCs and STRINGs, we could get away with only marking the block as a whole (not all the individual parts). Barring the ability to store the complete tree in one place, we could store groups of related PMCs together along with an array of escape pointers. The mark process would be simplified to marking the block as a whole and the array of escape pointers only. This idea is similar to generations and inter-generational pointer lists, but uses locality to group items together that are used together, instead of grouping by the number of mark phases survived (which will tend to have the same result for stable groups, but with worse performance). --Andrew Whitworth _______________________________________________ http://lists.parrot.org/mailman/listinfo/parrot-dev
