Optimistic Evaluation: a fast evaluation strategy for non-strict programs

Lazy programs are beautiful, but slow. A great deal of work has been done on static analyses (such as strictness analysis, or cheapness analysis) that conservatively estimate where call-by-need can be changed to call-by-value without changing the meaning of the program.

Our measurements show that many of the thunks that remain after such analyses are in fact always evaluated, or are always cheap. In this paper we describe a new evaluation strategy, optimistic evaluation, that explores the space between call-by-need and call-by-value. Optimistic evaluation complements compile-time analyses with run-time experiments: it evaluates a thunk speculatively, but has an abortion mechanism to back out if it makes a bad choice. We add a run-time adaption mechanism so that the system can avoid making the same bad choice again.

We have implemented optimistic evaluation in the Glasgow Haskell Compiler. The results are encouraging: many programs speed up significantly (5-25%), some are dramatically faster, and very few go slower.

Adaptive evaluation of non-strict programs
Robert Ennals, PhD thesis, University of Cambridge, 2004. This is Robert’s PhD thesis, which goes into much more detail.

• PhD thesis (PDF)