skip to main content
10.1145/1993478.1993493acmconferencesArticle/Chapter ViewAbstractPublication PagesismmConference Proceedingsconference-collections
research-article

Short-term memory for self-collecting mutators

Published: 04 June 2011 Publication History

Abstract

We propose a new memory model called short-term memory for managing objects on the heap. In contrast to the traditional persistent memory model for heap management, objects in short-term memory expire after a finite amount of time, which makes deallocation unnecessary. Instead, expiration of objects may be extended, if necessary, by refreshing. We have developed a concurrent, incremental, and non-moving implementation of short-term memory for explicit refreshing called self-collecting mutators that is based on programmer-controlled time and integrated into state-of-the-art runtimes of three programming languages: C, Java, and Go. All memory management operations run in constant time without acquiring any locks modulo the underlying allocators. Our implementation does not require any additional heap management threads, hence the name. Expired objects may be collected anywhere between one at a time for maximal incrementality and all at once for maximal throughput and minimal memory consumption. The integrated systems are heap management hybrids with persistent memory as default and short-term memory as option. Our approach is fully backwards compatible. Legacy code runs without any modifications with negligible runtime overhead and constant per-object space overhead. Legacy code can be modified to take advantage of short-term memory by having some but not all objects allocated in short-term memory and managed by explicit refreshing. We study single- and multi-threaded use cases in all three languages macro-benchmarking C and Java and micro-benchmarking Go. Our results show that using short-term memory (1) simplifies heap management in a state-of-the-art H.264 encoder written in C without additional time and minor space overhead, and (2) improves, at the expense of safety, memory management throughput, latency, and space consumption by reducing the number of garbage collection runs, often even to zero, for a number of Java and Go programs.

References

[1]
AIGNER, M., HAAS, A., KIRSCH, C. M., AND SOKOLOVA, A. Short-term memory for self-collecting mutators - revised version. Tech. Rep. 2010-06, Department of Computer Sciences, University of Salzburg, October 2010.
[2]
AIGNER, M., HAAS, A., AND LIPPAUTZ, M. Short-term memory implementation for C, Java, and Go, 2010. http://tiptoe.cs.uni-salzburg.at/ short-term-memory/.
[3]
ALPERN, B., ATTANASIO, C. R., BARTON, J. J., BURKE, M. G., CHENG, P., CHOI, J.-D., COCCHI, A., FINK, S. J., GROVE, D., HIND, M., HUMMEL, S. F., LIEBER, D., LITVINOV, V., MERGEN, M. F., NGO, T., RUSSELL, J. R., SARKAR, V., SERRANO, M. J., SHEPHERD, J. C., SMITH, S. E., SREEDHAR, V. C., SRINIVASAN, H., AND WHALEY, J. The Jalapeño virtual machine. IBM Syst. J. 39, 1 (2000), 211--238.
[4]
BACON, D. F., CHENG, P., AND RAJAN, V. T. A real-time garbage collector with low overhead and consistent utilization. In Proc. POPL (2003), ACM.
[5]
BACON, D. F., CHENG, P., AND RAJAN, V. T. A unified theory of garbage collection. In Proc. OOPSLA (2004), ACM.
[6]
BLACKBURN, S. M., AND MCKINLEY, K. S. Immix: a mark-region garbage collector with space efficiency, fast collection, and mutator performance. In Proc. PLDI (2008), ACM.
[7]
BOND, M. D., AND MCKINLEY, K. S. Leak pruning. In Proc. ASPLOS (2009), ACM.
[8]
CHEREM, S., AND RUGINA, R. Compile-time deallocation of individual objects. In Proc. ISMM (2006), ACM.
[9]
COLLINS, G. E. A method for overlapping and erasure of lists. Commun. ACM 3, 12 (1960), 655--657.
[10]
CORMEN, T. H., LEISERSON, C. E., RIVEST, R. L., AND STEIN, C. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001, ch. 6.5: Priority queues, pp. 138--142.
[11]
CRACIUNAS, S., KIRSCH, C. M., PAYER, H., SOKOLOVA, A., STADLER, H., AND STAUDINGER, R. A compacting real-time memory management system. In Proc. USENIX ATC (2008).
[12]
FRASER, K. Practical Lock-Freedom. PhD thesis, Computer Laboratory, University of Cambridge, 2003.
[13]
GAY, D., AND AIKEN, A. Memory management with explicit regions. In Proc. PLDI (1998), ACM.
[14]
GUYER, S. Z., MCKINLEY, K. S., AND FRAMPTON, D. Free-me: a static analysis for automatic individual object reclamation. In Proc. PLDI (2006), ACM.
[15]
JUMP, M., AND MCKINLEY, K. S. Cork: dynamic memory leak detection for garbage-collected languages. In Proc. POPL (2007), ACM.
[16]
KOCHAN, S. Programming in Objective-C 2.0, 2nd ed. Addison-Wesley Professional, 2009.
[17]
MASMANO, M., RIPOLL, I., CRESPO, A., AND REAL, J. TLSF: A new dynamic memory allocator for real-time systems. In Proc. ECRTS (2004), IEEE Computer Society, pp. 79--86.
[18]
MATHEW, J. A., CODDINGTON, P. D., AND HAWICK, K. A. Analysis and development of Java Grande benchmarks. In Proc. JAVA (1999), ACM.
[19]
MCCARTHY, J. Recursive functions of symbolic expressions and their computation by machine, Part I. Commun. ACM 3, 4 (1960), 184--195.
[20]
MERRITT, L., AND VANAM, R. X264: A high performance H.264/AVC encoder, 2006.
[21]
NGUYEN, H. H., AND RINARD, M. Detecting and eliminating memory leaks using cyclic memory allocation. In Proc. ISMM (2007), ACM.
[22]
OGATA, K., ONODERA, T., KAWACHIYA, K., KOMATSU, H., AND NAKATANI, T. Replay compilation: improving debuggability of a just-in-time compiler. In Proc. OOPSLA (2006), ACM.
[23]
TANENBAUM, A. S. Modern Operating Systems. Prentice Hall, 2001.
[24]
TOFTE, M., AND TALPIN, J.-P. Region-based memory management. Inf. Comput. 132, 2 (1997), 109--176.
[25]
WIEGAND, T., SULLIVAN, G. J., BJØNTEGAARD, G., AND LUTHRA, A. Overview of the H.264/AVC video coding standard. IEEE Transactions on Circuits and Systems for Video Technology 13, 7 (2003).
[26]
http://mewiki.project357.com/wiki/x264_settings.

