- 追加された行はこの色です。
- 削除された行はこの色です。
* [[a21_txt01_6]]の補足説明#1
-(by [[K]], 2021.02.04)
-(by [[K]], 2021.03.08)
** (0)
-これは[[「川合のプログラミング言語自作のためのテキスト第三版#6」>a21_txt01_6]]に対する補足説明のページです。
** (1) ループ命令の追加でどこまで速くなるか?
-TL-6は結構高速で、10億回ループの速度ではgcc比で''11.3倍''まで来ましたが、もっと速くできないでしょうか?そのためにはどうしたらいいでしょうか?
-x86にはLOOP命令というのがあります。LOOP命令は、ECXレジスタの値を1減じて、もし0でなければ指定したアドレスに分岐することができます。別にこのことそのものはすごくないのですが、それが1命令できるというのがポイントです。
-では、TL-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, OpTime, OpEnd, OpAdd1, OpLop }; // OpLopを追加.
enum { OpCpy = 0, OpAdd, OpSub, OpPrint, OpGoto, OpJeq, OpJne, OpJlt, OpJge, OpJle, OpJgt, OpLop, OpTime, OpEnd, OpAdd1, OpLop }; // OpLopをOpJgtの直後に追加.
int compile(String s)
{
(中略)
for (pc = 0; pc < pc1; pc++) { // コンパイル開始.
+ if (phrCmp( 13, "!!* = !!* + 1 ; if ( !!* != !!* ) goto !!* ;", tc, pc) && tc[pc] == tc[pc + 2] && tc[pc] == tc[pc + 8]) {
+ putIc3(OpLop, &var[tc[pc + 13]], &var[tc[pc]], &var[tc[pc + 10]]);
+ pc += 13;
+ continue;
+ }
if (phrCmp( 1, "=", tc, pc + 1)) { // 2単語目が"=".
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 (i == OpGoto || i == OpJne || i == OpJeq || i == OpLop) { // OpLopを追加.
icp[1] = &ic[*(IntP)icq[1]];
! if (OpGoto <= i && i <= OpLop) { // OpJgtをOpLopに変更.
icq[1] = (IntP) (*icq[1] + ic);
}
}
(中略)
}
void exec()
{
clock_t t0 = clock();
PtrTyp *icp = ic;
IntP *icp = ic;
+ int i;
for (;;) {
switch ((int) icp[0]) {
(中略)
+ case OpLop:
+ i = *(IntP)icp[2];
+ i = *icp[2];
+ i++;
+ *(IntP)icp[2] = i;
+ if (i != *(IntP)icp[3]) {
+ icp = icp[1];
+ *icp[2] = i;
+ if (i < *icp[3]) {
+ icp = (IntP *) icp[1];
+ continue;
+ }
+ icp += 5;
+ continue;
}
}
}
-プログラムでは、LOOP命令を使うための新しい構文は用意しないで、単に「i=i+1; if (i != 〇〇) goto ××;」みたいなのが出現したら適用するようにしています。
-このため、TL-3用のサンプルプログラムは無修正でも適用されるようになります。
-さてその速さは・・・gcc比で''6.5倍''まで高速化できました!
-このため、HL-3用のサンプルプログラムは無修正でも適用されるようになります。
-さてその速さは・・・gcc比で''5.5倍''まで高速化できました!
** (2) なぜこんなに効果があったのか?
-それはつまり、icpに加算してcontinueしてそしてswitchするというのが、結構なコストになっているからです。だから2つの命令をくっつけて1つにするだけで、それが1回減らせて、かなりの高速化になったわけです。
-このことから教訓を得るとするなら、使用頻度が高いものについては1命令で複数の機能を実行できるような、そんな内部命令を作ったほうが良いということになります。
* こめんと欄
#comment