research-article

The locality of concurrent write barriers

Authors:

Laurence Hellyer,

Antony L. HoskingAuthors Info & Claims

ISMM '10: Proceedings of the 2010 international symposium on Memory management

Pages 83 - 92

https://doi.org/10.1145/1806651.1806666

Published: 05 June 2010 Publication History

Abstract

Concurrent and incremental collectors require barriers to ensure correct synchronisation between mutator and collector. The overheads imposed by particular barriers on particular systems have been widely studied. Somewhat fewer studies have also compared barriers in terms of their termination properties or the volume of floating garbage they generate. Until now, the consequences for locality of different barrier choices has not been studied, although locality will be of increasing importance for emerging architectures. This paper provides a study of the locality of concurrent write barriers, independent of the processor architecture, virtual machine, compiler or garbage collection algorithm.

References

[1]

S. Abraham and J. Patel. Parallel garbage collection on a virtual memory system. In Int. Conf. on Parallel Processing, 243--246, 1987. Pennsylvania State University Press.

[2]

A. W. Appel, J. R. Ellis, and K. Li. Real-time concurrent collection on stock multiprocessors. ACM SIGPLAN Notices, 23 (7): 11--20, 1988.

Digital Library

[3]

D. F. Bacon and A. Diwan, editors. Int. Symp. on Memory Management, 2004. ACM Press.

[4]

H. G. Baker. List processing in real-time on a serial computer. Communications of the ACM, 21 (4): 280--94, 1978.

Digital Library

[5]

S. M. Blackburn, R. Garner, K. S. McKinley, A. Diwan, S. Z. Guyer, A. L. Hosking, J. E. B. Moss, and D. Stefanović. The DaCapo benchmarks: Java benchmarking development and analysis. In Object-Oriented Programming, Systems, Languages, and Applications, 2006.

Digital Library

[6]

S. M. Blackburn and A. L. Hosking. Barriers: Friend or foe? In ISMM04, 143--151.

Digital Library

[7]

S. M. Blackburn and K. S. McKinley. In or out? putting write barriers in their place. In Int. Symp. on Memory Management, 175--184, 2003.

Digital Library

[8]

S. M. Blackburn, R. E. Jones, K. S. McKinley, and J. E. B. Moss. Beltway: Getting around garbage collection gridlock. In Programming Language Design and Implementation, 153--164, 2002.

Digital Library

[9]

S. M. Blackburn, P. Cheng, and K. S. McKinley. Oil and water? High performance garbage collection in Java with MMTk. In Int. Conf. on Software Engineering, 137--146, 2004.

Digital Library

[10]

H.-J. Boehm. Reducing garbage collector cache misses. In Int. Symp. on Memory Management, 59--64, 2000.

Digital Library

[11]

H.-J. Boehm, A. J. Demers, and S. Shenker. Mostly parallel garbage collection. ACM SIGPLAN Notices, 26 (6): 157--164, 1991.

Digital Library

[12]

C. Chambers. The Design and Implementation of the SELF Compiler, an Optimizing Compiler for an Objected-Oriented Programming Language. PhD thesis, Stanford University, 1992.

Digital Library

[13]

W.-K. Chen, S. Bhansali, T. M. Chilimbi, X. Gao, and W. Chuang. Profile-guided proactive garbage collection for locality optimization. In PLDI06, 332--340.

Digital Library

[14]

C.-Y. Cher, A. L. Hosking, and T. N. Vijaykumar. Software prefetching for mark-sweep garbage collection: Hardware analysis and software redesign. In Architectural Support for Programming Languages and Operating Systems, 199--210, 2004.

Digital Library

[15]

T. M. Chilimbi, M. D. Hill, and J. R. Larus. Cache-conscious structure layout. In Programming Language Design and Implementation, 1--12, 1999.

Digital Library

[16]

D. Detlefs, W. D. Clinger, M. Jacob, and R. Knippel. Concurrent remembered set refinement in generational garbage collection. In Java Virtual Machine Research and Technology Symposium, 2002.

Digital Library

[17]

E. W. Dijkstra, L. Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens. On-the-fly garbage collection: An exercise in cooperation. Communications of the ACM, 21 (11): 965--975, 1978.

