a21_txt01_6a

a21_txt01_6の補足説明#1

• (by K, 2021.03.08)

(0)

• これは「川合のプログラミング言語自作のためのテキスト第三版#6」に対する補足説明のページです。

(1) ループ命令の追加でどこまで速くなるか？

• HL-6は結構高速で、10億回ループの速度ではgcc比で13.2倍まで来ましたが、もっと速くできないでしょうか？そのためにはどうしたらいいでしょうか？
• x86の機械語にはLOOP命令というのがあります。LOOP命令は、ECXレジスタの値を1減じて、もし0でなければ指定したアドレスに分岐することができます。別にこのことそのものはすごくないのですが、それが1命令できるというのがポイントです。
• では、HL-6に似たような命令を追加したとしたらどうでしょうか。しかし完全には真似せずに、1加算して、所定の値と比較して、もし小さかったら分岐するということにします。これは私の観察では、ほとんどのループではループカウンタを減少ではなく増加させているからです。

• 変更箇所を中心に書きます。

enum { OpCpy = 0, OpAdd, OpSub, OpPrint, OpGoto, OpJeq, OpJne, OpJlt, OpJge, OpJle, OpJgt, OpLop, OpTime, OpEnd, OpAdd1 }; // OpLopをOpJgtの直後に追加.

int compile(String s)
{
    (中略)
    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(10, "!!*0 = !!*1 + 1; if (!!*2 < !!*3) goto !!*4;", pc) && tc[wpc[0]] == tc[wpc[1]] && tc[wpc[0]] == tc[wpc[2]]) {
+           putIc(OpLop, &var[tc[wpc[4]]], &var[tc[wpc[0]]], &var[tc[wpc[3]]], 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);
    (中略)
    for (icq = ic; icq < icq1; icq += 5) {  // goto先の設定.
        i = (int) icq[0];
!       if (OpGoto <= i && i <= OpLop) { // OpJgtをOpLopに変更.
            icq[1] = (IntP) (*icq[1] + ic);
        }
    }
    (中略)
}

void exec()
{
    clock_t t0 = clock();
    IntP *icp = ic;
+   int i;
    for (;;) {
        switch ((int) icp[0]) {
        (中略)
+       case OpLop:
+           i = *icp[2];
+           i++;
+           *icp[2] = i;
+           if (i < *icp[3]) {
+               icp = (IntP *) icp[1];
+               continue;
+           }
+           icp += 5;
+           continue;
        }
    }
}

• プログラムでは、LOOP命令を使うための新しい構文は用意しないで、単に「i=i+1; if (i ＜ 〇〇) goto ××;」みたいなのが出現したら適用するようにしています。
• このため、HL-3用のサンプルプログラムは無修正でも適用されるようになります。
• さてその速さは・・・gcc比で5.5倍まで高速化できました！

(2) なぜこんなに効果があったのか？

• それはつまり、icpに加算してcontinueしてそしてswitchするというのが、結構なコストになっているからです。だから2つの命令をくっつけて1つにするだけで、それが1回減らせて、かなりの高速化になったわけです。
• このことから教訓を得るとするなら、使用頻度が高いものについては1命令で複数の機能を実行できるような、そんな内部命令を作ったほうが良いということになります。

こめんと欄