Performance Diagnosis for Inefficient Loops

Linhai Song; Shan Lu. 21 June, 2016.
Communicated by Shan Lu.


Writing efficient software is difficult. Design and implementation defects can easily cause severe performance degradation. Unfortunately, existing performance diagnosis techniques are still preliminary. Performance-bug detectors can identify specific type of inefficient computation, but are not suitable for accurately diagnosing a wide variety of real-world performance problems. Profilers can locate code regions that consume resources, but not the ones that waste resources. Statistical performance diagnosis can identify loops or branches that are most correlated with a performance symptom, but cannot decide whether and why a loop is inefficient, and how developers might fix it.

In this paper, we first design a root-cause and fix-strategy taxonomy for real-world inefficient loops, one of the most common performance problems in the field. We then design a static-dynamic hybrid analysis tool, LDoctor, to provide accurate performance diagnosis for loops. We further use sampling techniques to lower the run-time overhead without degrading the accuracy or latency of LDoctor diagnosis. Evaluation using real-world performance problems shows that LDoctor can provide better coverage and accuracy than existing techniques, with low overhead.

Original Document

The original document is available in PDF (uploaded 21 June, 2016 by Shan Lu).