Re: Best Ref-counting algorithms?

On Jul 21, 8:13 am, George Neuner <gneun...@comcast.net> wrote:
> I think John is getting tired of this thread - GC is more a runtime
> issue than a compiler one (except maybe for region-based GC which is
> explicitly compiler directed).


(I'll take the more general discussion to e-mail, but perhaps we can
continue the part that deals with compiler-directed GC)


Speaking about about regions, I stumbled over Cyclone by pure accident
(and by implication also read up on linear types).


Since I'm trying to do an imperative OO (yet another one), I feel its
sort of a fight where that an OO language by its nature is a natural
fit for heap allocation, whereas what one constantly dreams about is
if things could be as easy as stack allocation is, which both has
extremely fast allocation and perfect garbage collection.


Cyclone sort of showed an example on how it is possible to at least
get a little closer while actually giving a bit more to play with than
C.


Even before reading about Cyclone I was playing with the idea of being
able to define something similar, for instance being able to
explicitly select allocation region, where you then could define
multiple heaps and GC them separately. (Perhaps even having ways of
merging them, moving from one to another etc)


That's not quite the same as regions in Cyclone, but perhaps it might
be 'good enough'.


I was thinking about something like this:


Heap newHeap = Heap.allocate( ... arguments ...);


newHeap.push();


... all heap-allocations now default to newHeap ...


newHeap.pop();


... heap allocations now on default heap.


newHeap.collect(); // Collects the heap
Heap.current().merge(newHeap); // Merges the heaps.




Another scheme I was thinking of would be to _always_ initially
(dynamically) allocate on the stack, and then copy to the heap the
objects that still have references when exiting a function.


This would obviously cost a lot if most allocations need to be on the
heap, but if objects are mostly transient, could it be worth it?


One would obviously need to mark the object to know when it has been
assigned to a non-stack object, or a stack object that has been
marked.




This would then be sort of an alternative to escape analysis which I
suppose must be rather conservative. For that reason I suspect it is
even harder to do the proper analysis in a dynamically typed language
as it is not possible during compile time to determine the exact
methods that will be called.


Instead the pessimistic assumption must be that any local variable
that is sent as an argument to a method must be allocated on the heap
(as it might possibly be retained further down the calling chain).


If one instead would use a marking (i.e. 1 bit refcounting) scheme on
the stack allocated objects, one would perhaps get a less conservative
estimation, but obviously paid with the cost of having to copy stack
objects to the heap.




/Christoffer

Return to the comp.compilers page.
Search the comp.compilers archives again.