* 川合のプログラミング言語自作のためのテキスト第三版#6
-(by [[K]], 2021.03.02)
** (1) HL-6
-HL-5は多少速くなったものの、C言語と比べれば圧倒的に負けたままで、ちょっとくやしくなってきました。
|ページ名|名前|行数|.exeの大きさ|説明|速度のめやす|
|[[a21_txt01]]|HL-1|RIGHT:49行|RIGHT:6.0KB|初めの一歩、たった49行のシンプルすぎる言語処理系|RIGHT:計測不能|
|[[a21_txt01_2]]|HL-2|128行|RIGHT:6.5KB|変数名は1文字じゃなくてもOK、見やすいスペースやインデントもOKに|RIGHT:計測不能|
|[[a21_txt01_3]]|HL-3|148行|RIGHT:7.0KB|条件分岐などをサポートしてループ処理が可能に|RIGHT:1520倍|
|[[a21_txt01_4]]|HL-4|186行|RIGHT:7.5KB|REPLの導入（これは楽しい！）|RIGHT:1520倍|
|[[a21_txt01_5]]|HL-5|215行|RIGHT:7.5KB|少し高速化|RIGHT:260倍|
-ということで本気を出してどこまで速くなるか挑戦します。JITコンパイラに作り替えれば劇的に速くなるのはわかっているのですが、それはCPUに依存するようになるので後回しにして、ここではJITコンパイラやインラインアセンブラを使わない範囲での最速を目指してみたいと思います。
-基本方針としては、tc[]をphrCmp()で一致しているかどうか調べながら実行するのはやめて、まずもっとシンプルで高速に実行できそうなデータ列に変換し（内部コードへのコンパイル）、その後そのデータ列だけを見て高速に実行します。
#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) → HL-4と同じなので省略
///////////////////////////////////////////////////////////////////////////////
#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 var[MAX_TC + 1]; // 変数.
int getTc(String s, int len) → HL-4と同じなので省略
///////////////////////////////////////////////////////////////////////////////
int isAlphabet(unsigned char c) → HL-2と同じなので省略
int lexer(String s, int tc[]) → HL-2と同じなので省略
int tc[10000]; // トークンコード.
enum { TcSemi = 0, TcDot, TcWiCard, Tc0, Tc1, Tc2, Tc3, Tc4, Tc5, Tc6, Tc7, Tc8, TcEEq, TcNEq, TcLt, TcGe, TcLe, TcGt };
char tcInit[] = "; . !!* 0 1 2 3 4 5 6 7 8 == != < >= <= >";
///////////////////////////////////////////////////////////////////////////////
int phrCmp_tc[100 * 32], ppc1, wpc[9]; // ppc1:一致したフレーズの次のトークンをさす, wpc[]:ワイルドカードのトークンの場所をさす.
int phrCmp(int pid, String phr, int pc) → HL-5と同じなので省略
///////////////////////////////////////////////////////////////////////////////
typedef int *IntP; // こう書くと IntP は int * の代わりに使えるようになる.
enum { OpCpy = 0, OpAdd, OpSub, OpPrint, OpGoto, OpJeq, OpJne, OpJlt, OpJge, OpJle, OpJgt, OpTime, OpEnd, OpAdd1 };
IntP ic[10000], *icq; // ic[]:内部コード、icq:ic[]への書き込み用ポインタ.
void putIc(int op, IntP p1, IntP p2, IntP p3, IntP p4) // ic[]へ簡単に書き込むための便利関数.
{
icq[0] = (IntP) op;
icq[1] = p1;
icq[2] = p2;
icq[3] = p3;
icq[4] = p4;
icq += 5;
}
///////////////////////////////////////////////////////////////////////////////
int compile(String s)
{
int pc, pc1, i;
IntP *icq1;
pc1 = lexer(s, tc);
tc[pc1++] = TcSemi; // 末尾に「;」を付け忘れることが多いので、付けてあげる.
tc[pc1] = tc[pc1 + 1] = tc[pc1 + 2] = tc[pc1 + 3] = TcDot; // エラー表示用のために末尾にピリオドを登録しておく.
icq = ic;
for (pc = 0; pc < pc1; ) { // コンパイル開始.
if (phrCmp( 1, "!!*0 = !!*1;", pc)) { // 単純代入.
putIc(OpCpy, &var[tc[wpc[0]]], &var[tc[wpc[1]]], 0, 0);
} else if (phrCmp( 9, "!!*0 = !!*1 + 1;", pc) && tc[wpc[0]] == tc[wpc[1]]) { // 高速化のために+1専用の命令を用意(せこくてすみません).
putIc(OpAdd1, &var[tc[wpc[0]]], 0, 0, 0);
} else if (phrCmp( 2, "!!*0 = !!*1 + !!*2;", pc)) { // 加算.
putIc(OpAdd, &var[tc[wpc[0]]], &var[tc[wpc[1]]], &var[tc[wpc[2]]], 0);
} else if (phrCmp( 3, "!!*0 = !!*1 - !!*2;", pc)) { // 減算.
putIc(OpSub, &var[tc[wpc[0]]], &var[tc[wpc[1]]], &var[tc[wpc[2]]], 0);
} else if (phrCmp( 4, "print !!*0;", pc)) { // print.
putIc(OpPrint, &var[tc[wpc[0]]], 0, 0, 0);
} else if (phrCmp( 0, "!!*0:", pc)) { // ラベル定義命令.
var[tc[wpc[0]]] = icq - ic; // ラベルに対応するicqを記録しておく.
} else if (phrCmp( 5, "goto !!*0;", pc)) { // goto.
putIc(OpGoto, &var[tc[wpc[0]]], 0, 0, 0);
} else if (phrCmp( 6, "if (!!*0 !!*1 !!*2) goto !!*3;", pc) && TcEEq <= tc[wpc[1]] && tc[wpc[1]] <= TcLt) {
putIc(OpJeq + (tc[wpc[1]] - TcEEq), &var[tc[wpc[3]]], &var[tc[wpc[0]]], &var[tc[wpc[2]]], 0);
} else if (phrCmp( 7, "time;", pc)) {
putIc(OpTime, 0, 0, 0, 0);
} else if (phrCmp( 8, ";", pc)) {
// 何もしない.
} else
goto err;
pc = ppc1;
}
putIc(OpEnd, 0, 0, 0, 0);
icq1 = icq;
for (icq = ic; icq < icq1; icq += 5) { // goto先の設定.
i = (int) icq[0];
if (OpGoto <= i && i <= OpJgt) {
icq[1] = (IntP) &ic[*icq[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();
IntP *icp = ic; // これによりicpはic[0]を指すようになる.
for (;;) {
switch ((int) icp[0]) {
case OpCpy:
*icp[1] = *icp[2];
icp += 5;
continue;
case OpAdd:
*icp[1] = *icp[2] + *icp[3];
icp += 5;
continue;
case OpSub:
*icp[1] = *icp[2] - *icp[3];
icp += 5;
continue;
case OpPrint:
printf("%d\n", *icp[1]);
icp += 5;
continue;
case OpGoto:
icp = (IntP *) icp[1];
continue;
case OpJeq: if (*icp[2] == *icp[3]) { icp = (IntP *) icp[1]; continue; } icp += 5; continue;
case OpJne: if (*icp[2] != *icp[3]) { icp = (IntP *) icp[1]; continue; } icp += 5; continue;
case OpJlt: if (*icp[2] < *icp[3]) { icp = (IntP *) 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:
(*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) → HL-5と同じなので省略
-トータルの行数は285行まで一気に増えてしまいました。でもかなり高速になって、C言語との比較で13.2倍というところまで速くなりました！ HL-5と比較すると20倍速です。
** (2) HL-6の簡単な説明
-関数：
--void loadText(String path, String t, int siz)
---ファイルパスpathで指定されたソースファイルをtに読み込む。sizはtの最大サイズを表す（これを超える長さのファイルは途中で打ち切られる）。
--int getTc(String s, int len)
---トークン（単語）をsに渡すと、それに対応するトークンコード（整数）を返す。
--int isAlphabetOrNumber(unsigned char c)
---引数で渡された文字コードが、英数字であれば1を返す。それ以外なら0を返す。
---アンダースコアもHL-6の中ではアルファベットということにしておく。そうすることで、変数の一文字目に使えるようになる。
---この関数は以下のlexer()の下請け。
--int lexer(String s, int tc[])
---sにプログラムのソースコードを渡す。すると、tc[]にトークンコード（単語番号）に変換させられた数列が入って返される。
---より詳しい動作は、[[a21_txt01_2a]]を参照のこと。
--int phrCmp(int pid, String phr, int pc)
---tc[pc]からのトークンコード列がphrで指定されたトークン列と一致するかどうか調べる。
---pidはフレーズIDで、この番号を使ってphrCmp_tc[]のどこにphrのlexer結果をしまっておくかを決めている。
---なお、処理できるフレーズの最大長はこのプログラムの場合は31トークンである。
--void putIc(int op, IntP p1, IntP p2, IntP p3, IntP p4)
---引数で渡された内容を内部コードのic[]に書き込む関数。関数compile()を書きやすくするための便利関数。
--int compile(String s)
---与えられた文字列をプログラムだと解釈して、内部コードを生成しic[]へ出力する。
---関数run()の下請け関数。
--void exec()
---ic[]に格納された内部コードを高速に実行する。
---関数run()の下請け関数。
--int run(String s)
---言語処理の本体。HL-3までのmain()に相当。
---内部的にはcompile()してrun()しているだけ。
--int main(int argc, const char **argv)
---REPLの処理をしている。
-変数：
--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 var[]
---変数の値を記憶しておくための変数。トークンコードをそのまま変数番号に転用している。
--int tc[]
---プログラムをトークンコード列に変換したものがここに入る。
--int phrCmp_tc[]
---phrCmp()が管理している変数で、phrCmp_tc[]にはフレーズのlexer()の結果を保存する。
--int ppc1, wpc[]
---フレーズが一致した場合、ppc1に一致したフレーズの次のトークンの位置が入る。
---wpc[]にはワイルドカードで一致した位置が入る。
--IntP ic[10000], *icq
---ic[]は内部コード（internal-code）を格納しておくための変数。icqはputIc()関数が次にicのどこに書き込むのかを覚えておくための変数。
----
-まず、高速かつ簡潔に書くためにどうしたらいいかを検討しましたが、ポインタを多用することになってしまいました。だからポインタが苦手な人にはHL-6の理解が難しくなってしまったと思います。どうもすみません。
** (3) 内部コードに関する詳しい説明（compile(), exec()など）
-まず最初に、exec()から説明したいと思います。exec()の基本構造は、 for (;;) { ... } ループの中にswitch...case文が一つ入っているだけです。
-内部コードは、以下のような仕様にしています。
|icp[0]|icp[1]|icp[2]|icp[3]|icp[4]|動作|説明|
|OpCpy |p1|p2| | |*p1 = *p2;|単純代入|
|OpAdd |p1|p2|p3| |*p1 = *p2 + *p3;|加算|
|OpSub |p1|p2|p3| |*p1 = *p2 - *p3;|減算|
|OpPrint|p1| | | |print *p1;|値の表示|
|OpGoto |p1| | | |goto p1;|無条件分岐（icp = p1;しているだけ）|
|OpJeq |p1|p2|p3| |if (*p2 == *p3) goto p1;|条件分岐(jump if equal)|
|OpJne |p1|p2|p3| |if (*p2 != *p3) goto p1;|条件分岐(jump if not equal)|
|OpJlt |p1|p2|p3| |if (*p2 < *p3) goto p1;|条件分岐(jump if less than)|
|OpTime | | | | |時間表示|exec()を開始してからの経過時間を表示|
|OpEnd | | | | |exec()を終了|内部的にはreturnするだけ|
|OpAdd1 |p1| | | |(*p1)++;|変数に1を加算。OpAddで1を加算するよりも少し速い|
--表の中のp1～p3は、ポインタです。しかもgotoや条件分岐のp1以外のpは、すべてvar[]を指し示すようになっています。
--もしポインタを扱うのが嫌なら、p1～p3ではなくて、i1～i3という整数値にして、 var[i1] = var[i2] + var[i3]; のようにすることもできます。しかしこうするとOpAddの実行にあたって、var値とi値の加算演算をしながら実行されるので、実行速度が落ちてしまいます。しかし *p1 = *p2 + *p3; にすれば、varとの加算演算が内部で発生することはなくなるので、より速く実行することができます。
--これがやむなくポインタを多用することになった理由です。
-では、もう少し詳しく見ていきます。
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]")
