Optimistic evaluation: an adaptive evaluation strategy for non-strict programs
Optimistic evaluation: an adaptive evaluation strategy for non-strict programs
复制标题
乐观评估：非严格程序的自适应评估策略
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
S. Jones
中科院分区：
文献类型：
--
作者：
Robert Ennals;S. Jones
懒惰的程序很漂亮，但它们很慢，因为它们构建了许多thunk。简单的测量表明，这些thunk中的大多数都是不必要的：它们实际上总是被评估的，或者总是便宜的。在本文中，我们描述了乐观评估-一种利用这种观察的评估策略。乐观求值用运行时实验补充了编译时分析：它推测性地评估形实转换程序，但是如果它做出了错误的选择，它有一个中止机制来退出。一个运行时的适应机制记录的表达式发现不适合投机评估，并安排他们在未来进行评估更懒惰。我们已经实现了乐观的评估在格拉斯哥Haskell的编译器。结果是令人鼓舞的：许多程序的速度显着提高（5-25%），一些显着改善，没有一个慢15%以上。
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.