Article

Exploiting the efficiency of generational algorithms for hardware-supported real-time garbage collection

Authors:

Sylvain Stanchina,

Matthias MeyerAuthors Info & Claims

SAC '07: Proceedings of the 2007 ACM symposium on Applied computing

Pages 713 - 718

https://doi.org/10.1145/1244002.1244161

Published: 11 March 2007 Publication History

Abstract

Generational garbage collectors are more efficient than their non-generational counterparts. Unfortunately, however, generational algorithms require both write barriers and write barrier handlers and therefore degrade worst-case performance.

In this paper, we present novel hardware support for generational garbage collection. In contrast to previous work, we introduce a hardware write barrier that does not only detect inter-generational pointers, but also executes all related book-keeping operations entirely in hardware. For the first time, write barrier detection and handling occur completely in parallel to instruction execution, so that the runtime overhead of generational garbage collection is reduced to near zero.

For evaluation purposes, we extended a system with hardware-supported real-time garbage collection with our hardware support for generational garbage collection. Measurements of Java programs on an FPGA-based prototype show that the generational extensions reduce the total duration of garbage collection activities by a factor of 5 and the memory traffic caused by the collector by a factor of 4 on average.

References

[1]

Altera. STRATIX II device family data sheet, 2006.

[2]

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

Digital Library

[3]

H. G. Baker. The treadmill: real-time garbage collection without motion sickness. ACM Sigplan Notices, 27(3), 1992.

Digital Library

[4]

H. Lieberman and C. E. Hewitt. A real-time garbage collector based on the lifetimes of objects. Communications of the ACM, 26(6):419--429, 1983.

Digital Library

[5]

M. Meyer. A novel processor architecture with exact tag-free pointers. IEEE Micro, 24(3):46--55, 2004.

Digital Library

[6]

M. Meyer. An on-chip garbage collection coprocessor for embedded real-time systems. In 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, Hong Kong, Aug. 2005.

Digital Library

[7]

M. Meyer. A true hardware read barrier. In ISMM'06 Proceedings of the Fifth International Symposium on Memory Management, Ottawa, June 2006.

Digital Library

[8]

D. A. Moon. Architecture of the Symbolics 3600. In Proceedings of the 12th Annual International Symposium on Computer Architecture, pages 76--83, Boston, MA, June 1985.

Digital Library

[9]

K. D. Nilsen and W. J. Schmidt. A high-performance hardware-assisted real time garbage collection system. Journal of Programming Languages, 2(1), 1994.

[10]

M. Pfeffer. Ein echtzeitfähiges Java-System für einen mehrfädigen Java-Mikrocontroller. PhD thesis, University of Augsburg, Germany, Feb. 2004.

[11]

M. Pfeffer, T. Ungerer, S. Fuhrmann, J. Kreuzinger, and U. Brinkschulte. Real-time garbage collection for a multithreaded Java microcontroller. Real-Time Systems, 26(1):89--106, 2004.

Digital Library

[12]

A. D. Samples, D. M. Ungar, and P. Hilfinger. SOAR: Smalltalk without bytecodes. In OOPSLA'86 ACM Conference on Object-Oriented Systems, Languages and Applications, volume 21(11), pages 107--118, Oct. 1986.

Digital Library

[13]

W. J. Schmidt and K. D. Nilsen. Performance of a hardware-assisted real-time garbage collector. In International Conference on Architectural Support for Programming Languages and Operating Systems, pages 76--85, Oct. 1994.

Digital Library

[14]

D. Ungar, R. Blau, P. Foley, D. Samples, and D. Patterson. Architecture of soar: Smalltalk on a risc. In ISCA '84: Proceedings of the 11th International Symposium on Computer Architecture, pages 188--197, New York, NY, USA, June 1984.

Digital Library

[15]

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

Digital Library

[16]

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

Digital Library

Cited By

Cao TBlackburn SGao TMcKinley KLu STorrellas J(2012)The yin and yang of power and performance for asymmetric hardware and managed softwareProceedings of the 39th Annual International Symposium on Computer Architecture10.5555/2337159.2337185(225-236)Online publication date: 9-Jun-2012
https://dl.acm.org/doi/10.5555/2337159.2337185
Cao TBlackburn SGao TMcKinley K(2012)The yin and yang of power and performance for asymmetric hardware and managed softwareACM SIGARCH Computer Architecture News10.1145/2366231.233718540:3(225-236)Online publication date: 9-Jun-2012
https://dl.acm.org/doi/10.1145/2366231.2337185
Horvath OMeyer M(2010)Fine-Grained Parallel Compacting Garbage Collection through Hardware-Supported SynchronizationProceedings of the 2010 39th International Conference on Parallel Processing Workshops10.1109/ICPPW.2010.28(118-126)Online publication date: 13-Sep-2010
https://dl.acm.org/doi/10.1109/ICPPW.2010.28

Index Terms

Exploiting the efficiency of generational algorithms for hardware-supported real-time garbage collection
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Garbage collection

Recommendations

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, ...
A generational on-the-fly garbage collector for Java
PLDI '00: Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation

An on-the-fly garbage collector does not stop the program threads to perform the collection. Instead, the collector executes in a separate thread (or process) in parallel to the program. On-the-fly collectors are useful for multi-threaded applications ...
Age-based garbage collection
OOPSLA '99: Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications

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, ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SAC '07: Proceedings of the 2007 ACM symposium on Applied computing

March 2007

1688 pages

ISBN:1595934804

DOI:10.1145/1244002

Conference Chairs:
Yookun Cho
Seoul National University, Seoul, Korea
,
Roger L. Wainwright
University of Tulsa, Tulsa, Oklahoma
,
Hisham M. Haddad
Kennesaw State University, Kennesaw, Georgia
,
Sung Y. Shin
South Dakota State University, Brookings, South Dakota
,
Program Chair:
Yong Wan Koo
The University of Suwon, Gyeongggi-do, Korea

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

SIGAPP: ACM Special Interest Group on Applied Computing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 March 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SAC07

Sponsor:

SIGAPP

SAC07: The 2007 ACM Symposium on Applied Computing

March 11 - 15, 2007

Seoul, Korea

Acceptance Rates

Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

Upcoming Conference

SAC '25

Sponsor:
sigapp

The 40th ACM/SIGAPP Symposium on Applied Computing

March 31 - April 4, 2025

Catania , Italy

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
240
Total Downloads

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

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Cao TBlackburn SGao TMcKinley KLu STorrellas J(2012)The yin and yang of power and performance for asymmetric hardware and managed softwareProceedings of the 39th Annual International Symposium on Computer Architecture10.5555/2337159.2337185(225-236)Online publication date: 9-Jun-2012
https://dl.acm.org/doi/10.5555/2337159.2337185
Cao TBlackburn SGao TMcKinley K(2012)The yin and yang of power and performance for asymmetric hardware and managed softwareACM SIGARCH Computer Architecture News10.1145/2366231.233718540:3(225-236)Online publication date: 9-Jun-2012
https://dl.acm.org/doi/10.1145/2366231.2337185
Horvath OMeyer M(2010)Fine-Grained Parallel Compacting Garbage Collection through Hardware-Supported SynchronizationProceedings of the 2010 39th International Conference on Parallel Processing Workshops10.1109/ICPPW.2010.28(118-126)Online publication date: 13-Sep-2010
https://dl.acm.org/doi/10.1109/ICPPW.2010.28

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