Article

The transactional memory / garbage collection analogy

Author:

Dan GrossmanAuthors Info & Claims

OOPSLA '07: Proceedings of the 22nd annual ACM SIGPLAN conference on Object-oriented programming systems, languages and applications

Pages 695 - 706

https://doi.org/10.1145/1297027.1297080

Published: 21 October 2007 Publication History

Abstract

This essay presents remarkable similarities between transactional memory and garbage collection. The connections are fascinating in their own right, and they let us better understand one technology by thinking about the corresponding issues for the other.

References

[1]

M. Abadi, C. Flanagan, and S. N. Freund. Types for safe locking: Static race detection for Java. ACM Transactions on Programming Languages and Systems, 28(2), 2006.

Digital Library

[2]

A.-R. Adl-Tabatabai, B. Lewis, V. Menon, B. R. Murphy, B. Saha, and T. Shpeisman. Compiler and runtime support for efficient software transactional memory. In ACM Conference on Programming Language Design and Implementation, 2006.

Digital Library

[3]

E. Allen, D. Chase, J. Hallet, V. Luchangco, J.-W. Maessen, S. Ryu, G. L. Steele Jr., and STobin-Hochstadt. The Fortress language specification, version 1.0β, Mar. 2007. http://research.sun.com/projects/plrg/fortress1.0beta.pdf.

[4]

C. S. Ananian, K. Asanovic, B. C. Kuszmaul, C. E. Leiserson, and S. Lie. Unbounded transactional memory. In 11th International Symposium on High--Performance Computer Architecture, 2005.

Digital Library

[5]

D. F. Bacon, P. Cheng, and V. T. Rajan. A unified theory of garbage collection. In ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications, 2004.

Digital Library

[6]

G. Bellella, editor. The Real-Time Specification for Java. Addison-Wesley, 2000.

Digital Library

[7]

S. M. Blackburn, P. Cheng, and K. S. McKinley. Myths and realities: The performance impact of garbage collection. In SIGMETRICS-Proceedings of the International Conference on Measurements and Modeling of Computer Systems, 2004.

Digital Library

[8]

C. Blundell, E. C. Lewis, and M. Martin. Subtleties of transactional memory atomicity semantics. Computer Architecture Letters, 5(2), 2006.

Digital Library

[9]

B. D. Carlstrom, J. Chung, A. McDonald, H. Chafi, C. Kozyrakis, and K. Olukotun. The Atomos transactional programming language. In ACM Conference on Programming Language Design and Implementation, 2006.

Digital Library

[10]

P. Charles, C. Grothoff, V. Saraswat, C. Donawa, A. Kielstra, K. Ebcioglu, Cvon Praun, and V. Sarkar. X10: An Object-Oriented approach to non-uniform cluster computing. In ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications, 2005.

Digital Library

[11]

Cray Inc. Chapel specification 0.4. http://chapel.cs.washington.edu/specification.pdf.

[12]

P. Damron, A. Fedorova, Y. Lev, V. Luchangco, M. Moir, and D. Nussbaum. Hybrid transactional memory. In International Conference on Architectural Support for Programming Languages and Operating Systems, 2006.

Digital Library

[13]

A. Diwan, D. Tarditi, and J. E. B. Moss. Memory system performance of programs with intensive heap allocation. ACM Transactions on Computer Systems, 13(3), 1995.

Digital Library

[14]

R. Ennals. Software transactional memory should not be lock free. Technical Report IRC-TR-06-052, Intel Research Cambridge, 2006. http://berkeley.intel-research.net/rennals/pubs/052RobEnnals.pdf.

[15]

C. Flanagan and S. Qadeer. A type and effect system for atomicity. In ACM Conference on Programming Language Design and Implementation, 2003.

Digital Library

[16]

D. Gay and A. Aiken. Language support for regions. In ACM Conference on Programming Language Design and Implementation, 2001.

Digital Library

[17]

D. Grossman. Safe Programming at the C Level of Abstraction. PhD thesis, Cornell University, 2003.

Digital Library

[18]

D. Grossman. Type-safe multithreading in Cyclone. In ACM Workshop on Types in Language Design and Implementation, 2003.

Digital Library

[19]

D. Grossman, J. Manson, and W. Pugh. What do high-level memory models mean for transactions? In ACM SIGPLAN Workshop on Memory Systems Performance & Correctness, 2006.

Digital Library

[20]

D. Grossman, G. Morrisett, T. Jim, M. Hicks, Y. Wang, and J. Cheney. Region-based memory management in Cyclone. In ACM Conference on Programming Language Design and Implementation, 2002.

Digital Library

[21]

N. Haines, D. Kindred, J. G. Morrisett, S. M. Nettles, and J. M. Wing. Composing first-class transactions. ACM Transactions on Programming Languages and Systems, 16(6), 1994.

Digital Library

[22]

N. Hallenberg, M. Elsman, and M. Tofte. Combining region inference and garbage collection. In ACM Conference on Programming Language Design and Implementation, 2002.

Digital Library

[23]

L. Hammond, B. D. Carlstrom, V. Wong, B. Hertzberg, M. Chen, C. Kozyrakis, and K. Olukotun. Programming with transactional coherence and consistency (TCC). In International Conference on Architectural Support for Programming Languages and Operating Systems, 2004.

Digital Library

[24]

T. Harris and K. Fraser. Language support for lightweight transactions. In ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications, 2003.

Digital Library

[25]

T. Harris, S. Marlow, S. P. Jones, and M. Herlihy. Composable memory transactions. In ACM Symposium on Principles and Practice of Parallel Programming, 2005.

Digital Library

[26]

T. Harris, S. Marlow, and S. Peyton Jones. Haskell on a shared-memory multiprocessor. In Proceedings of the 2005 ACM SIGPLAN Workshop on Haskell, 2005.

Digital Library

[27]

T. Harris, M. Plesko, A. Shinnar, and D. Tarditi. Optimizing memory transactions. In ACM Conference on Programming Language Design and Implementation, 2006.

Digital Library

[28]

M. Herlihy, V. Luchangco, and M. Moir. A flexible framework for implementing software transactional memory. In ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications, 2006.

Digital Library

[29]

M. Herlihy, V. Luchangco, M. Moir, and I. William N. Scherer. Software transactional memory for dynamic-sized data structures. In ACM Symposium on Principles of Distributed Computing, 2003.

Digital Library

[30]

M. Herlihy and J. E. B. Moss. Transactional memory: architectural support for lock-free data structures. In International Symposium on Computer Architecture, 1993.

Digital Library

[31]

M. Hertz and E. D. Berger. Quantifying the performance of garbage collection vs. explicit memory management. In ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications, 2005.

Digital Library

[32]

B. Hindman and D. Grossman. Atomicity via source-to-source translation. In ACM SIGPLAN Workshop on Memory Systems Performance & Correctness, 2006.

Digital Library

[33]

R. E. Jones. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. Wiley, 1996.

Digital Library

[34]

S. Kumar, M. Chu, C. J. Hughes, P. Kundu, and A. Nguyen. Hybrid transactional memory. In ACM Symposium on Principles and Practice of Parallel Programming, 2006.

Digital Library

[35]

J. R. Larus and R. Rajwar. Transactional Memory. Morgan & Claypool Publishers, 2006.

[36]

J. Manson, J. Baker, A. Cunei, S. Jagannathan, M. Prochazka, B. Xin, and J. Vitek. Preemptible atomic regions for real-time Java. In 26th IEEE Real-Time Systems Symposium, 2005.

Digital Library

[37]

V. J. Marathe, W. N. Scherer, and M. L. Scott. Adaptive software transactional memory. In International Symposium on Distributed Computing, 2005.

Digital Library

[38]

A. McDonald, J. Chung, B. D. Carlstrom, C. Cao Minh, H. Chafi, C. Kozyrakis, and K. Olukotun. Architectural semantics for practical transactional memory. In International Symposium on Computer Architecture, 2006.

