Input-Sensitive Profiling

In this article we present a building block technique and a toolkit towards automatic discovery of workload-dependentperformance bottlenecks. From one or more runs of a program, our profiler automatically measures how the performance of individual routines scales as a function of the input size, yielding clues to their growth rate. The output of the profiler is, for each executed routine of the program, a set of tuples that aggregate performance costs by input size. The collected profiles can be used to produceperformance plots and derive trend functions by statistical curve fitting techniques. A key feature of our method is the ability toautomatically measure the size of the input given to a generic code fragment: to this aim, we propose an effective metric for estimating the input size of a routine and show how to compute it efficiently. We discuss several examples, showing that our approach can reveal asymptotic bottlenecks that other profilers may fail to detect and can provide useful characterizations of the workload and behavior of individual routines in the context of mainstream applications, yielding several code optimizations as well as algorithmic improvements. To prove the feasibility of our techniques, we implemented a Valgrind tool called aprof and performed an extensive experimentalevaluation on the SPEC CPU2006 benchmarks. Our experiments show that aprof delivers comparable performance to otherprominent Valgrind tools, and can generate informative plots even from single runs on typical workloads for mostalgorithmically-critical routines.