David Ungar
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.
- 1.S. Baden, High Performance Storage Reclamation in an Object-Based Memory System, Master's Report, Computer Science Division, Department of E.E.C.S, University of California, Berkeley, Berkeley, CA, June 9, 1982. Google Scholar
Digital Library
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 5.R. Blau, Paging on an Object-Oriented Personal Computer, Proceedings of the ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, Minneapolis, MN, August, 1983. Google ScholarDigital Library
- 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.Google Scholar
- 7.J. Cohen, Garbage collection of Linked Data Structures, ACM Computing Surveys 13, 3 (Sept. 1981), 341-367. Google ScholarDigital Library
- 8.G. E. Collins, A Method for Overlapping and Erasure of Lists, Comm. of the ACM 3, 12 (1960), 655-657. Google ScholarDigital Library
- 9.P. J. Denning, Virtual Memory, Computing Surveys 2, 3 (September, 1970), 153-189. Google ScholarDigital Library
- 10.L. P. Deutsch and D. G. Bobrow, An Efficient Incremental Automatic Garbage Collector, Comm. of the ACM 19, 9 (September 1976), 522-526. Google ScholarDigital Library
- 11.L. P. Deutsch, An Upper Bound for Smalltalk-80 Execution on a Motorola 68000 CPU, private communications, 1982.Google Scholar
- 12.L. P. Deutsch, Storage Reclamation, Berkeley Smalltalk Seminar, Feb. 5, 1982.Google Scholar
- 13.L. P. Deutsch, Storage Management, private communications, 1983.Google Scholar
- 14.L. P. Deutsch and A. M. Schiffman, Efficient Implementation of the Smalltalk-80 System, Proceedings of the 11th Annual ACM SIGACT News-SIGPLAN Notices Symposium on the Principles of Programming Languages, Salt Lake City, Utah, January, 1984. Google ScholarDigital Library
- 15.R. Fateman, Garbage Collection Overhead, private communication, August, 1983.Google Scholar
- 16.J. K. Foderaro and R. J. Fateman, Characterization of VAX Macsyma, Proceedings of the 1981 ACM Symposium on Symbolic and Algebraic Computation, Berkeley, CA, 1981, 14-19. Google ScholarDigital Library
- 17.A. J. Goldberg and D. Robson, Smalltalk-80: The Language and Its Implementation, Addison-Wesley Publishing Company, Reading, MA, 1983. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 22.D. Knuth, The Art of Computer Programming, Addison-Wesley, Reading, Mass., 1973. Google ScholarDigital Library
- 23.H. Lieberman and C. Hewitt, A Real-Time Garbage Collector Based on the Lifetimes of Objects, Comm. of the ACM 26, 6 419-429. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- 26.J. McCarthy, Recursive Functions of Symbolic Expressions and Their Computation by Machine, I, Comm. of the ACM 3 (1960), 184-195. Google ScholarDigital Library
- 27.D. A. Patterson, Smalltalk on a RISC: Architectural Investigations, Computer Science Division, University of California, Berkeley, CA, April 1983. Proceedings of CS292R.Google Scholar
- 28.B. Sheil, Environments for Exploratory Programming, Datamation, February, 1983.Google Scholar
- 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.Google Scholar
- 30.T. A. Standish, Data Structure Techniques, Addison-Wesley, Reading, Mass., 1980. Google ScholarDigital Library
- 31.A. J. Thadhani, Interactive User Productivity, IBM Systems Journal 20, 4 (1981), 407-421.Google ScholarDigital Library
- 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.Google Scholar
- 33.D. Ungar, R. Blau, P. Foley, D. Samples and D. Patterson, Architecture of SOAR: Smalltalk on a RISC, Eleventh Annual International Symposium on Computer Architecture, Ann Arbor, MI, June, 1984. Google ScholarDigital Library
- 34.J. L. White, Address/Memory Management For A Gigantic LISP Environment or, GC Considered Harmful, Conference Record of the 1980 LISP Conference, Redwood Estates, CA, 1980, 119-127. Google ScholarDigital Library
Index Terms
- Generation Scavenging: A non-disruptive high performance storage reclamation algorithm
Recommendations
Generation Scavenging: A non-disruptive high performance storage reclamation algorithm
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 ...
Generation Scavenging: A non-disruptive high performance storage reclamation algorithm
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 ...
Offline GC: trashing reachable objects on tiny devices
SenSys '11: Proceedings of the 9th ACM Conference on Embedded Networked Sensor SystemsThe ability of tiny embedded devices to run large and feature-rich Java programs is typically constrained by the amount of memory installed on those devices. Furthermore, the useful operation of such devices in a wireless sensor application is limited ...
Comments