Threaded Code(翻訳)
原文 : http://www.complang.tuwien.ac.at/forth/threaded-code.htmlを翻訳したサイトがあったのだが、いつの間にかなくなった。仕方ないので、自家翻訳する。
追記:(ほとんど訳した後に、Internet archiveがあることに気がついた。私が以前見た訳文は、Threaded Code。翻訳の質はこちらの方が上)
- スレッデッドコードとは何か?
- スレッデッドコードは何に効果的か?
- さまざまなスレッディング手法の違いは?
- どのようにスレッデッドコードを移植可能に実装するか?
- 各スレッディング手法はどのくらい速いか?
スレッデッドコードは何に効果的か?
スレッデッドコードは仮想マシンインタプリタを実装する手法である。インタプリタを実装する様々な方法がある: よく知られたものは:
- 直接文字列解釈
- ツリー(通常は抽象構文木)へコンパイルし、そのツリーを解釈していく
- 仮想機械語へコンパイルし、仮想機械語を解釈していく
もし性能に興味があるなら、仮想マシンのアプローチがその方法である(なぜなら、フェッチとデコードが簡単で、それゆえ速い)。もし性能に(まだ)興味がないなら、それでも仮想マシンのアプローチを検討してもよい。なぜなら、それは大抵、他と同じくらい簡単であるためである。
bell 73の元の意味のスレッデッドコードは、仮想マシンインタプリタを実装する手法の1つである。今日では、少なくともForthコミュニティは、Forthの仮想マシンを実装するのに使用するほとんど全ての手法に「スレッディング」の用語を用いる。
スレッデッドコードとは何か?
仮想マシン命令A、BおよびCを含む一直線のコード片を見てみよう。
仮想マシン命令の動作を行うのに、機械語レベルサブルーチンAr、Br、およびCrを書ける。それからこれらの仮想マシン命令を実行するのに以下の機械語コードを書ける:
call Ar call Br call Cr
これはサブルーチンスレッデッドコードとして知られるが、元の意味のスレッデッドコードではない; 実のところ、サブルーチンスレッディングはスレッディング手法ですらない。
ところで、callを取り除いてみよう:
Ar Br Cr
すなわち、仮想マシン命令を表すコード番地の列。
結果として、開始するために、ジャンプによってこのコードの断片を実行できない。(プロセッサのプログラムカウンタと戻り番地スタック/レジスタを用いる代わりに)別のレジスタで、現在の命令のポインタも追跡しなければならない。
どのように次の命令を実行するか?命令ポインタレジスタ(ip)は、コード列のワードを常に指し示していると仮定しよう。そのレジスタは、現在の命令ワードを直接追跡している。それから、ワードをロードし、それに指し示されたルーチンにジャンプし、命令ポインタをインクリメントしなければならない。例えば、MIPSアセンブリ言語で:
lw $2,0($4) #次の命令を得る, $4=命令ポインタ addu $4,$4,4 #命令ポインタを進める j $2 #次の命令を実行する #nop #分岐(j)のディレイスロット
このルーチンはインタプリタである(Forthコミュニティでは別名「内部インタプリタ」)。NEXTルーチンとしても知られる。全ての仮想マシン命令ルーチンは最後にNEXTのコピーを持つか、NEXTの1つのコピーを共有し、それにジャンプするかのどちらかである。
現代的なプロセッサでは、共有のNEXTはジャンプ命令のコストだけでなく、分岐ターゲットバッファ付きCPUや類似の間接分岐予測器の、間接ジャンプの予測ミスの比率が劇的に増加する。それゆえ、NEXTを共有しないことを勧める。
上で述べた方法はスレッデッドコードとしてbell 73に記述されたものであり、後に直接スレッデッドコードと呼ばれた。
一般的な俗説と対照的に、サブルーチンスレッディングは直接スレッディングよりも通常遅いことに注意すること。しかし、サブルーチンスレッディングはネイティブコード生成の第一歩である。
スレッディング技法
その考え方に基づいて、いくつかの変形が開発された:
間接スレッデッドコード
定数を考えてみよう: それらは仮想マシン命令lit(literalにちなんで)、続いてその定数値によって表現される。もしその定数が頻繁に現れる場合、この定数のために仮想マシン命令を持つことは、よりスペース効率が良い。もし定数がいくつかある場合、それらの仮想マシン命令のためのコードはほとんど同じに見えるだろう。だから、同じデータがあるなら、コードを共有すると良い。
NEXT内の間接参照のレベルの追加(結果として間接スレッデッドコード)によってこれを行うことが出来る。それぞれのワード(仮想機械語命令の一般化)はコードフィールドとパラメータフィールドを持つ。たとえば、定数の場合:
code-field: docon #共有される定数のコード番地 parameter-field: value #定数の値
仮想機械語はいま、コードの番地ではなく、コードフィールドの番地の列によって表現されている。単純な仮想機械語命令(プリミティブ)は一般的に以下のように表現される:
code-field2: parameter-field2 parameter-field2: code #プリミティブの機械語
間接スレッデッドコードのNEXTはMIPSアセンブリ言語ではこのように見える:
lw $2,0($4) #次のワードのコードフィールド番地を得る。$4=命令ポインタ #nop #ロード(lw)のディレイスロット lw $3,0($2) #ワードのコード番地を得る addu $4,$4,4 #命令ポインタを進める j $3 #ワードのコードを実行する #nop #分岐(j)のディレイスロット
次の命令のためのコードは、$2のコードフィールド番地からパラメータフィールド番地を計算できる。
Forthと直接スレッディング
伝統的にForthは間接スレッディングを用いて実装されている。それゆえ直接スレッディングのForth実装は間接スレッディングの実装と多くの共通点を持っている: 非プリミティブ(あらかじめ定義されていないワード)はコードフィールドを持っているが、今はそのアドレスの代わりにコードへのジャンプ先を含んでいる。ほとんどのプロセッサで、このジャンプ動作は間接スレッディングの余分なロード命令より時間がかかる。そして、直接スレッディングはプリミティブが実行されるときにだけ、この恩恵を受ける。この結果生じる時間短縮は、486では2%から8%である。
(注: Pentium、K5そしてK6(-2)では、コードとデータを混ぜることは非常に高くつくので、直接スレッディングのこの形式は、このプロセッサ上での間接スレッディングよりとても遅くなる)
トークンスレッデッドコード
直接スレッデッドコードは1つの機械から他へ簡単に移植できない。なぜなら、機械間で変化するコード番地を含んでいるためである。トークンスレッデッドコードは、固定された仮想マシン命令コードを用い、それぞれのNEXT内で(命令トークンからそのコード番地を示す)テーブル参照の代償を払ってコード移植性を持たせる。間接スレッディングとトークンスレッディングは直交した概念であるので、(さらに遅いNEXTを持つ)間接トークンスレッディングに組み合わせることができる。
その他の用語
- スイッチスレッディング
- Cのような言語で仮想マシンインタプリタを実装するために使われる方法。下記を参照。
- コールスレッディング
- Cのような言語で使われる別の方法。下記を参照。
- セグメントスレッディング
- 8086アーキテクチャで用いられる手法。コードはコード番地の列の代わりに、セグメントの列からなる。これは、16ビットの「ポインタ」で8086の全てのアドレス空間の使用を可能にする。しかし、全てのワードに16バイトの境界を要求する。
- ネイティブコード
- これはスレッディング手法ではない。解釈されるコードの代わりに機械語を生成する実装について、Forthコミュニティおよびその他で用いられる用語である。単純なネイティブコードシステムは、サブルーチンスレッデッドコードで始まり、いくつかのサブルーチンをインライン最適化・ピープホール最適化する。関連用語は本当のコンパイラ、ジャストインタイムコンパイラなどである。
- バイトコード
- 各々の仮想マシン命令は1バイトで表現される。これはトークンスレッディングの変形と考えられる。
どのようにスレッデッドコードを移植可能に実装するか?
多くの言語は間接ジャンプを実現する方法を用意していないので、直接または間接スレッデッドコードの実装には使用できない。この節は利用可能な選択肢を提示する。ertl95pldiやertl93でさらにこの話題を見つけることができる。
ここで直接スレッディングに相当する変形を提示する。間接スレッド版にするには、NEXTに間接参照を追加すること。
値としてのGNU Cのラベル
標準CへのGNU C拡張のひとつであり、スレッデッドコードを実装するのに現在最も移植性のある方法である。類似の特徴はFortranの計算されたgotoである。GNU Cでは、直接スレッデッドなNEXTは以下のように見える:
typedef void *Inst; Inst *ip; /* これにはローカル変数を使うべきである */ #define NEXT goto **ip++
継続渡しスタイル
継続渡しスタイルでは、全ての呼び出しは末尾呼び出しであり、末尾呼び出しをジャンプ命令に最適化できる。それゆえ、継続渡しスタイルでインタプリタを書くこと、および末尾呼び出し最適化を保証する言語またはコンパイラ(Scheme? ML?)を用いることで、間接末尾呼び出しとしてスレッデッドコードの間接ジャンプを実装できる。C言語(私の知っている限り、末尾呼び出し最適化を保証するCコンパイラはない)では、この手法の直接スレッディングは以下のように見えるだろう:
typedef void (* Inst)();
void inst1(Inst *ip, /* 他のレジスタ */)
{
...
(*ip)(ip+1, /* 他のレジスタ */);
}
スイッチスレッディング
スイッチスレッディングはC言語のswitch文(または、他の言語の類似の文、例えばPascalのCASE)、を用いる。その結果はトークンスレッデッドコードと同じ利点を持っている; トークンスレッデッドコードを超える欠点は、switch文でほとんどの(全ての?)Cコンパイラによって生成される、範囲チェックが原因の速度低下である; さらに、私が見たCコンパイラはswitch文のスケーリング(ワードの増加による速度低下)を回避していないが、正しい符号化をすれば、トークンスレッデッドコードはスケーリングを避けることができる。
C言語のスイッチスレッディングは以下のように見える:
typedef enum {
add /* ... */
} Inst;
void engine()
{
static Inst program[] = { inst1 /* ... */ };
Inst *ip;
for (;;)
switch (*ip++) {
case inst1:
...
break;
...
}
}
コールスレッディング
コールスレッディングは間接ジャンプの代わりに(ほとんどのプログラミング言語が持つ)間接呼び出しを用いる。各呼び出し毎に、リターン命令も存在せざるを得ない(最適化された末尾呼び出しを除く。ここでは起こらない)。なので、この方法のコストは、単純なジャンプ命令の代わりにコール・リターン命令を用いるときのものである。
コールスレッディングは以下のように見える:
typedef void (* Inst)();
Inst *ip;
void inst1()
{
...
}
void engine()
{
for (;;)
(*ip++)();
}
注: コールスレッディングは、私がこの手法に用いた用語である。これはまだ確立した用語でないようである。この手法の使用のためにサブルーチンスレッディングが使われるのを見たが、その用語は定着したものであり、異なった意味を持つ(上記参照)。
歴史
Charles Mooreはmoore87によると、1970年、アメリカ国立電波天文台(NRAO)で在職中に(間接)スレッデッドコードを考案した。最初の発表はbell73であり、それは1971年6月にCACMに最初に受理された; この論文はどんな歴史的な情報も含んでいない。
興味深いことに、moore&leach70(MooreがNRAOで働く前)に書かれたそのシステムは、スレッデッドコードを使わず、文字列解釈を用いた。しかし、コードフィールドを用いている。すなわち、間接スレッディングの種を持っている; その一方、コードフィールドはその当時においてプログラマの伝統的な手法だった(kay96)。
参考文献
- スレッド速度のベンチマーク
- Forth内部インタプリタの設計
- Prologのスレッデッドコードの実装(Internet archive)
- 値としてのGNU Cのラベル
- Pythonと間接スレッディング(Internet archive)
- Smalltalk実装Squeakのスレッデッドコード
@Article{bell73,
author = "James R. Bell",
title = "Threaded Code",
journal = cacm,
year = 1973,
volume = 16,
number = 6,
pages = "370--372"
}
@Article{dewar75,
author = {Robert B.K. Dewar},
title = {Indirect Threaded Code},
journal = cacm,
year = {1975},
volume = {18},
number = {6},
month = jun,
pages = {330--331}
}
@string{ieeecomputer="Computer"}
@Article{kogge82,
author = "Peter M. Kogge",
title = "An Architectural Trail to Threaded-Code Systems",
journal = ieeecomputer,
year = "1982",
pages = "22--32",
month = mar,
annote = "Explains the design of (a classical
implementation of) Forth, starting with threaded
code, then adding the parameter stack, constants,
variables, control structures, dictionary, outer
interpreter and compiler."
}
@InProceedings{ertl93,
author = "M. Anton Ertl",
title = "A Portable {Forth} Engine",
booktitle = "EuroFORTH '93 conference proceedings",
year = "1993",
address = "Mari\'ansk\'e L\'azn\`e (Marienbad)",
url = "http://www.complang.tuwien.ac.at/papers/ertl93.ps.Z",
abstract = "The Forth engine discussed in this paper is written
in GNU C, which provides several extensions that are
important for Forth implementation. The indirect
threaded Forth engine is completely
machine-independent, direct threading requires a few
machine-specific lines for each machine. Using
a portable language like GNU C encourages producing
an engine with many primitives. In order to make the
development of primitives easier and less
error-prone, an automatic tool generates most of the
code for a Forth primitive from the stack effect
notation, even if the TOS is kept in a register. The
engine is combined with the parts of the system
written in Forth by loading a machine-independent
image file that contains the executable Forth code
in relocatable form."
}
@InProceedings{ertl95pldi,
author = "M. Anton Ertl",
title = "Stack Caching for Interpreters",
crossref = "sigplan95",
pages = "315--327",
url = "http://www.complang.tuwien.ac.at/papers/ertl95pldi.ps.gz",
abstract = "An interpreter can spend a significant part of its
execution time on arguments of virtual machine
instructions. This paper explores two methods to
reduce this overhead for virtual stack machines by
caching top-of-stack values in (real machine)
registers. The {\em dynamic method} is based on
having, for every possible state of the cache, one
specialized version of the whole interpreter; the
execution of an instruction usually changes the
state of the cache and the next instruction is
executed in the version corresponding to the new
state. In the {\em static method} a state machine
that keeps track of the cache state is added to the
compiler. Common instructions exist in specialized
versions for several states, but it is not necessary
to have a version of every instruction for every
cache state. Stack manipulation instructions are
optimized away."
}
@Proceedings{sigplan95,
booktitle = "SIGPLAN '95 Conference on Programming Language
Design and Implementation",
title = "SIGPLAN '95 Conference on Programming Language
Design and Implementation",
year = "1995",
key = "SIGPLAN '95"
}
@TechReport{moore&leach70,
author = "Charles H. Moore and Geoffrey C. Leach",
title = "FORTH -- A Language for Interactive Computing",
institution = "Mohasco Industries, Inc.",
year = "1970",
address = "Amsterdam, NY",
url = "http://www.dnai.com/~jfox/F70POST.ZIP"
}
@Article{moore87,
author = {Charles Moore},
title = {Forth -- eine personliche Sprache},
journal = {Vierte Dimension},
year = {1987},
volume = {3},
number = {3},
month = oct,
pages = {11--13},
note = {Translated into German by Klaus Schleisiek, the
original is probably in More on NC4000},
}
@InProceedings{kay96,
author = "Alan C. Kay",
title = "The Early History of Smalltalk",
crossref = "hopl2",
pages = "511--579",
}
@Proceedings{hopl2,
title = {History of Programming Languages},
booktitle = {History of Programming Languages},
year = 1996,
key = {HOPL-II},
publisher = {ACM Press/Addison-Wesley}
}
