Trading data space for reduced time and code space in real-time garbage collection on stock hardware

ABSTRACT

This paper presents a new storage representation for cons cells (and all other LISP heap data structures) which allows more time efficient LISP with real-time garbage collection on stock hardware. “Stock hardware” refers to common modern architectures for Von Neumann uni-processors (e.g. MC68000, IBM370, VAX, NS32032, etc.). Previous real-time garbage collection schemes have either explicitly required specially tailored hardware in order to avoid multiple order of magnitude slowdowns, or have been merely extremely unattractive for implementation on stock hardware due to the high overhead assumed by all basic LISP primitives in checking the garbage collection status of pointers handed to them as arguments. We first show that copying compacting real-time garbage collection algorithms do not always need to protect user programs from seeing uncopied data, so long as a slightly more complicated collection termination condition is used. This opens the way to adding an indirection pointer to all LISP heap objects making it unnecessary to check the garbage collection status of pointers, and so the overhead costs for most primitives reduce to the addition of a single instruction. Impure primitives, i.e. those which write into existing structures (e.g. RPLACD), have their overhead reduced by a factor of almost 2. Code density is correspondingly decreased. The cost of this scheme is increased storage size for all LISP heap objects one extra pointer per object, although for some objects (e.g. floating point numbers) this expense is already necessary in many other non real-time garbage collection algorithms.

REFERENCES

• 1: Henry G. Baker, Jr., List processing in real time on a serial computer, Communications of the ACM, v.21 n.4, p.280-294, April 1978 [doi>10.1145/359460.359470]
• 2: Rodney A. Brooks , Richard P. Gabriel , Guy L. Steele, Jr., S-1 Common Lisp implementation, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.108-113, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802141]
• 3: Lieberman, Henry and Carl Hewitt. A Real Time Garbage Collector That Can Recover Temporary Storage Quickly, MIT AI Memo 596.
• 4: Marvin Minsky, A LISP Garbage Collector Algorithm Using Serial Secondary Storage, Massachusetts Institute of Technology, Cambridge, MA, 1963
• 5: Guy L. Steele, Jr., Multiprocessing compactifying garbage collection, Communications of the ACM, v.18 n.9, p.495-508, Sept. 1975 [doi>10.1145/361002.361005]
• 6: Steele, Guy Lewis Jr. et. al. Common Lisp Reference Manual, Digital Press, 1984.
• 7: Daniel Weinreb, Lisp machine manual, Massachusetts Institute of Technology, 1981

INDEX TERMS

Primary Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Memory management (garbage collection)

General Terms:
Management