[gclist] More questions for the FAQ

[Roy Ward]

> || Date: Wed, 20 Mar 96 13:05:19 EST
> || From: David Chase <chase@centerline.com>
> ||
> || Q: What languages include/require/provide-by-default garbage collection?
>
>The Macintosh operating system (MacOS) does garbage collection internally.
>>From what I am told, applications register their roots in an object table.
>The system does reference counting.

Sadly, no. Nearly all my programming is on Macintoshes, and I've never
heard of a mechanism that does this, in fact I've seen memory leaks can
cause major problems which surely they wouldn't in a GC system. Unless
there is something in the new memory manager that does this that I haven't
heard about.

 I think that you heard about is the way that the memory is allocated on
Macs. In most systems, you ask for a lump of memory of a given size, and you
get returned a pointer to it (or an error). On Macs, the usual way of asking
for memory is to request a 'handle'. I'm not sure if this a standard term or
not, so I'll explain:
A handle is a pointer into a block of master pointers, and the pointer in this
block points to the lump of memory, so a handle is a pointer to a pointer. The
upshot of this is that all memory references to the object are done through
the master pointer, so the memory can be moved around at will by the OS. i.e.
compaction can be done transparently. The other side of this is that all those
double dereferences cause a performance hit, and extra longword memory hit.
No garbage collection is done through this mechanism, although compaction is.
 It is also possible to allocate a non-movable pointer on a Mac, but this is
_deathly_ slow, as it compacts the memory _each_time_. When I want a just a
pointer, I allocate a handle, lock it, and work with a single dereference
(probably causing all sorts of headaches fot the allocator which is not really
designed for lots of locked handles).

In fact one of my reasons for being on this list is because I'm designing my
own allocator for a functional language I am designing because the built in
allocator seems to perform very poorly (speedwise), and I want to have the
capability to easily add compaction and maybe garbage collection. (At the
moment I just make sure that the memory is big enough that compaction isn't
needed. This is feasible because I only have a few sizes, and the code
doesn't leave any garbage lying around. yet.).

To bring this back to the topic of GC, it seems to me that allocation strategy
and garbage collection strategy are not independent (this may have been
discussed already but I'm a latecomer to this list). Most of the discussion
I've seen has ben around GC methods where the allocator is assumed to be
already there.

'Dynamic Storage Allocation: A Survey and Critical Review' (Paul R. Wilson et
al) has an overview of memory management strategies for non-GC systems. I was
wondering if there were any references [preferable online, the library is a
bit small here] for memory management for systems that allowed memory
compaction or garbage collection? Or is this so trivial that no-one worries
about it? (It seems to me that simple segregated  (fine-grained) classes of
free lists should give good performance, as they are very quick and
compaction/GC can take care of the fragmantation. Flame me if I'm wrong).

One thing that I like the idea of is that  when then compiler knows when
stuff can be safely disposed of, it does it, thereby short circuiting the GC.
This makes having an explicit free() method (even if not available directly
to the programmer) important.

Also, while I'm considering doing everything from scratch, has there been
any research on what VM strategies work well with GC? LRU sounds like it is
sometimes pathological, and maybe there are some good alternatives. (No I'm
not really serious about doing my own VM management, just a thought)

Roy Ward.


-----------------------------------------------------------------------
C++ - a language that sacrifices coherence on the altar of conciseness.
-----------------------------------------------------------------------