Software Performance Estimation Using Feedback-Directed Analysis

Software performance is considered a major concern when writing efficient code. In the past, developers were aware of the target’s organization and could easily determine the effect of an instruction on performance. The advent of high-level languages abstracted most of the target features that were at the core of assembly programming. Soon, developers started relying on asymptotic notations to describe the limiting behavior of code. However, this notation only describes how code tends to respond when the problem size grows but gives no insight on its real performance. To get a real performance estimate, the code has to be run or profiled. Nonetheless, running the code might be costly when the problem size is extremely large in some application domains such as numerical analysis. We propose a technique to estimate source code performance around compile time, before most of the code has been run. Our technique relies on the knowledge accumulated from benchmarked codes that have similar characteristics to the code at hand. To achieve this, (1) we study the effects of memory accesses, dependences and operations on performance; (2) define a performance similarity metric; (3) perform static analysis on the code-of-interest to extract important regions; (4) match these regions against a knowledge base of benchmarked codes; and (5) instrument the code and capture just-enough concrete program behavior through dynamic analysis to allow querying the knowledge base for similar behavior. We developed the SoPE framework as a compiler plugin which performs the aforementioned analyses, and reports the performance estimate of the code-of-interest at the end of compilation. Our estimates follow the concretely-run program performances