Aliasing and Garbage Collection

["Tom Locke" <tsl2@xxxxxxxxx>]

Hi,

This is the first of a few posts. A while back a thread kicked off about an
issue I raised in my talk at CPA: A language that has no aliasing has no
need for the runtime overhead of garbage collection.

This is a trivial observation - the responsibility of the garbage collector
is to determine when an object is unreachable, in a language with no
aliasing, data objects are referenced by only one pointer, when the pointer
is overwritten, the memory can be reclaimed. The point at which the object
is unreachable is known *statically*, the compiler just inserts the
'reclaim' code when the pointer is overwritten or goes (permanently) out of
scope.

I am a bit concerned (and hoping that I've misunderstood) by the suggestion
that the overhead of GC can also be removed by simply 'buying twice as much
memory', and not reclaiming anything. In a program with lots of dynamic
allocation, i.e. most programs, especially OO, memory would be leaked very
rapidly, I would imagine most Java code could get through a megabyte in a
matter of seconds. It might work if you buy a million times as much memory!


CAN WE DO WITHOUT GC ALTOGETHER?

Many programs use graph data structures. It's very nice to know that nodes
that are cut off from the graph are somebody elses problem (i.e.
automatically deleted). In the nameless language that I'm working on, the
overall system is free from aliasing and needs no GC, but I'd like to
provide a 'graph' as a standard container, every item in the graph has an
ID, and can contain the ID of other items, the only way to retrieve an
object from the graph is using its ID, and items are automatically removed
when all copies of the ID are lost. For ID read pointer and you've
effectively got a separate address space with it's own GC. The important
point is that it more managable beacuse the ID's are only valid inside their
own graph.

I'm going to be ranting more about this in another post so...

SUMMARY

GC is very useful, but is only needed when we have aliaing. In my ideal
language, some sub-components contain internal aliasing but the system as a
whole is alias free. We do need a GC but it is hopefuly relatively idle
compared to say GC in Java.