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 is never used.
Modern pipelined 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 execution is also a form of speculative execution (although the situation is complicated by the presence of side effects). The early execution 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 execution does not speculate. The incorporation of speculative execution into implementations of the Haskell programming language is a current research topic. Eager Haskell is designed around the idea of speculative execution. Recent versions of GHC support a kind of speculative execution called optimistic execution.