Improved effectiveness from a real time LISP garbage collector

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Improved effectiveness from a real time LISP garbage collector

Full text

Pdf (564 KB)

Source

Conference on LISP and Functional Programming archive
Proceedings of the 1982 ACM symposium on LISP and functional programming table of contents

Pittsburgh, Pennsylvania, United States

Pages: 159 - 167

Year of Publication: 1982

ISBN:0-89791-082-6

Author

Jeffrey L. Dawson

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence
SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 23, Citation Count: 6

Additional Information:

abstract references cited by index terms

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/800068.802146 What is a DOI?

ABSTRACT

This paper describes a real-time garbage collection algorithm for list processing systems. We identify two efficiency problems inherent to real-time garbage collectors, and give some evidence that the proposed algorithm tends to reduce these problems. In a virtual memory implementation, the algorithm restructures the cell storage area more compactly, thus reducing working sets. The algorithm also may provide a more garbage-free storage area at the end of the collection cycle, although this claim really must await empirical verification.

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	Henry G. Baker, Jr. , Carl Hewitt, The Incremental Garbage Collection of Processes, Massachusetts Institute of Technology, Cambridge, MA, 1977
	2	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]
	3	C. J. Cheney, A nonrecursive list compacting algorithm, Communications of the ACM, v.13 n.11, p.677-678, Nov 1970 [doi>10.1145/362790.362798]
	4	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 [doi>10.1145/359423.359427]
	5	Clark, D.W., "Measurements of dynamic list structure use in LISP," IEEE Transactions on Software Engineering, Vol. SE-5, No. 1, January 1979, pp. 51-59.
	6	Jacques Cohen, Garbage Collection of Linked Data Structures, ACM Computing Surveys (CSUR), v.13 n.3, p.341-367, Sept. 1981 [doi>10.1145/356850.356854]
	7	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]
	8	Hood, R. and R. Melville, "Real-time queue operations in pure LISP," Information Processing Letters, Vol. 13, No. 2, November 1981, pp. 50-54.
	9	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]
	10	Philip L. Wadler, Analysis of an algorithm for real time garbage collection, Communications of the ACM, v.19 n.9, p.491-500, Sept. 1976 [doi>10.1145/360336.360338]

CITED BY 6

	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
	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
	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
	J. D. Eckart , R. J. LeBlanc, Distributed garbage collection, ACM SIGPLAN Notices, v.22 n.7, p.264-273, July 1987
	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