[gclist] Representation of pointer set

Eliot Moss moss@emperor.cs.umass.edu
Tue, 2 May 2000 11:00:34 -0400 (EDT)

Well, you have something of a point. In "the old days", the view was that
GC was run when memory was tight, so it needed not to demand much more
space. In practice, providing a fixed amount of space, and then having a
fall back if it ever overflowed, seemed to work well.

When using copying algorithms (generational or not), Cheney's technique
(dating from 1970) uses the copied-but-not-yet-scanned objects as an
implicit queue, avoiding the need for a separate data structure.

These days, having a growable stack/queue/set seems reasonable, and I'd be
inclined to do it using linked "chunks", where each chunk is an array. This
is more flexible in terms of the actual storage allocation than insisting
that all elements reside in a single contiguous array, but it's not much
more complicated and its density (useful info versus data structure
overhead) is high.
J. Eliot B. Moss, Associate Professor     http://www.cs.umass.edu/~moss    www
Department of Computer Science            +1-413-545-4206                voice
140 Governor's Drive, Room 372            +1-413-545-1249                  fax
University of Massachusetts               moss@cs.umass.edu              email
Amherst, MA  01003-4610  USA              +1-413-545-3733 Priscilla Coe  sec'y