Wed 17 Jun 2015 09:15 - 09:40 at PLDI Main BLUE (Portland 254-255) - Performance Chair(s): Mary Hall

This paper identifies and formalizes a prevalent class of asymptotic performance bugs called redundant traversal bugs and presents a novel static analysis for automatically detecting them. We empirically evaluate our technique by implementing it in a tool called CLARITY and applying it to widely-used software packages such as the Google Core Collections Library, the Apache Common Collections, and the Apache Ant build tool. Across 1,6M lines of Java code, CLARITY finds 92 instances of redundant traversal bugs, including 72 that have never been previously reported, with just 5 false positives. To evaluate the performance impact of these bugs, we compare the performance of the original program with the repaired program for different input sizes. With an input size of 50,000, all repaired programs are at least 2.4 times faster than their original code.