Automatic pool allocation: Improving performance by controlling data structure layout in the heap

Chris Lattner, Vikram Adve

Research output: Contribution to conferencePaper

Abstract

This paper describes Automatic Pool Allocation, a transformation framework that segregates distinct instances of heap-based data structures into seperate memory pools and allows heuristics to be used to partially control the internal layout of those data structures. The primary goal of this work is performance improvement, not automatic memory management, and the paper makes several new contributions. The key contribution is a new compiler algorithm for partitioning heap objects in imperative programs based on a context-sensitive pointer analysis, including a novel strategy for correct handling of indirect (and potentially unsafe) function calls. The transformation does not require type safe programs and works for the full generality of C and C++. Second, the paper describes several optimizations that exploit data structure partitioning to further improve program performance. Third, the paper evaluates how memory hierarchy behavior and overall program performance are impacted by the new transformations. Using a number of bench-marks and a few applications, we find that compilation times are extremely low, and overall running times for heap intensive programs speed up by 10-25% in many cases, about 2x in two cases, and more than 10x in two small benchmarks. Overall, we believe this work provides a new framework for optimizing pointer intensive programs by segregating and controlling the layout of heap-based data structures.

Original languageEnglish (US)
Pages129-142
Number of pages14
StatePublished - Dec 1 2005
Event2005 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 05 - Chicago, IL, United States
Duration: Jun 12 2005Jun 15 2005

Other

Other2005 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 05
CountryUnited States
CityChicago, IL
Period6/12/056/15/05

Fingerprint

Data structures
Data storage equipment

Keywords

  • Cache, static analysis
  • Data layout
  • Pool allocation
  • Recursive data structure

ASJC Scopus subject areas

  • Software

Cite this

Lattner, C., & Adve, V. (2005). Automatic pool allocation: Improving performance by controlling data structure layout in the heap. 129-142. Paper presented at 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 05, Chicago, IL, United States.

Automatic pool allocation : Improving performance by controlling data structure layout in the heap. / Lattner, Chris; Adve, Vikram.

2005. 129-142 Paper presented at 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 05, Chicago, IL, United States.

Research output: Contribution to conferencePaper

Lattner, C & Adve, V 2005, 'Automatic pool allocation: Improving performance by controlling data structure layout in the heap', Paper presented at 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 05, Chicago, IL, United States, 6/12/05 - 6/15/05 pp. 129-142.
Lattner C, Adve V. Automatic pool allocation: Improving performance by controlling data structure layout in the heap. 2005. Paper presented at 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 05, Chicago, IL, United States.
Lattner, Chris ; Adve, Vikram. / Automatic pool allocation : Improving performance by controlling data structure layout in the heap. Paper presented at 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 05, Chicago, IL, United States.14 p.
@conference{8c9808b625174e3a8c9f045be31d4050,
title = "Automatic pool allocation: Improving performance by controlling data structure layout in the heap",
abstract = "This paper describes Automatic Pool Allocation, a transformation framework that segregates distinct instances of heap-based data structures into seperate memory pools and allows heuristics to be used to partially control the internal layout of those data structures. The primary goal of this work is performance improvement, not automatic memory management, and the paper makes several new contributions. The key contribution is a new compiler algorithm for partitioning heap objects in imperative programs based on a context-sensitive pointer analysis, including a novel strategy for correct handling of indirect (and potentially unsafe) function calls. The transformation does not require type safe programs and works for the full generality of C and C++. Second, the paper describes several optimizations that exploit data structure partitioning to further improve program performance. Third, the paper evaluates how memory hierarchy behavior and overall program performance are impacted by the new transformations. Using a number of bench-marks and a few applications, we find that compilation times are extremely low, and overall running times for heap intensive programs speed up by 10-25{\%} in many cases, about 2x in two cases, and more than 10x in two small benchmarks. Overall, we believe this work provides a new framework for optimizing pointer intensive programs by segregating and controlling the layout of heap-based data structures.",
keywords = "Cache, static analysis, Data layout, Pool allocation, Recursive data structure",
author = "Chris Lattner and Vikram Adve",
year = "2005",
month = "12",
day = "1",
language = "English (US)",
pages = "129--142",
note = "2005 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 05 ; Conference date: 12-06-2005 Through 15-06-2005",

}

TY - CONF

T1 - Automatic pool allocation

T2 - Improving performance by controlling data structure layout in the heap

AU - Lattner, Chris

AU - Adve, Vikram

PY - 2005/12/1

Y1 - 2005/12/1

N2 - This paper describes Automatic Pool Allocation, a transformation framework that segregates distinct instances of heap-based data structures into seperate memory pools and allows heuristics to be used to partially control the internal layout of those data structures. The primary goal of this work is performance improvement, not automatic memory management, and the paper makes several new contributions. The key contribution is a new compiler algorithm for partitioning heap objects in imperative programs based on a context-sensitive pointer analysis, including a novel strategy for correct handling of indirect (and potentially unsafe) function calls. The transformation does not require type safe programs and works for the full generality of C and C++. Second, the paper describes several optimizations that exploit data structure partitioning to further improve program performance. Third, the paper evaluates how memory hierarchy behavior and overall program performance are impacted by the new transformations. Using a number of bench-marks and a few applications, we find that compilation times are extremely low, and overall running times for heap intensive programs speed up by 10-25% in many cases, about 2x in two cases, and more than 10x in two small benchmarks. Overall, we believe this work provides a new framework for optimizing pointer intensive programs by segregating and controlling the layout of heap-based data structures.

AB - This paper describes Automatic Pool Allocation, a transformation framework that segregates distinct instances of heap-based data structures into seperate memory pools and allows heuristics to be used to partially control the internal layout of those data structures. The primary goal of this work is performance improvement, not automatic memory management, and the paper makes several new contributions. The key contribution is a new compiler algorithm for partitioning heap objects in imperative programs based on a context-sensitive pointer analysis, including a novel strategy for correct handling of indirect (and potentially unsafe) function calls. The transformation does not require type safe programs and works for the full generality of C and C++. Second, the paper describes several optimizations that exploit data structure partitioning to further improve program performance. Third, the paper evaluates how memory hierarchy behavior and overall program performance are impacted by the new transformations. Using a number of bench-marks and a few applications, we find that compilation times are extremely low, and overall running times for heap intensive programs speed up by 10-25% in many cases, about 2x in two cases, and more than 10x in two small benchmarks. Overall, we believe this work provides a new framework for optimizing pointer intensive programs by segregating and controlling the layout of heap-based data structures.

KW - Cache, static analysis

KW - Data layout

KW - Pool allocation

KW - Recursive data structure

UR - http://www.scopus.com/inward/record.url?scp=31844446709&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=31844446709&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:31844446709

SP - 129

EP - 142

ER -