research-article

Eliminating read barriers through procrastination and cleanliness

Authors:

KC Sivaramakrishnan,

Suresh JagannathanAuthors Info & Claims

ISMM '12: Proceedings of the 2012 international symposium on Memory Management

Pages 49 - 60

https://doi.org/10.1145/2258996.2259005

Published: 15 June 2012 Publication History

Abstract

Managed languages typically use read barriers to interpret forwarding pointers introduced to keep track of copied objects. For example, in a multicore environment with thread-local heaps and a global, shared heap, an object initially allocated on a local heap may be copied to a shared heap if it becomes the source of a store operation whose target location resides on the shared heap. As part of the copy operation, a forwarding pointer may be established in the original object to point to the copied object. This level of indirection avoids the need to update all of the references to the object that has been copied.

In this paper, we consider the design of a managed runtime that eliminates read barriers. Our design is premised on the availability of a sufficient degree of concurrency to stall operations that would otherwise necessitate the copy. Stalled actions are deferred until the next local collection, avoiding exposing forwarding pointers to the mutator. In certain important cases, procrastination is unnecessary -- lightweight runtime techniques can sometimes be used to allow objects to be eagerly copied when their set of incoming references is known, or when it can be determined that having multiple copies would not violate program semantics.

We evaluate our techniques on 3 platforms: a 16-core AMD64 machine, a 48-core Intel SCC, and an 864-core Azul Vega 3. Experimental results over a range of parallel benchmarks indicate that our approach leads to notable performance gains (20 - 32% on average) without incurring any additional complexity.

References

[1]

T. A. Anderson. Optimizations in a Private Nursery-based Garbage Collector. In ISMM, pages 21--30, 2010.

Digital Library

[2]

A. W. Appel. Simple Generational Garbage Collection and Fast Allocation. Software Practice and Experience, 19: 171--183, February 1989.

Digital Library

[3]

S. Auhagen, L. Bergstrom, M. Fluet, and J. Reppy. Garbage Collection for Multicore NUMA Machines. In Workshop on Memory Systems Performance and Correctness, pages 51--57, 2011.

Digital Library

[4]

D. F. Bacon, P. Cheng, and V. T. Rajan. A Real-Time Garbage Collector with Low Overhead and Consistent Utilization. In POPL, pages 285--298, 2003.

Digital Library

[5]

H. G. Baker, Jr. List Processing in Real Time on a Serial Computer. Communication of the ACM, 21: 280--294, 1978.

Digital Library

[6]

S. M. Blackburn and A. L. Hosking. Barriers: Friend or Foe? In ISMM, pages 143--151, 2004.

Digital Library

[7]

H. Boehm. A Garbage Collector for C and C, 2012. URL http://www.hpl.hp.com/personal/Hans_Boehm/gc

[8]

R. A. Brooks. Trading Data Space for Reduced Time and Code Space in Real-Time Garbage Collection on Stock Hardware. In Lisp and Functional Programming, pages 256--262, 1984.

Digital Library

[9]

D. Doligez and X. Leroy. A Concurrent, Generational Garbage Collector for a Multithreaded Implementation of ML. In POPL, pages 113--123, 1993.

Digital Library

[10]

L. Gidra, G. Thomas, J. Sopena, and M. Shapiro. Assessing the scalability of garbage collectors on many cores. SIGOPS Operating Systems Review, 45 (3): 15--19, 2012.

Digital Library

[11]

P. Hartel, M. Feeley, M. Alt, and L. Augustsson. Benchmarking Implementations of Functional Languages with "Pseudoknot", a Float-Intensive Benchmark. Journal of Functional Programming, 6 (4): 621--655, 1996.

[12]

Intel. SCC Platform Overview, 2012. URL http://communities.intel.com/docs/DOC-5512.

[13]

R. Jones and A. C. King. A Fast Analysis for Thread-Local Garbage Collection with Dynamic Class Loading. In International Workshop on Source Code Analysis and Manipulation, pages 129--138, 2005.

Digital Library

[14]

S. Marlow and S. Peyton Jones. Multicore Garbage Collection with Local Heaps. In ISMM, pages 21--32, 2011.

Digital Library

[15]

R. Milner, M. Tofte, and D. Macqueen. The Definition of Standard ML. MIT Press, Cambridge, MA, USA, 1997.

Digital Library

[16]

MLton. The MLton Compiler and Runtime System, 2012. URL http://www.mlton.org.

[17]

MultiMLton. MLton for Scalable Multicore Architectures, 2012. URL http://multimlton.cs.purdue.edu.

[18]

J. Reppy. Concurrent Programming in ML. Cambridge University Press, 2007.

Digital Library

[19]

P. M. Sansom. Dual-Mode Garbage Collection. In Proceedings of the Workshop on the Parallel Implementation of Functional Languages, pages 283--310, 1991.

[20]

F. Siebert. Limits of parallel marking garbage collection. In ISMM, pages 21--29, 2008.

Digital Library

[21]

G. L. Steele, Jr. Multiprocessing Compactifying Garbage Collection. Communcations of the ACM, 18: 495--508, September 1975.

Digital Library

[22]

B. Steensgaard. Thread-Specific Heaps for Multi-Threaded Programs. In ISMM, pages 18--24, 2000.

Digital Library

[23]

Streambench. The STREAM Benchmark: Computer Memory Bandwidth, 2012. URL http://http://www.streambench.org/.

[24]

L. Ziarek, K. Sivaramakrishnan, and S. Jagannathan. Composable Asynchronous Events. In PLDI, pages 628--639, 2011.

Digital Library

Cited By