Digital Library

[39]

M. M. Michael and M. L. Scott. Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. In ACM Symposium on Principles of Distributed Computing, 1996.

Digital Library

[40]

K. E. Moore, J. Bobba, M. J. Moravan, M. D. Hill, and D. A. Wood. LogTM: Log-based transactional memory. In 12th International Symposium on High- Performance Computer Architecture, 2006.

[41]

M. J. Moravan, J. Bobba, K. E. Moore, L. Yen, M. D. Hill, B. Liblit, M. M. Swift, and D. A. Wood. Supporting nested transactional memory in LogTM. In 12th International Conference on Architectural Support for Programming Languages and Operating Systems, 2006.

Digital Library

[42]

R. Rajwar, M. Herlihy, and K. Lai. Virtualizing transactional memory. In 32nd International Symposium on Computer Architecture, 2005.

Digital Library

[43]

J. H. Reppy. Concurrent Programming in ML. Cambridge University Press, 1999.

Digital Library

[44]

M. F. Ringenburg and D. Grossman. AtomCaml: First-class atomicity via rollback. In 10th ACM International Conference on Functional Programming, 2005.

Digital Library

[45]

N. Shavit and D. Touitou. Software transactional memory. Distributed Computing, Special Issue(10), 1997.

[46]

T. Shpeisman, V. Menon, A.-R. Adl-Tabatabai, S. Balensiefer, D. Grossman, R. Hudson, K. Moore, and B. Saha. Enforcing isolation and ordering in STM. In ACM Conference on Programming Language Design and Implementation, 2007.

Digital Library

[47]

M. Tofte and J.-P. Talpin. Region-based memory management. Information and Computation, 132(2), 1997.

Digital Library

[48]

P. R. Wilson. Uniprocessor garbage collection techniques. Technical report, University of Texas, 1994.

Digital Library

[49]

K. Zee and M. Rinard. Write barrier removal by static analysis. In ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications, 2002.

Digital Library

Cited By

Chen DLiu FJiao MDing CPai S(2019)Statistical caching for near memory managementProceedings of the International Symposium on Memory Systems10.1145/3357526.3357557(411-416)Online publication date: 30-Sep-2019
https://dl.acm.org/doi/10.1145/3357526.3357557
Bättig MGross T(2017)Synchronized-by-Default Concurrency for Shared-Memory SystemsACM SIGPLAN Notices10.1145/3155284.301874752:8(299-312)Online publication date: 26-Jan-2017
https://dl.acm.org/doi/10.1145/3155284.3018747
Bättig MGross TSarkar VRauchwerger L(2017)Synchronized-by-Default Concurrency for Shared-Memory SystemsProceedings of the 22nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3018743.3018747(299-312)Online publication date: 26-Jan-2017
https://dl.acm.org/doi/10.1145/3018743.3018747
Show More Cited By

Index Terms

The transactional memory / garbage collection analogy
1. Computing methodologies
  1. Parallel computing methodologies
    1. Parallel programming languages
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Concurrent programming structures
      2. Language types
        Parallel programming languages
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Garbage collection

Recommendations

The transactional memory / garbage collection analogy
Proceedings of the 2007 OOPSLA conference

This essay presents remarkable similarities between transactional memory and garbage collection. The connections are fascinating in their own right, and they let us better understand one technology by thinking about the corresponding issues for the ...
Age-based garbage collection

Modern generational garbage collectors look for garbage among the young objects, because they have high mortality; however, these objects include the very youngest objects, which clearly are still live. We introduce new garbage collection algorithms, ...
Exploring garbage collection with haswell hardware transactional memory
ISMM '14

Intel's latest processor microarchitecture, Haswell, adds support for a restricted form of transactional memory to the x86 programming model. We explore how this can be applied to three garbage collection scenarios in Jikes RVM: parallel copying, ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

OOPSLA '07: Proceedings of the 22nd annual ACM SIGPLAN conference on Object-oriented programming systems, languages and applications

October 2007

728 pages

