GC for pure functions -- implementation ideas

[Don]

I noticed a lively discussion in Bugzilla about the GC, with speculation 
about the impact of a precise GC on speed.
But it seems to me that a dedicated GC for pure functions has enormous 
unexplored potential, and might be relatively easy to implement.

LEAKY FUNCTIONS

Define a 'leaky' pure function as a pure function which can return
heap-allocated memory to the caller, ie, where the return value or a
parameter passed by reference has at least one pointer or reference
type. This can be determined simply by inspecting the signature. (Note
that the function does not need to be immutably pure).

The interesting thing is that heap allocation inside non-leaky pure
functions behaves like stack allocation. When you return from that
function, *all* those variables are unreachable, and can be discarded en 
masse. Here's an idea of how to exploit this.

THE PURE HEAP

Create a pure heap for each thread. This is a heap which can only be
used by pure functions. I present some simplistic code, with the
simplest possible implementation: just a big block of memory with a 
thread local 'stack pointer' which points to the first free slot.

static ubyte *heap; // initialized to big chunk of RAM.
static size_t stackptr = 0;
static size_t savedstackptr = 0;

For *non-leaky* pure functions: if any of the functions it calls are 
leaky, or if it makes any memory allocations, then call a HeapEnter 
function (in the druntime) at the start, and a HeapExit function at the 
end. Leaky pure functions don't get this prologue and epilogue code.
Non-leaky pure functions that don't do memory allocation are simply 
ignored. (Note that the compiler can determine if a function makes any 
memory allocations, simply by inspecting its body -- it isn't any more 
difficult than checking if it is nothrow).

void pureHeapEnter()
{
     cast(ubyte *)(heap + stackptr) = savedstackptr;
     savedstackptr = stackptr;
     stackptr += size_t.sizeof;
}

void pureHeapExit()
{
     stackptr = savedstackptr;  // instant GC!!
     savedstackptr = cast(ubyte *)(heap +stackptr);
}

The pureHeapExit function has the effect of instantly (and precisely!)
collecting all of the memory allocated in the non-leaky pure function 
and in every leaky function that it called.

In any pure function, leaky or non-leaky, when memory is allocated, call
pureMalloc instead of gcMalloc when allocating. (Non-leaky pure 
functions will of course always allocate on the pure heap.).

void *pureMalloc(int nbytes)
{
     if (!stackptr)
         return gcMalloc(nbytes); // we're leaky, do a normal malloc
     // we can use the pure heap
     auto r = heap + stackptr;
     stackptr += nbytes;
     return r;
}

REFINEMENTS
We can make this scheme more generally applicable. If there is a leaky 
return value which is cheap to copy, then we can pretend the function is 
non-leaky: at exit, if we were called with stackptr == 0, then we copy 
(deepdup) the return value to the gc heap, before calling pureHeapExit. 
If stackptr was non-zero, we don't need to copy it.

COMPLICATIONS
Classes with finalizers are an annoying complication. But again, we can 
look at all the functions we call, and all the 'new' operations we 
perform, to see if any finalizers exist. Maybe we could even have a 
separate finalizer heap?

Exceptions are the biggest nuisance, since they can also leak 
heap-allocated memory. A catch handler in a non-pure function would need 
to check to see if the pure heap 'stackpointer' is non-zero, and if so, 
it would need to do a deep dup of the exception, then clear the pure 
heap. Any pure function (leaky or not) which contains a catch handler 
would need to record the value of the savedstackptr at entry to the 
function, and the catch handler would need to unwind the pure heap until 
we get back to it.

In reality, things are going to be a bit more complicated than this. But
it seems to me that conceptually, something like this could still stay 
fairly simple and be very, very fast. With no changes required to the 
language, and not even any changes required to existing code.