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

[Geert Bosch]

Paul R. Wilson wrote:
`` You may want to use our GC. [...]
   You might also consider Hans Boehm's 
   collector, or Joel Bartlett's. ''

Although I should do my own homework, having a good look
at that code certainly wouldn't hurt. ;-)

You wrote about some possible ways to do (some) precise scanning
in a not-so-cooperative environment. I'll note them for the 
future, but I think I won't use them for now. The point is that 
I want to setup a basic frame-work for GC-aware allocators, which 
will be simple enough to implement and test relatively easy and 
which will be flexible enough to allow different kinds of 
allocators to be fit in.
The responses, ideas and suggestions I got thus far indicate that
the current scheme might actually accomplish this.

Paul Wilson wrote: 
`` The best allocators (fragmentation-wise) coalesce adjacent 
   free blocks into large blocks.  I think this can be done 
   without violating the constraints needed for interior pointers, 
   and fairly efficiently, but it's hairier. ''

Could you give some hints how to do such a thing? I wonder if
storing the free-list as some partially ordered tree-structure
might make it possible to collect large free regions, by reusing
isolated free spots first. I don't know however how this might
impact locality of reference. 

Paul wrote the following in response to my suggestion that 
FIFO memory reuse might help prevent fragmentation:

`` Also, it may have seriously weird locality consequences.  By mixing
   objects created during different phases, you may end up diluting
   your locality---when you need the old objects in memory, you have
   to bring in the young ones, and vice versa. ''

Agreed, but fragmentation can also have really bad locality 
consequenses, as in my worst-case example. This is one of the 
points that's really guessing for me. As you indicated the 
fragmentation problems might not be as bad as I had feared, so
locality issues are more important.

Leaves me with the following question:
`` How to reuse memory in an allocator 
   that groups objects by size? ''

I'll try to find some criterea:

  * Reuse most recently freed memory first
  * Try to cluster new allocations together
  * Try to keep large contiguous (sp?) areas of memory

Using these criterea the following might be a good solution 
for storage pools (read: VM pages) with small objects:

  * Use a per-pool bitmap indicating free spots
  * Put all pools of a certain type in a double-linked list,
    and promote it one step to the head when an object is freed.
    Or to prevent too much overhead: increment a counter and
    promote the pool when the counter has a certain treshold.
    The counter might be incremented more depending on the amount
    of free space on the page.
  * When allocating, pick a pool from the head of the list and
    search the bitmap for a short run of free objects. When 0
    means object free, and 1 means not free, then searching for
    a non-zero byte in the 'object-free' bitmap might be enough.
    This way a pool-type containing 4-byte objects could easily
    be converted to a pool-type containing 8, 12, 16, 20, 24, 28
    or 32-byte objects, for example. (The bitmap would need to be
    converted, but the new one would be smaller => no problem.)
    
It would be really nice if there would be a way to implement this,
without requiring the extra per-page meta-data. It must be possible 
to implement a comparable algorithm using only the free space (like
a linked list).