ISBN:9781595937865

DOI:10.1145/1297027

General Chair:
Richard P. Gabriel
IBM Research, USA
,
Program Chairs:
David F. Bacon
IBM Research, USA
,
Cristina Videira Lopes
University of California, Irvine, USA
,
Guy L. Steele
Sun Labs, USA

ACM SIGPLAN Notices Volume 42, Issue 10
Proceedings of the 2007 OOPSLA conference
October 2007
686 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1297105
Issue’s Table of Contents

Copyright © 2007 ACM.

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: 21 October 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

OOPSLA07

Sponsor:

OOPSLA07: ACM SIGPLAN Object Oriented Programming Systems and Applications Conference

October 21 - 25, 2007

Quebec, Montreal, Canada

Acceptance Rates

OOPSLA '07 Paper Acceptance Rate 33 of 156 submissions, 21%;

Overall Acceptance Rate 268 of 1,244 submissions, 22%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

28
Total Citations
View Citations
1,136
Total Downloads

Downloads (Last 12 months)13
Downloads (Last 6 weeks)1

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chen DLiu FJiao MDing CPai S(2019)Statistical caching for near memory managementProceedings of the International Symposium on Memory Systems10.1145/3357526.3357557(411-416)Online publication date: 30-Sep-2019
https://dl.acm.org/doi/10.1145/3357526.3357557
Bättig MGross T(2017)Synchronized-by-Default Concurrency for Shared-Memory SystemsACM SIGPLAN Notices10.1145/3155284.301874752:8(299-312)Online publication date: 26-Jan-2017
https://dl.acm.org/doi/10.1145/3155284.3018747
Bättig MGross TSarkar VRauchwerger L(2017)Synchronized-by-Default Concurrency for Shared-Memory SystemsProceedings of the 22nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3018743.3018747(299-312)Online publication date: 26-Jan-2017
https://dl.acm.org/doi/10.1145/3018743.3018747
Fahmy SSenousy ZAmin A(2017)Providing QoS in contention management for software transactional memory2017 13th International Computer Engineering Conference (ICENCO)10.1109/ICENCO.2017.8289793(231-236)Online publication date: Dec-2017
https://doi.org/10.1109/ICENCO.2017.8289793
Howard B(2015)Leveraging synergy between database and programming language coursesJournal of Computing Sciences in Colleges10.5555/2831373.283137831:1(23-30)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.5555/2831373.2831378
Kundu AXu GJi C(2014)Analysis on Cloud Classification using AccessibilityInternational Journal of Cloud Applications and Computing10.4018/ijcac.20140701034:3(44-53)Online publication date: 1-Jul-2014
https://dl.acm.org/doi/10.4018/ijcac.2014070103
Kundu AJi CLiu R(2014)Software-as-a-Service using Heterogeneous Distributed System for User Specific ApplicationsInternational Journal of Cloud Applications and Computing10.4018/ijcac.20140101024:1(15-32)Online publication date: 1-Jan-2014
https://doi.org/10.4018/ijcac.2014010102
McDirmid SEdwards JBlack AKrishnamurthi SBruegge BRuskiewicz J(2014)Programming with Managed TimeProceedings of the 2014 ACM International Symposium on New Ideas, New Paradigms, and Reflections on Programming & Software10.1145/2661136.2661145(1-10)Online publication date: 20-Oct-2014
https://dl.acm.org/doi/10.1145/2661136.2661145
Meier RRigo A(2014)A way forward in parallelising dynamic languagesProceedings of the 9th International Workshop on Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems PLE10.1145/2633301.2633305(1-4)Online publication date: 28-Jul-2014
https://dl.acm.org/doi/10.1145/2633301.2633305
Anderson Z(2012)Efficiently combining parallel software using fine-grained, language-level, hierarchical resource management policiesACM SIGPLAN Notices10.1145/2398857.238466947:10(717-736)Online publication date: 19-Oct-2012
https://dl.acm.org/doi/10.1145/2398857.2384669
Show More Cited By

View Options

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten