Article

Mark-sweep or copying?: a "best of both worlds" algorithm and a hardware-supported real-time implementation

Authors:

Sylvain Stanchina,

Matthias MeyerAuthors Info & Claims

ISMM '07: Proceedings of the 6th international symposium on Memory management

Pages 173 - 182

https://doi.org/10.1145/1296907.1296928

Published: 21 October 2007 Publication History

Abstract

Copying collectors offer a number of advantages over their mark-sweep counterparts. First, they do not have to deal with mark stacks and potential mark stack overflows. Second, they do not suffer from unpredictable fragmentation overheads since they inherently compact the heap. Third, the tospace invariant maintained by many copying collectors allows for incremental compaction and provides the basisfor efficient real-time implementations. Unfortunately, however, standard copying collectors depend on two semispaces and therefore need at least twice as much memory as required for the maximum amount of live data.In this paper, we introduce a novel mark-compact algorithm that combines the elegance and simplicity of Baker's copying algorithm with the memory efficiency of mark-sweep algorithms. Furthermore, we present a hardware-supported implementation for real-time applications in the framework of an object-based RISC architecture.Measurements of Java programs on an FPGA-based prototype show that our novel mark-compact algorithm outperforms a corresponding copying collector in every respect. It requires far less memory space for real-time behavior and, at the same time, reduces the overall runtime overhead under typical operating conditions.

References

[1]

Altera. STRATIX II Device Family Data Sheet, Apr. 2006.

[2]

D.F. Bacon, P. Cheng, and V. Rajan. A real--time garbage collector with low overhead and consistent utilization. In Conference Record of the Thirtieth Annual ACM Symposium on Principles of Programming Languages,ACM SIGPLAN Notices, New Orleans, LA, Jan. 2003. ACM Press.

Digital Library

[3]

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

Digital Library

[4]

O. Ben--Yitzhak, I. Goft, E. Kolodner, K.Kuiper, and V. Leikehman. An algorithm for parallel incremental compaction. In D. Detlefs, editor, ISMM'02 Proceedings of the Third International Symposium on Memory Management,ACM SIGPLAN Notices, pages 100--105, Berlin, June 2002. ACM Press.

Digital Library

[5]

R. A. Brooks. Trading data space for reduced time and code space in real--time garbage collection on stock hardware. In G. L. Steele, editor, Conference Record of the 1984 ACM Symposium on Lisp and Functional Programming, pages 256--262, Austin, TX, Aug. 1984. ACM Press.

Digital Library

[6]

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

Digital Library

[7]

D. Dube, M. Feeley, and M. Serrano. Un GC temps rel semicompactant. Journes Francophones des Langages Applicatifs, pages 165--181, Jan. 1996.

[8]

B.K. Haddon and W.M. Waite. A compaction procedure for variable length storage elements. Computer Journal, 10:162--165, Aug. 1967.

[9]

R. Jones, editor. ISMM'98 Proceedings of the First International Symposium on Memory Management, volume 34(3) of ACM SIGPLAN Notices,Vancouver, Oct. 1998.ACM Press.

[10]

H.B.M. Jonkers. A fast garbage compaction algorithm. Information Processing Letters, 9(1):25--30, July 1979.

[11]

B. Lang and F. Dupont. Incremental incrementally compacting garbage collection. In SIGPLAN'87 Symposium on Interpreters and Interpretive Techniques, volume 22(7) of ACM SIGPLAN Notices, pages 253--263.ACM Press, 1987.

Digital Library

[12]

M. Larose and M. Feeley. A compacting incremental collector and its performance in a production quality compiler. In Jones {9}, pages 1--9.

Digital Library

[13]

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

Digital Library

[14]

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, HongKong, Aug. 2005.

Digital Library

[15]

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

Digital Library

[16]

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

[17]

K. D. Nilsen. Cost--effective hardware--assisted real--time garbage collection. In Workshop on Language, Compiler, and Tool Support for Real--Time Systems, PLDI94, June 1994.

[18]

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

[19]

Y. Ossia, O. Ben--Yitzhak, and M. Segal. Mostly concurrent compaction for mark--sweep GC. In A. Diwan, editor, ISMM'04 Proceedings of the Fourth International Symposium on Memory Management,ACM SIGPLAN Notices,Vancouver, Oct. 2004.ACM Press.

Digital Library

[20]

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

[21]

N. Sachindran and E. Moss. MarkCopy: Fast copying GC with less space overhead. In OOPSLA'03 ACM Conference on Object--Oriented Systems, Languages and Applications, ACM SIGPLAN Notices, Anaheim,CA,Nov. 2003.ACM Press.

Digital Library

[22]

N. Sachindran, J. E. B. Moss, and E. D. Berger. MC2: High performance garbage collection for memory--constrained environments. In OOPSLA'04 ACM Conference on Object Oriented Systems, Languages and Applications,ACM SIGPLAN Notices,Vancouver, Oct. 2004.ACM Press.

Digital Library

[23]

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

[24]

F. Siebert. Guaranteeing non--disruptiveness and real--time deadlines in an incrementalgarbage collector. In Jones {9}, pages 130--137.

