[gclist] Compiler specialized GC's

[Dave Lloyd]

> 1. How efficient is the table interpreter?  You shouldn't need more than 

This was written in as good C as I could manage, but the PC compiler I used 
was not too hot about its code generation. The 5-fold improvement was the 
improvement I saw then. Actually one of the hot spots I find is simply in 
marking the bits in the heapmap - that and scanning the thing for holes can
easily dominate in a collection.

> 2. Do you need to dynamically look up object types?  If your language has
> implementation inheritance or some "void *" equivalent presumably the answer

Yes but they're rare. Even so, there is a statically known type behind them (we
record that tag with the value in contrast to C's void *), so it is a single 
table lookup to mark a value of ANYMODE.

> 3. Is your marker recursive, or does it use an explicit stack?  I would argue

Recursive is faster - certainly on x86 or T8/9 where it is not easy to add 
another stack.  Tail recursion elimination helps reduce the depth and I trust 
to the code-generator to keep each frame as small as necessary (which it mostly 
does).  But you're right that it is time that I should use an explicit stack or 
otherwise handle the stack exhaustion - which currently causes a bomb.  

Whilst it is vital to have an efficient garbage collection mechanism, I have 
found that there are far better ways to improve performance than fine-tune the 
GC:

(1) Reduce the calls to the heap (obvious, but very worth the effort, 
particularly inner procedure temporaries).

(2) Reduce the likelihood of a request for a large block - even with the 
efforts to reduce fragmentation discussed, I find the most common reason to 
extend the heap is the allocation request for a largish block.  This usually 
requires programmer cooperation.  

(3) Only trace recent pointers - for our compiler, most of the tracing at each 
GC is through all the tables and trees with a relatively long lifetime.  I 
intend to move to a generational scheme when I am happy to relocate all 
pointers.  

----------------------------------------------------------------------
Dave Lloyd                            Email: Dave@occl-cam.demon.co.uk
Oxford and Cambridge Compilers Ltd    Phone: (44) 1223 572074
55 Brampton Rd, Cambridge CB1 3HJ, UK