Super-Linear Speedup by Program Transformation

We investigate the use of repeated unfolding and simplification to achieve super-linear speedup in sequential programs. Our technique of repeated recursion unfolding repeatedly unfolds a recursion with itself and simplifies it while keeping all unfolded rules. Each unfolding doubles the number of recursive steps covered. This reduces the number of recursive steps to its logarithm at the expense of introducing a logarithmic number of unfolded recursive cases to the program. Our optimization can lower the time complexity class of a program if enough simplification in the recursions is possible. The actual runtime improvement quickly reaches several orders of magnitude.



Frühwirth, Thom
Repeated Recursion Unfolding for Super-Linear Speedup within Bounds
Pre-Proceedings of the 30th International Symposium on Logic-Based Program Synthesis and Transformation (LOPSTR 2020)
September 2020