Automatic Pool Allocation: Compile-Time Control of Data Structure Layout in the Heap

Lattner, Chris A.; Adve, Vikram S.

Permalink

https://hdl.handle.net/2142/10890 Copy

Description

Title

Automatic Pool Allocation: Compile-Time Control of Data Structure Layout in the Heap

Author(s)

• Lattner, Chris A.
• Adve, Vikram S.

Issue Date

2004-07

Keyword(s)

compilers

Abstract

Despite the potential importance of data structure layouts and traversal patterns, compiler transformations on pointer-intensive programs are performed primarily using pointer analysis, and not by controlling and using information about the layout of high-level data structures. This paper describes a compiler transformation called \emph{Automatic Pool Allocation} that segregates instances of ``logical'' data structures in the heap into distinct pools, and allows different heuristics to be used to partially control the internal layout of those data structures. Because these are rigorous transformations, their results, combined with pointer analysis information, can be used to perform further compiler analyses and transformations, and we briefly list a few examples. Automatic Pool Allocation also provides several direct performance benefits for pointer intensive programs, most importantly, that traversals of a logical data structure allocated to a separate pool can have better spatial locality and smaller working sets. We evaluate the performance and cache behavior of the code transformed by the automatic pool allocation transformation on a series of heap-intensive and general-purpose benchmarks, and find that it speeds up several C programs by 10-40\% percent or more, and does not hurt (or help) other programs.

Type of Resource

text

Permalink

http://hdl.handle.net/2142/10890

Copyright and License Information

You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections