* 川合のプログラミング言語自作のためのテキスト第三版#6 -(by [[K]], 2021.01.29) ** (13) TL-6 -TL-5は多少速くなったものの、C言語と比べれば圧倒的に負けたままで、ちょっとくやしくなってきました。 |ページ名|名前|行数|.exeの大きさ|説明|速度のめやす| |[[a21_txt01]]|TL-1|RIGHT:52行|RIGHT:6.00KB|初めの一歩、たった52行のシンプルすぎる言語処理系|RIGHT:計測不能| |[[a21_txt01_2]]|TL-2|123行|RIGHT:7.00KB|変数名は1文字じゃなくてもOK、見やすいスペースやインデントもOKに|RIGHT:計測不能| |[[a21_txt01_3]]|TL-3|141行|RIGHT:7.00KB|条件分岐などをサポートしてループ処理が可能に|RIGHT:320倍| |[[a21_txt01_4]]|TL-4|180行|RIGHT:7.50KB|REPLの導入(これは楽しい!)|RIGHT:320倍| |[[a21_txt01_5]]|TL-5|208行|RIGHT:8.00KB|少し高速化|RIGHT:203倍| -ということで本気を出してどこまで速くなるか挑戦します。JITコンパイラに作り替えれば劇的に速くなるのはわかっているのですが、それはCPUに依存するようになるので後回しにして、ここではJITコンパイラやインラインアセンブラを使わない範囲での最速を目指してみたいと思います。 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> typedef unsigned char *String; // こう書くと String は unsigned char * の代用になる. int loadText(String path, String t, int siz) → TL-4と同じなので省略 int isAlphabet(unsigned char c) → TL-2と同じなので省略 int lexer(String s, String b, String t[]) → TL-2と同じなので省略 #define MAX_TC 255 // トークンコードの最大値. String ts[MAX_TC + 1]; // トークンの内容(文字列)を記憶. unsigned char tcBuf[10000]; int tcs = 0, tcb = 0; int getTc(String s) → TL-4と同じなので省略 int phrCmp_tc[100 * 20]; unsigned char phrCmp_buf[100 * 100]; int phrCmp(int pid, String phr, int tc[], int pc) → TL-5と同じなので省略 int pc, pc1, var[MAX_TC + 1], tc[1000]; // 変数(var)とトークンコード(tc). String t[1000]; // トークン(t). typedef void *PtrTyp; // こう書くと PtrTyp は void * の代わりに使えるようになる. typedef int *IntP; // こう書くと IntP は int * の代わりに使えるようになる. enum { OpCpy = 0, OpAdd, OpSub, OpPrint, OpGoto, OpJeq, OpJne, OpTime, OpEnd, OpAdd1 }; PtrTyp ic[1000]; // 内部コード. int compile(String s) { unsigned char buf[10000]; int i, tcs0 = tcs, semi = getTc(";"); PtrTyp *icp = ic, *icp1; strcpy(s + strlen(s), ";"); // 末尾に「;」を付け忘れることが多いので、付けてあげる. pc1 = lexer(s, buf, t); t[pc1] = t[pc1 + 1] = t[pc1 + 2] = t[pc1 + 3] = ""; // エラー表示用のために末尾にいくつか長さ0の文字列を登録しておく. for (pc = 0; pc < pc1; pc++) { // プログラム中で使われているすべてのトークンを調べて、tc[]の初期化. tc[pc] = getTc(t[pc]); } for (i = tcs0; i < tcs; i++) { // 定数の初期値を代入. var[i] = strtol(ts[i], 0, 0); // 定数だった場合に初期値を設定(定数ではないときは0になる). } for (pc = 0; pc < pc1; pc++) { // コンパイル開始. if (phrCmp( 1, "=", tc, pc + 1)) { // 2単語目が"=". if (phrCmp( 2, ";", tc, pc + 3)) { // 単純代入. icp[0] = (PtrTyp) OpCpy; icp[1] = &var[tc[pc]]; icp[2] = &var[tc[pc + 2]]; icp += 5; } else if (phrCmp( 12, "!!* = !!* + 1 ;", tc, pc) && tc[pc] == tc[pc + 2]) { // 高速化のために+1専用の命令を用意(せこくてすみません). icp[0] = (PtrTyp) OpAdd1; icp[1] = &var[tc[pc]]; icp += 5; } else if (phrCmp( 3, "+ !!* ;", tc, pc + 3)) { // 加算. icp[0] = (PtrTyp) OpAdd; icp[1] = &var[tc[pc]]; icp[2] = &var[tc[pc + 2]]; icp[3] = &var[tc[pc + 4]]; icp += 5; } else if (phrCmp( 4, "- !!* ;", tc, pc + 3)) { // 減算. icp[0] = (PtrTyp) OpSub; icp[1] = &var[tc[pc]]; icp[2] = &var[tc[pc + 2]]; icp[3] = &var[tc[pc + 4]]; icp += 5; } else goto err; } else if (phrCmp( 5, "print !!* ;", tc, pc)) { // print. icp[0] = (PtrTyp) OpPrint; icp[1] = &var[tc[pc + 1]]; icp += 5; } else if (phrCmp( 6, ":", tc, pc + 1)) { // ラベル定義命令. var[tc[pc]] = icp - ic; // ラベルに対応するicpを記録しておく. pc++; // 1単語だけ読み飛ばす(for文がもう1単語を読み飛ばしてくれる). continue; } else if (phrCmp( 7, "goto !!* ;", tc, pc)) { // goto. icp[0] = (PtrTyp) OpGoto; icp[1] = &var[tc[pc + 1]]; icp += 5; } else if (phrCmp( 8, "if ( !!* !!* !!* ) goto !!* ;", tc, pc)) { // if (...) goto. icp[0] = (PtrTyp) -1; icp[1] = &var[tc[pc + 7]]; icp[2] = &var[tc[pc + 2]]; icp[3] = &var[tc[pc + 4]]; if (phrCmp( 9, "!=", tc, pc + 3)) { icp[0] = (PtrTyp) OpJne; } if (phrCmp( 10, "==", tc, pc + 3)) { icp[0] = (PtrTyp) OpJeq; } if ((int)icp[0] < 0) goto err; icp += 5; } else if (phrCmp( 11, "time ;", tc, pc)) { icp[0] = (PtrTyp) OpTime; icp += 5; } else if (tc[pc] == semi) { // 何もしない. } else goto err; while (tc[pc] != semi) pc++; } icp[0] = (PtrTyp) OpEnd; icp++; icp1 = icp; for (icp = ic; icp < icp1; icp += 5) { // goto先の設定. i = (int) icp[0]; if (i == OpGoto || i == OpJne || i == OpJeq) { icp[1] = &ic[*(IntP)icp[1]]; } } return icp1 - ic; err: printf("syntax error : %s %s %s %s\n", t[pc], t[pc + 1], t[pc + 2], t[pc + 3]); return -1; } void exec() { clock_t t0 = clock(); PtrTyp *icp = ic; for (;;) { switch ((int) icp[0]) { case OpCpy: *(IntP)icp[1] = *(IntP)icp[2]; icp += 5; continue; case OpAdd: *(IntP)icp[1] = *(IntP)icp[2] + *(IntP)icp[3]; icp += 5; continue; case OpSub: *(IntP)icp[1] = *(IntP)icp[2] - *(IntP)icp[3]; icp += 5; continue; case OpPrint: printf("%d\n", *(IntP)icp[1]); icp += 5; continue; case OpGoto: icp = icp[1]; continue; case OpJeq: if (*(IntP)icp[2] == *(IntP)icp[3]) { icp = icp[1]; continue; } icp += 5; continue; case OpJne: if (*(IntP)icp[2] != *(IntP)icp[3]) { icp = icp[1]; continue; } icp += 5; continue; case OpTime: printf("time: %.3f[sec]\n", (clock() - t0) / (double) CLOCKS_PER_SEC); icp += 5; continue; case OpEnd: return; case OpAdd1: (*(IntP)icp[1])++; icp += 5; continue; } } } int run(String s) { if (compile(s) < 0) return 1; exec(); return 0; } int main(int argc, const char **argv) → TL-4と同じなので省略 -トータルの行数は305行まで一気に増えてしまいました。でもかなり高速になって、C言語との比較で11.3倍というところまで速くなりました! TL-5と比較すると18倍速です。 ** (14) TL-6の簡単な説明 -まず、高速かつ簡潔に書くためにどうしたらいいかを検討しましたが、ポインタを多用することになってしまいました。だからポインタが苦手な人には理解が難しくなってしまったと思います。どうもすみません。 -さて基本的な改造内容としては、run()をcompile()とexe()に分割しました。compile()では、トークン列に変換されているプログラムをさらにシンプルな命令列に変換します。そしてexec()でそれを高速に実行します。そういう流れです。 -では、もう少し詳しく見ていきます。 PtrTyp ic[1000]; --これは配列変数ic[]の宣言です。icはinternal-codeの略で、つまり内部コードです。関数compile()は変換したプログラムをここに格納していきます。 --この配列変数の一つ一つの要素は「PtrTyp」なのですが、これは void * の別名なので、つまりポインタです。ポインタというと身構えてしまうかもしれませんが、メモリの番地だと思ってください(コンピュータにはかなり大きな容量のメモリが付いていて、そのメモリはすべて番地という番号が付いているのです。というか番地がなかったら、どこに何を記憶させるか管理できなくなってしまいます)。 -ということで、今度は関数compile()の中身を見てみましょう。 --きっと最初にわからなくなりそうなのはここです。 PtrTyp *icp = ic, *icp1; --これは、変数icpはポインタ変数で、最初は配列変数ic[]の先頭の番地をさす、という意味です。icp1もポインタ変数です(でもどこを指し示すかはまだ決めていません)。 --そしてさらに先を読んでいくと、単純代入の処理が書いてあります。 icp[0] = (PtrTyp) OpCpy; icp[1] = &var[tc[pc]]; icp[2] = &var[tc[pc + 2]]; icp += 5; --これは、ic[]に内部コードを書き込んでいるところです。icp[0]というのは配列変数のように書いてありますが、実は配列変数ではなく、ポインタを使った代入文になっています。 --つまりicpから0番目、1番目、2番目のメモリに右辺の値を書き込んで、最後にicpをメモリ5個分だけ進めているのです(ここでは最初の要素を0番目として数えています)。 --ここで OpCpy というのは内部コードの命令番号で、ただの整数値0です。そのまま代入せずに、 (PtrTyp) をつけているのは、「これは整数値でポインタではないけど、エラーにしないで代入させてください」とコンパイラに伝えるためです。 --次の2つの代入は、読み書きしたい変数の前に & をつけることで、変数の値ではなく番地をicp[1]とicp[2]に代入させています。 --他の命令についても、似たような感じで内部コードを生成していきます。 -最後に関数exec()の中身を見てみましょう。 case OpCpy: *(IntP)icp[1] = *(IntP)icp[2]; icp += 5; continue; --この部分さえわかれば、他は全部わかると思うので、ここを中心に説明します。 --*(IntP)icp[1]というのは、「icp[1]に書かれているポインタがさしているメモリ」という意味なのですが、つまりはcompileでいうところの var[tc[pc]] のことです。 --もともとcompile()とexec()に分かれる前は、 var[tc[pc]] = var[tc[pc + 2]]; だったわけですから、それをやっているだけなのです。 --なぜポインタなんかを使うことにしたのかですが、それはexec()内で使う変数をできるだけ減らしたかったらです。単純代入の処理のために、var[]とtc[]とpcの3つの変数を参照しなければいけないのはそれなりに処理時間がかかってしまいます。それをicpだけにできれば、スピードアップが望めます。 -[Q]なぜ内部コードは全部長さが5なのか?単純代入なんて3つしか使っていないのだから、長さ3でいいではないか。そうやって詰め込むほうがメモリの使用効率がよくなって性能が上がるのではないか? --[A]実は私も最初はそのように思っていたのですが、キャッシュメモリの都合なのか、どの命令も長さを5にしてそろえたほうが1~2割くらい高速になりました。だから無駄を承知で長さ5にしています。 ** 次回に続く -次回: [[a21_txt01_7]] *こめんと欄 #comment