Estimating the empirical cost function of routines with dynamic workloads

A crucial aspect in software development is understanding how an application’s performance scales as a function of its input data. Estimating the empirical cost function of indi-vidual routines of a program can help developers predict the runtime on larger workloads and pinpoint asymptotic ineffi-ciencies in the code. While this has been the target of exten-sive research in performance profiling, a major limitation of state-of-the-art approaches is that the input size is assumed to be determinable from the program’s state prior to the in-vocation of the routine to be profiled, failing to characterize the scenario where routines dynamically receive input values during their activations. This results in missing workloads generated by kernel system calls (e.g., in response to I/O or network operations) or by other threads, which play a cru-cial role in modern concurrent and interactive applications. Measuring dynamic workloads poses several challenges, re-quiring shared-memory communication between threads to be efficiently traced. In this paper we present a new metric and an efficient algorithm for automatically estimating the size of the input of each routine activation. We provide ex-amples showing that our metric allows the estimation of the empirical cost functions of complex applications more pre-cisely than previous approaches. An extensive experimen-tal investigation on a variety of benchmarks shows that our metric can be integrated in a Valgrind-based profiler incur-ring overheads comparable to other prominent heavyweight dynamic analysis tools