Article

Message analysis-guided allocation and low-pause incremental garbage collection in a concurrent language

Authors:

Konstantinos Sagonas,

Jesper WilhelmssonAuthors Info & Claims

ISMM '04: Proceedings of the 4th international symposium on Memory management

Pages 1 - 12

https://doi.org/10.1145/1029873.1029875

Published: 24 October 2004 Publication History

Abstract

We present a memory management scheme for a concurrent programming language where communication occurs using message-passing with copying semantics. The runtime system is built around process-local heaps, which frees the memory manager from redundant synchronization in a multithreaded implementation and allows the memory reclamation of process-local heaps to be a private business and to often take place without garbage collection. The allocator is guided by a static analysis which speculatively allocates data possibly used as messages in a shared memory area. To respect the (soft) real-time requirements of the language, we develop a generational, incremental garbage collection scheme tailored to the characteristics of this runtime system. The collector imposes no overhead on the mutator, requires no costly barrier mechanisms, and has a relatively small space overhead. We have implemented these schemes in the context of an industrial-strength implementation of a concurrent functional language used to develop large-scale, highly concurrent, embedded applications. Our measurements across a range of applications indicate that the incremental collector substantially reduces pause times, imposes only very small overhead on the total runtime, and achieves a high degree of mutator utilization.

References

[1]

J. Armstrong and R. Virding. One pass real-time generational mark-sweep garbage collection. In H. G. Baker, editor, Proceedings of IWMM'95: International Workshop on Memory Management, number 986 in LNCS, pages 313--322. Springer-Verlag, Sept. 1995.

Digital Library

[2]

J. Armstrong, R. Virding, C. Wikstrom, and M. Williams. Concurrent Programming in Erlang. Prentice Hall Europe, Herfordshire, Great Britain, second edition, 1996.

Digital Library

[3]

D. F. Bacon, P. Cheng, and V. T. Rajan. A real-time garbage collector with low overhead and consistent utilization. In Conference Record of POPL 2003: The 30th SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 285--298, New York, N.Y., Jan. 2003. ACM Press.

Digital Library

[4]

B. Blanchet. Escape analysis for Java™: Theory and practice. ACM Trans. Prog. Lang. Syst., 25(6):713--775, Nov. 2003.

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, Proceedings of the 1984 ACM Symposium on LISP and Functional Programming, pages 256--262, New York, N.Y., 1984. ACM Press.

Digital Library

[6]

R. Carlsson, K. Sagonas, and J. Wilhelmsson. Message analysis for concurrent languages. In R. Cousot, editor, Static Analysis: Proceedings of the 10th International Symposium, number 2694 in LNCS, pages 73--90, Berlin, Germany, June 2003. Springer.

Digital Library

[7]

C. J. Cheney. A nonrecursive list compacting algorithm. Communications of the ACM, 13(11):677--678, Nov. 1970.

Digital Library

[8]

P. Cheng and G. E. Blelloch. A parallel, real-time garbage collector. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 125--136, New York, N.Y., June 2001. ACM Press.

Digital Library

[9]

P. Cheng, R. Harper, and P. Lee. Generational stack collection and profile-driven pretenuring. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI'98, pages 162--173, New York, N.Y., 1998. ACM Press.

Digital Library

[10]

J.-D. Choi, M. Gupta, M. Serrano, V. C. Shreedhar, and S. P. Midkiff. Stack allocation and synchronization optimizations for Java using escape analysis. ACM Trans. Prog. Lang. Syst., 25(6):876--910, Nov. 2003.

Digital Library

[11]

G. E. Collins. A method for overlapping and erasure of lists. Communications of the ACM, 3(12):655--657, Dec. 1960.

Digital Library

[12]

D. Doligez and X. Leroy. A concurrent, generational garbage collector for a multithreaded implementation of ML. In Conference Record of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 113--123, New York, N.Y., Jan. 1993. ACM Press.

Digital Library

[13]

T. Domani, G. Goldshtein, E. Kolodner, E. Lewis, E. Petrank, and D. Sheinwald. Thread-local heaps for Java. In D. Detlefs, editor, Proceedings of ISMM'2002: ACM SIGPLAN International Symposium on Memory Management, pages 76--87, New York, N.Y., June 2002. ACM Press.

Digital Library

[14]

M. Feeley and M. Larose. A compacting incremental collector and its performance in a production quality compiler. In Proceedings of ISMM'98: ACM SIGPLAN International Symposium on Memory Management, pages 1--9, New York, N.Y., Oct. 1998. ACM Press.

Digital Library

[15]

L. Huelsbergen and J. R. Larus. A concurrent copying garbage collector for languages that distinguish (im) mutable data. In Proceedings of the 4th ACM Symposium on Principles and Practice of Parallel Programming, pages 73--82, New York, N.Y., May 1993. ACM Press.

Digital Library

[16]

E. Johansson, M. Pettersson, and K. Sagonas. HiPE: A High Performance Erlang system. In Proceedings of the ACM SIGPLAN Conference on Principles and Practice of Declarative Programming, pages 32--43, New York, NY, Sept. 2000. ACM Press.

Digital Library

[17]

E. Johansson, K. Sagonas, and J. Wilhelmsson. Heap architectures for concurrent languages using message passing. In D. Detlefs, editor, Proceedings of ISMM'2002: ACM SIGPLAN International Symposium on Memory Management, pages 88--99, New York, N.Y., June 2002. ACM Press.

Digital Library

[18]

R. E. Jones and R. Lins. Garbage Collection: Algorithms for automatic memory management. John Wiley & Sons, 1996.

Digital Library

[19]

D. Mosberger and T. Jin. httperf--a tool for measuring web server performance. SIGMETRICS Perform. Eval. Rev., 26(3):31--37, Dec. 1998.

