I think I know of two potential performance problems with the GC code.
They could be problems in my head, or real problems, as I haven't done any
profiling. We also don't have any real test cases. :)
The first example is the following code, which calls parrot_allocate to
create the string each time.
for(1..10000) {
push @a, "a";
}
If we start out with no room, it calls Parrot_go_collect for each push,
but the go_collect does nothing because there's no free memory. This then
requires another allocation, fit exactly to the size of the block, one
character.
Repeat.
Since we're never freeing any memory, it continually is allocating a block
of size 56 (memory pool) + 1 (character) from the underlying system api.
The second example involves headers. Say we have the following code:
loop:
new P0, PerlString
branch loop
Which might correspond to:
while(1) {
my $dummy;
}
Each time through the array, it has to alloc a PMC header. When we
allocate the header, we store it into P0, and the old header is
essentially freed.
The next time through the loop, entries_in_pool is 0, and it triggers
alloc_more_string_Headers, and a dod run. This finds the PMC we just
freed, and uses it. Repeat. Each time through the loop, it triggers a dod
run.
The above example might be a bit contrived, due to the fact that it could
pull 'my $dummy' outside of the loop, assuming it isn't tied. (If it is
tied, we need to do it each time through, since it could be counting the
number of times we set the variable, or somesuch.)
Now, I know that any memory management system can have cases which cause
worst-case behavior. I'm not sure if the cases I presented are those kind
of cases, or whether they are common enough that we need to worry about
it.
The first problem can probably be solved by enforcing a minimum block
allocation size. I'm not sure of a good solution to the second problem,
however.
If we do have a minimum block allocation size, it will perform horribly
memory-wise on something like:
while (1) {
push @a, "a";
push @a, "aaaaaa"x200;
}
This example destroys any implementation that has a minimum block
allocation size. This could be alleviated with a linked list of blocks
that have available memory at the tail of the block. This could give very
bad performance whenever we have lots of half-filled blocks. (Say, when we
continually allocate blocks of size 0.51*minimum_block_allocation_size.)
I recall Dan saying he didn't like traversing linked lists when searching
for memory, but it shouldn't be that bad since it all gets cleaned up on a
call to parrot_go_collect.
Finally, another approach is to randomize things. Lots of algorithms
randomize their behavior to prevent test cases that exhibit worst-case
behavior. Of course, I'm not sure if a non-deterministic interpreter is a
good thing, since it'll just make GC bugs that much more annoying to track
down.
These might all be things that were considered, and discarded as not
important enough. But I didn't see these potential problems mentioned
anywhere, so I figured I'd bring them up here, just in case.
Mike Lambert
