How to schedule collection cycles for custom mark-sweep collector?

Question

I've written a simple garbage collector for a Postscript virtual machine, and I'm having difficulty designing a decent set of rules for when to do a collection (when the free list is too short?) and when to allocate new space (when there's a lot of space to use?).

I've written bottom-up so far, but this question involves top-level design. So I feel I'm on shaky ground. All objects are managed and access is only through operator functions, so this is a collector in C, not for C.

The primary allocator function is called gballoc:

unsigned gballoc(mfile *mem, unsigned sz) {
    unsigned z = adrent(mem, FREE);
    unsigned e;
    memcpy(&e, mem->base+z, sizeof(e));
    while (e) {
        if (szent(mem,e) >= sz) {
            memcpy(mem->base+z, mem->base+adrent(mem,e), sizeof(unsigned));
            return e;
        }
        z = adrent(mem,e);
        memcpy(&e, mem->base+z, sizeof(e));
    }
    return mtalloc(mem, 0, sz);
}

I'm sure it's gibberish without knowing what all the types and functions mean, so here's pseudocode of the same function:

gballoc
    load free list head into ptr
    while ptr is not NULL
        if free element size is large enough
            return element, removed from list
        next ptr
    fallback to allocating new space

So it's a simple "first-fit" algorithm with no carving (but allocations retain their size; so a large space reused for a small object can be reused for a large object again, later).

But when should I call collect()?

Edit: The rest of the code and related modules have been posted in comp.lang.postscript, in the thread: http://groups.google.com/group/comp.lang.postscript/browse_thread/thread/56c1734709ee33f1#

Answer 1

There are several applicable philosophies:

• Do garbage collection as last-ditch avoidance of expanding the heap during an allocation. This is probably the most common strategy.
• Do garbage collection periodically, like every hundredth allocation or deallocation. In some situations, this might decrease the overall effort of garbage collection by not letting fragmentation get out of hand.
• Don't do any garbage collection. Always a possible strategy, especially for short-lived or simple programs.

As a developer of garbage collection, it might be desirable to give the choice of strategy to the application since it might know which will be most effective. Of course, if it doesn't have a preference, you should choose a default.

Answer 2

Here is the periodic collection strategy incorporated into the original code:

enum { PERIOD = 10 };

unsigned gballoc(mfile *mem, unsigned sz) {
    unsigned z = adrent(mem, FREE);
    unsigned e;
    static period = PERIOD;
    memcpy(&e, mem->base+z, sizeof(e));
try_again:
    while (e) {
        if (szent(mem,e) >= sz) {
            memcpy(mem->base+z, mem->base+adrent(mem,e), sizeof(unsigned));
            return e;
        }
        z = adrent(mem,e);
        memcpy(&e, mem->base+z, sizeof(e));
    }
    if (--period == 0) {
        period = PERIOD;
        collect(mem, 0);
        goto try_again;
    }
    return mtalloc(mem, 0, sz);
}