SHIVKUMAR BMURPHY JZIAREK L(2021)Real-time MLton: A Standard ML runtime for real-time functional programsJournal of Functional Programming10.1017/S095679682100017431Online publication date: 31-Aug-2021
https://doi.org/10.1017/S0956796821000174
Sivaramakrishnan KDolan SWhite LJaffer SKelly TSahoo AParimala SDhiman AMadhavapeddy A(2020)Retrofitting parallelism onto OCamlProceedings of the ACM on Programming Languages10.1145/34089954:ICFP(1-30)Online publication date: 3-Aug-2020
https://dl.acm.org/doi/10.1145/3408995
Gidra LThomas GSopena JShapiro MNguyen N(2015)NumaGiCACM SIGARCH Computer Architecture News10.1145/2786763.269436143:1(661-673)Online publication date: 14-Mar-2015
https://dl.acm.org/doi/10.1145/2786763.2694361
Show More Cited By

Index Terms

Eliminating read barriers through procrastination and cleanliness
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Concurrent programming structures
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Garbage collection

Recommendations

Eliminating read barriers through procrastination and cleanliness
ISMM '12

Managed languages typically use read barriers to interpret forwarding pointers introduced to keep track of copied objects. For example, in a multicore environment with thread-local heaps and a global, shared heap, an object initially allocated on a ...
Optimizations in a private nursery-based garbage collector
ISMM '10: Proceedings of the 2010 international symposium on Memory management

This paper describes a garbage collector designed around the use of permanent, private, thread-local nurseries and is principally oriented towards functional languages. We try to maximize the cache hit rate by having threads continually reuse their ...
WFR-TM

Transactional Memory (TM) is a promising concurrent programming paradigm which employs transactions to achieve synchronization in accessing common data known as transactional variables. A transaction may either commit, making its updates to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISMM '12: Proceedings of the 2012 international symposium on Memory Management

June 2012

152 pages

ISBN:9781450313506

DOI:10.1145/2258996

General Chair:
Martin Vechev
ETH Zurich
,
Program Chair:
Kathryn S. McKinley
The University of Texas at Austin and Microsoft Research

ACM SIGPLAN Notices Volume 47, Issue 11
ISMM '12
November 2012
136 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2426642
Issue’s Table of Contents

Copyright © 2012 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

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 June 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISMM '12

Sponsor:

SIGPLAN

ISMM '12: International Symposium on Memory Management

June 15 - 16, 2012

Beijing, China

Acceptance Rates

Overall Acceptance Rate 72 of 156 submissions, 46%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
272
Total Downloads

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

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

SHIVKUMAR BMURPHY JZIAREK L(2021)Real-time MLton: A Standard ML runtime for real-time functional programsJournal of Functional Programming10.1017/S095679682100017431Online publication date: 31-Aug-2021
https://doi.org/10.1017/S0956796821000174
Sivaramakrishnan KDolan SWhite LJaffer SKelly TSahoo AParimala SDhiman AMadhavapeddy A(2020)Retrofitting parallelism onto OCamlProceedings of the ACM on Programming Languages10.1145/34089954:ICFP(1-30)Online publication date: 3-Aug-2020
https://dl.acm.org/doi/10.1145/3408995
Gidra LThomas GSopena JShapiro MNguyen N(2015)NumaGiCACM SIGARCH Computer Architecture News10.1145/2786763.269436143:1(661-673)Online publication date: 14-Mar-2015
https://dl.acm.org/doi/10.1145/2786763.2694361
Gidra LThomas GSopena JShapiro MNguyen N(2015)NumaGiCACM SIGPLAN Notices10.1145/2775054.269436150:4(661-673)Online publication date: 14-Mar-2015
https://dl.acm.org/doi/10.1145/2775054.2694361
Gidra LThomas GSopena JShapiro MNguyen NOzturk OEbcioglu KDwarkadas S(2015)NumaGiCProceedings of the Twentieth International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/2694344.2694361(661-673)Online publication date: 14-Mar-2015
https://dl.acm.org/doi/10.1145/2694344.2694361
Carpen-Amarie MDice DMarlier PThomas GFelber P(2015)Evaluating HTM for Pauseless Garbage Collectors in JavaProceedings of the 2015 IEEE Trustcom/BigDataSE/ISPA - Volume 0310.1109/Trustcom.2015.606(1-8)Online publication date: 20-Aug-2015
https://dl.acm.org/doi/10.1109/Trustcom.2015.606
SIVARAMAKRISHNAN KZIAREK LJAGANNATHAN S(2014)MultiMLton: A multicore-aware runtime for standard MLJournal of Functional Programming10.1017/S095679681400016124:06(613-674)Online publication date: 18-Jun-2014
https://doi.org/10.1017/S0956796814000161
Gidra LThomas GSopena JShapiro M(2013)A study of the scalability of stop-the-world garbage collectors on multicoresACM SIGPLAN Notices10.1145/2499368.245114248:4(229-240)Online publication date: 16-Mar-2013
https://dl.acm.org/doi/10.1145/2499368.2451142
Gidra LThomas GSopena JShapiro M(2013)A study of the scalability of stop-the-world garbage collectors on multicoresACM SIGARCH Computer Architecture News10.1145/2490301.245114241:1(229-240)Online publication date: 16-Mar-2013
https://dl.acm.org/doi/10.1145/2490301.2451142
Gidra LThomas GSopena JShapiro MSarkar VBodik R(2013)A study of the scalability of stop-the-world garbage collectors on multicoresProceedings of the eighteenth international conference on Architectural support for programming languages and operating systems10.1145/2451116.2451142(229-240)Online publication date: 16-Mar-2013
https://dl.acm.org/doi/10.1145/2451116.2451142
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.

Media

Figures

Other

Tables

View Table of Contents