投機的実行
出典: フリー百科事典『ウィキペディア（Wikipedia）』
投機的実行(とうきてきじっこう、speculative execution)とは、コンピュータが実際にはその結果を捨ててしまうかもしれないコードを実行することである。関数型言語では、"speculative evaluation"という用語が使われている。
投機的実行は最適化のひとつの手法である。 これは、先に実行する方が後で実行するより時間的にも空間的にも得な場合に意味があり、結果として捨ててしまうことになる処理にかかった時間的、空間的損失よりも全体としての利益が大きくなければならない。
最近のパイプライン化されたマイクロプロセッサでは、条件付分岐命令のコストを削減するために投機的実行を使用している。 条件付分岐命令が現れた場合、プロセッサは分岐しそうかどうか予測し(分岐予測)、即座に決定した方の実行を開始する。 その予測が後に間違っていたことがわかると、分岐命令以後の処理結果は全て捨てられてしまう。このように先に実行しなければ、パイプラインは分岐するかしないか判明するまで何もしないため、投機的に実行しても時間を浪費していることにはならない。
積極的実行は投機的実行の一種である(ただし副作用があるため、複雑さの度合いが異なる)。 計算に必要な値はしばしばスタックから得られ、メモリに戻すことなく後でヒープ領域から取り出すことが多いため、先に実行しても高くつかない。 1から1,000,000までの整数のリストを作るような場合は実際のところやや高くつく。 一般的なプログラミング言語でコードを書くプログラマは明示的に遅延性を導入したり、まわりくどい(複雑な)書き方をしたりすることで上記のようなケースを防ぐ。
遅延評価は投機的ではない。投機的実行をHaskellプログラミング言語の実装に導入することは最近の研究上の話題のひとつである。Eager Haskellはそのような試みとして生まれた言語である。 Glasgow Haskell Compiler(GHC)は「悲観的評価」と名づけたある種の投機的実行をサポートしている。
投機的実行の実装は複雑で難しい。次のような処理を例として説明する。
- あるデータ格納域へのポインタptrが存在する。ptrがゼロの場合、データ格納域が存在しないことを示す。
- ptrがゼロでない場合、データ格納域に何らかの書き込みをする。
- ptrがゼロの場合、何もしないで次の処理に移行する。
この処理を何度も通っていて、ほとんど必ずptrがデータ格納域を指している場合、投機的実行では分岐予測の結果にしたがってptrの指すデータ格納域に書き込みを行おうとする。しかし、ptrがゼロであれば、それは不正なアドレスへの書き込みとなってしまう。投機的実行を行うコンピュータではこの不正書き込みで例外を発生してはならない。また、アドレスではなく書き込む内容が間違っている場合や、ロードしようとするアドレスが不正な場合など、投機的実行の実装の困難さは、このようなところにある。
