Memory Management with Explicit Regions David Gay* and Alex Aiken’ EECS Department University of California, Berkeley {dgay,aiken}@cs.berkeley.edu Abstract Much research has been devoted to studies of and algo- rithms for memory management based on garbage col- lection or explicit allocation and deallocation. An al- ternative approach, region-based memory management, has been known for decades, but has not been well- studied, In a region-based system each allocation spec- ifies a region, and memory is reclaimed by destroying a region, freeing all the storage allocated therein. We show that on a suite of allocation-intensive C programs, regions are competitive with malloc/free and sometimes substantially faster. We also show that regions sup- port safe memory management with low overhead. Ex- perience with our benchmarks suggests that modifying many existing programs to use regions is not difficult. 1 Introduction The two most popular memory management tech- niques are explicit allocation and deallocation, as in C’s malloc/free, and various forms of garbage- collection [Wi192]. Both have well-known advantages and disadvantages, discussed further below. A third al- ternative is region-based memory allocation, which has been widely used as an implementation technique for many years under a variety of names, e.g., zones [ROSEN], groups [lY90], or arenas [HanSO]. Regions have also re- cently attracted research attention as a target for static inference of memory management [TT97] and for im- proving locality of dynamically allocated data [Sto97]. In a region-based memory allocation scheme each al- located object is placed in a program-specified region. Memory is reclaimed by destroying a region, freeing all the objects allocated therein. A simple example is shown in Figure 1. Each iteration of the loop allocates a small array. The call to deleteregion frees all arrays. *This material is based in part upon work supported by NSF Young Investigator Award No. CCR9457812, DARPA contract F30602-95-C-0136 and a Microsoft graduate fellowship. ~3 ,666 ACM 0-89791-987-4/98/0006...$6.00 void f (1 c Region r = newregion ; for (i = 0; i < 10; i++) C int *x = ralloc(r, (i + 1) * sizeof (int)); work(i, x); 1 deleteregion( I Figure 1: An example of region-based allocation. In the commonly used version of region-based program- ming, regions are explicit in the program and entirely under programmer control. To our knowledge, the per- formance of this popular implementation technique has never been studied. Our f&t contribution is a detailed comparison of the performance of regions with mal- lot/free libraries and conservative garbage collection on a set of benchmark programs. Our conclusion is that explicit regions are, for our benchmarks, faster than ei- ther malloc/free or conservative garbage collection, and sometimes significantly so (up to 16%). Memory con- sumption is good in our experiments: regions use from 9% less to 19% more memory than the best alternative and always rank either first or second (see Section 5). While our study supports the use of regions on perfor- mance grounds, the common implementation of regions is unsafe, as a region r can be deleted even if other regions have accessible pointers to objects in r. Our second contribution is the study of a safe region imple- mentation in which a region r can be deleted only if there are no ezternalreferences to objects in r (a refer- ence external to r is any pointer not stored within r). We enforce this rule by keeping a reference counf for each region; deleteregion is a no-op when this refer- ence count is nonzero. Note that by reference count- ing regions instead of individual objects two common problems with reference counting are ameliorated: min- imal space is devoted to storing reference counts, and cyclic structures can be collected so long as they are al- located within a single region. The overhead of safety varies from negligible to 17% on our benchmarks, but the comparative performance remains almost the same: regions are still faster (up to 9%) than the alternatives 313in all but a few cases, and in those cases regions are only slightly slower (up to 5%). A third contribution is an assessment of how difficult it is to program with explicit regions. Our metric is the number and type of changes required to modify an appli- cation to use regions. All of our benchmarks required only modest recoding to use regions, and the needed region organization was straightforward to derive (see Section 5.1). We also found that explicit regions have some partic- ular strengths. First, regions bring structure to mem- ory management, making programs clearer and, in our subjective assessment, easier to write compared to us- ing malloc/free. For example, it is not necessary to walk through a complex data structure to deallocate it. Second, we found some evidence that regions can be used to provide significantly improved data local- ity, as posited by Stoutamire [Sto97]. The execution time of one benchmark was improved 24% simply by reorganizing allocation so that the most frequently ac- cessed objects are allocated in a single region. Nei- ther malloc/free nor garbage-collected systems provide any mechanism for expressing locality. Third, regions are useful for building software with predictable perfor- mance, as the cost of every operation is easily bounded, at least for unsafe regions and in [TT97] for compiler- inferred safe regions (see Section 2). Our safe imple- mentation uses a moderately sophisticated scheme for efficiency; we show that the overhead of this scheme is amortized constant time per instruction executed, as- suming that the size of stack frames is bounded by a constant (see Section