Cited By

View all
  • (2017)Selfie and the basicsProceedings of the 2017 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software10.1145/3133850.3133857(198-213)Online publication date: 25-Oct-2017
  • (2012)RETRACTED ARTICLE: A new compaction strategy for enhancing the utilization of reconfigurable chipsThe International Journal of Advanced Manufacturing Technology10.1007/s00170-012-4497-167:1-4(455-473)Online publication date: 19-Sep-2012
  • (2017)Selfie and the basicsProceedings of the 2017 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software10.1145/3133850.3133857(198-213)Online publication date: 25-Oct-2017

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
ISMM '11: Proceedings of the international symposium on Memory management
June 2011
148 pages
ISBN:9781450302630
DOI:10.1145/1993478
  • cover image ACM SIGPLAN Notices
    ACM SIGPLAN Notices  Volume 46, Issue 11
    ISMM '11
    November 2011
    135 pages
    ISSN:0362-1340
    EISSN:1558-1160
    DOI:10.1145/2076022
    Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 June 2011

Permissions

Request permissions for this article.

Check for updates

Author Tag

  1. explicit heap management

Qualifiers

  • Research-article

Conference

ISMM '11
Sponsor:
ISMM '11: International Symposium on Memory Management
June 4 - 5, 2011
California, San Jose, USA

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)6
  • Downloads (Last 6 weeks)0
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2017)Selfie and the basicsProceedings of the 2017 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software10.1145/3133850.3133857(198-213)Online publication date: 25-Oct-2017
  • (2012)RETRACTED ARTICLE: A new compaction strategy for enhancing the utilization of reconfigurable chipsThe International Journal of Advanced Manufacturing Technology10.1007/s00170-012-4497-167:1-4(455-473)Online publication date: 19-Sep-2012
  • (2017)Selfie and the basicsProceedings of the 2017 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software10.1145/3133850.3133857(198-213)Online publication date: 25-Oct-2017

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media