  Input-sensitive profiling is a recent performance analysis technique that
makes it possible to estimate the empirical cost function of individual
routines of a program, helping developers understand how performance scales to
larger inputs and pinpoint asymptotic bottlenecks in the code. A current
limitation of input-sensitive profilers is that they specifically target
sequential computations, ignoring any communication between threads. In this
paper we show how to overcome this limitation, extending the range of
applicability of the original approach to multithreaded applications and to
applications that operate on I/O streams. We develop new metrics for
automatically estimating the size of the input given to each routine
activation, addressing input produced by non-deterministic memory stores
performed by other threads as well as by the OS kernel (e.g., in response to
I/O or network operations). We provide real case studies, showing that our
extension allows it to characterize the behavior of complex applications more
precisely than previous approaches. An extensive experimental investigation on
a variety of benchmark suites (including the SPEC OMP2012 and the PARSEC
benchmarks) shows that our Valgrind-based input-sensitive profiler incurs an
overhead comparable to other prominent heavyweight analysis tools, while
collecting significantly more performance points from each profiling session
and correctly characterizing both thread-induced and external input.