Digital Library

[18]

R. Garner, S. M. Blackburn, and D. Frampton. Effective prefetch for mark-sweep garbage collection. In Int. Symp. on Memory Management, 43--54, 2007.

Digital Library

[19]

U. Hölzle. A fast write barrier for generational garbage collectors. In OOPSLA Workshop on Garbage Collection in Object-Oriented Systems, 1993. URL ftp://self.stanford.edu/pub/papers/write-barrier.ps.Z.

[20]

A. L. Hosking, J. E. B. Moss, and D. Stefanović. A comparative performance evaluation of write barrier implementations. In Object-Oriented Programming, Systems, Languages, and Applications, 92--109, 1992.

Digital Library

[21]

A. L. Hosking and J. E. B. Moss. Protection traps and alternatives for memory management of an object-oriented language. In Symp. on Operating Systems Principles, 106--119, 1993.

Digital Library

[22]

R. E. Jones, and R. Lins Garbage Collection. Wiley, 1996.

[23]

H. T. Kung and S. W. Song. An efficient parallel garbage collection system and its correctness proof. In Symp. on Foundations of Computer Science, 120--131. IEEE Press, 1977.

Digital Library

[24]

M. S. Lam, P. R. Wilson, and T. G. Moher. Object type directed garbage collection to improve locality. In Int. Workshop on Memory Management, Lecture Notes in Computer Science 637, 1992. Springer.

Digital Library

[25]

D. A. Moon. Garbage collection in a large LISP system. In Lisp and Functional Programming, 235--245, 1984.

Digital Library

[26]

G. Novark, T. Strohman, and E. D. Berger. Custom object layout for garbage-collected languages. Tech. Report, University of Massachusetts at Amherst, 2006.

[27]

P. P. Pirinen. Barrier techniques for incremental tracing. In Int. Symp. on Memory Management, 20--25, 1999.

Digital Library

[28]

F. Pizlo, E. Petrank, and B. Steensgaard. A study of concurrent real-time garbage collectors. In Programming Language Design and Implementation, 33--44, 2008.

Digital Library

[29]

M. I. Schwartzbach and T. Ball, editors. Programming Language Design and Implementation, 2006.

[30]

Y. Shuf, M. Gupta, R. Bordawekar, and J. P. Singh. Exploiting prolific types for memory management and optimizations. In Principles of Programming Languages, 2002.

Digital Library

[31]

D. Siegwart and M. Hirzel. Improving locality with parallel hierarchical copying GC. In Int. Symp. on Memory Management, 52--63, 2006.

Digital Library

[32]

P. Sobalvarro. A lifetime-based garbage collector for Lisp systems on general-purpose computers. Tech. Report AITR-1417, MIT AI Lab, 1988.

Digital Library

[33]

G. L. Steele. Multiprocessing compactifying garbage collection. Communications of the ACM, 18 (9): 495--508, 1975.

Digital Library

[34]

D. Stefanović, K. S. McKinley, and J. E. B. Moss. Age-based garbage collection. In Object-Oriented Programming, Systems, Languages, and Applications, 370--381, 1999.

Digital Library

[35]

Sun Microsystems. Java SE 6 HotSpot virtual machine garbage collection tuning, 2009. URL http://java.sun.com/javase/technologies/hotspot/gc/gc_tuning_6.html.

[36]

D. M. Ungar. Generation scavenging: A non-disruptive high performance storage reclamation algorithm. ACM SIGPLAN Notices, 19 (5): 157--167, 1984.

Digital Library

[37]

M. Vechev, D. F. Bacon, P. Cheng, and D. Grove. Derivation and evaluation of concurrent collectors. In European Conf. on Object-Oriented Programming, 2005. Springer-Verlag.

Digital Library

[38]

M. T. Vechev, E. Yahav, and D. F. Bacon. Correctness-preserving derivation of concurrent garbage collection algorithms. In PLDI06, 341--353.

Digital Library

[39]

P. R. Wilson. Uniprocessor garbage collection techniques. Tech. Report, University of Texas, 1994.

[40]

P. R. Wilson and T. G. Moher. Design of the opportunistic garbage collector. In Object-Oriented Programming, Systems, Languages, and Applications, 23--35, 1989.