Digital Library

[20]

S. Nettles and J. O'Toole. Real-time replication garbage collection. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 217--226, New York, N.Y, June 1993. ACM Press.

Digital Library

[21]

M. Pettersson. Linux x86 performance-monitoring counters driver. http://user.it.uu.se/~mikpe/linux/perfctr/.

[22]

E. Ruf. Effective synchronization removal for Java. In Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation, pages 208--218, New York, N.Y., June 2000. ACM Press.

Digital Library

[23]

B. Steensgaard. Thread-specific heaps for multi-threaded programs. In Proceedings of the ACM SIGPLAN International Symposium on Memory Management, pages 18--24, New York, N.Y., Oct. 2000. ACM Press.

Digital Library

[24]

L. Stein and D. MacEachern. Writing Apache Modules with Perl and C. O'Reilly & Associates, 1999.

Digital Library

[25]

P. R. Wilson. Uniprocessor garbage collection techniques. In Y. Bekkers and J. Cohen, editors, Proceedings of IWMM'92: International Workshop on Memory Management, number 637 in LNCS, pages 1--42, Berlin, Germany, Sept. 1992. Springer-Verlag. See also expanded version as Univ. of Texas Austin technical report submitted to ACM Computing Surveys.

Digital Library

Cited By

Ueno KOhori ALippautz MChisnall D(2022)Concurrent and parallel garbage collection for lightweight threads on multicore processorsProceedings of the 2022 ACM SIGPLAN International Symposium on Memory Management10.1145/3520263.3534652(29-42)Online publication date: 14-Jun-2022
https://dl.acm.org/doi/10.1145/3520263.3534652
Fähndrich MAiken MHawblitzel CHodson OHunt GLarus JLevi S(2006)Language support for fast and reliable message-based communication in singularity OSACM SIGOPS Operating Systems Review10.1145/1218063.121795340:4(177-190)Online publication date: 18-Apr-2006
https://dl.acm.org/doi/10.1145/1218063.1217953
Fähndrich MAiken MHawblitzel CHodson OHunt GLarus JLevi SBerbers YZwaenepoel W(2006)Language support for fast and reliable message-based communication in singularity OSProceedings of the 1st ACM SIGOPS/EuroSys European Conference on Computer Systems 200610.1145/1217935.1217953(177-190)Online publication date: 18-Apr-2006
https://dl.acm.org/doi/10.1145/1217935.1217953
Show More Cited By

Index Terms

Recommendations

Message analysis for concurrent programs using message passing

We describe an analysis-driven storage allocation scheme for concurrent systems that use message passing with copying semantics. The basic principle is that in such a system, data which is not part of any message does not need to be allocated in a ...
Efficient memory management for concurrent programs that use message passing
Special issue on five perspectives on modern memory management: Systems, hardware and theory

We present an efficient memory management scheme for concurrent programming languages where communication occurs by using message passing with copying semantics. The runtime system is built around process-local heaps, which frees the memory manager from ...
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, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

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

General Chair:
David F. Bacon
IBM Research
,
Program Chair:
Amer Diwan
University of Colorado

Copyright © 2004 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: 24 October 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ISMM04

Sponsor:

ISMM04: 2004 International Symposium on Memory Management ( in conjunction with OOPSLA 2004 Conference )

October 24 - 25, 2004

BC, Vancouver, Canada

Acceptance Rates

Overall Acceptance Rate 72 of 156 submissions, 46%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
367
Total Downloads

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

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ueno KOhori ALippautz MChisnall D(2022)Concurrent and parallel garbage collection for lightweight threads on multicore processorsProceedings of the 2022 ACM SIGPLAN International Symposium on Memory Management10.1145/3520263.3534652(29-42)Online publication date: 14-Jun-2022
https://dl.acm.org/doi/10.1145/3520263.3534652
Fähndrich MAiken MHawblitzel CHodson OHunt GLarus JLevi S(2006)Language support for fast and reliable message-based communication in singularity OSACM SIGOPS Operating Systems Review10.1145/1218063.121795340:4(177-190)Online publication date: 18-Apr-2006
https://dl.acm.org/doi/10.1145/1218063.1217953
Fähndrich MAiken MHawblitzel CHodson OHunt GLarus JLevi SBerbers YZwaenepoel W(2006)Language support for fast and reliable message-based communication in singularity OSProceedings of the 1st ACM SIGOPS/EuroSys European Conference on Computer Systems 200610.1145/1217935.1217953(177-190)Online publication date: 18-Apr-2006
https://dl.acm.org/doi/10.1145/1217935.1217953
Vechev MYahav EBacon DSchwartzbach MBall T(2006)Correctness-preserving derivation of concurrent garbage collection algorithmsProceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/1133981.1134022(341-353)Online publication date: 11-Jun-2006
https://dl.acm.org/doi/10.1145/1133981.1134022
Vechev MYahav EBacon D(2006)Correctness-preserving derivation of concurrent garbage collection algorithmsACM SIGPLAN Notices10.1145/1133255.113402241:6(341-353)Online publication date: 11-Jun-2006
https://dl.acm.org/doi/10.1145/1133255.1134022
Lindgren TSagonas KArmstrong J(2005)Atom garbage collectionProceedings of the 2005 ACM SIGPLAN workshop on Erlang10.1145/1088361.1088369(40-45)Online publication date: 26-Sep-2005
https://dl.acm.org/doi/10.1145/1088361.1088369
Bacon DCheng PGrove DHind MRajan VYahav EHauswirth MKirsch CSpoonhower DVechev MWolf W(2005)High-level real-time programming in JavaProceedings of the 5th ACM international conference on Embedded software10.1145/1086228.1086242(68-78)Online publication date: 18-Sep-2005
https://dl.acm.org/doi/10.1145/1086228.1086242

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