日々の流転

λ. “Optimistic evaluation: an adaptive evaluation strategy for non-strict programs” by Robert Ennals and Simon Peyton Jones

Lazy programs are beautiful, but they are slow because they build many thunks. Simple measurements show that most of these thunks are unnecessary: they are in fact always evaluated, or are always cheap. In this paper we describe Optimistic Evaluation ― an evaluation strategy that exploits this observation. 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. A run‐time adaption mechanism records expressions found to be unsuitable for speculative evaluation, and arranges for them to be evaluated more lazily in the future.We have implemented optimistic evaluation in the Glasgow Haskell Compiler. The results are encouraging: many programs speed up significantly (5–25%), some improve dramatically, and none go more than 15% slower.

を読んだ。

先行評価を組み合わせることで遅延評価の非効率性を避ける試みで、Eager Haskell (c.f. 20070706#p01) と同様だが、独立に行われたもの。

Eager Hasekll は常に投機的に実行することを試みていたのに対して、こいつはプロファイラを持っていて、投機的に実行した結果が無駄になっている比率が高い場合には、そのletに関しては遅延評価に戻すようになっている。

個人的に面白かったのは、chunky evaluation の実現方法に関しての、「The intuition is that the deeper the speculation stack, the less likely a new speculation is to be useful」という洞察。それから、「let x = (let y = <expensive> in y+1) in ...」という式があったときに、<expensive>を投機的に実行するコストを、yではなくxに帰する方法。