Algorithmic profiling

Traditional profilers identify where a program spends most of its resources. They do not provide information about why the pro-gram spends those resources or about how resource consumption would change for different program inputs. In this paper we intro-duce the idea of algorithmic profiling. While a traditional profiler determines a set of measured cost values, an algorithmic profiler determines a cost function. It does that by automatically determin-ing the “inputs ” of a program, by measuring the program’s “cost” for any given input, and by inferring an empirical cost function