A nonrecursive list compacting algorithm

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A nonrecursive list compacting algorithm

Full text

Pdf (172 KB)

Source

Communications of the ACM archive
Volume 13 , Issue 11 (November 1970) table of contents

Pages: 677 - 678

Year of Publication: 1970

ISSN:0001-0782

Author

C. J. Cheney

Univ. Mathematical Lab, Cambridge, England

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 24, Downloads (12 Months): 136, Citation Count: 109

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/362790.362798 What is a DOI?

ABSTRACT

A simple nonrecursive list structure compacting scheme or garbage collector suitable for both compact and LISP-like list structures is presented. The algorithm avoids the need for recursion by using the partial structure as it is built up to keep track of those lists that have been copied.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Wilfred J. Hansen, Compact list representation: definition, garbage collection, and system implementation, Communications of the ACM, v.12 n.9, p.499-507, Sept. 1969 [doi>10.1145/363219.363225]
	2	Robert R. Fenichel , Jerome C. Yochelson, A LISP garbage-collector for virtual-memory computer systems, Communications of the ACM, v.12 n.11, p.611-612, Nov. 1969 [doi>10.1145/363269.363280]
	3	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997

CITED BY 109

	Stefan Monnier , Bratin Saha , Zhong Shao, Principled scavenging, ACM SIGPLAN Notices, v.36 n.5, p.81-91, May 2001
	Antony L. Hosking , Jiawan Chen, Mostly-copying reachability-based orthogonal persistence, ACM SIGPLAN Notices, v.34 n.10, p.382-398, Oct. 1999
	Bart Demoen , Konstantinos Sagonas, Memory management for Prolog with tabling, ACM SIGPLAN Notices, v.34 n.3, p.97-106, March 1999
	B. Pearlmutter, Garbage collection with pointers to individuals cells, Communications of the ACM, v.39 n.12es, Dec. 1996
	Douglas W. Clark, An efficient list-moving algorithm using constant workspace, Communications of the ACM, v.19 n.6, p.352-356, June 1976
	William D. Clinger , Lars T. Hansen, Generational garbage collection and the radioactive decay model, ACM SIGPLAN Notices, v.32 n.5, p.97-108, May 1997
	Douglas W. Clark, A fast algorithm for copying list structures, Communications of the ACM, v.21 n.5, p.351-357, May 1978
	Douglas W. Clark , C. Cordell Green, An empirical study of list structure in Lisp, Communications of the ACM, v.20 n.2, p.78-87, Feb. 1977
	Chi-Keung Luk , Todd C. Mowry, Memory forwarding: enabling aggressive layout optimizations by guaranteeing the safety of data relocation, ACM SIGARCH Computer Architecture News, v.27 n.2, p.88-99, May 1999
	Henry C. Baker, Jr. , Carl Hewitt, The incremental garbage collection of processes, ACM SIGPLAN Notices, v.12 n.8, p.55-59, August 1977
	Ralph E. Johnson, Reducing the latency of a real-time garbage collector, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.1, p.46-58, March 1992
	David C. Walden, A note on Cheney's nonrecursive list-compacting algorithm, Communications of the ACM, v.15 n.4, p.275-276, April 1972
	Mark B. Reinhold, Cache performance of garbage-collected programs, ACM SIGPLAN Notices, v.29 n.6, p.206-217, June 1994
	Yoo C. Chung , Soo-Mook Moon , Kemal Ebcioğlu , Dan Sahlin, Reducing sweep time for a nearly empty heap, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.378-389, January 19-21, 2000, Boston, MA, USA
	F. Lockwood Morris, A time- and space-efficient garbage compaction algorithm, Communications of the ACM, v.21 n.8, p.662-665, Aug. 1978
	Lorenz Huelsbergen , James R. Larus, A concurrent copying garbage collector for languages that distinguish (im)mutable data, ACM SIGPLAN Notices, v.28 n.7, p.73-82, July 1993
	Lorenz Huelsbergen , James R. Larus , Alexander Aiken, Using the run-time sizes of data structures to guide parallel-thread creation, ACM SIGPLAN Lisp Pointers, v.VII n.3, p.79-90, July-Sept. 1994
	Antony L. Hosking , J. Eliot B. Moss , Darko Stefanovic, A comparative performance evaluation of write barrier implementation, ACM SIGPLAN Notices, v.27 n.10, p.92-109, Oct. 1992
	Stephen M Blackburn , Richard Jones , Kathryn S. McKinley , J Eliot B Moss, Beltway: getting around garbage collection gridlock, ACM SIGPLAN Notices, v.37 n.5, May 2002
	Robert R. Fenichel, Comment on Cheney's list-compaction algorithm, Communications of the ACM, v.14 n.9, p.603-604, Sept. 1971
	Pascal Fradet, Collecting more garbage, ACM SIGPLAN Lisp Pointers, v.VII n.3, p.24-33, July-Sept. 1994
	Raphael Alonso , Andrew W. Appel, An advisor for flexible working sets, ACM SIGMETRICS Performance Evaluation Review, v.18 n.1, p.153-162, May 1990
	Martin Rudalics, Distributed copying garbage collection, Proceedings of the 1986 ACM conference on LISP and functional programming, p.364-372, August 1986, Cambridge, Massachusetts, United States
	Edward M. Reingold, A nonrecursive list moving algorithm, Communications of the ACM, v.16 n.5, p.305-307, May 1973
	Niels Hallenberg , Martin Elsman , Mads Tofte, Combining region inference and garbage collection, ACM SIGPLAN Notices, v.37 n.5, May 2002
	Perry Cheng , Robert Harper , Peter Lee, Generational stack collection and profile-driven pretenuring, ACM SIGPLAN Notices, v.33 n.5, p.162-173, May 1998
	Jeffrey L. Dawson, Improved effectiveness from a real time LISP garbage collector, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.159-167, August 15-18, 1982, Pittsburgh, Pennsylvania, United States
	Elliot Kolodner , Barbara Liskov , William Weihl, Atomic garbage collection: managing a stable heap, ACM SIGMOD Record, v.18 n.2, p.15-25, June 1989
	Amer Diwan , David Tarditi , Eliot Moss, Memory subsystem performance of programs using copying garbage collection, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-14, January 16-19, 1994, Portland, Oregon, United States
	Jacques Cohen, Garbage Collection of Linked Data Structures, ACM Computing Surveys (CSUR), v.13 n.3, p.341-367, Sept. 1981
	Saleh E. Abdullahi , Graem A. Ringwood, Garbage collecting the Internet: a survey of distributed garbage collection, ACM Computing Surveys (CSUR), v.30 n.3, p.330-373, Sept. 1998
	Amer Diwan , David Tarditi , Eliot Moss, Memory system performance of programs with intensive heap allocation, ACM Transactions on Computer Systems (TOCS), v.13 n.3, p.244-273, Aug. 1995
	Daniel G. Bobrow , Douglas W. Clark, Compact Encodings of List Structure, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.2, p.266-286, Oct. 1979
	Trishul M. Chilimbi , James R. Larus, Using generational garbage collection to implement cache-conscious data placement, ACM SIGPLAN Notices, v.34 n.3, p.37-48, March 1999
	David A. Moon, Garbage collection in a large LISP system, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.235-246, August 06-08, 1984, Austin, Texas, United States
	Patrick M. Sansom , Simon L. Peyton Jones, Generational garbage collection for Haskell, Proceedings of the conference on Functional programming languages and computer architecture, p.106-116, June 09-11, 1993, Copenhagen, Denmark
	Raymond L. Bates , David Dyer , Johannes A. G. M. Koomen, Implementation of Interlisp on the VAX, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.81-87, August 15-18, 1982, Pittsburgh, Pennsylvania, United States
	Benjamin Zorn, Comparing mark-and sweep and stop-and-copy garbage collection, Proceedings of the 1990 ACM conference on LISP and functional programming, p.87-98, June 27-29, 1990, Nice, France
	David C. Walden, A note on Cheney's nonrecursive list-compacting algorithm, Communications of the ACM, v.15 n.4, p.275, April 1972
	Michael W. Hicks , Jonathan T. Moore , Scott M. Nettles, The measured cost of copying garbage collection mechanisms, ACM SIGPLAN Notices, v.32 n.8, p.292-305, Aug. 1997
	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
	Perry Cheng , Guy E. Blelloch, A parallel, real-time garbage collector, ACM SIGPLAN Notices, v.36 n.5, p.125-136, May 2001
	Xining Li, Efficient memory management in a merged heap/stack prolog machine, Proceedings of the 2nd ACM SIGPLAN international conference on Principles and practice of declarative programming, p.245-256, September 20-23, 2000, Montreal, Quebec, Canada
	Michael Hicks , Luke Hornof , Jonathan T. Moore , Scott M. Nettles, A study of large object spaces, ACM SIGPLAN Notices, v.34 n.3, p.138-145, March 1999
	Hans-J. Boehm , Alan J. Demers , Scott Shenker, Mostly parallel garbage collection, ACM SIGPLAN Notices, v.26 n.6, p.157-164, June 1991
	Guy E. Blelloch , Perry Cheng, On bounding time and space for multiprocessor garbage collection, ACM SIGPLAN Notices, v.34 n.5, p.104-117, May 1999
	Martin Larose , Marc Feeley, A compacting incremental collector and its performance in a production quality compiler, ACM SIGPLAN Notices, v.34 n.3, p.1-9, March 1999
	Bart Demoen , Geert Engels , Paul Tarau, Segment order preserving copying garbage collection for WAM based Prolog, Proceedings of the 1996 ACM symposium on Applied Computing, p.380-386, February 17-19, 1996, Philadelphia, Pennsylvania, United States
	Paul R. Wilson , Michael S. Lam , Thomas G. Moher, Effective “static-graph” reorganization to improve locality in garbage-collected systems, ACM SIGPLAN Notices, v.26 n.6, p.177-191, June 1991
	Yefim Shuf , Manish Gupta , Hubertus Franke , Andrew Appel , Jaswinder Pal Singh, Creating and preserving locality of java applications at allocation and garbage collection times, ACM SIGPLAN Notices, v.37 n.11, November 2002
	Matthias Meyer, A true hardware read barrier, Proceedings of the 2006 international symposium on Memory management, June 10-11, 2006, Ottawa, Ontario, Canada
	Yoo C. Chung , Soo-Mook Moon , Kemal Ebcioğlu , Dan Sahlin, Selective sweeping, Software—Practice & Experience, v.35 n.1, p.15-26, January 2005
	Stephen M. Blackburn , Kathryn S. McKinley, Ulterior reference counting: fast garbage collection without a long wait, ACM SIGPLAN Notices, v.38 n.11, November 2003
	Lars T. Hansen , William D. Clinger, An experimental study of renewal-older-first garbage collection, ACM SIGPLAN Notices, v.37 n.9, p.247-258, September 2002
	A. M. Cheadle , A. J. Field , S. Marlow , S. L. Peyton Jones , R. L. While, Non-stop Haskell, ACM SIGPLAN Notices, v.35 n.9, p.257-267, Sept. 2000
	Antony L. Hosking , J. Eliot B. Moss, Object fault handling for persistent programming languages: a performance evaluation, ACM SIGPLAN Notices, v.28 n.10, p.288-303, Oct. 1, 1993
	Darko Stefanović , Kathryn S. McKinley , J. Eliot B. Moss, Age-based garbage collection, ACM SIGPLAN Notices, v.34 n.10, p.370-381, Oct. 1999
	Stuart Norcross , Ron Morrison , Dave Munro , Henry Detmold, Implementing a family of distributed garbage collectors, Proceedings of the twenty-sixth Australasian conference on Computer science: research and practice in information technology, p.161-170, February 01, 2003, Adelaide, Australia
	Amir Roth , Gurindar S. Sohi, Effective jump-pointer prefetching for linked data structures, ACM SIGARCH Computer Architecture News, v.27 n.2, p.111-121, May 1999
	Jonathan E. Cook , Artur W. Klauser , Alexander L. Wolf , Benjamin G. Zorn, Semi-automatic, self-adaptive control of garbage collection rates in object databases, ACM SIGMOD Record, v.25 n.2, p.377-388, June 1996
	Erik Johansson , Konstantinos Sagonas , Jesper Wilhelmsson, Heap architectures for concurrent languages using message passing, ACM SIGPLAN Notices, v.38 n.2 supplement, February 2003
	Stephen M. Blackburn , Perry Cheng , Kathryn S. McKinley, Myths and realities: the performance impact of garbage collection, ACM SIGMETRICS Performance Evaluation Review, v.32 n.1, June 2004
	Martin Hirzel , Amer Diwan , Matthew Hertz, Connectivity-based garbage collection, ACM SIGPLAN Notices, v.38 n.11, November 2003
	David F. Bacon , Perry Cheng , David Grove, Garbage collection for embedded systems, Proceedings of the 4th ACM international conference on Embedded software, September 27-29, 2004, Pisa, Italy
	R. Dimpsey , R. Arora , K. Kuiper, Java server performance: a case study of building efficient, scalable Jvms, IBM Systems Journal, v.39 n.1, p.151-174, January 2000
	Guy E. Blelloch , Perry Cheng, On bounding time and space for multiprocessor garbage collection, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Narendran Sachindran , J. Eliot B. Moss , Emery D. Berger, MC²: high-performance garbage collection for memory-constrained environments, ACM SIGPLAN Notices, v.39 n.10, October 2004
	Martin Hirzel , Johannes Henkel , Amer Diwan , Michael Hind, Understanding the connectivity of heap objects, ACM SIGPLAN Notices, v.38 n.2 supplement, February 2003
	Mads Tofte , Lars Birkedal , Martin Elsman , Niels Hallenberg, A Retrospective on Region-Based Memory Management, Higher-Order and Symbolic Computation, v.17 n.3, p.245-265, September 2004
	A. M. Cheadle , A. J. Field , S. Marlow , S. L. Peyton Jones , R. L. While, Exploring the barrier to entry: incremental generational garbage collection for Haskell, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada
	David F. Bacon , Perry Cheng , V. T. Rajan, A unified theory of garbage collection, ACM SIGPLAN Notices, v.39 n.10, October 2004
	Konstantinos Sagonas , Jesper Wilhelmsson, Message analysis-guided allocation and low-pause incremental garbage collection in a concurrent language, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada
	Cliff Click , Gil Tene , Michael Wolf, The pauseless GC algorithm, Proceedings of the 1st ACM/USENIX international conference on Virtual execution environments, June 11-12, 2005, Chicago, IL, USA
	Lars Birkedal , Noah Torp-Smith , John C. Reynolds, Local reasoning about a copying garbage collector, ACM SIGPLAN Notices, v.39 n.1, p.220-231, January 2004
	Matthew Hertz , Yi Feng , Emery D. Berger, Garbage collection without paging, ACM SIGPLAN Notices, v.40 n.6, June 2005
	Daniel Spoonhower , Guy Blelloch , Robert Harper, Using page residency to balance tradeoffs in tracing garbage collection, Proceedings of the 1st ACM/USENIX international conference on Virtual execution environments, June 11-12, 2005, Chicago, IL, USA
	Cormac Flanagan , Rishiyur S. Nikhil, pHluid: the design of a parallel functional language implementation on workstations, ACM SIGPLAN Notices, v.31 n.6, p.169-179, June 15, 1996
	Daniel Spoonhower , Joshua Auerbach , David F. Bacon , Perry Cheng , David Grove, Eventrons: a safe programming construct for high-frequency hard real-time applications, ACM SIGPLAN Notices, v.41 n.6, June 2006
	Timothy J. McEntee, Overview of garbage collection in symbolic computing, ACM SIGPLAN Lisp Pointers, v.1 n.3, p.8-16, August-September 1987
	Michal Wegiel , Chandra Krintz, The mapping collector: virtual memory support for generational, parallel, and concurrent compaction, ACM SIGOPS Operating Systems Review, v.42 n.2, March 2008
	Noah Torp-Smith , Lars Birkedal , John C. Reynolds, Local reasoning about a copying garbage collector, ACM Transactions on Programming Languages and Systems (TOPLAS), v.30 n.4, p.1-58, July 2008
	Antony L. Hosking, Portable, mostly-concurrent, mostly-copying garbage collection for multi-processors, Proceedings of the 2006 international symposium on Memory management, June 10-11, 2006, Ottawa, Ontario, Canada
	Rasmus Pedersen , Martin Schoeberl, Exact roots for a real-time garbage collector, Proceedings of the 4th international workshop on Java technologies for real-time and embedded systems, October 11-13, 2006, Paris, France
	Tony Printezis, Hot-swapping between a mark&sweep and a mark&compact garbage collector in a generational environment, Proceedings of the Java^TM Virtual Machine Research and Technology Symposium on Java^TM Virtual Machine Research and Technology Symposium, p.20-20, April 23-24, 2001, Monterey, California
	Katherine Barabash , Niv Buchbinder , Tamar Domani , Elliot K. Kolodner , Yoav Ossia , Shlomit S. Pinter , Janice Shepherd , Ron Sivan , Victor Umansky, Mostly accurate stack scanning, Proceedings of the Java^TM Virtual Machine Research and Technology Symposium on Java^TM Virtual Machine Research and Technology Symposium, p.19-19, April 23-24, 2001, Monterey, California
	Xiaolan Zhang , Margo Seltzer, HBench: JGC - an application-specific benchmark suite for evaluating JVM garbage collector performance, Proceedings of the 6th conference on USENIX Conference on Object-Oriented Technologies and Systems, p.4-4, January 29-February 02, 2001, San Antonia, Texas
	Konstantinos Sagonas , Jesper Wilhelmsson, Efficient memory management for concurrent programs that use message passing, Science of Computer Programming, v.62 n.2, p.98-121, 1 October 2006
	Wen-ke Chen , Sanjay Bhansali , Trishul Chilimbi , Xiaofeng Gao , Weihaw Chuang, Profile-guided proactive garbage collection for locality optimization, ACM SIGPLAN Notices, v.41 n.6, June 2006
	Wei Fu , Carl Hauser, A real-time garbage collection framework for embedded systems, Proceedings of the 2005 workshop on Software and compilers for embedded systems, p.20-26, September 29-October 01, 2005, Dallas, Texas
	Huu-Duc Nguyen , Atsushi Ohori, Compiling ML polymorphism with explicit layout bitmap, Proceedings of the 8th ACM SIGPLAN symposium on Principles and practice of declarative programming, July 10-12, 2006, Venice, Italy
	David Siegwart , Martin Hirzel, Improving locality with parallel hierarchical copying GC, Proceedings of the 2006 international symposium on Memory management, June 10-11, 2006, Ottawa, Ontario, Canada
	A. M. Cheadle , A. J. Field , J. W. Ayres , N. Dunn , R. A. Hayden , J. Nystrom-Persson, Visualising dynamic memory allocators, Proceedings of the 2006 international symposium on Memory management, June 10-11, 2006, Ottawa, Ontario, Canada
	Konstantinos Sagonas , Jesper Wilhelmsson, Mark and split, Proceedings of the 2006 international symposium on Memory management, June 10-11, 2006, Ottawa, Ontario, Canada
	Martin Hirzel, Data layouts for object-oriented programs, ACM SIGMETRICS Performance Evaluation Review, v.35 n.1, June 2007
	Martin Schoeberl , Jan Vitek, Garbage collection for safety critical Java, Proceedings of the 5th international workshop on Java technologies for real-time and embedded systems, September 26-28, 2007, Vienna, Austria
	Stephen M. Blackburn , Kathryn S. McKinley, Immix: a mark-region garbage collector with space efficiency, fast collection, and mutator performance, ACM SIGPLAN Notices, v.43 n.6, June 2008
	Carsten Varming , Lars Birkedal, Higher-Order Separation Logic in Isabelle/HOLCF, Electronic Notes in Theoretical Computer Science (ENTCS), 218, p.371-389, October, 2008
	Antony L. Hosking , Jiawan Chen, PM3: An Orthogonal Persistent Systems Programming Language - Design, Implementation, Performance, Proceedings of the 25th International Conference on Very Large Data Bases, p.587-598, September 07-10, 1999
	Henry G. Baker, CONS should not CONS its arguments, part II: Cheney on the M.T.A., ACM SIGPLAN Notices, v.30 n.9, p.17-20, Sept. 1995
	Nandakumar Sankaran, A bibliography on garbage collection and related topics, ACM SIGPLAN Notices, v.29 n.9, p.149-158, Sept. 1994
	B. Lang , F. Dupont, Incremental incrementally compacting garbage collection, ACM SIGPLAN Notices, v.22 n.7, p.253-263, July 1987
	A. M. Cheadle , A. J. Field , J. Nystrom-Persson, A method specialisation and virtualised execution environment for Java, Proceedings of the fourth ACM SIGPLAN/SIGOPS international conference on Virtual execution environments, March 05-07, 2008, Seattle, WA, USA
	Martin Kero , Johan Nordlander , Per Lindgren, A correct and useful incremental copying garbage collector, Proceedings of the 6th international symposium on Memory management, October 21-22, 2007, Montreal, Quebec, Canada
	Simon Marlow , Tim Harris , Roshan P. James , Simon Peyton Jones, Parallel generational-copying garbage collection with a block-structured heap, Proceedings of the 7th international symposium on Memory management, June 07-08, 2008, Tucson, AZ, USA
	Chris Hawblitzel , Erez Petrank, Automated verification of practical garbage collectors, Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 21-23, 2009, Savannah, GA, USA
	Magnus O. Myreen , Michael J. C. Gordon , Konrad Slind, Machine-code verification for multiple architectures: an application of decompilation into logic, Proceedings of the 2008 International Conference on Formal Methods in Computer-Aided Design, p.1-8, November 17-20, 2008, Portland, Oregon
	Cosmin E. Oancea , Alan Mycroft , Stephen M. Watt, A new approach to parallelising tracing algorithms, Proceedings of the 2009 international symposium on Memory management, June 19-20, 2009, Dublin, Ireland
	Mauricio J. Serrano , Xiaotong Zhuang, Placement optimization using data context collected during garbage collection, Proceedings of the 2009 international symposium on Memory management, June 19-20, 2009, Dublin, Ireland
	Gary H. Sockut , Balakrishna R. Iyer, Online reorganization of databases, ACM Computing Surveys (CSUR), v.41 n.3, p.1-136, July 2009

INDEX TERMS

Keywords:
LISP, compact list, garbage collection, list compacting

Collaborative Colleagues:

C. J. Cheney: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player