Subject: Re: Conservative vs. precise GC
From: (Rob Warnock)
Date: Sat, 11 Jan 2003 08:05:24 -0600
Newsgroups: comp.lang.lisp
Message-ID: <>
Paul Dietz  <> wrote:
>Barry Margolin wrote:
| There are 'mostly copying' collectors in which some subset of the
| objects can be understood by the collector.  Data in those objects
| are never 'maybe' pointers; the collector knows what they are.
| Objects pointed to only by definite pointers can be moved.
| As I understand it, this idea is patented, with the US patent
| expiring in 2007(?).

Are you thinking of Joel Bartlett's mostly-copying collector?

    Joel F. Bartlett, "Compacting Garbage Collection with Ambiguous Roots"
    Compaq Western Research (formerly DECWRL) Research Report 88/2,
    February 1988

    This paper introduces a copying garbage collection algorithm which
    is able to compact most of the accessible storage in the heap without
    having an explicitly defined set of pointers that contain the roots
    of all accessible storage. Using "hints" found in the processor's
    registers and stack, the algorithm is able to divide heap allocated
    objects into two groups: those that might be referenced by a pointer
    in the stack or registers, and those that are not. The objects which
    might be referenced are left in place, and the other objects are
    copied into a more compact representation. 

This was written [in 1987?] for his "Scheme2C" compiler. The core code
appears as "Appendix I" of the paper. I didn't know that it was patented,


Rob Warnock, PP-ASEL-IA		<>
627 26th Avenue			<URL:>
San Mateo, CA 94403		(650)572-2607