On Monday 21 April 2008 12:25:53 Patrick R. Michaud wrote: > To me, the scary part of src/stacks.c is at the beginning: > > The stack is stored as a linked list of chunks (C<Stack_Chunk>), > where each chunk has room for one entry. > > Eek! For something like bsr_ic, which is really just pushing a > return address (i.e., opcode_t *) onto a stack, we're allocating a > new GC-able object for every bsr invocation, and freeing it on ret. > Since PGE uses bsr/ret for its backtracking, that's a lot of allocations. > > In fact, this seems to be the case for everything using the > "generic stack", which AFAICT is the &interp->dynamic_env structure. > So, everything that gets pushed onto this stack (exceptions, > continuations, coroutines, bsr/ret calls) ends up with a separate > gc-able structure (Stack_Chunk) to hold the stack entry. > So, switching PGE from bsr/ret to another control structure doesn't > give us a win here. > > I think we'd get a BIG win if we changed the dynamic_env stack to > have an approach similar to ResizableIntegerArray, where we allocate > arrays of Stack_Chunk entries and manage them that way, instead of > a separate allocation per element in the stack.
That sounds reasonable. For now, I've taken a hint from the paper on how all garbage collectors are hybrids and added a reference count to Stack_Chunk_t elements in stack_push and a stack_pop. If the reference count is zero at the end of the latter, it's safe to recycle the Stack_Chunk_t back to its free list immediately. r27081 produces an 11.73% improvement in the benchmark. The Perl 6 tests run in 12 seconds for me now, with an optimized Parrot. -- c
