間接スレッディングは速い
Speed of various interpreter dispatch techniques V2
http://www.complang.tuwien.ac.at/forth/threading/
で配布されている簡易ベンチマークをgcc-4.8.4でコンパイルすると、最適化が効き過ぎてsubroutine-threadingのコードが殆ど削除されていた。
そこで、subroutineだけx86アセンブリで書き直して自分のマシン(AMD FX-8350)で走らせると、コンパイラの最適化オプションを(gcc -O3)最高にした場合、subroutine-threadingがdirect-threadingどころかindirect-threadingにまで負けてしまう。
仮想マシン命令一つを発行するのに、subroutineは4.4クロック、directとindirectは3.6クロックかかっている。
インタプリタを必要としないsubroutineが負ける理由は、FX-8350の場合については
(a)ジャンプ命令の処理能力(の低さ)
(b)アウト・オブ・オーダ実行
だと私は考える。
FX-8350の場合、ジャンプ命令の類が実行されると、命令フェッチが1クロック停止する。
結果、FX-8350ではジャンプ命令は2クロックに一回しか処理できない。
ジャンプが無い場合、1クロックで4命令を読み込む能力がFX-8350にはあり、データ読み込みなら1クロックで二回出来る。
勿論、データ読み込みの遅延は一回4クロックなので、二回参照を辿るindirectでは仮想マシン命令を一回処理するのに8クロックの遅延が生じる。
しかしそこは、最近のプロセッサの並列処理能力が何とかしてくれる。
命令の先読み予測が上手く行っている限り、次に処理する仮想マシン命令も並行して処理することで、遅延の影響が無くなる。
結果、二回データ参照を辿るより、一回だけ命令のジャンプ先を辿る方が、時間がかかる。
データ参照回数が異なるdirectとindirectで速度に違いが無いのは、ジャンプ命令がボトルネックとなっている証拠だ。
ましてやsubroutineの場合、仮想マシン命令一回につきcall-retのペアが使われ、ジャンプが二回生じる。
directやindirectの場合、仮想マシン命令の最後に間接ジャンプが一回だけ。
これが、indirectがsubroutineより速くなる理由だと私は考える。
forthでは仮想マシン命令を並べたthreaded codeのサブルーチンも仮想マシン命令と同様に扱う。
このため、直接呼び出す仮想マシン命令が機械語を並べたものに限られるdirect-threadingでは、機械語のcall-retを模倣する仮想マシン命令を使ったり、indirect-threadingのコードフィールド部に機械語を埋め込んだり、何らかの無理をしなければ、threaded codeのサブルーチンを扱えない。
単純化のため、上記のベンチマークではthreaded codeのサブルーチン呼び出しについては計測していない。
仮にこれも計測に含めれば、無理をする分だけ、direct-threadingは遅くなるはずだ。
FX-8350に限らず、データ読み出しパイプラインが多重化されているものは、命令のジャンプ先を辿るよりデータ参照を辿る方が速い。
これは、パソコン用プロセッサの殆どに当てはまる。
そのようなプロセッサでは、間接スレッディングより速い処理系を書くのは簡単ではない。
http://www.complang.tuwien.ac.at/forth/threading/
で配布されている簡易ベンチマークをgcc-4.8.4でコンパイルすると、最適化が効き過ぎてsubroutine-threadingのコードが殆ど削除されていた。
そこで、subroutineだけx86アセンブリで書き直して自分のマシン(AMD FX-8350)で走らせると、コンパイラの最適化オプションを(gcc -O3)最高にした場合、subroutine-threadingがdirect-threadingどころかindirect-threadingにまで負けてしまう。
仮想マシン命令一つを発行するのに、subroutineは4.4クロック、directとindirectは3.6クロックかかっている。
インタプリタを必要としないsubroutineが負ける理由は、FX-8350の場合については
(a)ジャンプ命令の処理能力(の低さ)
(b)アウト・オブ・オーダ実行
だと私は考える。
FX-8350の場合、ジャンプ命令の類が実行されると、命令フェッチが1クロック停止する。
結果、FX-8350ではジャンプ命令は2クロックに一回しか処理できない。
ジャンプが無い場合、1クロックで4命令を読み込む能力がFX-8350にはあり、データ読み込みなら1クロックで二回出来る。
勿論、データ読み込みの遅延は一回4クロックなので、二回参照を辿るindirectでは仮想マシン命令を一回処理するのに8クロックの遅延が生じる。
しかしそこは、最近のプロセッサの並列処理能力が何とかしてくれる。
命令の先読み予測が上手く行っている限り、次に処理する仮想マシン命令も並行して処理することで、遅延の影響が無くなる。
結果、二回データ参照を辿るより、一回だけ命令のジャンプ先を辿る方が、時間がかかる。
データ参照回数が異なるdirectとindirectで速度に違いが無いのは、ジャンプ命令がボトルネックとなっている証拠だ。
ましてやsubroutineの場合、仮想マシン命令一回につきcall-retのペアが使われ、ジャンプが二回生じる。
directやindirectの場合、仮想マシン命令の最後に間接ジャンプが一回だけ。
これが、indirectがsubroutineより速くなる理由だと私は考える。
forthでは仮想マシン命令を並べたthreaded codeのサブルーチンも仮想マシン命令と同様に扱う。
このため、直接呼び出す仮想マシン命令が機械語を並べたものに限られるdirect-threadingでは、機械語のcall-retを模倣する仮想マシン命令を使ったり、indirect-threadingのコードフィールド部に機械語を埋め込んだり、何らかの無理をしなければ、threaded codeのサブルーチンを扱えない。
単純化のため、上記のベンチマークではthreaded codeのサブルーチン呼び出しについては計測していない。
仮にこれも計測に含めれば、無理をする分だけ、direct-threadingは遅くなるはずだ。
FX-8350に限らず、データ読み出しパイプラインが多重化されているものは、命令のジャンプ先を辿るよりデータ参照を辿る方が速い。
これは、パソコン用プロセッサの殆どに当てはまる。
そのようなプロセッサでは、間接スレッディングより速い処理系を書くのは簡単ではない。
