- 追加された行はこの色です。
- 削除された行はこの色です。
* 川合のプログラミング言語自作のためのテキスト第三版#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|125行|RIGHT:6.50KB|変数名は1文字じゃなくてもOK、見やすいスペースやインデントもOKに|RIGHT:計測不能|
|[[a21_txt01_3]]|TL-3|143行|RIGHT:7.00KB|条件分岐などをサポートしてループ処理が可能に|RIGHT:1090倍|
|[[a21_txt01_4]]|TL-4|181行|RIGHT:7.50KB|REPLの導入（これは楽しい！）|RIGHT:1090倍|
|[[a21_txt01_5]]|TL-5|203行|RIGHT:7.50KB|少し高速化|RIGHT:192倍|
-ということで本気を出してどこまで速くなるか挑戦します。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と同じなので省略
#define MAX_TC 255 // トークンコードの最大値.
String ts[MAX_TC + 1]; // トークンの内容(文字列)を記憶.
int tl[MAX_TC + 1]; // トークンの長さ.
unsigned char tcBuf[(MAX_TC + 1) * 10]; // トークン1つ当たり平均10バイトを想定.
int tcs = 0, tcb = 0;
int getTc(String s, int len) → TL-4と同じなので省略
int lexer(String s, int tc[]) → TL-2と同じなので省略
int phrCmp_tc[100 * 20], phrCmp_wildCard = -1;
int phrCmp(int pid, String phr, int tc[], int pc) → TL-5と同じなので省略
int pc, pc1, var[MAX_TC + 1], tc[1000]; // 変数(var)とトークンコード(tc).
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], *icq; // ic[]:内部コード、icq:ic[]への書き込み用ポインタ.
void putIc3(int op, PtrTyp p0, PtrTyp p1, PtrTyp p2) // ic[]へ簡単に書き込むための便利関数. パラメータ3個用.
{
icq[0] = (PtrTyp) op;
icq[1] = p0;
icq[2] = p1;
icq[3] = p2;
icq += 5;
}
int compile(String s)
{
int pc, pc1, i, tcs0 = tcs, semi = getTc(";", 1);
PtrTyp *icp1;
pc1 = lexer(s, tc);
tc[pc1++] = semi; // 末尾に「;」を付け忘れることが多いので、付けてあげる.
tc[pc1] = tc[pc1 + 1] = tc[pc1 + 2] = tc[pc1 + 3] = getTc(" ", 1); // エラー表示用のために末尾にスペースを登録しておく.
for (i = tcs0; i < tcs; i++) { // 定数の初期値を代入.
var[i] = strtol(ts[i], 0, 0); // 定数だった場合に初期値を設定（定数ではないときは0になる）.
}
icq = ic;
for (pc = 0; pc < pc1; pc++) { // コンパイル開始.
if (phrCmp( 1, "=", tc, pc + 1)) { // 2単語目が"=".
if (phrCmp( 2, ";", tc, pc + 3)) { // 単純代入.
putIc3(OpCpy, &var[tc[pc]], &var[tc[pc + 2]], 0);
} else if (phrCmp( 12, "!!* = !!* + 1 ;", tc, pc) && tc[pc] == tc[pc + 2]) { // 高速化のために+1専用の命令を用意(せこくてすみません).
putIc3(OpAdd1, &var[tc[pc]], 0, 0);
} else if (phrCmp( 3, "+ !!* ;", tc, pc + 3)) { // 加算.
putIc3(OpAdd, &var[tc[pc]], &var[tc[pc + 2]], &var[tc[pc + 4]]);
} else if (phrCmp( 4, "- !!* ;", tc, pc + 3)) { // 減算.
putIc3(OpSub, &var[tc[pc]], &var[tc[pc + 2]], &var[tc[pc + 4]]);
} else
goto err;
} else if (phrCmp( 5, "print !!* ;", tc, pc)) { // print.
putIc3(OpPrint, &var[tc[pc + 1]], 0, 0);
} else if (phrCmp( 6, ":", tc, pc + 1)) { // ラベル定義命令.
var[tc[pc]] = icp - ic; // ラベルに対応するicpを記録しておく.
var[tc[pc]] = icp - ic; // ラベルに対応するicqを記録しておく.
pc++; // 1単語だけ読み飛ばす(for文がもう1単語を読み飛ばしてくれる).
continue;
} else if (phrCmp( 7, "goto !!* ;", tc, pc)) { // goto.
putIc3(OpGoto, &var[tc[pc + 1]], 0, 0);
} else if (phrCmp( 8, "if ( !!* !!* !!* ) goto !!* ;", tc, pc)) { // if (...) goto.
i = -1;
if (phrCmp( 9, "!=", tc, pc + 3)) { i = OpJne; }
if (phrCmp( 10, "==", tc, pc + 3)) { i = OpJeq; }
if (i < 0) goto err;
putIc3(i, &var[tc[pc + 7]], &var[tc[pc + 2]], &var[tc[pc + 4]]);
} else if (phrCmp( 11, "time ;", tc, pc)) {
putIc3(OpTime, 0, 0, 0);
} else if (tc[pc] == semi) {
// 何もしない.
} else
goto err;
while (tc[pc] != semi)
pc++;
}
putIc3(OpEnd, 0, 0, 0);
icq1 = icq;
for (icq = ic; icq < icq1; icq += 5) { // goto先の設定.
i = (int) icp[0];
if (i == OpGoto || i == OpJne || i == OpJeq) {
icp[1] = &ic[*(IntP)icp[1]];
}
}
return icq1 - ic;
err:
printf("syntax error : %s %s %s %s\n", ts[tc[pc]], ts[tc[pc + 1]], ts[tc[pc + 2]], ts[tc[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と同じなので省略
-トータルの行数は287行まで一気に増えてしまいました。でもかなり高速になって、C言語との比較で11.3倍というところまで速くなりました！ TL-5と比較すると17倍速です。
** (14) TL-6の簡単な説明
-関数：
--void loadText(String path, String t, int siz)
---ファイルパスpathで指定されたソースファイルをtに読み込む。sizはtの最大サイズを表す（これを超える長さのファイルは途中で打ち切られる）。
--int isAlphabet(unsigned char c)
---引数で渡された文字コードが、アルファベットであれば1を返す。アルファベットでなければ0を返す。
---アンダースコアもTL-3の中ではアルファベットということにしておく。そうすることで、変数の一文字目に使えるようになる。
--int getTc(String s, int len)
---トークン（単語）をsに渡すと、それに対応するトークンコード（整数）を返す。
--int lexer(String s, int tc[])
---sにプログラムのソースコードを渡す。すると、tc[]にトークンコード（単語番号）に変換させられた数列が入って返される。
---より詳しい動作は、[[a21_txt01_2a]]を参照のこと。
-- int phrCmp(int pid, String phr, int tc[], int pc)
---tc[pc]からのトークンコード列がphrで指定されたトークン列と一致するかどうか調べる。
---pidはフレーズIDで、この番号を使ってphrCmp_tc[]のどこにphrのlexer結果をしまっておくかを決めている。
---なお、処理できるフレーズの最大長はこのプログラムの場合は19トークンである。
--void putIc3(int op, PtrTyp p0, PtrTyp p1, PtrTyp p2)
---op, p0～p2をic[]に書き込む。
--int compile(String s)
---文字列sをプログラムだと解釈して、内部コードに変換しic[]に出力する。
---この関数は出力したプログラムの長さを返す。エラー時は負の値を返す。
--void exec()
---ic[]に格納された内部コードを高速に実行する。
--int run(String s)
---文字列sをプログラムだと解釈して実行する。
--int main(int argc, const char **argv)
---言語処理の本体。
-変数：
--String ts[]
---getTc()が管理している配列変数で、トークンコードからトークン文字列を得るために使う。
--int tl[]
---getTc()が管理している配列変数で、トークンコードからトークン文字列の長さを得るために使う。
--unsigned char tcBuf[]
---getTc()が管理している変数で、トークン文字列の実体を保存しておくための場所。
--int tcs, tcb
---どちらもgetTc()が管理している変数で、tcsは今までに発行したトークンコードの個数（0～tcs-1が発行済み）。
---tcbはtcBuf[]の未使用領域を指している。
---もしtcBuf[]やtcbの役割がピンとこない場合は、[[a21_txt01_2b]]を参照。
--int phrCmp_tc[], phrCmp_wildCard
---どちらもphrCmp()が管理している変数で、phrCmp_tc[]にはフレーズのlexer()の結果を保存する。
---phrCmp_wildCardには、"!!*"のトークンコードを入れている。
--int var[], tc[]
---var[]は変数の値を保持するための変数。tc[]はプログラムのトークン列をトークンコードに変換して並べたもの。
--PtrTyp ic[]
---関数compile()の出力した内部コードが入る変数。
----
-まず、高速かつ簡潔に書くためにどうしたらいいかを検討しましたが、ポインタを多用することになってしまいました。だからポインタが苦手な人には理解が難しくなってしまったと思います。どうもすみません。
-さて基本的な改造内容としては、run()をcompile()とexe()に分割しました。compile()では、トークン列に変換されているプログラムをさらにシンプルな命令列に変換します。そしてexec()でそれを高速に実行します。そういう流れです。
-では、もう少し詳しく見ていきます。
PtrTyp ic[1000];
--これは配列変数ic[]の宣言です。icはinternal-codeの略で、つまり内部コードです。関数compile()は変換したプログラムをここに格納していきます。
--この配列変数の一つ一つの要素は「PtrTyp」なのですが、これは void * の別名なので、つまりポインタです。ポインタというと身構えてしまうかもしれませんが、メモリの番地だと思ってください（コンピュータにはかなり大きな容量のメモリが付いていて、そのメモリはすべて番地という番号が付いているのです。というか番地がなかったら、どこに何を記憶させるか管理できなくなってしまいます）。
-ということで、今度は関数compile()の中身を見てみましょう。
--きっと最初にわからなくなりそうなのはここです。
icq = ic;
--これは、変数icqが最初は配列変数ic[]の先頭の番地をさす、という意味です。
--そしてさらに先を読んでいくと、単純代入の処理が書いてあります。
putIc3(OpCpy, &var[tc[pc]], &var[tc[pc + 2]], 0);
--これはつまり、以下の記述に相当します。
icq[0] = (PtrTyp) OpCpy;
icq[1] = &var[tc[pc]];
icq[2] = &var[tc[pc + 2]];
icq[3] = 0; // これに意味はない.
icq += 5;
--これは、ic[]に内部コードを書き込んでいるところです。icq[0]というのは配列変数のように書いてありますが、実は配列変数ではなく、ポインタを使った代入文になっています。
--つまりicqから0番目、1番目、2番目のメモリに右辺の値を書き込んで、最後にicpをメモリ5個分だけ進めているのです（ここでは最初の要素を0番目として数えています）。
--ここで OpCpy というのは内部コードの命令番号で、ただの整数値0です。そのまま代入せずに、 (PtrTyp) をつけているのは、「これは整数値でポインタではないけど、エラーにしないで代入させてください」とコンパイラに伝えるためです。こうするとコンパイラは「自分にはよくわからないけど、プログラマはちゃんとわかったうえでやっているのだろう」ということで、余計なことは何もせずに、そのまま代入してくれます。
--次の2つの代入は、読み書きしたい変数の前に & をつけることで、変数の値ではなく番地をicq[1]とicq[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にしています。
----
-TL-6では、少しでも高速化するために、+1するための専用の命令OpAdd1を付けてあります。しかしこの考え方をさらに発展させて、カウンタのインクリメントと、条件分岐を1命令にまとめたOpLop命令を付けたらどのくらい速くできるでしょうか。興味を持ったら以下のページを見てみてください。
--[[a21_txt01_6a]]
** 次回に続く
-次回: [[a21_txt01_7]]
*こめんと欄
#comment
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
