Analyzing system performance with probabilistic performance annotations

To understand, debug, and predict the performance of complex software systems, we develop the concept of probabilistic performance annotations. In essence, we annotate components (e.g., methods) with a relation between a measurable performance metric, such as running time, and one or more features of the input or the state of that component. We use two forms of regression analysis: regression trees and mixture models. Such relations can capture non-trivial behaviors beyond the more classic algorithmic complexity of a component. We present a method to derive such annotations automatically by generalizing observed measurements. We illustrate the use of our approach on three complex systems---the ownCloud distributed storage service; the MySQL database system; and the x264 video encoder library and application---producing non-trivial characterizations of the performance. Notably, we isolate a performance regression and identify the root cause of a second performance bug in MySQL.