skip to main content
10.1145/1029873.1029891acmconferencesArticle/Chapter ViewAbstractPublication PagesismmConference Proceedingsconference-collections
Article

Barriers: friend or foe?

Published: 24 October 2004 Publication History

Abstract

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 collector. It has been a long-standing untested assumption that barriers impose significant overhead to garbage-collected applications. As a result, researchers have devoted effort to development of optimization approaches for elimination of unnecessary barriers, or proposed new algorithms for garbage collection that avoid the need for barriers while retaining the capability for independent collection of heap partitions. On the basis of the results presented here, we dispel the assumption that barrier overhead should be a primary motivator for such efforts.
We present a methodology for precise measurement of mutator overheads for barriers associated with mutator heap accesses. We provide a taxonomy of different styles of barrier and measure the cost of a range of popular barriers used for different garbage collectors within Jikes RVM. Our results demonstrate that barriers impose surprisingly low cost on the mutator, though results vary by architecture. We found that the average overhead for a reasonable generational write barrier was less than 2% on average, and less than 6% in the worst case. Furthermore, we found that the average overhead of a read barrier consisting of just an unconditional mask of the low order bits read on the PowerPC was only 0.85%, while on the AMD it was 8.05%. With both read and write barriers, we found that second order locality effects were sometimes more important than the overhead of the barriers themselves, leading to counter-intuitive speedups in a number of situations.

References

