HaskellImplementorsWorkshop/2013/Robinson

SpecConstr: optimising purely functional loops

Amos Robinson

SpecConstr, a generalisation of worker/wrapper, reduces allocations in functions by finding recursive calls with constructors as arguments and creating a specialised copy of the function for those particular constructors. As a trade-off, specialisation is generally limited to a fixed number of copies, as too many copies can increase compilation time and memory usage in the compiler. For high performance code such as the vector library, programmers may override this fixed limit by using ForceSpecConstr, which allows specialisation to occur an unbounded number of times. Unfortunately, unbounded specialisation can generate too many copies, or worse, infinite copies for arguments with recursive types such as list.

We have fixed infinite specialisation by modifying SpecConstr to specialise functions on recursive values only a fixed number of times. For other cases of excessive specialisation, we have reduced specialisations that would be later removed as dead code, by inspecting calls to non-exported top-level functions and then only generating the specialisations that will be used. This does not affect the resulting program, but decreases compilation time as there is less intermediate code.

In this talk, I will briefly outline the SpecConstr optimisation, and the changes that have been made since the original algorithm was described. I will detail the problems of code blowup and compiler divergence, and their solutions.