Re: Best Ref-counting algorithms?

On Wed, 22 Jul 2009 02:31:06 -0700 (PDT), Christoffer Lernv
<lerno@dragonascendant.com> wrote:


>Even before reading about Cyclone I was playing with the idea of being
>able to define something similar [to lexically scoped heap regions],
>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'.


Cyclone's compiler does not perform region analysis (per Tofte) to
direct allocation of program objects to particular region heaps. In
Cyclone, regions are named entities and allocation of program objects
from them is under programmer control.


Tofte's regions are hidden runtime entities known only to the compiler
- the decision to allocate an object from a particular region is made
automatically by the compiler using a combination of escape and static
lifetime analysis.


Tofte's regions are lexically scoped, but because the language he
used, ML, provides 1st class functions and closures, his regions have
indefinite extent and behave more like Cyclone's "dynamic" regions
than like its lexical regions.




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


It's always worth avoiding such a copy if possible. It would be much
more useful to perform escape analysis on your objects to determine
whether they can be stack allocated.




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


Escape analysis is purely an issue of lexical scoping and whether the
object may outlive the scope in which it is defined. What form of
typing the language uses is not relevant ... you are only looking for
the object to leave the control of the scope chain.


It is not really any harder to do escape analysis for Lisp than it is
for C - it just takes longer because Lisp allows nested functions and
C doesn't.




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


No. Technically, only objects which have identity can escape. For
this purpose "identity" means "location" and further means that
potential escapees are limited to actual data structures (closure
creation) or to pointers to local data structures.


However, a pointer to a local data structure is only a problem if it
if is somehow passed upward to an enclosing scope or sideways to a
disjoint scope which preserves it (which may be indeterminate). In
either case you would need to heap allocate the data structure to be
safe. If neither situation applies, the data structure can be stack
allocated.


George

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