川合のプログラミング言語自作のためのテキスト第三版#6
(13) TL-6
- TL-5は多少速くなったものの、C言語と比べれば圧倒的に負けたままで、ちょっとくやしくなってきました。
| ページ名 | 名前 | 行数 | .exeの大きさ | 説明 | 速度のめやす |
| a21_txt01 | TL-1 | 52行 | 6.00KB | 初めの一歩、たった52行のシンプルすぎる言語処理系 | 計測不能 |
| a21_txt01_2 | TL-2 | 123行 | 7.00KB | 変数名は1文字じゃなくてもOK、見やすいスペースやインデントもOKに | 計測不能 |
| a21_txt01_3 | TL-3 | 141行 | 7.00KB | 条件分岐などをサポートしてループ処理が可能に | 320倍 |
| a21_txt01_4 | TL-4 | 180行 | 7.50KB | REPLの導入（これは楽しい！） | 320倍 |
| a21_txt01_5 | TL-5 | 208行 | 8.00KB | 少し高速化 | 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()の中身を見てみましょう。
- TL-6では、少しで高速化するために、+1するための専用の命令OpAdd1を付けてあります。しかしこの考え方をさらに発展させて、カウンタのインクリメントと、条件分岐を1命令にまとめたOpLop命令を付けたらどのくらい速くできるでしょうか。興味を持ったら以下のページを見てみてください。
次回に続く
こめんと欄
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
