[gclist] Representation of pointer set
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 email@example.com email
Amherst, MA 01003-4610 USA +1-413-545-3733 Priscilla Coe sec'y