article

Free access

Memory system performance of programs with intensive heap allocation

Editor: Kenneth P. Birman Authors:

Eliot MossAuthors Info & Claims

ACM Transactions on Computer Systems (TOCS), Volume 13, Issue 3

Pages 244 - 273

https://doi.org/10.1145/210126.210129

Published: 01 August 1995 Publication History

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]

APPEL, A. W. 1987. Garbage collection can be faster than stack allocation. Inf. Process. Lett. 25, 4, 275-279.

[2]

APPEL, A. W. 1989. Simple generational garbage collection and fast allocation. Softw. Pract. Exper. 19, 2 (Feb.l, 171-184.

[3]

APPEL, A. W. 1990. A runtime system. L~sp Symb. Comput. 3, 4 (Nov.), 343-380.

[4]

APPEL, A. W. 1992. Compiling with Continuations. Cambridge University Press, Cambridge, Mass.

[5]

APPEL, A. W. AND JIM, T. Y. 1989. Continuation-passing, closure-passing style. In Proceedings of the 16th Annual ACM Symposium on Principles of Programming Languages (Austin, Tex.). ACM, New York, 293-302.

[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]

BALL, T. AND LARUS, J. R. 1992. Optimally profihng the tracing programs. In the 19th Symposzum on Principles of Programming Languages. ACM, New York.

[8]

CHEN, J. B. AND BERSHAD, g. N. 1993. The impact of operating system structure on memory system performance. In the 14th Symposium on Operating Systems Principles ACM, New York.

[9]

CHENE~, C. 1970. A nonrecursive list compacting algorithm Commun ACM 13, 11 (Nov.), 677 678.

[10]

CLEAVELAND, R., PARROW, J., AND STEFFEN, g. 1993. The Concurrency Workbench: A semanticsbased tool for the verification of concurrent systems. ACM Trans. Program. Lang. Syst. 15, 1 (Jan.), 36-72.

[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]

FENICHEL, R. R. AND YOCHELSON, J. C. 1969. A LISP garbage-collector for virtual-memory computer systems Commun. ACM 12, 11 (Nov.), 611-612.

[18]

HIEB, R., DYBVIG, R. K., AND BRUGGEMAN, C. 1990. Representing control in the presence of first-class continuations. In Proceedings of the SIGPLAN '90 Conference on Programming Language Design and Implementatton (White Plains, N Y.). ACM, New York, 66 77.

[19]

HILL, M. D. 1988. A case for direct mapped caches. Computer 21, 12 (Dec.), 25-40.

[20]

HILL, M. AND SMITH, A. 1989. Evaluating associativity in CPU caches. IEEE Trans. Comput. 38, 12 (Dec.), 1612 1630.

[21]

JouPPI, N. P. 1993. Cache write policies and performance. In Proceedings of the 20th Annual International Symposium on Computer Architecture (San Diego, Calif.). ACM Press, New York, 191 201.

[22]

I4ANE, G. AND HEINRICI~, J. 1992. MIPS RISC Architecture. Prentice-Hall, Englewood Cliffs, N.J.

[23]

KESSLER, R. E. ~3~D HmL, M. D. 1992. Page placement algorithms for large real-indexed caches. ACM Trans. Comput. Syst. 10, 4 (Nov.), 338-359.

[24]

KOOPMAN, P. J., JR., LEE, P., AND SIEWIOREK, D. P. 1992. Cache behavior of combinator graph reduction. ACM Trans. Program. Lang. Syst. 14, 2 (Apr.), 265-277.

[25]

KRANz, D., KELSE~, R., REES, J., HUDAK, P., PHmBI~, J., ANo ADAMS, N. 1986. ORBIT: An optimizing compiler for Scheme. In Proceedings of the SIGPLAN '86 Conference Symposium on Compiler Construction (Palo Alto, Calif.). ACM, New York, 219-233.

[26]

LARUS, J. R. 1990. Abstract execution: A technique for efficiently tracing programs. Softw. Pract. Exper. 20, 12 (Dec.), 1241-1258.

[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]

PATTERSON, D. A. AND HENNESSY, J. L. 1990. Computer Architecture: A Quantitative Approach. Morgan Kaufmann, San Mateo, Calif.

[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]

PRZ~S~, S. A. 1990. Cache and Memory Hierarchy Destgn: A Performance-Directed Approach. Morgan Kaufmann, San Mateo, Calif.

[32]

READE, C. 1989. Elements of Functional Programming. Addison-Wesley, Reading, Mass.

[33]

REINHOLD, M. B. 1993. Cache performance of garbage-collected programming languages. Ph.D. thesis, Laboratory for Computer Science, MIT, Cambridge, Mass.

[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]

WmSON, P. R., L~vr, M. S., AND MOHER, T. G. 1992. Caching considerations for generational garbage collection. In the 1992 ACM Conference on Lisp and Functional Programming (San Francisco, Calif.). ACM, New York, 32-42.

[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.

Cited By

Chen H(2008)Design of a low‐power way‐predicting cache using valid‐bit pre‐decision strategyJournal of the Chinese Institute of Engineers10.1080/02533839.2008.967143431:5(805-814)Online publication date: Jul-2008
https://doi.org/10.1080/02533839.2008.9671434
Grossman D(2007)The transactional memory / garbage collection analogyACM SIGPLAN Notices10.1145/1297105.129708042:10(695-706)Online publication date: 21-Oct-2007
https://dl.acm.org/doi/10.1145/1297105.1297080
Grossman DGabriel RBacon DLopes CSteele G(2007)The transactional memory / garbage collection analogyProceedings of the 22nd annual ACM SIGPLAN conference on Object-oriented programming systems, languages and applications10.1145/1297027.1297080(695-706)Online publication date: 21-Oct-2007
https://dl.acm.org/doi/10.1145/1297027.1297080
Show More Cited By

Recommendations

A generational on-the-fly garbage collector for Java
PLDI '00: Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation

An on-the-fly garbage collector does not stop the program threads to perform the collection. Instead, the collector executes in a separate thread (or process) in parallel to the program. On-the-fly collectors are useful for multi-threaded applications ...
A generational on-the-fly garbage collector for Java

An on-the-fly garbage collector does not stop the program threads to perform the collection. Instead, the collector executes in a separate thread (or process) in parallel to the program. On-the-fly collectors are useful for multi-threaded applications ...
Memory Subsystem Performance of Programs with Intensive Heap Allocation

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Computer Systems

ACM Transactions on Computer Systems Volume 13, Issue 3

Aug. 1995

106 pages

ISSN:0734-2071

EISSN:1557-7333

DOI:10.1145/210126

Editor:
Kenneth P. Birman
Cornell Univ., Ithaca, NY

Issue’s Table of Contents

Copyright © 1995 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 1995

Published in TOCS Volume 13, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

51
Total Citations
View Citations
778
Total Downloads

Downloads (Last 12 months)141
Downloads (Last 6 weeks)20

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen H(2008)Design of a low‐power way‐predicting cache using valid‐bit pre‐decision strategyJournal of the Chinese Institute of Engineers10.1080/02533839.2008.967143431:5(805-814)Online publication date: Jul-2008
https://doi.org/10.1080/02533839.2008.9671434
Grossman D(2007)The transactional memory / garbage collection analogyACM SIGPLAN Notices10.1145/1297105.129708042:10(695-706)Online publication date: 21-Oct-2007
https://dl.acm.org/doi/10.1145/1297105.1297080
Grossman DGabriel RBacon DLopes CSteele G(2007)The transactional memory / garbage collection analogyProceedings of the 22nd annual ACM SIGPLAN conference on Object-oriented programming systems, languages and applications10.1145/1297027.1297080(695-706)Online publication date: 21-Oct-2007
https://dl.acm.org/doi/10.1145/1297027.1297080
Hirzel M(2007)Data layouts for object-oriented programsACM SIGMETRICS Performance Evaluation Review10.1145/1269899.125491535:1(265-276)Online publication date: 12-Jun-2007
https://dl.acm.org/doi/10.1145/1269899.1254915
Hirzel MGolubchik LAmmar MHarchol-Balter M(2007)Data layouts for object-oriented programsProceedings of the 2007 ACM SIGMETRICS international conference on Measurement and modeling of computer systems10.1145/1254882.1254915(265-276)Online publication date: 12-Jun-2007
https://dl.acm.org/doi/10.1145/1254882.1254915
Morrisett GCrary KGlew NWalker D(2006)Stack-based Typed Assembly LanguageTypes in Compilation10.1007/BFb0055511(28-52)Online publication date: 28-May-2006
https://doi.org/10.1007/BFb0055511
Reddy VSawyer RGehringer E(2006)A cache-pinning strategy for improving generational garbage collectionProceedings of the 13th international conference on High Performance Computing10.1007/11945918_15(98-110)Online publication date: 18-Dec-2006
https://dl.acm.org/doi/10.1007/11945918_15
Schmidt AJensen C(2006)Efficient maintenance of ephemeral dataProceedings of the 11th international conference on Database Systems for Advanced Applications10.1007/11733836_12(141-155)Online publication date: 12-Apr-2006
https://dl.acm.org/doi/10.1007/11733836_12
Hertz MBerger E(2005)Quantifying the performance of garbage collection vs. explicit memory managementACM SIGPLAN Notices10.1145/1103845.109483640:10(313-326)Online publication date: 12-Oct-2005
https://dl.acm.org/doi/10.1145/1103845.1094836
Hertz MBerger EJohnson RBaniassad EGabriel RNoble JMarick B(2005)Quantifying the performance of garbage collection vs. explicit memory managementProceedings of the 20th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications10.1145/1094811.1094836(313-326)Online publication date: 17-Oct-2005
https://dl.acm.org/doi/10.1145/1094811.1094836
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents