スレッデド・コード
Forthの伝統的なスレッディング技術について説明してみたいと思う（自分はネイティブコード方式しか経験はないが）。
注：全てマシン語におき直すネイティブコード方式では、スレッディング方式は関係がない。
スレッディング技術とは、ワード（サブルーチン、関数）のコンパイルと解釈実行のための技法である。
スレッディング(threading)という言葉は、掲示板等のいわゆる「スレ」と同じ語threadが語源で、"糸"という意味である。
辞書内にコンパイルされたワードの領域は、複数のスレッドのリストであり、イメージとしては、たくさんの糸を等間隔でぶら下げた棒のような感じである。そして、ぶら下がった糸にはそれぞれ実行すべきワードがつながっており、それを順番に引っ張って糸の先のワードを動かしていくことで処理が連続していくわけである。
そのようなコードの状態をスレッデド(threaded)コードと呼ぶ。"糸で繋げられた"という感じであろう。
辞書内のワード登録域は、まずヘッダデータ領域があり、続いてコード領域 (code field)と呼ばれる領域がある。ワードの実行において先頭にくるのは、このコード領域であって、コード領域アドレス (code field address : cfa)の数値がワード自体の代理として用いられることも多い。
間接スレッディング方式 (Indirect Threaded Code: ITC)
間接スレッディング方式は最も古典的なForthのスレッディング技術である。
コード領域
間接スレッディング方式では、コード領域の大きさは1セルである。つまり、8ビットコンピュータなら1バイト、16ビットなら2バイト、32ビットなら4バイト、64ビットなら8バイトである。この領域は、マシンコードへのポインタを格納している。
プリミティブ (primitives)と呼ばれる基本的なワードでは、コード領域はそのワードの内容を成すマシンコードのポインタである。
コロンを用いて定義されたワードでは、コード領域において、DoColonとかENTERとか呼ばれる決まったパターンのマシンコードがポイントされている。このDoColonコードは呼び出し (call) に対応するもので、呼び出し側の実行個所をリターンスタックに保存し、呼び出されたワードの実行個所を現在の実行個所とする。つまり実行個所を指す値を、元に戻せるよう準備した後で、すげ替えるのである。
パラメター領域
コロン定義の場合、コード領域の後には、その定義が呼び出しているワードのcfa（コード フィールド アドレス）を順番に格納したリストが続く。このリストはパラメター領域と呼ばれている。DoColonの後、実行個所は当ワードのパラメター領域の先頭（パラメター領域アドレス：parameter field address : pfa）、ということになる。
どの項目もメモリーアドレスであるから1セルになり、項目の大きさが均一なリストが出来上がる。このリストの一番最後には、EXITというプリミティブのcfaが格納されている。このワードは要するにDoColonの逆動作であって、リターンスタックのトップの値をポップして、IPレジスタに格納するのである。これで実行が１段階戻る。
プリミティブの場合、cfaリストという意味でのパラメター領域は存在しない。古典的には、プリミティブのパラメター領域には内容マシンコードが直接に格納され、コード領域はそこをポイントしていたようである。
パラメター領域は実際のマシンコードをポイントしているのではなく、呼び出されるワードのコードフィールドをポイントしている。したがって、実際のマシンコードに到達するには、ポインタを二回デレファレンスしないといけない。このような特性を捉えて、間接スレッディングというのである。
アルゴリズム
もう少し細かく、動作原理を記述してみる。
Forthインタープリタは、現在の実行個所のアドレスを格納するレジスタを保守している。このレジスタはIPと呼ばれる。インストラクション ポインタの略であろう。現代的CPUは大抵特殊レジスタとしてIPレジスタ（PowerPCではPCレジスタと呼ぶ）を持っており、forthの場合と機能は同じだが、内容は異なる。通常のCPUでは、実際のマシンインストラクションの、現在実行中のものの次をポイントしている。他方、forthではワードの辞書内の実行のリストのうち、現在実行中のものの次をポイントしている。現在IPレジスタがあるワードのパラメタ領域を指しているものとして、インタープリタの動作を考えてみる。
インタープリタは、
- まずIPレジスタをデレファレンスして呼び出されるべきワードのcfaを取る。
- IPレジスタを1セル先に進める。
- 先に取ったcfaをデレファレンスしてコードアドレスを取る。
- コードアドレスに実行をジャンプする。
この四つですべてが終了する。
この一つ一つが普通一つのマシンインストラクションで済む。インタープリタは、たった4つのインストラクションでできているわけである。この部分は、内部インタープリタなどと呼ばれている。
ワードのためのすべてのマシンコードは、その一番最後にインタープリタへのジャンプを含んでいる。この操作はNEXTと呼ばれる。
初めにソースからワードが入力されてきた場合を考えてみる。このとき、辞書内でワードが検索されて、そのcfaが獲得される。
ここから、インタープリタのアルゴリズムに入る。IPレジスタの値が１セル進められ、前に獲得されたcfaがデレファレンスされてコードポインタが獲得され、実行はそのコードへとジャンプする。
コロン定義の場合、コード領域にはDoColonのマシンコードがポイントされておりジャンプの直後にこれが実行される。DoColonの内容は、IPレジスタをリターンスタックにプッシュし、現在のcfaを1セル進めたパラメタ領域のアドレス（pfa）をIPに格納することである。Docolonの最後にはNEXTが来る。すると、またインタープリタアルゴリズムが開始され、IPレジスタの値のデレファレンスから始まる上記の手順が必要な分だけ繰り返される。コロン定義のパラメタ領域のポインタリストの最後には、EXITというワードが呼び出されている。これは通常はプリミティブ（動作については次の段落参照）であるようだが、動作内容は上にも書いたようにリターンスタックからポップして、IPレジスタの値を呼び出し側に戻す。ここでも最後はNEXTであるから、IPをすげ替えてまた初めからインタープリターアルゴリズムが始まることになる。
プリミティブの場合、上のDoColonと同じような形で、そのプリミティブの内容を実行するマシンコードが実行される。このときは、IPレジスタは掻き回されないので、NEXTの際には、これが他のワードから呼び出されたものであれば、そのまま次の項目のインタープリトに戻る。つまり、プリミティブの場合、DoColonとEXITの実行は不要なので省かれる。
少し考えると分るように、上のインタープリタの動作をそのまま繰り返すだけで、プリミティブが呼ばれたときも、コロン定義が入れ子で呼ばれたときも、すべて動作する。驚くほどシンプルで巧妙な機構である。
動作の特徴的な点としては、標準的なマシン語の場合はリターンスタックは呼び出し側にあるCALLのインストラクションが手配するが、forthインタープリターでは、呼び出された側が手配するということであろう。
直接スレッディング方式 (Direct Threaded Code: DTC)
直接スレッディング方式は、ITCとほとんど同じような機構なのだが、コロン定義におけるパラメター領域のリスト中、プリミティブを呼び出す項目には、そのcfaではなくマシンコードのアドレスが直接に格納される点が異なっている。他方、コロン定義からコロン定義を呼び出す場合には、ITCの場合と同様、呼び出されるワードのcfaがポイントされる。この結果、インタープリタはデレファレンスを1回すれば済むことになる。
つまり、直接スレッディングのインタープリタは、
- IPレジスタをデレファレンスしコードアドレスを取る。
- IPレジスタを1セル進める。
- 上で取ったコードアドレスにジャンプする。
で済む。
一回のデレファレンスでコードアドレスに至るには、プリミティブの場合には、コード領域にマシンコードがそのまま書き込まれていなければならない。また、コロン定義でも、コードフィールドには、DoColon（Enter）の実行マシンコードがそのまま書き込まれるか、そのマシンコードを呼び出すマシンコードがなければならない。他方、先にも述べたように、パラメタ領域に格納するのは、通常通り、呼び出されるワードのcfaでよい。
上のことが、直接スレッディングには間接スレッディングに比してちょっと不利な効果をもたらしている。コードのサイズの問題である。
通常は、すべてのコロン定義のコード領域にDoColonコードを書き込むよりは、DoColonマシンコードをどこかに置いてそれをコールする方がサイズは小さい。しかしコードポインタを使ったジャンプのインストラクションは、JMPのopコードに飛ぶ先のアドレスを繋げて構成するのが普通であるから、通常、1セルよりも大きいのである。結果として、DTCのコードはITCのコードよりサイズが少し大きくなる。
とはいえこれも場合による。
そして、デレファレンスが一回減った分だけ実行は普通は速くなる。
補遺
上のような辞書（ディクショナリ）内の、一つのワードに対応している領域の全体を考えると、ポインタデータを格納しているデータ部分と、内容として直接実行されるマシンコードを格納しているコード部分とがある。現代的CPUでは、メモリ内の実行コードを格納する領域とデータを格納する領域（変数）を別々にして遠ざけて配置することによって、処理速度の高速化（キャッシュの効率化など）を図っており、データとコードがメモリー内の近い位置に混在していると処理速度が非常に遅くなるものもある。上のスレッディングの仕組みを考えると、間接スレッディングの場合は、データと実行コードを完全に切り離すことが容易である（プリミティブの実行コードを少し離しておけばよいだけ）が、直接スレッディングでは、コロン定義は定義冒頭に実行コードそのものが格納されるので、データとコードを切り離すには、少し工夫がいる。このような工夫は、コードを複雑にするのであまり採用されず、結果として、CPUによっては、間接スレッディング方式の方が直接スレッディング方式より高速である場合もかつてはあったそうである。
その他の方式
サブルーチン スレッディング方式(Subroutine Threaded Code: STC)
慣用としてこの方式もスレッディングと呼ばれることも多いが、現実にはこれはスレッディング技術ではない。というのはスレッド（糸）に当たるポインタ経由の参照が無いからである。
この方式は要するにDTCのパラメター領域のポインタも全部、各ポインタに対応するワードを呼び出すcallのマシンインストラクションに置き換えてしまうのである。つまり、ワードの辞書領域は、すべて実行可能マシンコードが格納されることになる。
各ワードをサブルーチンと見なしてサブルーチンコールインストラクションで詰め込んでしまうので、この名があるのだろう。
この方式では、DoColonのような準備コードは不要となる。直接ワードのcfaをcallすればよいのである。マシンコードの最後はNEXTではなくてret(リターン)となる。これはcallに対応して実行を戻すインストラクションである。また、コロン定義の最後にEXITも要らなくなる。retでよいわけである。
これはネイティブコード方式の出発点といわれるが、ネイティブコード方式に近いにもかかわらず、実は実行速度が遅いらしい。新しいCPUでもまだそうなのだが、コンピュータは狭い範囲に立て続けにcallがあると動作が遅くなる。短時間にあちこちに実行が飛ぶのでコードキャッシュが効果的に働かないからである。この方式を文字通りに実現すれば、ワードの内容はズラズラとcallだけが続くことになる。少し古い実測だが、大抵のCPUでサブルーチンスレッディングよりDTC方式の方が速かったそうである。
ネイティブコード方式
これはサブルーチンスレッディングの一種なのだが、callばかり使わずに最適化したものは、特別にネイティブコード方式と呼ばれることがある。もちろんこれもスレッディング方式ではない。実行速度は最速となることが期待される。最近のCPUではコードサイズも最小になることが多いらしい。
最適化の最も基本的なものはいくつかのプリミティブのインライン化である。頻繁に使う小さい基本ルーチンについては、いちいち呼び出すのではなく対応するマシンコードをその場所に埋め込んでしまうわけである。Mopsでいえば、四則演算、ビット操作、スタック操作、変数、定数、メモリーアクセス（@,!の系統）、比較演算などはインラインコンパイルされる。これだけで実行速度はかなり上がる。通常は他にも細かい最適化をする。定数の演算はコンパイル時にしてしまったり、スタックアイテムをレジスタにおいたり、条件分岐の判定部分を短縮したり、スタック操作については現実に必要な場合以外は何もせず、入力値の位置の指定だけを変更するに留める、などである。
トークン スレッディング方式（Token Threaded Code: TTC）
これは、速さではなくサイズの小ささを狙った方式である。動作は一番遅い。メモリースペースが非常に限られたCPUのために考案された方式である。これは名前通りスレッディング方式といえる。
例えば、32ビットシステムであるとする。この場合、ITCだと、ワードの辞書領域は、各項目が4バイト長のリストになる。メモリーアドレスが4バイトだからである。
ここで、すべてのワードに付いて各1項目で対応するcfaを格納したワードテーブルを作る。ワードの個数を65535個（2バイト数）までに制限すれば、各項目が４バイトなので、最高256kbである。そして、ワードの辞書領域は、呼び出されるべきワードの、このワード表内の順位数を格納したリストにするのである。そうすると、ワードの辞書領域のリストは、各項２バイトのリストになって、サイズが半分になる。普通はワードの辞書領域内リストは同じワードを何度も呼び出すので長い。したがって、リスト各項が半分になる圧縮効果は大きい。
このワード表の番号がトークン（しるし）であって、これを使ってワードの代理をさせるのがトークンスレッディング方式である。
動作は、二回目が表の番号を解いてアドレスを取り出すところを除けば、ITCと同じである。上の例で書けば、
- IPのさす場所からトークンを取り出す。
- IP:=IP+2
- ワードテーブルのトークンの場所からコードアドレスを取り出す
- 上で取ったコードアドレスにジャンプ
実行速度上は、三番目の、トークンからテーブル内の該当場所を計算するという手順が、必ずしも単純にできるとは限らないところが弱点となる。
しかし、最大のネックは、総ワード個数に上限があるところである。もっとも、実際上は2バイト分もあれば多過ぎるほどである。
PowerMopsもiMopsも、ガチャガチャ様々な機能を付けて、クロスコンパイル用にわざわざ少し名前の違うワードを定義して後で変えたりしているにもかかわらず、どちらも総ワード数は3000程度である。
この程度のワード数としてサイズ圧縮効果を考えてみる。
3000項目なら表のサイズは12kbである。Forthでは各ワードが呼び出す他のワードは高々7個程度といわれている。平均４つとして、各ワードの辞書領域は８バイト小さくなる。とすると3000ワードならリスト総体が24kb圧縮されるので、表の分があってもITCより全体で12kb程度サイズを小さくすることができるわけである。新ワード用に1000個分程度のスペースをつくっても、まだおつりがくる。
とはいえ、もともとは16ビット（2バイト）システムで1バイト（256個まで）のワード表（512バイト）を構成するというやりかただったらしい。実際、厳しい制約の中でこそ活きる方式であろう。この場合、2バイトシステムでも各ワードの辞書内リストは1バイトリストで済むわけである。
理屈からいえば、トークンは番号でなくてもいいわけである。ワードアドレス表も使用環境にあわせて様々な形態が考えられるだろう。
最終更新：2019年06月04日 23:20