Digital Library

[25]

Sun Microsystems. picoJava--II Programmer's Reference Manual, Mar. 1999.

[26]

I. W. Williams and M. I. Wolczko. An object--based memory architecture. In A. Dearle, G. M. Shaw, and S. B. Zdonik, editors, Implementing Persistent Object Bases: Principles and Practice (Proceedings of the Fourth International Workshop on Persistent Object Systems), pages 114--130, Martha's Vineyard, MA, Sept. 1990. Morgan Kaufman.

Cited By

García AMay DNutting E(2021)Integrated Hardware Garbage CollectionACM Transactions on Embedded Computing Systems10.1145/345014720:5(1-25)Online publication date: 9-Jul-2021
https://dl.acm.org/doi/10.1145/3450147
Jang JHeo JLee YWon JKim SJung SJang HHam TLee J(2019)CharonProceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture10.1145/3352460.3358297(726-739)Online publication date: 12-Oct-2019
https://dl.acm.org/doi/10.1145/3352460.3358297
Smith RRixner S(2016)Leveraging Managed Runtime Systems to Build, Analyze, and Optimize Memory GraphsACM SIGPLAN Notices10.1145/3007611.289225351:7(131-143)Online publication date: 25-Mar-2016
https://dl.acm.org/doi/10.1145/3007611.2892253
Show More Cited By

Index Terms

Mark-sweep or copying?: a "best of both worlds" algorithm and a hardware-supported real-time implementation
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Garbage collection

Recommendations

Exploiting the efficiency of generational algorithms for hardware-supported real-time garbage collection
SAC '07: Proceedings of the 2007 ACM symposium on Applied computing

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 ...
Comparing mostly-copying and mark-sweep conservative collection

Many high-level language compilers generate C code and then invoke a C compiler for code generation. To date, most, of these compilers link the resulting code against a conservative mark-sweep garbage collector in order to reclaim unused memory. We ...
Comparing mostly-copying and mark-sweep conservative collection
ISMM '98: Proceedings of the 1st international symposium on Memory management

Many high-level language compilers generate C code and then invoke a C compiler for code generation. To date, most, of these compilers link the resulting code against a conservative mark-sweep garbage collector in order to reclaim unused memory. We ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ISMM '07: Proceedings of the 6th international symposium on Memory management

October 2007

192 pages

ISBN:9781595938930

DOI:10.1145/1296907

General Chair:
Greg Morrisett
Not supplied
,
Program Chair:
Mooly Sagiv
Not supplied

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

ISMM07

Sponsor:

ISMM07: International Symposium on Memory Management

October 21 - 22, 2007

Quebec, Montreal, Canada

Acceptance Rates

Overall Acceptance Rate 72 of 156 submissions, 46%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
371
Total Downloads

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

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

García AMay DNutting E(2021)Integrated Hardware Garbage CollectionACM Transactions on Embedded Computing Systems10.1145/345014720:5(1-25)Online publication date: 9-Jul-2021
https://dl.acm.org/doi/10.1145/3450147
Jang JHeo JLee YWon JKim SJung SJang HHam TLee J(2019)CharonProceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture10.1145/3352460.3358297(726-739)Online publication date: 12-Oct-2019
https://dl.acm.org/doi/10.1145/3352460.3358297
Smith RRixner S(2016)Leveraging Managed Runtime Systems to Build, Analyze, and Optimize Memory GraphsACM SIGPLAN Notices10.1145/3007611.289225351:7(131-143)Online publication date: 25-Mar-2016
https://dl.acm.org/doi/10.1145/3007611.2892253
Smith RRixner SGupta-Cledat VPorter DSarkar V(2016)Leveraging Managed Runtime Systems to Build, Analyze, and Optimize Memory GraphsProceedings of the12th ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments10.1145/2892242.2892253(131-143)Online publication date: 25-Mar-2016
https://dl.acm.org/doi/10.1145/2892242.2892253
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
Cao TBlackburn SGao TMcKinley K(2012)The Yin and Yang of power and performance for asymmetric hardware and managed software2012 39th Annual International Symposium on Computer Architecture (ISCA)10.1109/ISCA.2012.6237020(225-236)Online publication date: Jun-2012
https://doi.org/10.1109/ISCA.2012.6237020
Tarau P(2011)Integrated symbol table, engine and heap memory management in multi-engine prologACM SIGPLAN Notices10.1145/2076022.199349746:11(129-138)Online publication date: 4-Jun-2011
https://dl.acm.org/doi/10.1145/2076022.1993497
Wagner GGal AWimmer CEich BFranz M(2011)Compartmental memory management in a modern web browserACM SIGPLAN Notices10.1145/2076022.199349646:11(119-128)Online publication date: 4-Jun-2011
https://dl.acm.org/doi/10.1145/2076022.1993496
Singer JKovoor GBrown GLuján M(2011)Garbage collection auto-tuning for Java mapreduce on multi-coresACM SIGPLAN Notices10.1145/2076022.199349546:11(109-118)Online publication date: 4-Jun-2011
https://dl.acm.org/doi/10.1145/2076022.1993495
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