Language support for regions | ACM SIGPLAN Notices
- ️AikenAlex
- ️Tue May 01 2001
Abstract
Region-based memory management systems structure memory by grouping objects in regions under program control. Memory is reclaimed by deleting regions, freeing all objects stored therein. Our compiler for C with regions, RC, prevents unsafe region deletions by keeping a count of references to each region. Using type annotations that make the structure of a program's regions more explicit, we reduce the overhead of reference counting from a maximum of 27% to a maximum of 11% on a suite of realistic benchmarks. We generalise these annotations in a region type system whose main novelty is the use of existentially quantified abstract regions to represent pointers to objects whose region is partially or totally unknown. A distribution of RC is available at http://www.cs.berkeley.edu/~dgay/rc.tar.gz.
References
[1]
D. A Barrett and B. G. Zorn Using Lifetime Predictors to Improve Memory Allocation Performance In Proceedings of the ACM SIGPLAN '93 Conference on Programming Languages Design and Implementation pages 187-196, Albuquerque, New Mexico, June 1993.
[2]
D G Bobrow Managing Re-entrant Structures using Reference Counts ACM Transactions on Programming Languages and Systems 2(3):269-273, July 1980.
[3]
K Crary, D Walker, and G Morrisett. Typed Memory Management in a Calculus of Capabilities. In Conference Record of POPL '99: The 26th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages pages 262-275, San Antonio, Texas, Jan 1999.
[4]
R Deline and M. F~hndrich. Enforcing High-Level Protocols in Low-Level Software.In Proceedings of the ACM SIGPLAN '01 Conference on Programming Language Design and Implementation Snowbird, Utah, June 2001.
[5]
C W Fraser and D. R. Hanson A Retargetable C Compiler: Design and Implementation Benjamin/Cummings Pub. Co., Redwood City, CA, USA, 1995.
[6]
D Gay and A Aiken Memory Management with Explicit Regions. In Proceedings of the ACM SIGPLAN '98 Conference on Programming Language Design and Implementation pages 313-323, Montr~al, Canada, June 1998.
[7]
D Gay and A Aiken Language Support and Compilation Techniques for Regions Technical Report UCB//CSD-00-1115, EECS Department, University of California, Berkeley, Nov 2000.
[8]
D R Hanson Fast Allocation and Deallocation of Memory Based on Object Lifetimes. Software Practice and Experience 20(1):5-12, Jan 1990.
[9]
Y Ichisugi and A. Yonezawa Distributed Garbage Collection Using Group Reference Counting In OOPSLA/ECOOP '90 Workshop on Garbage Collection in Object-Oriented Systems Oct 1990.
[10]
D T. Ross. The AED Free Storage Package. Communications of the ACM 10(8): 481-492, Aug. 1967.
[11]
D Stoutamire. Portable, Modular Expression of Locality PhD thesis, University of California at Berkeley, 1997.
[12]
D. Stoutamire and S Omohundro The Sather 11 Specification Technical Report TR-96-012, International Computer Science Institute, Berkeley, CA,August 1996.
[13]
M. Tofte and J.-P Talpin Region-Based Memory Management Information and Computation 132(2):109-176, Feb 1997.
[14]
K -P Vo. Vmalloc: A General and Efficient Memory Allocator. Software Practice and Experience 26(3):357-374, Mar. 1996.
[15]
D Walker and G Morrisett Alias Types for Recursive Data Structures. Technical Report TR2000-1787, Cornell University, Mar. 2000.
[16]
P R Wilson Uniprocessor Garbage Collection Techniques In Proceedings of International Workshop on Memory Management volume 637 of Lecture Notes in Computer Science St Malo, France, Sept 1992. Springer-Verlag.
[17]
P R Wilson, M S Johnstone, M Neely, and D. Boles Dynamic Storage Allocation: A Survey and Critical Review. In Proceedings of International Workshop on Memory Management volume 986 of Lecture Notes in Computer Science Kinross, Scotland, Sept 1995. Springer-Verlag.
Information & Contributors
Information
Published In
ACM SIGPLAN Notices Volume 36, Issue 5
May 2001
330 pages
PLDI '01: Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation
June 2001
331 pages
Copyright © 2001 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]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 May 2001
Published in SIGPLAN Volume 36, Issue 5
Check for updates
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- Downloads (Last 12 months)7
- Downloads (Last 6 weeks)0
Reflects downloads up to 18 Feb 2025
Other Metrics
Citations
- Arvidsson ECastegren EClebsch SDrossopoulou SNoble JParkinson MWrigstad T(2023)Reference Capabilities for Flexible Memory ManagementProceedings of the ACM on Programming Languages10.1145/36228467:OOPSLA2(1363-1393)Online publication date: 16-Oct-2023
- SHIVKUMAR BMURPHY JZIAREK L(2021)Real-time MLton: A Standard ML runtime for real-time functional programsJournal of Functional Programming10.1017/S095679682100017431Online publication date: 31-Aug-2021
- Mezzina CSchlatte RGlück RHaulund THoey JHolm Cservenka MLanese IMogensen TSiljak HSchultz UUlidowski I(2020)Software and Reversible Systems: A Survey of Recent ActivitiesReversible Computation: Extending Horizons of Computing10.1007/978-3-030-47361-7_2(41-59)Online publication date: 12-May-2020
- Margossian C(2019)A review of automatic differentiation and its efficient implementationWIREs Data Mining and Knowledge Discovery10.1002/widm.13059:4Online publication date: 20-Mar-2019
- Nguyen KWang KBu YFang LHu JXu GOzturk OEbcioglu KDwarkadas S(2015)FACADEProceedings of the Twentieth International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/2694344.2694345(675-690)Online publication date: 14-Mar-2015
- Garbervetsky DYovine SBraberman VRouaux MTaboada A(2011)Quantitative dynamic-memory analysis for JavaConcurrency and Computation: Practice & Experience10.1002/cpe.165623:14(1665-1678)Online publication date: 1-Sep-2011
- Boudol G(2008)Typing Safe DeallocationProgramming Languages and Systems10.1007/978-3-540-78739-6_10(116-130)Online publication date: 2008
- Salagnac GRippert CYovine S(2007)Semi-Automatic Region-Based Memory Management for Real-Time Java Embedded SystemsProceedings of the 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications10.1109/RTCSA.2007.67(73-80)Online publication date: 21-Aug-2007
- Swamy NHicks MMorrisett GGrossman DJim T(2006)Safe manual memory management in cycloneScience of Computer Programming10.1016/j.scico.2006.02.00362:2(122-144)Online publication date: 1-Oct-2006
- Lee OYang HYi K(2005)Static insertion of safe and effective memory reuse commands into ML-like programsScience of Computer Programming10.1016/j.scico.2005.02.00758:1-2(141-178)Online publication date: 1-Oct-2005
- 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.