Memory subsystem performance of programs using copying garbage collection

ABSTRACT

Heap allocation with copying garbage collection is believed to have poor memory subsystem performance. We conducted a study of the memory subsystem performance of heap allocation for memory subsystems found on many machines. We found that many machines support heap allocation poorly. However, with the appropriate memory subsystem organization, heap allocation can have good memory subsystem performance.

REFERENCES

• 1: Andrew W. Appel, Garbage collection can be faster than stack allocation, Information Processing Letters, v.25 n.4, p.275-279, June 17, 1987 [doi>10.1016/0020-0190(87)90175-X]
• 2: Andrew W. Appel, A runtime system, Lisp and Symbolic Computation, v.3 n.4, p.343-380, Nov. 1990 [doi>10.1007/BF01807697]
• 3: Andrew W. Appel, Compiling with continuations, Cambridge University Press, New York, NY, 1992
• 4: Andrew W. Appel. Personal Communication. March 22 1993.
• 5: A. W. Appel , T. Jim, Continuation-passing, closure-passing style, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.293-302, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75303]
• 6: Andrew W. Appel, James S. Mattson, and David Tarditi. A lexical analyzer generator for Standard ML. Distributed with Standard ML of New Jersey, 1989.
• 7: Thomas Ball , James R. Larus, Optimally profiling and tracing programs, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.59-70, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143180]
• 8: Anita Borg, R. E. Kessler, Georgia Lazana, and David W. Wall. Long address traces from RISC machines: Generation and analysis. Technical Report 89/14, DEC Western Research Laboratory, September 1989.
• 9: Brian Case. PA-RISC provides rich instruction set within RISC framework. Microprocessor Report, 5(6), April 1991.
• 10: J. Bradley Chen , Brian N. Bershad, The impact of operating system structure on memory system performance, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.120-133, December 05-08, 1993, Asheville, North Carolina, United States
• 11: 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]
• 12: Rance Cleaveland , Joachim Parrow , Bernhard Steffen, The concurrency workbench: a semantics-based tool for the verification of concurrent systems, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.1, p.36-72, Jan. 1993 [doi>10.1145/151646.151648]
• 13: W. P. Crowley, C. P. Hendrickson, and T. E. Rudy. The SIMPLE code. Technical Report UCID 17715, Lawrence Livermore Laboratory, Livermore, CA, February 1978.
• 14: Cypress Semiconductor, Ross Technology Subsidiary. SPARC RISC User's Guide, second edition, February 1990.
• 15: Digital Equipment Corporation. DS5000/200 KN02 System Module Functional Specification.
• 16: Digital Equipment Corporation, Palo Alto, CA. DECStation 3100 Desktop Workstation Function Specification, 1.3 edition, August 1990.
• 17: Amer Diwan, David Tarditi, and Eliot Moss. Memory subsystem performance of programs with intensive heap allocation. Work in progress, oct 1993.
• 18: 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]
• 19: R. Hieb , R. Kent Dybvig , Carl Bruggeman, Representing control in the presence of first-class continuations, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.66-77, June 1990, White Plains, New York, United States
• 20: Mark D. Hill, A Case for Direct-Mapped Caches, Computer, v.21 n.12, p.25-40, December 1988 [doi>10.1109/2.16187]
• 21: M. D. Hill , A. J. Smith, Evaluating Associativity in CPU Caches, IEEE Transactions on Computers, v.38 n.12, p.1612-1630, December 1989 [doi>10.1109/12.40842]
• 22: Norman P. Jouppi, Cache write policies and performance, Proceedings of the 20th annual international symposium on Computer architecture, p.191-201, May 16-19, 1993, San Diego, California, United States
• 23: Gerry Kane , Joe Heinrich, MIPS RISC architectures, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 24: Philip J. Koopman, Jr. , Peter Lee , Daniel P. Siewiorek, Cache behavior of combinator graph reduction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.14 n.2, p.265-297, April 1992 [doi>10.1145/128861.128867]
• 25: David Kranz , Norman Adams , Richard Kelsey , Jonathan Rees , Paul Hudak , James Philbin, ORBIT: an optimizing compiler for scheme, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.219-233, June 25-27, 1986, Palo Alto, California, United States
• 26: J. R. Larus, Abstract execution: a technique for efficiently tracing programs, Software—Practice & Experience, v.20 n.12, p.1241-1258, Dec. 1990 [doi>10.1002/spe.4380201205]
• 27: James R. Larus and Thomas Ball. Rewriting executable files to measure program behavior. Technical Report Wis 1083, Computer Sciences Department, University of Wisconsin-Madison, March 1992.
• 28: 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]
• 29: R.L. Mattson, J. Gecsei, D. R. Slutz, and I. L. Traiger. Evaluation techniques for storage hierarchies. IBM Systems Journal, 9(2), 1970.
• 30: Robin Milner , Mads Tofte , Robert Harper, The definition of Standard ML, MIT Press, Cambridge, MA, 1990
• 31: Chih-Jui Peng and Gurindar S. Sohi. Cache memory design considerations to support languages with dynamic heap allocation. Technical Report 860, Computer Sciences Department, University of Wisconsin-Madison, July 1989.
• 32: Steven A. Przybylski, Cache and memory hierarchy design: a performance-directed approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 33: Chris Reade, Elements of functional programming, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 34: J Rees , W Clinger, Revised report on the algorithmic language scheme, ACM SIGPLAN Notices, v.21 n.12, p.37-79, Dec. 1986 [doi>10.1145/15042.15043]
• 35: Michael Slater. PA workstations set price/performance records. Microprocessor Report, 5(6), April 1991.
• 36: David Tarditi and Andrew W. Appel. ML-YACC, version 2.0. Distributed with Standard ML of New Jersey, April 1990.
• 37: Kevin G. Waugh, Patrick McAndrew, and Greg Michaelson. Parallel implementations from function prototypes: a case study. Technical Report Computer Science 90/4, Heriot-Watt University, Edinburgh, August 1990.
• 38: Paul R. Wilson, Michael S. Lam, and Thomas G. Moher. Caching considerations for generational garbage collection: a case for large and set-associative caches. Technical Report EECS-90-5, University of Illinios at Chicago, December 1990.
• 39: Paul R. Wilson , Michael S. Lam , Thomas G. Moher, Caching considerations for generational garbage collection, Proceedings of the 1992 ACM conference on LISP and functional programming, p.32-42, June 22-24, 1992, San Francisco, California, United States
• 40: Benjamin Zorn. The effect of garbage collection on cache performance. Technical Report CU-CS-528-91, University of Colorado at Boulder, May 199 i.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.3 Performance Analysis and Design Aids**
          Subjects: Simulation**

  D. Software
  D.3 PROGRAMMING LANGUAGES
  D.4 OPERATING SYSTEMS

General Terms:
Measurement, Performance, Theory