Morris's Garbage Compaction Algorithm Restores Reference Counts

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Morris's Garbage Compaction Algorithm Restores Reference Counts

Full text

Pdf (304 KB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 1 , Issue 1 (July 1979) table of contents

Pages: 115 - 120

Year of Publication: 1979

ISSN:0164-0925

Author

David S. Wise

Computer Science Department, Indiana University, 101 Lindley Hall, Bloomington, IN

Publisher

ACM New York, NY, USA

Bibliometrics

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

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

ABSTRACT

The two-pass compaction algorithm of F.L. Morris, which follows upon the mark phase in a garbage collector, may be modified to recover reference counts for a hybrid storage management system. By counting the executions of two loops in that algorithm where upward and downward references, respectively, are forwarded to the relocation address of one node, we can initialize a count of active references and then update it but once. The reference count may share space with the mark bit in each node, but it may not share the additional space required in each pointer by Morris's algorithm, space which remains unused outside the garbage collector.

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	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]
	2	CLARli, D.W., ANO GREEN, C.C. A note on shared structure in Lisp. Inform. Proc. Ltrs. 7, 6 (Oct. 1978), 312-314.
	3	L. Peter Deutsch , Daniel G. Bobrow, An efficient, incremental, automatic garbage collector, Communications of the ACM, v.19 n.9, p.522-526, Sept. 1976 [doi>10.1145/360336.360345]
	4	FRIEDMAN, D.P., ANO WISE, D.S. Garbage collecting a heap which includes a scatter table. Inform. Proc. Ltrs. 5, 6 (Dec. 1976), 161-164. Erratum. Inform. Proc. Ltrs. 6, 2 (April 1977), 72.
	5	FRIEDMAN, D.P., AND WISE, D.S. Reference counting can manage the circular environments of mutual recursion. Inform. Proc. Ltrs. 8, 1 (Jan. 1979), 41-44.
	6	F. Lockwood Morris, A time- and space-efficient garbage compaction algorithm, Communications of the ACM, v.21 n.8, p.662-665, Aug. 1978 [doi>10.1145/359576.359583]
	7	T~.RASI~IMA, M., AND GOTO, E. Genetic order and compactffying garbage collectors. Inform. Proc. Ltrs. 7, 1 (Jan. 1978), 27-32.
	8	WISE, D.S., AND FRIEDMAN, D.P. The one-bit reference count. Nordisk Tidskr. Informationsbehandling (BIT) 17, 3 (Sept. 1977), 351-359.

CITED BY 3

	Johannes J. Martin, An efficient garbage compaction algorithm, Communications of the ACM, v.25 n.8, p.571-580, Aug 1982
	Jacques Cohen, Garbage Collection of Linked Data Structures, ACM Computing Surveys (CSUR), v.13 n.3, p.341-367, Sept. 1981
	Nandakumar Sankaran, A bibliography on garbage collection and related topics, ACM SIGPLAN Notices, v.29 n.9, p.149-158, Sept. 1994