Traditional profilers identify where a program spends most of its resources. They do not provide information about why the program spends those resources or about how resource consumption would change for different program inputs. In this paper we introduce 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 determining the "inputs" of a program, by measuring the program's "cost" for any given input, and by inferring an empirical cost function.

When designers of Java runtime systems evaluate the performance of their systems for the purpose of running clientside Java applications, they normally use the Dacapo and SPEC JVM benchmark suites. However, when users of those Java runtime systems run client applications, they usually run interactive applications such as Eclipse or NetBeans. In this paper we study whether this mismatch is a problem: Do the prevalent Java client-side benchmark suites faithfully represent the characteristics of real-world Java client applications? To answer this question we characterize benchmarks and applications using three kinds of metrics: static metrics, architecture-independent dynamic metrics, and hardware performance counters. We find that real-world applications significantly differ from existing benchmarks. Our finding indicates that the current benchmark suites should be augmented to more faithfully represent the large segment of interactive applications.

Many experimental performance evaluations depend on accurate measurements of the cost of executing a piece of code. Often these measurements are conducted using infrastructures to access hardware performance counters. Most modern processors provide such counters to count micro-architectural events such as retired instructions or clock cycles. These counters can be difficult to configure, may not be programmable or readable from user-level code, and can not discriminate between events caused by different software threads. Various software infrastructures address this problem, providing access to per-thread counters from application code. This paper constitutes the first comparative study of the accuracy of three commonly used measurement infrastructures (perfctr, perfmon2, and PAPI) on three common processors (Pentium D, Core 2 Duo, and AMD ATHLON 64 X2).