GC for pure functions -- implementation ideas

[Denis Koroskin]

On Sat, 16 Apr 2011 00:12:34 +0400, Don <nospam at nospam.com> wrote:

> 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.

I was doing something similar to get rid of the memory leaks in DDMD: I  
allocated with something like pureMalloc, then took one of the root  
objects and made a deep copy of the entire object hierarchy. The newly  
constructed object hierarchy (allocated in managed heap) is then used  
instead of the original one.