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.