Dynaplex: Inferring Asymptotic Runtime Complexity of Recursive Programs
Published in Proceedings of the 44th ACM/IEEE International Conference on Software Engineering: Companion Proceedings, 2022
Recommended citation: Ishimwe, D., Nguyen, T., & Nguyen, K. (2022, May). Dynaplex: inferring asymptotic runtime complexity of recursive programs. In Proceedings of the ACM/IEEE 44th International Conference on Software Engineering: Companion Proceedings (pp. 61-64).
Automated runtime complexity analysis can help developers detect egregious performance issues. Existing runtime complexity analysis are often done for imperative programs using static analyses. In this demo paper, we demonstrate the implementation and usage of Dynaplex, a dynamic analysis tool that computes the asymptotic runtime complexity of recursive programs. Dynaplex infers recurrence relations from execution traces and solve them for a closed-form complexity bound. Experimental results show that Dynaplex can infer a wide range of complexity bounds (eg: logarithmic, polynomial, exponential, non-polynomial) with great precision (eg: O(nlog23) for karatsuba). A video demonstration of Dynaplex usage is available at https://youtu.be/t7dhwZ7fbVs. Download paper here