[gclist] Fast-allocating non-copying GC's

[Geert Bosch]

Hans Boehm wrote:
`` I strongly recommend against 
   assuming a fixed page size. ''

Of course I'll try to keep the code as generic as possible, but due
to time constraints it won't be possible to make some assumptions
about the target system. It will be fairly easy to change to 8 kB
pages, but some tables might need to get changed and things like that.
In any case I won't be able to do any testing on other platforms than
the one I described. 

``  You probably eventually want to use some black listing 
    and stack cleaning mechanism to avoid scanning bogus 
    and dead pointers. ''

Those areas can be put in a 'pointer-free' storage pool. When
the application starts, the memory map is scanned and any memory
blocks containing static data, program-code, stacks etc. are 
converted into storage pools. The type of storage-pool determines
the type of data. For static data this will either be pools of
the main pool type (containing only objects that occupy an integer
number of contigious VM pages) or the pointer-free variant of this
pool-type. 

`` - The allocation strategy for the main storage pool matters.  You want
   something that behaves a lot like best fit. ''

What would be the reason for this? Actually I though of using 
first-fit. I wouldn't expect problems with fragmentation of 
virtual memory, since unused VM pages can be released and the
total VM range is normally rather large. 

On the other hand, I don't see any drawbacks to best-fit in this
case and it might prevent problems with applications allocating
many large memory blocks.

`` - How do you handle running out of memory?  
     This typically effects the way you design the 
     marker in fairly profound ways. ''

I'd think by raising an exception if after GC there still 
isn't enough free memory. I'm not actually what memory
you mean though. Having a fragmented memory-map would be
a different problem than having full RAM and page-file.
Many OS-es using VM already behave very badly when running 
out of memory and I wouldn't know how to prevent this at 
the application level. 

`` Which incremental GC algorithm do you use? ''

The assumption I use is that all data which is garbage
at some time T, will be garbage at any time T + X. 
So, at the start of the GC an imaginary snapshot of the 
complete state of the application is made. The snapshot 
is made as follows: first all threads are blocked and 
their context (eg CPU-registers) is saved. Then all 
writable memory (including any stacks) is put behind 
a write-barrier. At last the threads are unblocked and 
the GC starts.

`` How may page faults do you have to handle?  
   Are they likely to occur in rapid succession? ''

I wouldn't know. The point is that I can't do everything at the
same time and first having a working allocator for a single-tasking
environment is my priority. 

`` Some operating systems don't let you recover gracefully 
   from page faults in system calls.  Can you deal with that 
   (or punt) gracefully? ''

No, I'm sorry ;-) One of my assumptions as listed in my original
posting is that an efficient write-barrier implementation has to
be possible on any systems that allow multi-threading.

`` Do you detect and recycle completely empty pools? ''

Yes, but I don't know yet what's the most efficient 
approach to do that. Probably there should be a low-priority
thread doing things like that. When fragmentation gets high,
the priority of that thread might be raised. 

For now, I'm only implementing the allocator part.

`` Does the collector run concurrently with the mutator 
   in its own thread, or does it run incrementally in 
   the mutator thread?  In my experience, the latter
   is more robust, but less pleasant to program. ''

In principle, after the memory snapshot has been made, the
collection takes place in a seperate thread, but in practice
I think there will be many page-faults from the mutator, so
in practise most of the scanning and marking will be done 
executing in the mutator thread.

   Geert