Loading article…
コンピュータサイエンスにおいて、スレッドコードとは、コードが基本的にサブルーチンへの呼び出しのみで構成される形式のプログラミング手法です。これはコンパイラでよく用いられ、コンパイラはスレッドコードを生成する場合もあれば、スレッドコード自体がその形式で実装される場合もあります。スレッドコードはインタプリタによって処理される場合もあれば、単に機械語呼び出し命令のシーケンスである場合もあります。
スレッド化されたコードは、代替生成手法や代替呼び出し規約によって生成されたコードよりも密度が高い。キャッシュアーキテクチャでは、実行速度がわずかに遅くなる可能性がある。しかし、コンピュータプロセッサのキャッシュに収まるほど小さいプログラムは、キャッシュミスが頻繁に発生する大きなプログラムよりも高速に実行される可能性がある。[ 1 ]また、他のプログラムがキャッシュを埋め尽くした場合、小さなプログラムはスレッド切り替えも高速になる可能性がある。
スレッドコードは、Forth、BASICの多くの実装、COBOLのいくつかの実装、 Bの初期バージョン[ 2 ]、小型ミニコンピュータやアマチュア無線衛星用のその他の言語など、多くのプログラミング言語のコンパイラでの使用で最もよく知られています。
コンピュータプログラムを作成する一般的な方法は、コンパイラを使用してソースコード（何らかの記号言語で記述されている）を機械語に変換することです。生成される実行ファイルは通常高速ですが、ハードウェアプラットフォームに特化しているため、移植性がありません。別の方法として、仮想マシン用の命令を生成し、各ハードウェアプラットフォーム上でインタプリタを使用する方法があります。インタプリタは仮想マシン環境をインスタンス化し、命令を実行します。このように、機械語にコンパイルされたインタプリタは、「インタプリタ型言語」のための抽象化レイヤーを提供します。このレイヤーに準拠するためにコンパイルはほとんど必要なく（コンパイルは抽象構文木の生成に限定される場合もあります）、あるいは（レイヤーが生のソースコードを消費するように設計されている場合は）コンパイル自体が全く必要ありません。
初期のコンピュータはメモリ容量が比較的少なかった。例えば、データゼネラル社のNova、IBM 1130、そして初期のマイクロコンピュータの多くは、わずか 4KBのRAMしか搭載していなかった。そのため、利用可能なメモリに収まるようにプログラムのサイズを縮小する方法を見つけるのに多くの時間が費やされた。
一つの解決策は、記号言語を少しずつ読み込み、関数を呼び出してアクションを実行するインタプリタを使用することです。ソースコードは通常、生成されるマシンコードよりもはるかに密度が高いため、これにより全体のメモリ使用量を削減できます。これが、 Microsoft BASICがインタプリタである理由です。 [ a ] Microsoft BASIC自身のコードは、Altair 8800 のようなマシンの 4 kB のメモリをユーザーのソースコードと共有する必要がありました。コンパイラはソース言語からマシンコードに変換するため、コンパイラ、ソース、出力はすべて同時にメモリ上に存在する必要があります。インタプリタには出力はありません。
スレッドコードとは、コンパイル済みコードのフォーマットスタイルの一つで、メモリ使用量を最小限に抑えることを目的としています。例えばマクロアセンブラのように、プログラム内で操作の各ステップを毎回記述するのではなく、コンパイラは共通するコードの各部分をサブルーチンに書き込みます。そのため、各部分はメモリ上の1箇所にのみ存在します（「繰り返しを避ける」原則を参照）。これらのプログラムにおける最上位アプリケーションは、サブルーチン呼び出しのみで構成される場合があります。そして、これらのサブルーチンの多くもまた、下位レベルのサブルーチン呼び出しのみで構成されています。
メインフレームやRCA 1802などの初期のマイクロプロセッサでは、サブルーチンを呼び出すのに複数の命令が必要でした。最上位アプリケーションや多くのサブルーチンでは、この命令シーケンスが繰り返し実行され、呼び出しごとにサブルーチンのアドレスだけが変わります。つまり、多数の関数呼び出しで構成されるプログラムには、かなりの量の重複コードが含まれる可能性があるということです。
この問題を解決するため、スレッドコードシステムでは、関数呼び出しを単一の演算子で表現するために擬似コードが使用されました。実行時には、小さな「インタプリタ」がトップレベルのコードをスキャンし、メモリ内のサブルーチンのアドレスを抽出して呼び出します。他のシステムでは、この基本的な概念は、サブルーチンのアドレスのテーブルで構成される分岐テーブル、ディスパッチテーブル、または仮想メソッドテーブルとして実装されています。
1970年代、ハードウェア設計者はサブルーチン呼び出しをより高速かつ簡潔にするために多大な努力を払った。改良された設計では、サブルーチン呼び出しに必要な命令は1つだけなので、擬似命令を使用してもメモリ容量の節約にはならない。さらに、これらの呼び出しのパフォーマンスは、ほとんど追加のオーバーヘッドなしで向上する。今日では、ほとんどすべてのプログラミング言語がコードをサブルーチンに分離することに重点を置いているが、それはメモリ容量を節約するためではなく、コードの明瞭性と保守性を高めるためである。
スレッド化されたコードシステムは、サブルーチンのアドレスだけが呼び出しごとに変わる関数呼び出しのリストを、呼び出しオペコードが取り除かれた関数呼び出しである実行トークンのリストに置き換えることで、スペースを節約します。これにより、アドレスのリストだけが残ります。[ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ]
長年にわたり、プログラマーは「インタプリタ」または「小型セレクタ」の様々なバリエーションを生み出してきました。アドレスリスト内の特定のアドレスは、インデックス、汎用レジスタ、またはポインタを使用して抽出できます。アドレスは、直接アドレスまたは間接アドレス、連続アドレスまたは非連続アドレス（ポインタでリンク）、相対アドレスまたは絶対アドレス、コンパイル時に解決されるアドレスまたは動的に構築されるアドレスのいずれかになります。あらゆる状況において「最適」な単一のバリエーションは存在しません。
スペースを節約するために、プログラマーはサブルーチン呼び出しのリストをサブルーチンアドレスの単純なリストに圧縮し、小さなループを使用して各サブルーチンを順番に呼び出しました。たとえば、次の擬似コードは、この手法を使用して2つの数値AとBを加算します。この例では、リストはthreadというラベルが付けられており、変数ip（命令ポインタ）はリスト内の現在位置を追跡します。別の変数sp（スタックポインタ）には、一時的に値を保持するために使用できるメモリ内の別のアドレスが格納されています。
start : ip = & thread // アドレス '&pushA' を指し、テキスト ラベル 'thread' を指すわけではありませんtop : jump * ip ++ // ip をたどってスレッド内のアドレスに移動し、そのアドレスをたどってサブルーチンに移動し、ip を進めますthread : & pushA & pushB & add ... pushA : * sp ++ = A // sp をたどって使用可能なメモリに移動し、そこに A を格納し、sp を次のjump topに進めますpushB : * sp ++ = B jump top add : addend1 = *-- sp // スタックから最上位の値をポップしますaddend2 = *-- sp // スタックから 2 番目の値をポップします* sp ++ = addend1 + addend2 // 2 つの値を加算し、結果をスタックの最上位に格納しますjump top の呼び出しループはtop非常に単純なので、各サブルーチンの最後にインラインで繰り返すことができます。これにより、制御は を介して 2 回ジャンプするのではなく、サブルーチンの終了から別のサブルーチンの開始まで 1 回ジャンプするようになりますtop。例:
start : ip = & thread // ip は &pushA (pushA の最初の命令を指す) を指すjump * ip ++ // 制御を pushA の最初の命令に送り、ip を &pushB に進めるthread : & pushA & pushB & add ... pushA : * sp ++ = A // sp をたどって使用可能なメモリに移動し、A をそこに格納し、sp を次の命令に進めるjump * ip ++ // ip が指示する場所 (つまり pushB) に制御を送り、ip を進めるpushB : * sp ++ = B jump * ip ++ add : addend1 = *-- sp // スタックから最上位の値をポップするaddend2 = *-- sp // スタックから 2 番目の値をポップする* sp ++ = addend1 + addend2 // 2 つの値を加算し、結果をスタックの最上位に格納するjump * ip ++これは直接スレッドコード（DTC）と呼ばれます。この技術自体は古いものですが、「スレッドコード」という用語が広く普及したのは、おそらくジェームズ・R・ベルの1973年の論文「スレッドコード」でしょう。[ 8 ]
1970年、チャールズ・H・ムーアは、自身のForth仮想マシン向けに、よりコンパクトな構成である間接スレッドコード（ITC）を考案した。ムーアがこの構成に至ったのは、 Novaミニコンピュータがすべてのアドレスに間接ビットを持っていたため、ITCが簡単かつ高速に実行できたからである。後に彼は、この方式が非常に便利だと感じたため、その後のすべてのForth設計に採用したと述べている。[ 9 ]
現在、Forthコンパイラの中には直接スレッドコードを生成するものと、間接スレッドコードを生成するものがある。どちらの場合も、実行ファイルの動作は同じである。
実行可能なスレッドコードは、ほぼすべて、サブルーチンを呼び出すためにこれらの方法のいずれかを使用します（それぞれの方法は「スレッドモデル」と呼ばれます）。
スレッド内のアドレスは、機械語のアドレスです。この形式は単純ですが、スレッドが機械語のアドレスのみで構成されているため、オーバーヘッドが発生する可能性があります。そのため、以降のすべてのパラメータはメモリから間接的にロードする必要があります。一部のForthシステムは、直接スレッド化されたコードを生成します。多くのマシンでは、直接スレッド化はサブルーチンスレッド化よりも高速です（下記の参照を参照）。
スタックマシンの一例として、「A をプッシュ、B をプッシュ、追加」というシーケンスが考えられます。これは、次のスレッドとルーチンに変換される可能性があり、ここで はipラベル付けされたアドレスthread(つまり、 が格納されているアドレス&pushA) に初期化されます。
#define PUSH(x) (*sp++ = (x)) #define POP() (*--sp) start : ip = & thread // ip は &pushA (pushA の最初の命令を指す) を指すjump * ip ++ // 制御を pushA の最初の命令に送り、ip を &pushB に進めるthread : & pushA & pushB & add ... pushA : PUSH ( A ) jump * ip ++ // ip が指示する場所 (つまり pushB) に制御を送り、ip を進めるpushB : PUSH ( B ) jump * ip ++ add : result = POP () + POP () PUSH ( result ) jump * ip ++あるいは、オペランドをスレッドに含めることもできます。これにより、上記で必要となる間接参照の一部が不要になりますが、スレッドのサイズが大きくなります。
#define PUSH(x) (*sp++ = (x)) #define POP() (*--sp) start : ip = & thread jump * ip ++ thread : & push & A // A が格納されているアドレス (リテラル A ではない) & push & B & add ... push : variable_address = * ip ++ // ip はサブルーチン アドレスではないため、オペランド アドレスより後に移動する必要があるPUSH ( * variable_address ) // 変数から値を読み取り、スタックにプッシュするjump * ip ++ add : result = POP () + POP () PUSH ( result ) jump * ip ++間接スレッドでは、マシンコードを指すポインタを使用します。間接ポインタの後にはオペランドが続くことがあり、オペランドはスレッド内で繰り返し格納されるのではなく、間接「ブロック」に格納されます。そのため、間接コードは直接スレッドコードよりもコンパクトになることがよくあります。間接処理によって通常は処理速度が低下しますが、それでもバイトコードインタープリタよりは高速です。ハンドラオペランドに値と型の両方が含まれる場合、直接スレッドコードに比べて大幅なメモリ削減効果が得られる可能性があります。古いFORTHシステムでは、通常、間接スレッドコードが生成されます。
例えば、「push A, push B, add」を実行するのが目的であれば、以下のように記述できます。ここで、ipはアドレスに初期化され&thread、各コード断片（push、add）はと間接ブロックを介して二重間接参照によって見つかりますip。また、断片へのオペランドは、断片のアドレスに続く間接ブロック内で見つかります。これは、以前の例のように次に呼び出されるサブルーチンをに保持するのではなく、現在のサブルーチンをに保持する必要があることを意味します。ip
start : ip = & thread // '&i_pushA' を指すjump ** ip // 'push' の最初の命令へのポインタをたどるが、まだ ip を進めないthread : & i_pushA & i_pushB & i_add ... i_pushA : & push & A i_pushB : & push & B i_add : & add push : * sp ++ = ** ( * ip + 1 ) // オペランド アドレスについて、間接ブロックの開始位置から 1 つ先を参照jump * ( *++ ip ) // スレッドで ip を進め、次の間接ブロックを通り抜けて次のサブルーチンにジャンプするadd : addend1 = *-- sp addend2 = *-- sp * sp ++ = addend1 + addend2 jump * ( *++ ip )いわゆる「サブルーチン・スレッド・コード」（または「コール・スレッド・コード」）は、一連の機械語の「call」命令（または「呼び出す」関数のアドレス。直接スレッドでは「jump」命令が用いられる）で構成されます。ALGOL、Fortran、Cobol、および一部のForthシステム向けの初期のコンパイラは、しばしばサブルーチン・スレッド・コードを生成します。これらのシステムの多くは、後入れ先出し（LIFO）方式のオペランド・スタック上で動作し、コンパイラ理論は十分に発展していました。現代のプロセッサのほとんどは、サブルーチンの「call」命令と「return」命令をハードウェアでサポートしているため、ディスパッチごとに1つの追加の機械語命令が発生するオーバーヘッドはいくらか軽減されています。
Gforthコンパイラの共同開発者であるアントン・エルトル氏は、「一般的な通説とは異なり、サブルーチン・スレッディングは通常、直接スレッディングよりも遅い」と述べています。[ 10 ]しかし、エルトル氏の最新のテスト[ 1 ]では、25のテストケースのうち15でサブルーチン・スレッディングが直接スレッディングよりも高速であることが示されています。より具体的には、Xeon、Opteron、Athlonプロセッサでは直接スレッディングが最速のスレッディングモデルであり、Pentium Mプロセッサでは間接スレッディングが最速であり、Pentium 4、Pentium III、PPCプロセッサではサブルーチン・スレッディングが最速であることが分かりました。
「push A、push B、add」の呼び出しスレッドの例として、以下を示します。
スレッド: pushAを呼び出すpushBを呼び出すaddを呼び出すret pushA : * sp ++ = A ret pushB : * sp ++ = B ret add : addend1 = *-- sp addend2 = *-- sp * sp ++ = addend1 + addend2 retトークンスレッドコードは、スレッドを操作テーブルへのインデックスのリストとして実装します。インデックス幅は、密度と効率を考慮して、できるだけ小さくなるように自然に選択されます。プログラミングの容易さから、1バイト/8ビットが自然な選択肢ですが、サポートする操作の数に応じて、4ビットなどのより小さいサイズ、または12ビットや16ビットなどのより大きなサイズを使用することもできます。インデックス幅がマシンポインタよりも狭く選択されている限り、プログラマが特別な努力をしなくても、他のスレッドタイプよりも自然にコンパクトになります。通常、他のスレッドの半分から4分の3のサイズであり、他のスレッド自体も非スレッドコードの4分の1から8分の1のサイズです。テーブルのポインタは、間接ポインタまたは直接ポインタのいずれかになります。一部のForthコンパイラは、トークンスレッドコードを生成します。一部のプログラマーは、一部のPascalコンパイラによって生成される「pコード」や、.NET、Java、BASIC、および一部のCコンパイラで使用されるバイトコードをトークンスレッディングであると考えている。
歴史的に一般的なアプローチはバイトコードであり、これは通常、スタックベースの仮想マシンで8ビットのオペコードを使用する。典型的なバイトコードインタープリタは「デコードおよびディスパッチインタープリタ」として知られており、次の形式に従う。
開始: vpc = &スレッドディスパッチ: addr = decode ( & vpc ) // 次のバイトコード操作を、それを実装するマシン コードへのポインタに変換します// 命令間の操作はここで実行されます (グローバル ステートの更新、イベント処理など) jump addr CODE_PTR decode ( BYTE_CODE ** p ) { // より複雑なエンコーディングでは、選択できる複数のテーブルまたは制御/モード フラグが存在する場合がありますreturn table [ * ( * p ) ++ ]; }スレッド: /* マシン アドレスではなくバイト コードが含まれています。そのため、よりコンパクトです。 */ 1 /*pushA*/ 2 /*pushB*/ 0 /*add*/ table : & add /* table[0] = バイトコード 0 を実装するマシン コードのアドレス */ & pushA /* table[1] ... */ & pushB /* table[2] ... */ pushA : * sp ++ = AジャンプディスパッチpushB : * sp ++ = Bジャンプディスパッチadd : addend1 = *-- sp addend2 = *-- sp * sp ++ = addend1 + addend2ジャンプディスパッチ仮想マシンがバイトサイズの命令のみを使用する場合、decode()は単にからのフェッチですが、多くの場合、よく使用される 1 バイト命令に加えて、あまり一般的ではないマルチバイト命令 (複雑な命令セットコンピュータthreadを参照) があり、その場合はがより複雑になります。シングルバイトのオペコードのデコードは、オペコードを直接インデックスとして使用する分岐テーブルによって非常に簡単かつ効率的に処理できます。decode()
「プッシュ」や「加算」といった個々の操作が単純な命令の場合、実行する操作を決定する際のオーバーヘッドが、実際に実行するコストよりも大きくなるため、このようなインタプリタは機械語よりもはるかに低速になることが多い。しかし、より複雑な（「複合」）命令の場合、オーバーヘッドの割合は比例して小さくなる。
トークンスレッドコードは、マシンコードが物理CPUのL1命令キャッシュに収まらないほど大きくなる場合、同等のマシンコードよりも高速に実行されることがあります。スレッドコード、特にトークンスレッドコードはコード密度が高いため、本来収まらない場合でもL1キャッシュに完全に収まることができ、キャッシュスラッシングを回避できます。ただし、マシンコードが命令キャッシュのみを消費するのとは異なり、スレッドコードは命令キャッシュ（各操作の実装用）とデータキャッシュ（バイトコードとテーブル用）の両方を消費します。つまり、スレッドコードは、CPUが一度に処理用に保持できるデータ量の予算を消費することになります。いずれにせよ、計算対象の問題が少量のデータに多数の操作を適用することである場合、スレッドコードの使用は理想的な最適化となる可能性があります。 [ 4 ]
ハフマン スレッド コードは、ハフマン コードとして格納されたトークンのリストで構成されます。ハフマン コードとは、一意のトークンを識別する可変長のビット列です。ハフマン スレッド インタプリタは、インデックス テーブルまたはハフマン コードでナビゲートできるポインタ ツリーを使用してサブルーチンを検索します。ハフマン スレッド コードは、コンピュータ プログラムの最もコンパクトな表現方法の 1 つです。インデックスとコードは、コード内の各サブルーチンへの呼び出し頻度を測定することによって選択されます。頻繁に呼び出されるサブルーチンには、最短のコードが割り当てられます。呼び出し頻度がほぼ同じ操作には、ほぼ同じビット長のコードが割り当てられます。ほとんどのハフマン スレッド システムは、直接スレッド Forth システムとして実装され、大量の低速なコードを小型で安価なマイクロコントローラに詰め込むために使用されています。公開されているほとんどの使用例は、スマート カード、おもちゃ、電卓、時計です。PBASICで使用されるビット指向のトークン化コードは、一種のハフマン スレッド コードと見なすことができます。
一例として、文字列スレッディングがあります。これは、操作を文字列で識別し、通常はハッシュテーブルで検索する方式です。この方式は、チャールズ・H・ムーアによる初期のForth実装や、イリノイ大学の実験的なハードウェアインタプリタ型コンピュータ言語で使用されていました。また、 Bashforthでも使用されています。
HPのRPL は、1986 年にHP-18C電卓で初めて導入された、独自のハイブリッド (直接スレッドと間接スレッド)スレッド インタプリタ言語(TIL) [ 12 ]の一種で、他の TIL とは異なり、RPL 「オブジェクト」[ b ]を「ランストリーム」、つまりインタプリタ ポインタが進むアドレス ストリームに埋め込むことができます。RPL 「オブジェクト」は、メモリ内の構造にオブジェクトの先頭にある「オブジェクト プロローグ」のアドレスが含まれ、その後にデータまたは実行可能コードが続く、特殊なデータ型と考えることができます。オブジェクト プロローグは、オブジェクトの本体がどのように実行または処理されるかを決定します。1986年に William C. Wickes によって発明され、特許を取得[ 14 ] 、1988 年に公開された「RPL インナー ループ」 [ 13 ]を使用すると、実行は次のように続きます。[ 15 ]
これはより正確には次のように表すことができます。
O = [I] I = I + Δ PC = [O] + Δ
上記において、Oは現在のオブジェクトポインタ、Iはインタプリタポインタ、Δは1アドレスワードの長さであり、"[]"演算子は「逆参照」を表します。
オブジェクトポインタまたは埋め込みオブジェクトに制御が移ると、実行は次のように継続されます。
PROLOG -> PROLOG（プロローグコードの先頭にあるプロローグアドレスは、自身を指している） O + Δ ≠ PC の場合 次に間接実行へ（直接実行のテスト） O = I - Δ（埋め込みオブジェクトの開始位置を指すようにOを修正してください） I = I + α（埋め込みオブジェクトの後を指すようにIを修正してください。αはオブジェクトの長さです。） 間接的（プロローグの残りの部分）
RPLを使用するHPのSaturnマイクロプロセッサでは、アーキテクチャ/プログラミングのトリックによって3番目のレベルの間接参照が可能になり、より高速な実行が可能になります。[ 13 ]
すべてのインタプリタにおいて、分岐は単にスレッドポインタ（ip）をスレッド内の別のアドレスに変更するだけです。スタックの最上位の値がゼロの場合にのみジャンプする条件付きジャンプ・イフ・ゼロ分岐は、以下のように実装できます。この例では、直接スレッド処理の埋め込みパラメータ版を使用しているため、&thread[123]条件が真の場合にジャンプする先は行であり、ip++分岐が実行されない場合はスキップ（）する必要があります。
スレッド: ... & brz &スレッド[ 123 ] ... brz : when_true_ip = * ip ++ // 分岐の宛先アドレスを取得if ( *-- sp == 0 ) // スタックの最上位をポップ/消費し、ゼロかどうかを確認ip = when_true_ip jump * ip ++マシン内でデータスタックとリターンスタックを分離することで、スタック管理コードが大幅に削減され、スレッドコードのサイズが著しく小さくなります。デュアルスタックの原理は、Burroughsの大規模システム、Forth、PostScriptの3つのシステムでそれぞれ独立して生まれました。一部のJava仮想マシンでも使用されています。
スレッド型仮想マシンには、通常3つのレジスタが存在します。もう1つは、サブルーチン間（「ワード」）でデータを渡すためのものです。これらは以下のとおりです。
Forthの実装など、スレッド型仮想マシンは、多くの場合、3つの基本要素からなるシンプルな仮想マシンを中核としています。それらは以下のとおりです。
ここで示されているような間接スレッド型仮想マシンでは、操作は次のようになります。
next : * ip ++ -> w jump ** w ++ nest : ip -> * rp ++ w -> ip next unnest : *-- rp -> ip nextip関数パラメータに置き換えるスタイルです。