Speculative execution

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

Types

Generally, statements and definitions in a program can be divided into three types:
* things which must be run and are mandatory
* things which do not need to be run because they are irrelevant
* statements which cannot be proven to be in either of the first two groups

The first group does not benefit from speculative execution because its members need to run anyway.

The second group can be quietly discarded much like lazy evaluation would discard its members.

The third group is the target of speculative evaluation, as its members can be run concurrently with the mandatory computations until they are needed or shown to be of the second group; this concurrency means that speculative execution can be parallelized.

Function

Speculative execution is a performance optimization. It is only useful 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 relatively cheap because the pipeline stages involved would otherwise lie dormant until the next instruction was known. However, wasted instructions consume CPU cycles that could have otherwise delivered performance, and on a laptop, those cycles consume batteries. There is always a penalty for a mispredicted branch. Many microprocessors (such as the Intel Pentium II and successors) have a conditional move instruction. This is an operation to move data, usually, between a register and memory, if a condition is met. There is no branching any more, and the misprediction penalty is less.

Eager Execution

Though it is 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). 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, for instance 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

Lazy evaluation 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. [http://research.microsoft.com/~simonpj/papers/optimistic/]

External links

* [http://www.hpl.hp.com/techreports/Compaq-DEC/CRL-90-1.html "Speculative computation in Multilisp."]