Automatic pool allocation for disjoint data structures
Authors:
Open Access
- 16 June 2002
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 38 (2 suppleme) , 13-24
Abstract
This paper presents an analysis technique and a novel program transformation that can enable powerful optimizations for entire linked data structures. The fully automatic transformation converts ordinary programs to use pool (aka region) allocation for heap-based data structures. The transformation relies on an efficient link-time interprocedural analysis to identify disjoint data structures in the program, to check whether these data structures are accessed in a type-safe manner, and to construct a Disjoint Data Structure Graph that describes the connectivity pattern within such structures. We present preliminary experimental results showing that the data structure analysis and pool allocation are effective for a set of pointer intensive programs in the Olden benchmark suite. To illustrate the optimizations that can be enabled by these techniques, we describe a novel pointer compression transformation and briefly discuss several other optimization possibilities for linked data structures.Keywords
This publication has 26 references indexed in Scilit:
- Using generational garbage collection to implement cache-conscious data placementACM SIGPLAN Notices, 1998
- A region inference algorithmACM Transactions on Programming Languages and Systems, 1998
- Scalable cross-module optimizationACM SIGPLAN Notices, 1998
- Solving shape-analysis problems in languages with destructive updatingACM Transactions on Programming Languages and Systems, 1998
- Region-Based Memory ManagementInformation and Computation, 1997
- Simple and effective link-time optimization of Modula-3 programsACM SIGPLAN Notices, 1995
- Customalloc: Efficient synthesized memory allocatorsSoftware: Practice and Experience, 1993
- Interprocedural optimizationACM Transactions on Programming Languages and Systems, 1993
- Parallelizing programs with recursive data structuresIEEE Transactions on Parallel and Distributed Systems, 1990
- Improving locality of reference in a garbage-collecting memory management systemCommunications of the ACM, 1988