Generation Scavenging

ABSTRACT

Many interactive computing environments provide automatic storage reclamation and virtual memory to ease the burden of managing storage. Unfortunately, many storage reclamation algorithms impede interaction with distracting pauses. Generation Scavenging is a reclamation algorithm that has no noticeable pauses, eliminates page faults for transient objects, compacts objects without resorting to indirection, and reclaims circular structures, in one third the time of traditional approaches. We have incorporated Generation Scavenging in Berkeley Smalltalk(BS), our Smalltalk-80 implementation, and instrumented it to obtain performance data. We are also designing a microprocessor with hardware support for Generation Scavenging.

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	Scott B. Baden, High Performance Storage Reclamation in an Object-Based Memory System, University of California at Berkeley, Berkeley, CA, 1982
	2	H. G. Baker, List Processing in Real Time on a Serial Computer, A.I. Working Paper 139, MIT-AI Lab, Boston, MA, April, 1977.
	3	S. Ballard and S. Shirron, The Design and Implementation of VAX/Smalltalk-80, in Smalltalk-80: Bits of History, Words of Advice, G. Krasner (editor), Addison Wesley, September, 1983, 127-150.
	4	W. Becker and D. Fagen, Throw Back the Little Ones, in Throw Back the Little Ones, Steely Dan, © American Broadcasting Music, Inc. (ASCAP), Los Angeles, CA, 1974.
	5	Ricki Blau, Paging on an object-oriented personal computer, Proceedings of the 1983 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.44-54, August 29-31, 1983, Minneapolis, Minnesota, United States [doi>10.1145/800040.801394]
	6	R. Blomseth and H. Davis, The Orion Project—A Home for SOAR, in Smalltalk on a RISC: Architectural Investigations, D. Patterson (editor), Computer Science Division, Department of E.E.C.S., University of California, Berkeley, CA, April, 1983, 64-109.
	7	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]
	8	George E. Collins, A method for overlapping and erasure of lists, Communications of the ACM, v.3 n.12, p.655-657, Dec. 1960 [doi>10.1145/367487.367501]
	9	Peter J. Denning, Virtual Memory, ACM Computing Surveys (CSUR), v.2 n.3, p.153-189, Sept. 1970 [doi>10.1145/356571.356573]
	10	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]
	11	L. P. Deutsch, An Upper Bound for Smalltalk-80 Execution on a Motorola 68000 CPU, private communications, 1982.
	12	L. P. Deutsch, Storage Reclamation, Berkeley Smalltalk Seminar, Feb. 5, 1982.
	13	L. P. Deutsch, Storage Management, private communications, 1983.
	14	L. Peter Deutsch , Allan M. Schiffman, Efficient implementation of the smalltalk-80 system, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.297-302, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800542]
	15	R. Fateman, Garbage Collection Overhead, private communication, August, 1983.
	16	John K. Foderaro , Richard J. Fateman, Characterization of VAX Macsyma, Proceedings of the fourth ACM symposium on Symbolic and algebraic computation, p.14-19, August 05-07, 1981, Snowbird, Utah, United States [doi>10.1145/800206.806364]
	17	Adele Goldberg , David Robson, Smalltalk-80: the language and its implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
	18	D. H. H. Ingalls, The Evolution of the Smalltalk Virtual Machine, in Smalltalk-80: Bits of History, Words of Advice, G. Krasner (editor), Addison Wesley, September, 1983, 9-28.
	19	T. Kaehler and G. Krasner, LOOM-Large Object-Oriented Memory for Smalltalk-80 Systems, in Smalltalk-80: Bits of History, Words of Advice, G. Krasner (editor), Addison-Wesley, Reading, MA, 1983, 249.
	20	T. Kilburn, D. B. G. Edwards, M. J. Lanigan and F. H. Sumner, One-Level Storage System, in Computer Structures: Principles and Examples, D. P. Siewiorek, C. G. Bell and A. Newell (editor), McGraw-Hill, New York, NY, 1982, 135-148. Originally in IRE Transactions, EC-11, vol 2, April 1962, pp 223-235.
	21	M. Klein and P. Foley, Preliminary SOAR Architecture, in Smalltalk on a RISC: Architectural Investigations, D. Patterson (editor), Computer Science Division, Department of E.E.C.S., University of California, Berkeley, CA, April, 1983, 1-24.
	22	Donald E. Knuth, The Art of Computer Programming Volumes 1-3 Boxed Set, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
	23	Henry Lieberman , Carl Hewitt, A real-time garbage collector based on the lifetimes of objects, Communications of the ACM, v.26 n.6, p.419-429, June 1983 [doi>10.1145/358141.358147]
	24	W. Lonergan and P. King, Design of the B 5500 System, in Computer Structures: Principles and Examples, D. P. Siewiorek, C. G. Bell and A. Newell (editor), McGraw-Hill, New York, NY, 1982, 129-134. Originally in Datamation, vol. 7, no. 5, May 1961. pp 28-32.
	25	K. McCall, The Smalltalk-80 Benchmarks, in Smalltalk 80: Bits of History, Words of Advice, G. Krasner (editor), Addison-Wesley, Reading, MA, 1983, 151-173.
	26	John McCarthy, Recursive functions of symbolic expressions and their computation by machine, Part I, Communications of the ACM, v.3 n.4, p.184-195, April 1960 [doi>10.1145/367177.367199]
	27	D. A. Patterson, Smalltalk on a RISC: Architectural Investigations, Computer Science Division, University of California, Berkeley, CA, April 1983. Proceedings of CS292R.
	28	B. Sheil, Environments for Exploratory Programming, Datamation, February, 1983.
	29	J. W. Stamos, A Large Object-Oriented Virtual Memory: Grouping Strategies, Measurements, and Performance, Xerox technical report, SCG-82-2, Xerox, Pals Alto Research Center, Pals Alto, CA, May 1982.
	30	Thomas A. Standish, Data Structure Techniques, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1980
	31	A. J. Thadhani, Interactive User Productivity, IBM Systems Journal 20, 4 (1981), 407-421.
	32	D. M. Ungar and D. A. Patterson, Berkeley Smalltalk: Who Knows Where the Time Goes?, in Smalltalk-80: Bits of History, Word of Advice, G. Krasner (editor), September, 1983, 189.
	33	David Ungar , Ricki Blau , Peter Foley , Dain Samples , David Patterson, Architecture of SOAR: Smalltalk on a RISC, Proceedings of the 11th annual international symposium on Computer architecture, p.188-197, January 1984
	34	Jon L. White, Address/memory management for a gigantic LISP environment or, GC considered harmful, Proceedings of the 1980 ACM conference on LISP and functional programming, p.119-127, August 25-27, 1980, Stanford University, California, United States [doi>10.1145/800087.802797]