[gclist] Re: gclist-digest V1 #43

[Robert A Duff]

cef@geode.geodesic.com (Charles Fiterman) says:

> Without a garbage collector the target of
> the reference can be deleted and the storage
> used for something else. This destroys any
> hope of type safety.

I don't think that's true.  It is possible to make a manual storage
management scheme type safe, using run-time checks.  Two possible
implementations:

(1) On every "free", set a bit in the object, saying it's been freed,
and complain if it's ever referenced again.  Don't reuse the storage
right away.  Every so often, trace all references, nil-out any that
point to freed stuff, and reuse the freed storage.  The trace, of
course, is about as expensive as a real gc.  Nonetheless, this technique
is, I imagine, what is used by various
"memory-leak-and-dangling-pointer" detection tools that are available
for C.

(2) Generation counts.  On every allocation, increment a variable to
produce a unique id.  Store that in *both* the allocated object and in
the pointer.  On a dereference, check that the pointer's id matches the
thing it points to.  If the counter is 64 bits, it will never overflow
(not unless machines get a lot faster!).  Even if it's only, say, 16
bits, it has a high probability of detecting dangling pointers.  If you
can swallow the notion of conservative gc, then this probabilistic check
ought to be easily swallowed, too.

Of course, the overhead of a real gc is probably lower than the
above-mentioned schemes.  My point is just that manual storage
reclamation is not *necessarily* type-unsafe.

Furthermore, it is possible, in some languages, to deallocate storage
manually, even in the presence of gc.  Implementing this as a no-op is a
bad idea, IMHO.  It can cause storage leaks.  Better would be to mark
the storage, and if the gc ever trips over it, nil-out the relevant
pointers (and *then* reuse the storage).

Somebody in this thread has been pointing out that maybe gc is not
desirable for every program.  Certainly true.  I think there's also a
place for a system that allows manual storage management, but also
allows (optional) detection of bugs in that manual code.  It's optional
because it's potentially very expensive.  So you don't put it in the
production version.  But you use it to detect and debug memory leaks
when they occur.

Has anybody built any systems that use a mixture of techniques?  We all
know that gc can avoid polluting abstractions with extra
memory-management operations.  Fine, but *some* abstractions know quite
well when to manually de-allocate.  *Some* abstractions (like
varying-length strings) are free of cycles.

- Bob