川合のプログラミング言語自作のためのテキスト第三版#6

  • (by K, 2021.03.02)

(1) HL-6

  • HL-5は多少速くなったものの、C言語と比べれば圧倒的に負けたままで、ちょっとくやしくなってきました。
ページ名名前行数.exeの大きさ説明速度のめやす
a21_txt01HL-149行6.0KB初めの一歩、たった49行のシンプルすぎる言語処理系計測不能
a21_txt01_2HL-2128行6.5KB変数名は1文字じゃなくてもOK、見やすいスペースやインデントもOKに計測不能
a21_txt01_3HL-3148行7.0KB条件分岐などをサポートしてループ処理が可能に1520倍
a21_txt01_4HL-4186行7.5KBREPLの導入(これは楽しい!)1520倍
a21_txt01_5HL-5215行7.5KB少し高速化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;  // これで、icqはic[0]を指すようになる. ここから書き始める.
    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) (*icq[1] + ic);
        }
    }
    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]動作説明
    OpCpyp1p2*p1 = *p2;単純代入
    OpAddp1p2p3*p1 = *p2 + *p3;加算
    OpSubp1p2p3*p1 = *p2 - *p3;減算
    OpPrintp1print *p1;値の表示
    OpGotop1goto p1;無条件分岐(icp = p1;しているだけ)
    OpJeqp1p2p3if (*p2 == *p3) goto p1;条件分岐(jump if equal)
    OpJnep1p2p3if (*p2 != *p3) goto p1;条件分岐(jump if not equal)
    OpJltp1p2p3if (*p2 < *p3) goto p1;条件分岐(jump if less than)
    OpTime時間表示exec()を開始してからの経過時間を表示
    OpEndexec()を終了内部的にはreturnするだけ
    OpAdd1p1(*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との加算演算が内部で発生することはなくなるので、より速く実行することができます。
    • これがやむなくポインタを多用することになった理由です。
    • この表と見比べると、exec()で不可解なところはほぼないのではないかと思われます。
    • あ、そうだ。OpGotoのところで、「icp = (IntP *) icp[1];」となっていて、(IntP *)というキャストが付いている理由は、icpが IntP * 型で、icp[1]の IntP 型と型が合わなくて、そのままだと警告やエラーが出てしまうので、付けています。OpJeqとかでも同じ理由で同じキャストが付いています。
  • 次はcompile()です。
    • HL-5と比較すれば、より分かりやすいだろうと思うので、比較してみます。
      [HL-5]
          } else if (phrCmp( 2, "!!*0 = !!*1 + !!*2;", pc)) {  // 加算.
              var[tc[wpc[0]]] = var[tc[wpc[1]]] + var[tc[wpc[2]]];
      
      [HL-6]
          } else if (phrCmp( 2, "!!*0 = !!*1 + !!*2;", pc)) {  // 加算.
              putIc(OpAdd,  &var[tc[wpc[0]]], &var[tc[wpc[1]]], &var[tc[wpc[2]]], 0);
    • HL-5のときは、実際に変数の値を2つ読み取って加算して、結果を書き込めばいいだけでした。しかし今回は変数の値は読みません。書き込むこともしません。その代わり、どこを読むのか、どこに書くのかというポインタだけを確定させて計算して、それを内部コードに書き込みます。
    • C言語では、変数名を書けば変数の値を意味しますが、その前に&を付ければ、変数の値ではなくポインタを意味するようになります。だから&を付けて、それをputIc()の引数に渡しているのです。
    • これでexec()でうまく実行できるようになります。
    • compile()でちょっとわかりにくいかもしれないのは、gotoのところでしょう。
    • まずラベル定義命令が来たら、内部コードは何も出力しないで、ラベル名の変数にその時のicq値を記録しておきます。しかしvar[]はint型なので、ポインタを記憶することはできません。仕方ないので、icを引いて、その差を記憶させておきます。
    • (C言語では、2つのポインタの差は整数値になります。)
    • この整数値は、icqがic[]の何番目になっているかを表す整数値です。
    • そしてgoto命令を見つけたら、OpGoto命令を生成して第一引数にラベル名変数へのポインタを指定しておきます。
    • HL-5までだったら、ここでpc値を更新してgoto先に移動するのですが、HL-6では実際に分岐するのはexec()のときで、今は全部の命令を内部コードに変換したいだけなので、gotoが来てもpc値は更新しません。他の普通の命令と同様に、pc値はそのまま次の命令へ進みます。
    • そうして、最後まで内部コードへの変換が終わると、OpEnd命令を付加した後に、goto先の調整があります。
          icq1 = icq;
          for (icq = ic; icq < icq1; icq += 5) {  // goto先の設定.
              i = (int) icq[0];
              if (OpGoto <= i && i <= OpJgt) {
                  icq[1] = (IntP) (*icq[1] + ic);
              }
          }
    • ここでやっているのは、もしOpGotoやOpJeqのように、p1がジャンプ先の変数へのポインタになっているものがあったら、それにic値を加算して、icq値に戻して、それで上書きします。
    • ここでもやはり型が合わないので、(IntP)でキャストしてエラーにならないようにしています。

  • あとは、こまごましたことをQ&A形式で説明します。
  • [Q]なぜジャンプ先の計算を後になってやっているんですか?goto命令の時に
    putIc(OpGoto, (IntP) (var[tc[wpc[0]]] + ic), 0, 0, 0);
    • ってやっちゃえばいいじゃないですか。
    • [A]それは良い質問です。実は私もそうしたいのですが、このやり方だとこのgotoより前に定義されたラベルにしかジャンプできません。なぜならこれから定義されるラベルの変数にはvar[]に値が入っていないからです。・・・それでしょうがなく、現状のようなやり方になりました。
  • [Q]なぜ内部コードは全部長さが5なのか?単純代入なんて3つしか使っていないのだから、長さ3でいいではないか。2つ分も無駄になっている。長さをそろえずに詰め込むほうがメモリの使用効率がよくなって性能が上がるのではないか?
    • [A]実は私も最初はそのように思っていたのですが、キャッシュメモリの都合なのか、どの命令も長さを5にしてそろえたほうが1~2割くらい高速になりました。だから無駄を承知で長さ5にしています。

(4) 発展的な改造

  • HL-6では、少しでも高速化するために、+1するための専用の命令OpAdd1を付けてあります。しかしこの考え方をさらに発展させて、カウンタのインクリメントと、条件分岐を1命令にまとめたOpLop命令を付けたらどのくらい速くできるでしょうか。興味を持ったら以下のページを見てみてください。

次回に続く

こめんと欄


コメントお名前NameLink

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2021-03-05 (金) 00:26:24 (2d)