Recursive Data Structure Profiling [abstract] (ACM DL, PDF)
Easwaran Raman and David I. August
Proceedings of the Third Annual ACM SIGPLAN Workshop on
Memory Systems Performance (MSP), June 2005.
As the processor-memory performance gap increases, so does the need
for aggressive data structure optimizations to reduce memory access
latencies. Such optimizations require a better understanding of the
memory behavior of programs. We propose a profiling technique called
Recursive Data Structure Profiling to help better understand the
memory access behavior of programs that use recursive data structures
(RDS) such as lists, trees, etc. An RDS profile captures the runtime
behavior of the individual instances of recursive data structures.
RDS profiling differs from other memory profiling techniques in its
ability to aggregate information pertaining to an entire data
structure instance, rather than merely capturing the behavior of
individual loads and stores, thereby giving a more global view of a
program's memory accesses. This paper describes a method for collecting RDS profile without
requiring any high-level program representation or type
information. RDS profiling achieves this with manageable space and
time overhead on a mixture of pointer intensive benchmarks from the SPEC, Olden and other
benchmark suites. To illustrate the potential of the RDS profile in
providing a better understanding of memory accesses, we introduce a
metric to quantify the notion of
stability of an RDS instance. A stable RDS instance is one that
undergoes very few changes to its structure between its initial
creation and final destruction, making it an attractive candidate to certain
data structure optimizations.