Digital Library

[41]

P. R. Wilson, M. S. Lam, and T. G. Moher. Effective "static-graph" reorganization to improve locality in garbage-collected systems. In Programming Language Design and Implementation, 177--191, 1991. 10.1145/113445.113461.

Digital Library

[42]

T. Yuasa. Real-time garbage collection on general-purpose machines. J. Systems and Software, 11 (3): 181--198, 1990.

Digital Library

[43]

B. Zorn. Barrier methods for garbage collection. Tech. Report CU-CS-494-90, University of Colorado, Boulder, 1990.

Cited By

Yang XBlackburn SFrampton DHosking A(2012)Barriers reconsidered, friendlier still!ACM SIGPLAN Notices10.1145/2426642.225900447:11(37-48)Online publication date: 15-Jun-2012
https://dl.acm.org/doi/10.1145/2426642.2259004
Yang XBlackburn SFrampton DHosking AVechev MMcKinley K(2012)Barriers reconsidered, friendlier still!Proceedings of the 2012 international symposium on Memory Management10.1145/2258996.2259004(37-48)Online publication date: 15-Jun-2012
https://dl.acm.org/doi/10.1145/2258996.2259004
Sewe AYuan DSinschek JMezini MKrall AMössenböck H(2010)Headroom-based pretenuringProceedings of the 8th International Conference on the Principles and Practice of Programming in Java10.1145/1852761.1852767(29-38)Online publication date: 15-Sep-2010
https://dl.acm.org/doi/10.1145/1852761.1852767

Index Terms

The locality of concurrent write barriers
1. General and reference
  1. Cross-computing tools and techniques
    1. Measurement
    2. Metrics
2. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Garbage collection

Recommendations

Barriers: friend or foe?
ISMM '04: Proceedings of the 4th international symposium on Memory management

Modern garbage collectors rely on read and write barriers imposed on heap accesses by the mutator, to keep track of references between different regions of the garbage collected heap, and to synchronize actions of the mutator with those of the ...
The locality of concurrent write barriers
ISMM '10

Concurrent and incremental collectors require barriers to ensure correct synchronisation between mutator and collector. The overheads imposed by particular barriers on particular systems have been widely studied. Somewhat fewer studies have also ...
Controlling garbage collection and heap growth to reduce the execution time of Java applications

In systems that support garbage collection, a tension exists between collecting garbage too frequently and not collecting it frequently enough. Garbage collection that occurs too frequently may introduce unnecessary overheads at the risk of not ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISMM '10: Proceedings of the 2010 international symposium on Memory management

June 2010

140 pages

ISBN:9781450300544

DOI:10.1145/1806651

General Chair:
Jan Vitek
Purdue University
,
Program Chair:
Doug Lea
State University of New York at Oswego

ACM SIGPLAN Notices Volume 45, Issue 8
ISMM '10
August 2010
129 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1837855
Issue’s Table of Contents

Copyright © 2010 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: 05 June 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISMM '10

Sponsor:

SIGPLAN

ISMM '10: International Symposium on Memory Management

June 5 - 6, 2010

Ontario, Toronto, Canada

Acceptance Rates

Overall Acceptance Rate 72 of 156 submissions, 46%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
252
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)2

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yang XBlackburn SFrampton DHosking A(2012)Barriers reconsidered, friendlier still!ACM SIGPLAN Notices10.1145/2426642.225900447:11(37-48)Online publication date: 15-Jun-2012
https://dl.acm.org/doi/10.1145/2426642.2259004
Yang XBlackburn SFrampton DHosking AVechev MMcKinley K(2012)Barriers reconsidered, friendlier still!Proceedings of the 2012 international symposium on Memory Management10.1145/2258996.2259004(37-48)Online publication date: 15-Jun-2012
https://dl.acm.org/doi/10.1145/2258996.2259004
Sewe AYuan DSinschek JMezini MKrall AMössenböck H(2010)Headroom-based pretenuringProceedings of the 8th International Conference on the Principles and Practice of Programming in Java10.1145/1852761.1852767(29-38)Online publication date: 15-Sep-2010
https://dl.acm.org/doi/10.1145/1852761.1852767

View Options

Get Access

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