An adaptive tenuring policy for generation scavengers

ABSTRACT

One of the more promising automatic storage reclamation techniques, generation scavenging, suffers poor performance if many objects live for a fairly long time and then die. We have investigated the severity of this problem by simulating a two-generation scavenger using traces taken from actual 4-h sessions. There was a wide variation in the sample runs, with garbage-collection overhead ranging from insignificant, during three of the runs, to severe, during a single run. All runs demonstrated that performance could be improved with two techniques: segregating large bitmaps and strings, and adapting the scavenger's tenuring policy according to demographic feedback. We therefore incorporated these ideas into a commercial Smalltalk implementation. These two improvements deserve consideration for any storage reclamation strategy that utilizes a generation scavenger.

REFERENCES

• 1: BAKER, H. G. List processing in real time on a serial computer. A i Working Paper 139, MIT-AI Lab., Boston, Mass., Apr. 1977.
• 2: BECK, K. Private communication, Mar. 1988.
• 3: C. Chambers , D. Ungar , E. Lee, An efficient implementation of SELF a dynamically-typed object-oriented language based on prototypes, Conference proceedings on Object-oriented programming systems, languages and applications, p.49-70, October 02-06, 1989, New Orleans, Louisiana, United States
• 4: 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]
• 5: BOSWORTH, G. Private communication, Mar. 1988.
• 6: BROWNBmD6E, D R. Recursive structures in computer systems Ph D dissertation, University of Newcastle upon Tyne, Sept. 1984.
• 7: CAUDmL, P. J., AND Wn~Fs-BRocK, A. A third generation Smalltalk-80 implementatlon. ACM SIGPLAN Not~ces 21, 11 (Nov. 86).
• 8: DEUTSCH, L.P. The Dorado Smalltalk-80 implementation: Hardware architecture's impact on software architecture. In G. Krasner, Ed., Smalltalk~80 Bits ofHistory, Words of Advice, Addison-Wesley, Reading, Mass., 1983, pp. 113-126.
• 9: 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]
• 10: 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]
• 11: FATEMAN, R.J. Private communication, 1983.
• 12: 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]
• 13: Adele Goldberg , David Robson, Smalltalk-80: the language and its implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 14: KAE~LER, T., AND KRASNER, G. LOOM Large object-oriented memory for Smalltalk-80 systems. In Smalltalk-80: Bits of Histor~, Words of Advice, G. Krasner, Ed., Addison-Welsey, Reading, Mass., 1983, pp. 251-271.
• 15: LEE, E. Object storage and inheritance for SELF, a prototype-based object-oriented programming language. Engineer's thesis, Stanford Univerity, Stanford, Calif., Dec. 1988.
• 16: 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]
• 17: 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]
• 18: David A. Moon, Architecture of the Symbolics 3600, Proceedings of the 12th annual international symposium on Computer architecture, p.76-83, June 17-19, 1985, Boston, Massachusetts, United States
• 19: SHAW, R. A. Empirical analysis of a Lisp system. Tech. Rep. CSL~TR-88-351, Stanford University, Stanford, Calif., Feb. 1988.
• 20: STAMOS, J. W. A large object-oriented virtual memory: Grouping, measurements, and performance. Tech. Rep. SCG-82-2, Xerox, PARC, Palo Alto, Calif., May 1982.
• 21: James W. Stamos, Static grouping of small objects to enhance performance of a paged virtual memory, ACM Transactions on Computer Systems (TOCS), v.2 n.2, p.155-180, May 1984 [doi>10.1145/190.194]
• 22: Thomas A. Standish, Data Structure Techniques, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1980
• 23: David Ungar, Generation Scavenging: A non-disruptive high performance storage reclamation algorithm, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.157-167, April 1984
• 24: David Michael Ungar, The design and evaluation of a high performance Smalltalk system, MIT Press, Cambridge, MA, 1987
• 25: David Ungar , Frank Jackson, Tenuring policies for generation-based storage reclamation, Conference proceedings on Object-oriented programming systems, languages and applications, p.1-17, September 25-30, 1988, San Diego, California, United States
• 26: David Ungar , Randall B. Smith, Self: The power of simplicity, Conference proceedings on Object-oriented programming systems, languages and applications, p.227-242, October 04-08, 1987, Orlando, Florida, United States
• 27: P. R. Wilson , T. G. Moher, Design of the opportunistic garbage collector, Conference proceedings on Object-oriented programming systems, languages and applications, p.23-35, October 02-06, 1989, New Orleans, Louisiana, United States
• 28: Benjamin G. Zorn, Comparative Performance Evaluation of, University of California at Berkeley, Berkeley, CA, 1989

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.6 Programming Environments
          Subjects: Interactive environments
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Smalltalk; Self
      D.3.4 Processors
          Subjects: Run-time environments

General Terms:
Algorithms, Languages, Measurement, Performance, Theory