スレッデッドコード
スレッデッドコード（英: threaded code）は、プログラミング言語処理系におけるコード生成手法のひとつで、呼出すべきサブルーチンのアドレスを羅列する、というものである。「内部インタプリタ」と呼ばれる極小のインタプリタで順次呼出したり、サブルーチン・スレッディング方式と言われるコンパイル手法の場合は機械語のサブルーチンコール命令の羅列になっているので、先頭にジャンプ（ないし呼出し）してそのまま実行する。
スレッデッドコードは、他のコード生成技法や他の呼出規約よりもコード密度が高いが、若干実行速度が遅くなる（通常、1命令多くなる）[要出典]。しかし、プログラムが小さくなるのでCPUのキャッシュに完全に収まる可能性が高くなり、キャッシュミスが起きにくくなって性能が向上する可能性が高い[1]。
スレッデッドコードは、Forth、多くのBASICの実装[要出典]、一部のCOBOLの実装[要出典]、初期のB言語、小型ミニコンピュータ向けなどのプログラミング言語での実装技法としてよく知られている。
背景と基本
[編集]一般にコンピュータプログラムは何らかの記号言語で書かれ、コンパイラを使って機械語に変換することで実行可能となる。機械語の実行コードは高速に実行できるが、特定のコンピュータアーキテクチャにのみ対応しているので、他のプラットフォームでは実行できない。それとは異なる手法として、仮想機械の命令セットを使う技法がある。この場合は、特定のハードウェアを対象としない。各プラットフォーム上のインタプリタが仮想機械向けの実行コードを解釈実行する。
初期のコンピュータのメモリ容量は今よりもずっと小さかった。例えば、Data General Nova、IBM 1130、多くの初代 Apple II は4KワードのRAMしか搭載していなかった。結果として、プログラムをどうやって小さくまとめ、利用可能なメモリ容量内に収めるかに多くのプログラマが頭を悩ませることになった。また処理速度も今より遅く、単純なインタプリタでは機械語とは比べものにならないほど遅くなってしまう。
プログラム内のそれぞれ必要とする箇所で演算ステップをいちいち書くのではなく、プログラマはそのような演算ステップを一度だけ書いて（"Don't repeat yourself" を参照）、サブルーチン内に置くことでメモリを節約する。
これはコードリファクタリングとして今でも行われている技法だが、理由は異なる。この技法を徹底して適用すると、プログラムのトップレベルはサブルーチンコールの羅列だけになる。また、そこから呼び出すサブルーチンの多くも、より低いレベルのサブルーチンを呼び出しているだけとなる。
メインフレームや RCA 1802 などの初期のマイクロプロセッサは、サブルーチンを呼び出すのに数命令を必要とする。アプリケーションのトップレベルや多くのサブルーチンでは、その命令シーケンスを常に繰り返し、呼び出すサブルーチンのアドレスだけが毎回異なることになる。そういった同じ命令列を繰り返し格納するのは、メモリの無駄である。
さらにメモリを節約するには、サブルーチンコールの羅列を呼び出すべきサブルーチンのアドレスのリストへと変換し、そのリストを参照して次々にサブルーチンを呼び出す小さな「インタプリタ」を書けばよい。
これは、ジャンプテーブルやディスパッチテーブルや仮想関数テーブルと呼ばれるテーブルにジャンプ先アドレスだけを格納しておき、小さなセレクタでジャンプ先を選択してプログラムの流れを制御する技法と同じである。スレッデッドコードやこれらの技法では、プログラムは実際に実行すべきコードへのエントリポイントのリストとなる。
長年、プログラマ達はこのような「インタプリタ」や「小さなセレクタ」の様々なバリエーションを生み出してきた。アドレスリスト内の特定のアドレスは、インデックスまたは汎用レジスタまたはポインタを使って取り出される。そのアドレス群は、直接または間接であり、連続または不連続（ポインタで連結されている）であり、相対または絶対であり、コンパイル時に解決されるか動的に構築される。どの方式が最善というわけではない。
開発
[編集]メモリを節約するため、一連のサブルーチンコールからサブルーチンのアドレスのリストを作り、小さなループを使って次々にサブルーチンを呼び出す。例えば次のようになる。
start: ip = &thread top: jump *ip++ thread: &pushA &pushB &add ... pushA: *sp++ = A jump top pushB: *sp++ = B jump top add: *sp++ = *--sp + *--sp jump top
この場合、バイトコードのデコードは1回だけ、コンパイル時かプログラムロード時になされ、実行時に毎回デコードするわけではない。実行コストに比べてデコードとディスパッチのオーバーヘッドが大きい場合、これで時間と領域を節約できる。
なお、バイトコードのデコードとディスパッチを同時に行うインタプリタにおいては解釈すべき命令はそれぞれ1バイトだが、上記のスレッデッドコードのthread内の&pushAや&pushBといったアドレスは2バイト以上ということが普通である。一般にデコード&ディスパッチ・インタプリタにおける命令のサイズは一定ではない。例えば、そのようなインタプリタで Intel Pentium のシミュレーションを行う場合、デコードすべき命令の大きさは1バイトから16バイトまで様々である。しかし、バイトコード化システムは最も一般的な操作に1バイトのコードを割り当てる。従ってこのスレッデッドコードはバイトコードよりスペースコストがやや高い。多くの用途では、デコードコストの縮小はスペースコストの増加に優る。
また、バイトコードは名目上マシンから独立しているが、スレッド内のポインタの形式や値はインタプリタを実行するターゲットマシンに依存しているのが一般的である。したがって、インタプリタがポータブルなバイトコードのプログラムをロードし、そのバイトコードをデコードしてプラットフォーム依存のスレッデッドコードを生成し、実際の実行時には元のバイトコードを全く参照せずにスレッデッドコードを実行する、ということになる。
このループは単純なので、個々のインタプリタ命令を実装した機械語命令列の最後尾にある jump top を取り除き、それぞれが直接次のインタプリタ命令へジャンプするように修正可能である。例えば次のようになる。
start: ip = &thread jump *ip++ thread: &pushA &pushB &add ... pushA: *sp++ = A jump *ip++ pushB: *sp++ = B jump *ip++ add: *sp++ = *--sp + *--sp jump *ip++
これを直接スレッデッドコード (direct threaded code, DTC) と呼ぶ。この技法は古くからあるが、「スレッデッドコード」という呼称が広まったのはベルの1973年の論文 "Threaded Code" からである[2]。
チャールズ・ムーアは、1970年にForth仮想機械のためにもっとコンパクトな技法を発明しており、それを間接スレッデッドコード (indirect threaded code, ITC) と呼ぶ。元々ムーアがその技法を発明したのは、Novaというミニコンピュータに多重メモリ間接モード（メモリ上のアドレスに間接ビットを付与できる）があり、実装が容易で高速だったためである。バイト誌のForth特集でムーアは、その後のForthの設計にもそれを適用していったことで、それがいかに便利だったかがわかったと述べている。
ForthコンパイラがForthプログラムをコンパイルする場合、間接スレッデッドコードを生成するものと直接スレッデッドコードを生成するものがある。どちらであってもプログラムは同じように動作する。
スレッディングモデル
[編集]事実上、実行可能なスレッデッドコードは以下に挙げるサブルーチン呼び出し技法のいずれかを使用する。個々の技法を「スレッディングモデル」と呼ぶ。
直接スレッディング
[編集]スレッド内のアドレス群は機械語コードのアドレスである。単純だが、そのマシンのアドレスのみがスレッドに羅列されるため、何らかのパラメータが必要でもそれらはメモリから間接的にロードするしかない。したがって若干オーバーヘッドがある。一部のForth処理系は直接スレッデッドコードを生成する。多くのマシンにおいて、直接スレッディングは後述するサブルーチン・スレッディングよりも高速である。
例として、スタックマシンで "push A, push B, add" を実行する場合を見てみよう。直接スレッディングでは次のようなスレッドとルーチンに変換される。ここで ip は &thread というアドレスに初期化されるものとする。
thread: pushA: *sp++ = A pushB: *sp++ = B add: *sp++ = *--sp + *--sp &pushA jump *ip++ jump *ip++ jump *ip++ &pushB &add ...
また、オペランドをスレッドに含める方式もある。スレッドは大きくなるが、ルーチンは少なくなる。
thread: push: *sp++ = *ip++ add: *sp++ = *--sp + *--sp &push jump *ip++ jump *ip++ &A &push &B &add
間接スレッディング
[編集]間接スレッディングでは、機械語コードを指すポインタのある場所へのポインタを使用する。間接ポインタの後には必要に応じてオペランドが続き、それによって間接ブロックを形成する。そうすることで、スレッド本体にオペランドが繰り返し出現するのを防ぐ。したがって間接スレッデッドコードは直接スレッデッドコードよりコンパクトになることが多いが、間接参照なので性能は低下するものの、それでもバイトコード・インタプリタより通常は高速である。ハンドラのオペランドが値と型からなる場合、直接スレッデッドコードからの領域節約効果は大きくなる。古いForthシステムは間接スレッデッドコードを生成するのが一般的だった。
例として "push A, push B, add" を実行する場合を挙げる。ここで ip は &thread というアドレスに初期化され、各コード断片（push、add）は ip からの二重間接で見つけられる。そして、各コード断片のオペランドのアドレスは、1段めの間接参照で得られる場所に、コード断片のアドレスに続いて置かれている。
thread: i_pushA: push: add:
&i_pushA &push *sp++ = *(*ip + 1) *sp++ = *--sp + *--sp
&i_pushB &A jump *(*ip++) jump *(*ip++)
&i_add i_pushB:
&push
&B
i_add:
&add
サブルーチン・スレッディング
[編集]「サブルーチン・スレッデッドコード」あるいは「コール・スレッデッドコード」と呼ばれ、機械語のコール命令（サブルーチン呼び出し用の命令であり、直接スレッディングがジャンプすなわち無条件分岐命令を使うのとは異なる）をスレッドに並べる。ALGOL、FORTRAN、COBOLなどの初期のコンパイラや一部のForth処理系でサブルーチン・スレッデッドコードを生成する。これらのシステムの多くで、コードはオペランドのLIFOスタック上で実行され、その技法はコンパイラ理論でよく研究されている。最近の多くのプロセッサはサブルーチン用の特別な命令であるコール命令とリターン命令を持っており、ディスパッチ用に余分な機械語命令が必要であっても、オーバーヘッドは小さくなる。Anton Ertl は「よく言われている伝説とは対照的に、サブルーチン・スレッディングは一般に直接スレッディングより遅い」と述べている[3]。しかし、Ertl 自身の最近の評価[1]によれば、25件のうち15件で直接スレッディングよりサブルーチン・スレッディングの方が高速ということが示されている。Ertlの最近の評価では、Xeon/Opteron/Athlon では直接スレッディングが最も高速、Pentium M では間接スレッディングが最も高速、Pentium 4/Pentium III/PowerPCではサブルーチン・スレッディングが最も高速である。
コール・スレッディングでの "push A, push B, add" の例は次の通り。
thread: pushA: pushB: add: call pushA *sp++ = A *sp++ = B *sp++ = *--sp + *--sp call pushB ret ret ret call add
トークン・スレッディング
[編集]トークン・スレッデッドコードは8ビットか12ビットのインデックスのリストを使用し、このインデックスはポインタテーブルのインデックスとなっている。トークン・スレッデッドコードはプログラマが特別に努力しなくても非常にコンパクトになる。トークン・スレッデッドコードは他のスレッデッドコードの半分から4分の3の大きさで、スレッデッドコードは一般に普通にコンパイルされたコードの4分の1から8分の1の大きさである。ポインタテーブル内のポインタは直接の場合と間接の場合がある。一部のForthコンパイラはトークン・スレッデッドコードを生成する。一部のPascalコンパイラが生成するPコードをトークン・スレッデッドコードに分類する場合もあり、同様に.NET/Java/BASIC/一部のCコンパイラで使用するバイトコードもトークン・スレッディングだと言われることがある。
バイトコードは歴史的に、8ビットの命令コードを使用し、スタックに基づく仮想機械で実行される。典型的なインタプリタはデコード&ディスパッチ・インタプリタと呼ばれ、次のような形式である。
bytecode: top: pushA: pushB: add: 0 /*pushA*/ i = decode(vpc++) *sp++ = A *sp++ = B *sp++ = *--sp + *--sp 1 /*pushB*/ addr = table[i] jump top jump top jump top 2 /*add*/ jump *addr
仮想機械が1バイトの命令しか使わない場合、decode() は単に bytecode から1つフェッチするだけだが、1バイト命令を基本として多バイト命令も持つ場合があり、そのときは decode() がさらに複雑になる。1バイト命令コードのデコードは非常に単純で、命令コードをインデックスとしてジャンプテーブルを参照するだけでよい。
各命令の行う操作や演算は "push" や "add" などのように単純で、それらを実際に実行するコストよりもどれを実行するかを選択するオーバーヘッドの方が大きい。そのためこのようなインタプリタは単純に機械語コードを実行するよりも遅いことが多い。しかし、命令の処理内容がより複雑になれば、オーバーヘッドの割合は小さくなる。
ハフマン・スレッディング
[編集]ハフマン・スレッデッドコードはハフマン符号のリストで構成される。ハフマン符号は可変長のビット列で何らかのアイテムを一意に示すのに使われる。ハフマン・スレッデッドコードに対応したインタプリタは、ハフマン符号をインデックスとするテーブルか木構造からサブルーチンを特定する。ハフマン・スレッデッドコードはコンピュータプログラムの最もコンパクトな表現の一つである。どのサブルーチンにどの符号語を割り当てるかは、基本的にその使用頻度に基づき、最も頻繁に使うサブルーチンには最も短い符号語を割り当てる。使用頻度が近いサブルーチンにはほぼ同じ長さの符号語を割り当てることになる。ハフマン・スレッデッドコードのシステムは、Frothシステムで実装されているものが多く、処理速度は遅くなるが小さいメモリに大きなコードを詰め込むことができるため、安価なマイクロコントローラでの利用が見られる。電子式のおもちゃ、電卓、腕時計などでの使用例がある。
その他のスレッディング
[編集]ストリング・スレッディングは、文字列をキーとしてハッシュテーブルを参照し、実行すべきサブルーチンを特定する方式である。チャールズ・ムーアの最初のForth実装で使われ、イリノイ大学アーバナ・シャンペーン校でハードウェアでコンピュータ言語を実験的に実装する際に採用された。bashで書かれたBashforthもストリング・スレッディングで実装されている。
分岐
[編集]これまでの例では分岐を示していない。どんなインタプリタでも、分岐命令はスレッドポインタ（上述の例では ip）を変化させる。例として、スタックトップの値がゼロなら分岐するという条件分岐命令は次のようになる。ここで &thread[123] は分岐先の場所を示しており、ハンドラのアドレスではない。したがって、分岐するしないに関わらずスキップ (ip++) しなければならない。
thread: brz: ... tmp = *ip++ &brz if (*sp++ == 0) &thread[123] ip = tmp ... jump *ip++
共通の工夫
[編集]データスタックとリターンスタックを分離すると、スタック管理コードの大部分を排除でき、結果としてスレッデッドコードのサイズを大幅に縮小することができる。このスタックを2つ持つという方式は独自に3回発明されている（バロース B5000、Forth、PostScript）。また、Java仮想マシンでも使われている。
スレッデッドコードを実行する仮想機械は4つのレジスタを持つことが多い。サブルーチン（ワード）間でデータを渡すのにもう1つのレジスタを持つこともある。4つのレジスタは次の通りである。
- ip または i - 仮想機械の命令ポインタ（そのVMを実装したハードウェアの持つプログラムカウンタとは異なる）
- rp または r - リターンスタック（コールスタック）ポインタ
- sp または s - パラメータスタックポインタ（ワード間でパラメータの受け渡しを行う）
- w - ワークポインタ
スレッデッドコード対応の仮想機械の中核部分は非常に単純なことが多く、次の3つのプリミティブから構成される。
- nest または docol
- unnest または semi_s (;s)
- next
間接スレッデッドコードの仮想機械では、それらはそれぞれ次の操作を行う。
next: (ip)+ -> w ; jmp (w)+ nest: ip -> -(rp) ; w -> ip ; next unnest: (rp)+ -> ip ; next
これがおそらく最も単純で高速なインタプリタ、または仮想機械である。
関連項目
[編集]脚注
[編集]- ^ a b Speed of various interpreter dispatch techniques V2
- ^ James R. Bell, "Threaded Code", CACM, 1973, 16, 6, pp 370–372
- ^ "What is Threaded Code?" by Anton Ertl
参考文献
[編集]- Anton Ertl's explanatory page What is Threaded Code? - 各種スレッディング技法を解説し、さらなる参考文献を提供している。
- The Development of the C Language by Dennis M. Ritchie - Cの前身であるBを「スレッデッドコード」を使って実装されたものとして解説している。
- Thinking Forth Project - 1984年に出版された Leo Brodie の重要な著作 Thinking Forth （絶版）の内容を含む。
- Starting FORTH - 1981年出版の Leo Brodie の著作 Starting FORTH のオンライン版
- Brad Rodriguez's Moving FORTH: Part 1: Design Decisions in the Forth Kernel - スレッディング技法について詳述している。
- GCC extensions. Labels as Values
- RPL.DOC - HPの電卓で使われていたスレッデッド言語 RPL の概要 by Joe Horn