[1]
Alpern, B., Attanasio, C. R., Barton, J. J., Cocchi, A., Hummel, S. F., Lieber, D., Ngo, T., Mergen, M., Shepherd, J. C., and Smith, S. Implementing Jalapeño in Java. In, pp. 314--324.
[2]
Appel, A. W. Simple generational garbage collection and fast allocation. Software---Practice and Experience 19, 2 (Feb. 1989), 171--183.
[3]
Arnold, M., Fink, S. J., Grove, D., Hind, M., and Sweeney, P. F. Adaptive optimization in the Jalapeño JVM. In Proceedings of the ACM Conference on Object-Oriented Programming Systems, Languages, and Applications(Minneapolis, Minnesota, Oct.). ACM SIGPLAN Notices 35, 10 (Oct. 2000), pp. 47--65.
[4]
Azagury, A., Kolodner, E. K., Petrank, E., and Yehudai, Z. Combining card marking with remembered sets: How to save scanning time. In ISMM'98 pp. 10--19.
[5]
Bacon, D. F., Cheng, P., and Rajan, V.T. A real-time garbage collector with low overhead and consistent utilization. In Conference Record of the ACM Symposium on Principles of Programming Languages(New Orleans, Lousiana, Jan.). ACM SIGPLAN Notices 38, 1 (Jan. 2003), pp.285--298.
[6]
Blackburn, S., and McKinley, K.S. In or out?: Putting write barriers in their place. In Proceedings of the ACM International Symposium on Memory anagement(Berlin, Germany, Jun., 2002). ACM SIGPLAN Notices 38 2(Feb. 2003), pp. 281--29.
[7]
Blackburn, S., and McKinley, K.S. Ulterior reference counting: fast garbage collection without a long wait. In OOPSLA'03 oopsla03, pp. 344--358.
[8]
Blackburn, S. M., Cheng, P., and McKinley, K. S. Myths and reality: The performance impact of garbage collection. In ACM International Conference on Measurement and Modeling of Computer Systems(New York, New York, June). 2004, p. To appear.
[9]
Blackburn, S.M., Jones, R. E., McKinley, K. S., and Moss, J. E.B. Beltway: Getting around garbage collection gridlock. In Proceedings of the ACM Conference on Programming Language Design and Implementation(Berlin, Germany, June). ACM SIGPLAN Notices 37, 5 (May 2002), pp. 153--164.
[10]
Brahnmath, K., Nystrom, N., Hosking, A. L., and Cutts, Q. Swizzle barrier optimizations for orthogonal persistence in Java. In Proceedings of the Third International Workshop on Persistence and Java/(Tiburon, California, August 1998), R. Morrison M. Jordan, and M. Atkinson, Eds. Advances in Persistent Object Systems. Morgan Kaufmann, 1999, pp. 268--278.
[11]
Brooks, R.A. Trading data space for reduced time and code space in real-time garbage collection on stock hardware. In Proceedings of the ACM Conference on Lisp and Functional Programming(Austin, Texas, Aug.). 1984, pp. 256--262.
[12]
Caudill, P. J., and Wirfs-Brock, A. A third generation Smalltalk-80 implementation. In Proceedings of the ACM Conference on Object-Oriented Programming Systems, Languages, and Applications/Portland, Oregon, Sept.). ACM SIGPLAN Notices 21, 11 (Nov. 1986), pp. 119--130.
[13]
Hirzel, M., Diwan, A., and Hertz, M. Connectivity-based garbage collection. In pp. 359--373.
[14]
Hosking, A. L., and Hudson, R. L. Remembered sets can also play cards. In Proceedings of the OOPSLA Workshop on Memory Management and Garbage Collection (Washington, DC, Sept.). 1993.
[15]
Hosking, A. L., and Moss, J. E. B. Protection traps and alternatives for memory management of an object-oriented language. In Proceedings of the ACM Symposium on Operating Systems Principles (Asheville, North Carolina, Dec.). ACM Operating Systems Review 27, 5 (Dec. 1993), pp. 106--119.
[16]
Hosking, A. L., Moss, J. E. B., and Stefanoviç D. A comparative performance evaluation of write barrier implementations. In Proceedings of the ACM Conference on Object-Oriented Programming Systems, Languages, and Applications (Vancouver, Canada, Oct.). ACM SIGPLAN Notices 27, 10 (Oct. 1992), pp.92--109.
[17]
Hosking, A. L., Nystrom, N., Cutts, Q., and Brahnmath, K. Optimizing the read and write barriers for orthogonal persistence. In Proceedings of the Eighth International Workshop on Persistent Object Systems (Tiburon, California, August 1998), R. Morrison, M. Jordan, and M. Atkinson, Eds. Advances in Persistent Object Systems. Morgan Kaufmann, 1999, pp.149--159.
[18]
Hudson, R. L., and Moss, J. E. B. Incremental collection of mature objects. In Proceedings of the International Workshop on Memory Management (St. Malo, France, Sept.), Y. Bekkers and J. Cohen, Eds. vol. 637 of Lecture Notes in Computer Science. Springer-Verlag, 1992, pp. 388--403.
[19]
Proceedings of the ACM International Symposium on Memory Management (Vancouver, Canada, Oct., 1998). ACM SIGPLAN Notices 34, 3 (Mar. 1999).
[20]
Jones, R., and Lins, R. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. Wiley, May 1996. Chapter on distributed collection by Lins.
[21]
Proceedings of the ACM Conference on Object-Oriented Programming Systems, Languages, and Applications (Anaheim, California, Nov.). ACM SIGPLAN Notices 38, 11 (Nov. 2003).
[22]
Proceedings of the ACM Conference on Object-Oriented Programming Systems, Languages, and Applications (Denver, Colorado, Nov.). ACM SIGPLAN Notices 34, 10 (Oct. 1999).
[23]
Pettersson, M. Linux Intel/x86 performance counters, 2003 http://user.it.uu.se/mikpe/linux/perfctr/.
[24]
Roth, D. J., and Wise, D. S. One-bit counts between unique and sticky. In ISMM'98, pp. 49--56.
[25]
Seligmann, J., and 235-252, S. G. E. Incremental mature garbage collection using the Train algorithm. In Proceedings of the European Conference on Object-Oriented Programming (AAarhus, Denmark, Aug.). vol. 952 of Lecture Notes in Computer Science. Springer-Verlag, 1995, pp. 235--252.
[26]
Sobalvarro, P. G. A lifetime-based garbage collector for LISP systems on general-purpose computers, 1988. B.S. Thesis, Dept. of EECS, Massachusetts Institute of Technology, Cambridge.
[27]
SPECjvm98 benchmarks, 1998.http://www.spec.org/osg/jvm98.
[28]
SPECjbb2000 benchmarks, 2000.http://www.spec.org/jbb2000.
[29]
Stefanoviç, D., McKinley, K. S., and Moss, J. E. B. Age-based garbage collection. In OOPSLA'99 oopsla99, pp. 370--381.
[30]
Ungar, D.Generation scavenging: A non-disruptive high performance storage reclamation algorithm. In Proceedings of the ACM Symposium on Practical Software Development Environments(Pittsburgh, Pennsylvania, Apr.). 1984, pp. 157--167.
[31]
Wilson, P. R., and Moher, T. G. A ``card-marking'' scheme for controlling intergenerational references in generation-based garbage collection on stock hardware. ACM SIGPLAN Notices 24, 5 (May 1989), 87--92.
[32]
Wilson, P. R., and Moher, T. G. Design of the opportunistic garbage collector. In Proceedings of the ACM Conference on Object-Oriented Programming Systems, Languages, and Applications (New Orleans, Louisiana, Oct.). ACM SIGPLAN Notices 24, 10 (Oct. 1989), pp. 23--35.
[33]
Zee, K., and Rinard, M. C. Write barrier removal by static analysis. In Proceedings of the ACM Conference on Object-Oriented Programming Systems, Languages, and Applications (Seattle, Washington, Nov.). ACM SIGPLAN Notices 37, 11 (Nov. 2002), pp. 191--210.
[34]
Zorn, B. Barrier methods for garbage collection. Tech. Rep. CU-CS-494-90, University of Colorado at Boulder, Nov. 1990.

