Towards an automatic complexity analysis for generic programs
Kyle D. Ross · 2006
Generic libraries, such as the C++ Standard Template Library (STL), provide flexible, high-performance algorithms and datatypes, along with functional specifications and performance guarantees. It is left as a nontrivial task to the library user to choose appropriate algorithms and data types for a particular problem. In the present paper, we describe an automatic analysis to aid library users in selecting types for use in generic programs. The analysis is based on manipulation and comparison of symbolic complexity expressions, constructed using cost-bound functions and abstract interpretation of program behaviour. Our analysis serves to detect and rectify "performance bugs" by recommending type selections that will improve performance.