川合のプログラミング言語自作のためのテキスト#0008
(15) TJ-21
- TJ-20ではC言語の速さに到達できなかったので、さらにもう一つの高速化テクニックを紹介します。
- TJ-20とC言語では、機械語はこんな感じになっています（読みやすさのためにアセンブラで書いて代用しています）。
// TJ-20.
MOV EDX,0
cont:
MOV EAX,EDX
MOV ECX,100000000
CMP EAX,ECX
JGE break;
ADD EDX,1
JMP cont
break:
（print i;の機械語）
（time;の機械語）
// C言語の場合.
MOV EDX,0
cont:
ADD EDX,1
CMP EDX,100000000
JL cont
break:
（print i;の機械語）
（time;の機械語）
- つまり、TJ-20のレジスタ変数の導入によってi=i+1;が4命令から1命令になったのは快挙だったのですが、それでもループ処理はまだ6命令もあり、Cコンパイラはこれを3命令にまで減らしているのです。だからむやみに速いのです。
- TJ-03ではループ処理は9命令でした。それがTJ-20では6命令になりました。そしてTJ-21ではこれをC言語と同じ3命令にしようと考えているのです。
- まずC言語が内部で何をやっているのかを説明しましょう。C言語はwhileループを以下のdo～whileループに書き換えます。
- [書き換え前] i=0; while(i<100000000){ i=i+1; }
- [書き換え後] i=0; do{ i=i+1; }while(i<100000000);
- まずこの書き換えによって処理内容に違いがないことを確認してください。
- さてではなぜこの書き換えをするかですが、do～whileにするとJMP命令を省略できるようになるからです。より詳しく言うと、比較の後の条件ジャンプがループ先頭へ戻るためのJMP命令を兼ねられるようになるのです。
- ということでなぜC言語がTJ-20よりも高速になっているのかはこれで分かりました。
- ではTJ-21ではどうしたらいいでしょうか。C言語みたいに「書き換えができるケースは自動的に書き換えを実施する」・・・のをここでやるのはちょっと面倒なので、新規にdo{～}while構文を追加して、この構文を使えばC言語と同じくらいに高速になるよー、ということにします。
→この部分はTJ-20と同じなので省略
int main(int argc, const char **argv)
{
→この部分はTJ-20と同じなので省略
for (;;) {
pc0 = pc;
if (txt[pc] == 0) // ファイル終端.
break;
if (txt[pc] == REGVAR && txt[pc + 1] == '=') { // レジスタ変数への代入.
→この部分はTJ-20と同じなので省略
}
if (txt[pc] == '\n' || txt[pc] == ' ' || txt[pc] == '\t' || txt[pc] == ';') { // 空行など.
pc++;
} else if (txt[pc + 1] == '=') { // 2文字目が"=".
→この部分はTJ-20と同じなので省略
} else if (txt[pc] == 'p' && txt[pc + 1] == 'r' && txt[pc + 5] == ' ') { // 最初の2文字しか調べてない(手抜き).
→この部分はTJ-20と同じなので省略
} else if (txt[pc] == 'd' && txt[pc + 1] == 'o' && txt[pc + 2] == '{') {
wqc = qc;
pc += 3;
} else if (txt[pc] == '}' && txt[pc + 1] == 'w') { // }while ?<?;
pc += 7;
if (txt[pc] == REGVAR && isNumber(txt[pc + 2]) != 0) {
pc += 2;
code[qc++] = 0x81; // CMP EDX,const.
code[qc++] = 0xf8 + EDX;
getNumberSub();
} else {
getNumber(EAX); // 1文字の変数名.
pc++;
getNumber(ECX);
code[qc++] = 0x39; // CMP EAX,ECX.
code[qc++] = 0xc8;
}
code[qc++] = 0x0f; // JGE ????
code[qc++] = 0x8c;
put32(wqc - (qc + 4));
} else if (txt[pc] == 'w' && txt[pc + 1] == 'h' && txt[pc + 5] == ' ' && txt[pc + 7] == '<') { // 最初の2文字しか調べてない(手抜き).
→この部分はTJ-20と同じなので省略
} else if (txt[pc] == '}') {
→この部分はTJ-20と同じなので省略
} else if (txt[pc] == 't' && txt[pc + 1] == 'i') { // 最初の2文字しか調べてない(手抜き).
→この部分はTJ-20と同じなので省略
} else
goto err;
}
→この部分はTJ-20と同じなので省略
}
- 書き足したのは、 do{ と }w だけです。ここで一つだけ注意点があって、 }w を追加するのはwhileループの } よりは前にする必要があります。そうでなければ }w と書いても } のほうに引っかかってしまい、うまく処理できません。
- 実行するプログラムの方はこんな感じになります。
i=0;
do{
i=i+1;
}while i<100000000;
print i;
time;
(16) 速度比較
- この単純1億回ループについて、当方の環境での速度を記録しておきます。
| TL-3 | 38.44秒 | | | TJ-02 | 9.824秒 | | | TJ-03 | 0.169秒 | | | TJ-20 | 0.061秒 | | | TJ-21 | 0.032秒 | do{～}whileを使用 | | gcc | 0.029秒 | 参考用, 最適化レベルは最強 |
- TJ-21はまだgccには追い付いていませんが、それはループの処理が負けているからではなく、JITコンパイルに時間がかかっているためです。まずファイルをオープンしてそれをメモリに読み込んだうえで、機械語に翻訳しなければいけないのです。そのために0.003秒ほど要しているわけです。
- これは遅いと思うかもしれませんが、gccはwhileを使った1億回ループのC言語のプログラムのコンパイル＆リンクに少なくとも0.7秒くらいはかかっているので、はっきり言ってこれは圧倒的に高速なのです。
- ということでループ回数を増やしたりしてより重い処理内容にすれば、このJITコンパイルに要する時間はもうほとんど見えなくなって、Cコンパイラと同等の速度でプログラムが実行されることになります。
- TJ-21はもうコンパイルなしでコンパイラ並みの速度が出るわけです。これって落ち着いて考えると相当にすごいことです。コンパイルして実行ファイルにしてしまうと、OSによって実行ファイルはまちまちになってしまいますが、ソースコードなら同じにできます。またJITコンパイラなら機械語を生成するときに、CPUに応じてより適切な機械語を生成するように工夫することも可能で、だから共通の機械語を生成しているCコンパイラよりも高速な実行結果になる可能性すらあります。
- ここまでいろいろと妥協はしてきましたが、しかしそれでもTJ-21がたったの212行のプログラムであるというのも事実です。標準関数以外のライブラリを使わなくても、たった212行のプログラムで、gccで最強レベルの最適化の結果に負けないほどの、プログラミング言語が作れるということなのです。JITコンパイラというのはそういう技術なのです。
次回に続く
- 次回: （この先にJCKライブラリを利用した話を予定していますが、準備ができるのは当分先です。）
こめんと欄
|
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