Cited By

View all
  • (2024)Mutator-Driven Object Placement using Load BarriersProceedings of the 21st ACM SIGPLAN International Conference on Managed Programming Languages and Runtimes10.1145/3679007.3685060(14-27)Online publication date: 13-Sep-2024
  • (2024)Getting a Handle on Unmanaged MemoryProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 310.1145/3620666.3651326(448-463)Online publication date: 27-Apr-2024
  • (2023)Improving Garbage Collection Observability with Performance TracingProceedings of the 20th ACM SIGPLAN International Conference on Managed Programming Languages and Runtimes10.1145/3617651.3622986(85-99)Online publication date: 19-Oct-2023
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
ISMM '04: Proceedings of the 4th international symposium on Memory management
October 2004
182 pages
ISBN:1581139454
DOI:10.1145/1029873
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: 24 October 2004

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. garbage collection
  2. java
  3. memory management
  4. write barriers

Qualifiers

  • Article

Conference

ISMM04
Sponsor:

Acceptance Rates

Overall Acceptance Rate 72 of 156 submissions, 46%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)25
  • Downloads (Last 6 weeks)4
Reflects downloads up to 18 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Mutator-Driven Object Placement using Load BarriersProceedings of the 21st ACM SIGPLAN International Conference on Managed Programming Languages and Runtimes10.1145/3679007.3685060(14-27)Online publication date: 13-Sep-2024
  • (2024)Getting a Handle on Unmanaged MemoryProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 310.1145/3620666.3651326(448-463)Online publication date: 27-Apr-2024
  • (2023)Improving Garbage Collection Observability with Performance TracingProceedings of the 20th ACM SIGPLAN International Conference on Managed Programming Languages and Runtimes10.1145/3617651.3622986(85-99)Online publication date: 19-Oct-2023
  • (2022)Distilling the Real Cost of Production Garbage Collectors2022 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS)10.1109/ISPASS55109.2022.00005(46-57)Online publication date: May-2022
  • (2020)Deconstructing the garbage-first collectorProceedings of the 16th ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments10.1145/3381052.3381320(15-29)Online publication date: 17-Mar-2020
  • (2019)Lazy pointer update for low heap compaction pause timesProceedings of the 15th ACM SIGPLAN International Symposium on Dynamic Languages10.1145/3359619.3359741(15-27)Online publication date: 20-Oct-2019
  • (2019)Design and analysis of field-logging write barriersProceedings of the 2019 ACM SIGPLAN International Symposium on Memory Management10.1145/3315573.3329981(103-114)Online publication date: 23-Jun-2019
  • (2019)QuickCheck: using speculation to reduce the overhead of checks in NVM frameworksProceedings of the 15th ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments10.1145/3313808.3313822(137-151)Online publication date: 14-Apr-2019
  • (2016)Boosting the Priority of GarbageACM Transactions on Architecture and Code Optimization10.1145/287542413:1(1-25)Online publication date: 7-Mar-2016
  • (2015)LeakTracer: Tracing leaks along the way2015 IEEE 15th International Working Conference on Source Code Analysis and Manipulation (SCAM)10.1109/SCAM.2015.7335414(181-190)Online publication date: Sep-2015
  • Show More Cited By

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