Perfrewrite -- Program Complexity Analysis via Source Code Instrumentation

2014/09/07 by Michael Kruse, Kruse, Michael
Computer Science · #FOS: Computer and information sciences #Programming Languages (cs.PL) #cs.PL

paper · pdf · doi:10.48550/arxiv.1409.2089

ACACES 2012 summer school (2012)

arxiv created 2014/09/07 · arxiv updated 2014/09/09

Abstract

Most program profiling methods output the execution time of one specific program execution, but not its computational complexity class in terms of the big-O notation. Perfrewrite is a tool based on LLVM's Clang compiler to rewrite a program such that it tracks semantic information while the program executes and uses it to guess memory usage, communication and computational complexity. While source code instrumentation is a standard technique for profiling, using it for deriving formulas is an uncommon approach.

Related

• pymwp: A Tool for Guaranteeing Complexity Bounds for C Programs
• A new metric for evaluating the performance and complexity of computer programs: A new approach to the traditional ways of measuring the complexity of algorithms and estimating running times
• Software Metric Framework
• Analyzing Runtime and Size Complexity of Integer Programs
• Hierarchical Complexity: Measures of High Level Modularity