From: Godmar Back (gback@cs.utah.edu)
Date: Wed Jan 06 1999 - 19:44:05 EST
I had a discussion with Jason today about how kaffe's current gc compares
to Boehm's. Also, I talked with Matthew Flatt about how Boehm's gc compares
to a compacting gc in his experience. He reported that a 2x speedup from using
a compacting is not unheard of (in the scheme world)
I feel we should plunge ahead with the current homebrew.
Basically, the message I took away from it is that
+ we should be on par as far as pointer identification speed goes.
+ we should be on par as far as primitive list mngt. goes.
+ we need to work on list and state mgnt.
For instance, instead of using doubly linked lists, which are expensive and
unnecessary, Boehm uses simple bitmaps to keep track of the state of
each object. When marking the heap, instead of keeping grey objects
on a list, they're simply stored in a mark stack - a stack data structure,
basically a linear array that's dynamically resized. The memory cost
is only 4 bytes per grey object, a lot less than 8 bytes per allocated
object.
Jason might look at speeding some of these things up. This should also
reduce the object overhead for non-finalizable objects by getting rid of
the 8 byte header. Finalizable objects will probably still be kept on
a list. This means that we should look at finalization as something
expensive that we must avoid whenever possible (as my recent improvements
for strings have dramatically shown.)
Jason also mentioned another possible strategy that apparently was
implemented in an earlier version of kaffe, but was later scrapped (why?).
This strategy would include to keep gc_blocks on the white/grey and
black lists if any of its objects are on the white/grey or black lists.
(A block can be on multiple lists here.)
This approach would mean that the sweeping costs would be proportional
to the number of objects swept, and not proportional to the size
of the heap like it would if you only used bitmaps.
+ I'll come up with a better gc interface that moves all the VM specific
crap out of mem and allows for independent gc testing.
Anyway, stay tuned for more.
- Godmar
This archive was generated by hypermail 2b29 : Sat Sep 23 2000 - 19:57:30 EDT