スレッデッドコード
スレッデッドコードは、プログラミング言語処理系におけるコード生成手法の一つで、呼び出すべきサブルーチンのアドレスを羅列する方式です。この手法は、特にメモリ容量が限られていた初期のコンピュータ環境において、プログラムサイズを小さく保ちつつ、ある程度の実行速度を維持するために有効でした。
一般的に、コンピュータプログラムは記号言語で記述され、コンパイラによって機械語に変換されて実行されます。機械語は高速に実行できますが、特定のアーキテクチャに依存するため、他のプラットフォームでは動作しません。一方、仮想機械の命令セットを使用する方式では、プラットフォームに依存しない実行が可能になります。しかし、初期のコンピュータではメモリ容量が非常に限られており、プログラムを小さくまとめる必要がありました。
この問題に対応するため、プログラマは繰り返し使用する演算ステップをサブルーチンとして定義し、コードの再利用性を高めました。その結果、プログラムのトップレベルはサブルーチンコールの羅列となり、サブルーチン自体もさらに低いレベルのサブルーチンを呼び出す構造となりました。しかし、サブルーチンを呼び出すための命令シーケンスは繰り返し現れ、メモリの無駄につながっていました。
そこで、サブルーチンコールの羅列をサブルーチンのアドレスリストに変換し、そのリストを順次実行する小さな「インタプリタ」を導入するスレッデッドコードが開発されました。これにより、同じ命令列を繰り返し格納する必要がなくなり、メモリ使用量を削減できるようになりました。
スレッデッドコードにはいくつかの実装方式があり、それぞれ特徴が異なります。
直接スレッデッドコード (DTC): 機械語コードのアドレスを直接リスト化します。シンプルで高速ですが、オペランドが必要な場合は、メモリから間接的にロードする必要があるため、多少のオーバーヘッドがあります。
間接スレッデッドコード (ITC): 機械語コードを指すポインタのある場所へのポインタを使用します。これにより、スレッド本体にオペランドが繰り返し出現するのを防ぎ、コードをコンパクトにできますが、間接参照のため実行速度は若干低下します。
サブルーチン・スレッデッドコード: 機械語のコール命令をスレッドに並べます。初期のコンパイラや一部のForth処理系で採用され、最近のプロセッサではコール命令とリターン命令のオーバーヘッドが小さいため、効率的な実装が可能です。
トークン・スレッデッドコード: 8ビットまたは12ビットのインデックスリストを使用し、ポインタテーブルのインデックスとして利用します。非常にコンパクトなコードを生成できます。
ハフマン・スレッデッドコード: ハフマン符号のリストを使用し、頻繁に使用されるサブルーチンに短い符号を割り当てることで、コードサイズをさらに圧縮します。メモリが限られた環境で特に有効です。
例えば、スタックマシンで "push A, push B, add" という処理を実行する場合、直接スレッデッドコードは以下のように構成されます。
thread:
&pushA
&pushB
&add
...
pushA:
sp++ = A
jump ip++
pushB:
sp++ = B
jump ip++
add:
sp++ = sp + sp
jump *ip++
ここで、ipはスレッド内のアドレスを指し、各サブルーチンはスタック操作を実行した後、次の命令へジャンプします。
スレッデッドコードは、他のコード生成技法と比較して、コード密度が高いという利点があります。また、プログラムが小さくなるため、CPUキャッシュに収まりやすく、キャッシュミスを減らすことで性能が向上する可能性があります。しかし、一般的には、実行速度が若干遅くなる傾向があります。これは、インタプリタがサブルーチンを呼び出す際のオーバーヘッドによるものです。また、スレッデッドコードは、バイトコードのようにマシンに依存しないコードを生成するというより、マシンに依存した命令を並べることになるので、基本的には、マシン依存になります。
スレッデッドコードは、Forth、多くのBASIC実装、一部のCOBOL実装、初期のB言語、小型ミニコンピュータなど、多くのプログラミング言語で利用されてきました。特に、メモリ容量が限られていた初期のコンピュータシステムや、組み込みシステムなどで重宝されてきました。ハフマン・スレッデッドコードは、電子式のおもちゃ、電卓、腕時計など、非常に小さなメモリ容量しかないデバイスで利用されています。
スレッデッドコードは、プログラムの実行効率とメモリ使用量を最適化するための重要な技術であり、特にリソースが限られた環境で有効です。その多様な実装方式は、プログラマが特定の要件に合わせて最適な方法を選択できる柔軟性を提供しています。また、その歴史的な意義も深く、コンピュータの発展に大きく貢献した技術の一つと言えるでしょう。
スレッデッドコードの基本
一般的に、コンピュータプログラムは記号言語で記述され、コンパイラによって機械語に変換されて実行されます。機械語は高速に実行できますが、特定のアーキテクチャに依存するため、他のプラットフォームでは動作しません。一方、仮想機械の命令セットを使用する方式では、プラットフォームに依存しない実行が可能になります。しかし、初期のコンピュータではメモリ容量が非常に限られており、プログラムを小さくまとめる必要がありました。
この問題に対応するため、プログラマは繰り返し使用する演算ステップをサブルーチンとして定義し、コードの再利用性を高めました。その結果、プログラムのトップレベルはサブルーチンコールの羅列となり、サブルーチン自体もさらに低いレベルのサブルーチンを呼び出す構造となりました。しかし、サブルーチンを呼び出すための命令シーケンスは繰り返し現れ、メモリの無駄につながっていました。
そこで、サブルーチンコールの羅列をサブルーチンのアドレスリストに変換し、そのリストを順次実行する小さな「インタプリタ」を導入するスレッデッドコードが開発されました。これにより、同じ命令列を繰り返し格納する必要がなくなり、メモリ使用量を削減できるようになりました。
スレッデッドコードの種類
スレッデッドコードにはいくつかの実装方式があり、それぞれ特徴が異なります。
直接スレッデッドコード (DTC): 機械語コードのアドレスを直接リスト化します。シンプルで高速ですが、オペランドが必要な場合は、メモリから間接的にロードする必要があるため、多少のオーバーヘッドがあります。
間接スレッデッドコード (ITC): 機械語コードを指すポインタのある場所へのポインタを使用します。これにより、スレッド本体にオペランドが繰り返し出現するのを防ぎ、コードをコンパクトにできますが、間接参照のため実行速度は若干低下します。
サブルーチン・スレッデッドコード: 機械語のコール命令をスレッドに並べます。初期のコンパイラや一部のForth処理系で採用され、最近のプロセッサではコール命令とリターン命令のオーバーヘッドが小さいため、効率的な実装が可能です。
トークン・スレッデッドコード: 8ビットまたは12ビットのインデックスリストを使用し、ポインタテーブルのインデックスとして利用します。非常にコンパクトなコードを生成できます。
ハフマン・スレッデッドコード: ハフマン符号のリストを使用し、頻繁に使用されるサブルーチンに短い符号を割り当てることで、コードサイズをさらに圧縮します。メモリが限られた環境で特に有効です。
スレッデッドコードの動作例
例えば、スタックマシンで "push A, push B, add" という処理を実行する場合、直接スレッデッドコードは以下のように構成されます。
thread:
&pushA
&pushB
&add
...
pushA:
sp++ = A
jump ip++
pushB:
sp++ = B
jump ip++
add:
sp++ = sp + sp
jump *ip++
ここで、ipはスレッド内のアドレスを指し、各サブルーチンはスタック操作を実行した後、次の命令へジャンプします。
スレッデッドコードのメリットとデメリット
スレッデッドコードは、他のコード生成技法と比較して、コード密度が高いという利点があります。また、プログラムが小さくなるため、CPUキャッシュに収まりやすく、キャッシュミスを減らすことで性能が向上する可能性があります。しかし、一般的には、実行速度が若干遅くなる傾向があります。これは、インタプリタがサブルーチンを呼び出す際のオーバーヘッドによるものです。また、スレッデッドコードは、バイトコードのようにマシンに依存しないコードを生成するというより、マシンに依存した命令を並べることになるので、基本的には、マシン依存になります。
スレッデッドコードの歴史と応用
スレッデッドコードは、Forth、多くのBASIC実装、一部のCOBOL実装、初期のB言語、小型ミニコンピュータなど、多くのプログラミング言語で利用されてきました。特に、メモリ容量が限られていた初期のコンピュータシステムや、組み込みシステムなどで重宝されてきました。ハフマン・スレッデッドコードは、電子式のおもちゃ、電卓、腕時計など、非常に小さなメモリ容量しかないデバイスで利用されています。
まとめ
スレッデッドコードは、プログラムの実行効率とメモリ使用量を最適化するための重要な技術であり、特にリソースが限られた環境で有効です。その多様な実装方式は、プログラマが特定の要件に合わせて最適な方法を選択できる柔軟性を提供しています。また、その歴史的な意義も深く、コンピュータの発展に大きく貢献した技術の一つと言えるでしょう。
もう一度検索
【記事の利用について】
タイトルと記事文章は、記事のあるページにリンクを張っていただければ、無料で利用できます。
※画像は、利用できませんのでご注意ください。
【リンクついて】
リンクフリーです。