Re: Storage management, was Compiler writers will love this language

Eric wrote:
>>Reference counting and mark-and-sweep are just ways of implementing the basic
>>idea of deallocating when references are out of scope.
>
> Just out of curiosity, are these the only major automatic memory
> management techniques out there?


  From a distance, yes.
There are countless variations on both themes.


Reference counting often has various degrees of delaying the actual
deallocation (to keep reference count decrease times predictable).


Another common technique is avoiding having to install a reference
counter in the first place. I.e. there are approaches that try to
identify memory blocks that don't ever make it out of the scope where
they were created, and don't let them enter the garbage collection
mechanism in the first place. Actually this technique is applicable
to both reference counting and mark-and-sweep.


Mark-and-sweep variations include:
1) Incremental collection. Both mark and sweep phase are somehow
integrated into the program. Some schemes do "a little bit of work" on
every call to malloc(), others run as a coroutine or in a separate process.
2) Generational collection. This tries to exploit the assumption that
data that has lived for a long time is unlikely to vanish in the next
cycle of garbage collection, and not garbage collected. Every so often
the older generation(s) are collected as well. The usefulness of this
approach isn't generally accepted AFAIK, but most incremental collectors
are generational as well anyway.
3) Copying collectors. The simplest version of this is having two heaps.
Live blocks are "marked" by copying them from heap 1 to heap 2. When all
live blocks are copied, the garbage is summarily collected by declaring
heap 1 to be a huge free block, and the next cycle starts by reversing
the roles of heap 1 and heap 2. (The "treadmill" scheme splits this into
more sub-heaps, and only one heap being copied from, so that the
overhead shrinks from 50% to as low as your space-time trade-off dictates.)


Interesting variations exist for heaps that are fragmented into
separate areas with unreliable communication (i.e. if data is
distributed over networked computers). Last time I looked, there was
no reliable algorithm that was had better than O(N^2) performance for
N nodes. In other words, that's an area where lots of scientific kudos
can be gained :-)


> This problem really bugs, because the standard library is going to be
> full of data structures the utilise two way links (eg. doubly linked
> lists). Is there a general solution (other than using a completely
> different scheme like mark-and-sweep) for this?


There is: use two types of pointers, normal and weak. Normal pointers
keep the referred-to block alive, weak pointers don't. (For example,
in a doubly-linked list, the back pointers are usually made weak.)


The downside is that it's sometimes not easy to determine which pointer
should be made weak. Besides, weak pointers may become dangling at any time.


> One of the reasons I really fancy reference-counting is its low
> overhead,


Let me repeat: reference counting does NOT have low overhead. Every
single assignment to a pointer adds two (!) memory writes. Unless your
data structures are relatively static, this will have a serious
performance impact!


A good incremental garbage collector will have a 5-10% overhead.
Reference counting is usually in the same domain.
There's a simple experiment, easy to do in C++. Write a
reference-counting smart pointer class, and a variant that's just normal
pointers. (Make sure that the normal-pointer variant of the class is
always fully inlined by the compiler, i.e. check the assembly output
that assignments to a pointer don't go through a subroutine call.) Run
your software with reference counting, then with normal pointers and
with the the Boehm-Demers-Weiser collector installed. For comparison
purposes, run the software with no garbage collection at all (i.e. with
normal pointers and no garbage collector), just to see how much overhead
garbage collection takes in general. (Make sure you have enough memory
to run your program when it never deallocates...)
I'm pretty sure that the difference between having no GC and any GC is
more than the difference between reference-counting GC and
mark-and-sweep GC :-)


> but I suspect that with a few adjustments to the algorithm, one can
> add in logic that will detect circular links during deallocation.


If you do that, you have a "hybrid" collector. It has been done
several times. Research conclusions were that hybrid collectors are
neither simpler nor faster than normal mark-and-sweep collectors.


> Its seems to be a general graph traversal/tracing problem, where one
> wants to know "have I visited this node before?" and if the answer
> is "yes" then we know a circular link exists somewhere and act
> accordingly inorder to deallocate the objects involved.


That's exactly the mark phase of a mark-and-sweep collector :-)


>>Generational collection is nice partly
>>because it's complete (all unused allocations are reclaimed)
>
> How, by the way, does generational collection deal with circular
> references?


Just like any other mark-and-sweep collector. Generational collection
simply considers all blocks of older generations to be alive without
actually checking them. In other words, it cuts down on checking time
and pays by keeping blocks alive that have become unreachable. (This
is why generational algorithms check older generations every once in a
while, to get rid of the accumulated cruft.)


  > Could the algorithm used be adapted for use in reference
> counting, to form a sort of new hybrid scheme?


Yes, but it would probably not be worth the work. Generational
collection is there to reduce the marking work; however, in a hybrid
scheme, the mark-and-sweep phase would only serve to clean up the
remnants that accidentally formed cycles.


> [mark-and-sweep is] unideal for use in real-time environments.


The reverse is true. With reference counting, every single assignment to
a pointer may remove the last reference to a potentially large set of
blocks. This makes reasoning over the cost of a pointer assignment
non-local.
For mark-and-sweep GC, all you have to do is to set aside enough time to
do the garbage collection. You still have a global number to compute,
namely an upper bound on the number of blocks that get allocated and/or
unreachable, but you do that computation once, not for every point in
the code where a pointer is modified.
Even better, mark-and-sweep is error-tolerant. You have a memory
requirement; add a bit more memory, and unexpected "spikes" in memory
usage will not matter since the additional memory will be collected
anyway (and if the time for GC isn't enough, the accumulated garbage
will still be deallocated in the GC run AFTER the incomplete run). Of
course, the unexpected memory usage should be monitored and analyzed,
and the error in the memory consumption calculations should be
corrected. But the chances for device failure will be reduced, and
/that's/ a Good Thing.


>>You may be able to find some decent heuristics, but I suspect it's a lot
>>harder than it looks.
>
> The scheme as it stands now actually seems to work fine, when you do
> not have any conditional statements (eg If..End If statements).


But that's the entire point!
As long as you don't have if/end if, you can do all memory usage
calculations at compile time.
With if/end if, things get interesting in the first place...


Regards,
Jo

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