Main Page | See live article | Alphabetical index

Speculative execution

In computer science, speculative execution is the execution of code whose result may not actually be needed. In the context of functional programming the term "speculative evaluation" is used instead.

Speculative execution is an optimization. It is useful only when early execution consumes less time and space than later execution would, and the savings are enough to compensate, in the long run, for the possible wasted effort of computing a value which may never be used.

Modern pipelinedd microprocessors use speculative execution to reduce the cost of conditional branch instructions. When a conditional branch instruction is encountered, the processor guesses which way the branch is most likely to go (this is called branch prediction), and immediately starts executing instructions from that point. If the guess later proves to be incorrect, all computation past the branch point is discarded. The early execution is cheap because the pipeline stages involved would otherwise lie dormant until the next instruction was known.

Though it's seldom referred to as such, eager evaluation is also a form of speculative execution (although the situation is complicated by the presence of side effects). The early evaluation is often cheaper because values needed for the computation are likely to be available on the stack and need not be stored and later retrieved from the heap. It can also be substantially more expensive, as in the case of generating the list of integers from 1 to 1,000,000. Programmers writing code in a strict programming language avoid these cases by using explicit laziness or by circumlocution (which can become very elaborate).

Lazy evaluation does not speculate. The incorporation of speculative evaluation into implementations of the Haskell programming language is a current research topic. Eager Haskell is designed around the idea of speculative evaluation. Recent versions of GHC support a kind of speculative evaluation called optimistic evaluation.