Memory system performance of programs with intensive heap allocation

ABSTRACT

Heap allocation with copying garbage collection is a general storage management technique for programming languages. It is believed to have poor memory system performance. To investigate this, we conducted an in-depth study of the memory system performance of heap allocation for memory systems found on many machines. We studied the performance of mostly functional Standard ML programs which made heavy use of heap allocation. We found that most machines support heap allocation poorly. However, with the appropriate memory system organization, heap allocation can have good performance. The memory system property crucial for achieving good performance was the ability to allocate and initialize a new object into the cache without a penalty. This can be achieved by having subblock by placement with a subblock size of one word with a write-allocate policy, along with fast page-mode writes or a write buffer. For caches with subblock placement, the data cache overhead was under 9% for a 64K or larger data cache; without subblock placement the overhead was often higher than 50%.

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: A. W. Appel, Simple generational garbage collection and fast allocation, Software—Practice & Experience, v.19 n.2, p.171-183, February 1989 [doi>10.1002/spe.4380190206]
• 3: Andrew W. Appel, A runtime system, Lisp and Symbolic Computation, v.3 n.4, p.343-380, Nov. 1990 [doi>10.1007/BF01807697]
• 4: Andrew W. Appel, Compiling with continuations, Cambridge University Press, New York, NY, 1992
• 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: APPEL, A. W., MATTSON, J. S., AND TARDITI, D. 1989. A lexical analyzer generator for Standard ML. User manual distributed with Standard ML of New Jersey.
• 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: 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
• 9: 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]
• 10: 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]
• 11: CROWLEY, W. P., HENDRICKSON, C. P., AND RUDY, T. E. 1978. The SIMPLE code. Tech. Rep. UCID 17715, Lawrence Livermore Laboratory, Livermore, Calif. Feb.
• 12: CYPRESS. 1990. SPARC R{SC User's Grade, 2nd ed. Cypress Semiconductor, San Jose, Calif.
• 13: DEC. 1990a. DS5000/200 KN02 System Module Functtonal Specification. Digital Equipment Corp., Palo Alto, Calif.
• 14: DEC. 1990b. DECStation 3100 Desktop Workstation Functzon Specificatzon, 1 3 ed. Digital Equipment Corp., Palo Alto, Calif.
• 15: DEC. 1992. DECchip 21064-AA M~croprocessor Hardware Reference Manual, 1st ed. Digital Equipment Corp., Maynard, Mass.
• 16: EKANADHAM, K. AND ARVIND. 1987. SIMPLE: An exercise in future scientific programming. Tech. Rep. Computation Structures Group Memo 273, MIT, Cambridge, Mass. July. Also available as IBM/T. J. Watson Research Center Research Rep. 12686.
• 17: 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]
• 18: 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
• 19: Mark D. Hill, A Case for Direct-Mapped Caches, Computer, v.21 n.12, p.25-40, December 1988 [doi>10.1109/2.16187]
• 20: 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]
• 21: 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
• 22: I4ANE, G. AND HEINRICI~, J. 1992. MIPS RISC Architecture. Prentice-Hall, Englewood Cliffs, N.J.
• 23: R. E. Kessler , Mark D. Hill, Page placement algorithms for large real-indexed caches, ACM Transactions on Computer Systems (TOCS), v.10 n.4, p.338-359, Nov. 1992 [doi>10.1145/138873.138876]
• 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: LARUS, J. R. AND BALL, T. 1992. Rewriting executable files to measure program behavior. Tech. Rep. Wis 1083, Computer Sciences Dept., Univ. of Wisconsin-Madison, Madison, Wisc. Mar.
• 28: MmNER, R., TOFTE, M., AND HARPER, R. 1990. The Definitwn of Standard ML. MIT Press, Cambridge, Mass.
• 29: David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 30: PENG, C.-J. AND SOHI, G. S. 1989. Cache memory design considerations to support languages with dynamic heap allocation. Tech. Rep. 860, Computer Sciences Dept., Univ. of Wisconsin- Madison, Madison, Wisc. July.
• 31: Steven A. Przybylski, Cache and memory hierarchy design: a performance-directed approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 32: Chris Reade, Elements of functional programming, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 33: Mark Baldwin Reinhold, Cache performance of garbage-collected programming languages, Massachusetts Institute of Technology, Cambridge, MA, 1993
• 34: SLATER, M. 1991. PA workstations set price/performance records. Microprocess. Rep. 5, 6 (Apr.), 1.
• 35: T~nm, D. AND APPEL, A. W. 1990. ML-YACC, version 2.0. Distributed with Standard ML of New Jersey. Software.
• 36: TARDITI, D. AND DIWAN, A. 1993. The full cost of a generational copying garbage collection implementation. In OOPSLA '93 Workshop on Memory Management and Garbage Collection. ACM, New York.
• 37: WAUGH, K. G., McANDREW, P., AND MIC~LSON, G. 1990. Parallel implementations from function prototypes: A case study. Tech. Rep. Computer Science 90/4, Heriot-Watt Univ., Edinburgh, U.K.
• 38: Wmso~, P. R., L~, M. S., AND MOHER, T. G. 1990. Caching considerations for generational garbage collection: A case for large and set-associative caches. Tech. Rep. EECS-90-5, Univ. of Illinois at Chicago, Chicago, Ill. Dec.
• 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: ZoRn, B. 1991. The effect of garbage collection on cache performance. Tech. Rep. CU-CS-528-91, Univ. of Colorado at Boulder, Boulder, Colo. May.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Dynamic storage management

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories; Associative memories
      B.3.3 Performance Analysis and Design Aids**
          Subjects: Simulation**

  C. Computer Systems Organization

  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.3 PROGRAMMING LANGUAGES

General Terms:
Experimentation, Languages, Measurement, Performance

Keywords:
automatic storage reclamation, copying garbage collection, garbage collection, generational garbage collection, heap allocation, page mode, subblock placement, write through, write-back, write-buffer, write-miss policy, write-policy