- 追加された行はこの色です。
- 削除された行はこの色です。
* 川合のプログラミング言語自作のためのテキスト#0008
-(by [[K]], 2019.05.07)
** (15) TJ-21
-TJ-20ではC言語の速さに到達できなかったので、さらにもう一つの高速化テクニックを紹介します。
-TJ-20では、機械語はこんな感じになっています。
-TJ-20とC言語では、機械語はこんな感じになっています(読みやすさのためにアセンブラで書いて代用しています)。
// TJ-20.
MOV EDX,0
cont:
MOV EAX,EDX
MOV ECX,
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命令を兼ねられるようになるのです。
-TJ-03が高評価なので、予定を変更してちょっとした発展版を作ってみようと思います。
-TJ-03はTJ-02と比較すると圧倒的に高速でしたが、しかしまだ簡単に速くする余地が残っています。それをここで紹介したいと思います。
-C言語には「レジスタ変数」という機能があります。しかし最近のCコンパイラはこの機能を使わなくても最適化によって自動的に同等の速さが出ます。だから自作言語でも、レジスタ変数をサポートすれば、C言語に負けない速さがでる・・・かもしれないのです。
-どうですか?面白そうじゃないですか?ということでやってみましょう。
→ 最初から以下の #define ECX 1 までは、TJ-03と同じなので省略
#define ECX 1
#define EDX 2
#define REGVAR 'i' // レジスタ変数の変数名(固定).
-ということでなぜC言語がTJ-20よりも高速になっているのかはこれで分かりました。
-ではTJ-21ではどうしたらいいでしょうか。C言語みたいに「書き換えができるケースは自動的に書き換えを実施する」・・・のをここでやるのはちょっと面倒なので、新規にdo{~}while構文を追加して、この構文を使えばC言語と同じくらいに高速になるよー、ということにします。
int isNumber(unsigned char c) → TL-02と同じなので省略.
→この部分はTJ-20と同じなので省略
void getNumberSub()
int main(int argc, const char **argv)
{
unsigned char *p = &txt[pc], *q;
put32(strtol(p, (char **) &q, 0));
pc += q - p;
→この部分は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と同じなので省略
}
void getNumber(int reg) // 定数は2桁以上でもOK. レジスタに値をセットするための命令群を出力する.
{
unsigned char c = txt[pc], *p, *q;
if (isNumber(c) != 0) { // 数字.
code[qc++] = 0xb8 + reg; // MOV reg,const.
getNumberSub();
return;
}
pc++; // 1文字の変数.
if (c == REGVAR) {
if (reg != EDX) {
code[qc++] = 0x89; // MOV reg,EDX.
code[qc++] = reg + EDX * 8 + 0xc0;
}
} else {
code[qc++] = 0x8b; // MOV reg,[const].
code[qc++] = reg * 8 + 0x05;
put32((int) &var[c]);
}
}
void sub_print(int i) → TJ-03と同じなので省略
void sub_time() → TJ-03と同じなので省略
int main(int argc, const char **argv)
{
→ ここの部分はTJ-03と同じなので省略.
for (;;) {
pc0 = pc;
if (txt[pc] == 0) // ファイル終端.
break;
if (txt[pc] == REGVAR && txt[pc + 1] == '=') { // レジスタ変数への代入.
pc += 2;
getNumber(EDX);
if (txt[pc] == ';') {
} else if (txt[pc] == '+') { // 加算.
pc++;
if (isNumber(txt[pc]) != 0) {
code[qc++] = 0x81;
code[qc++] = 0xc0 + EDX;
getNumberSub();
} else
goto err; // 変数の加算はまだ作ってない.
} else
goto err; // 加算以外はまだ作ってない.
continue;
}
if (txt[pc] == '\n' || txt[pc] == ' ' || txt[pc] == '\t' || txt[pc] == ';') { // 空行など.
pc++;
} else if (txt[pc + 1] == '=') { // 2文字目が"=".
→ ここ以降はTJ-03と同じなので省略.
-結局どこを改造したのかというと、getNumber()を改造したことと、レジスタ変数への代入があった場合に、特別な処理をするようにしたことだけです。
-このTJ-20では、変数iが自動でレジスタ変数として扱われます。内部的にはEDXレジスタに割り当てられます。
-これにより、処理が以下のように単純化されます。
|処理|普通の変数の場合|レジスタ変数の場合|
|i=3;|[2命令] MOV(EAX,3); MOV([const],EAX);|[1命令] MOV(EDX,3);|
|i=a;|[2命令] MOV(EAX,[const]); MOV([const],EAX);|[1命令] MOV(EDX,[const]);|
|i=i;|[2命令] MOV(EAX,[const]); MOV([const],EAX);|[0命令]|
|i=i+5;|[4命令] MOV(EAX,[const]); MOV(ECX,5); ADD(EAX,ECX); MOV([const],EAX); |[1命令] ADD(EDX,5);|
-ということで、おそらくTJ-03と比較して2倍くらい速くなったのではないかと思われます。
-でもC言語の速さはこんなものじゃありません。ということで、次回ではもっと速くする方法を紹介しますね。
-書き足したのは、 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ライブラリを利用した話を予定していますが、準備ができるのは当分先です。)
*こめんと欄
#comment