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.
