a21_p01 のバックアップ(No.5)

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
a21_p01 へ行く。
- 1 (2021-05-14 (金) 17:05:54)
- 2 (2021-05-14 (金) 17:17:56)
- 3 (2021-05-15 (土) 00:33:25)
- 4 (2021-05-15 (土) 00:33:25)
- 5 (2021-05-15 (土) 14:26:18)

なぜHLシリーズはこんなに高速なのか？

(by K, 2021.05.14)

(1)

HL-16aやHL-22aはJITコンパイラですが、どちらもかなり小さな処理系です。しかしそれでも結構な速さで動きます。

ページ名	名前	行数	.exeの大きさ	速度のめやす1	速度のめやす2
a21_txt02_6a	HL-16a	1081行	24.5KB	1.0倍	0.9倍
a21_txt02_12a	HL-22a	1223行		1.0倍	0.7倍

速度のめやす
- 速度のめやす1: 10億回ループをgcc-O3(32bit)でやった場合との実行時間の比較です。
- 速度のめやす2: mandel.cをgcc-O3(32bit)でやった場合との実行時間の比較です。1より小さいのはHLのほうが速いということです。mandel.cはa21_txt01_9aにあります。
  - ちなみにgcc-O3(64bit)と比較すると、HL-22aでも2%くらい負けます。やっぱりgccはすごいです。
これを実現するために、種もしかけもあるので、それを紹介しようと思います。

↑

(2)

[1] まず最初に心がけたことは、「高度なことはやらない」です。高度なことをやれば、言語処理系が一気に大きくなってしまいます。それは私のやりたいことではありません。
私は高度なことをやらないで、それでもどこまでできるのか、を知りたいのです。既存コンパイラがやっているようなことを真似すれば、そりゃあすごいことができるでしょう（当然です）。しかしそれは芸がないと私は考えました。だからそれは目指さないことにしたのです。
少ない労力でできて、それいて効果が結構ありそうなことは何か。それだけを寄せ集めたのがHL-16aやHL-22aなのです。

[2] 私はその次に構文木を構築しないと決めました。既存の多くの言語処理系は、まずソースコードから構文木を生成して、次にその構文木に基づいて実行したり、コンパイル結果を出力したりします。これに対してHL-16aやHL-22aは構文木を構築しません。
構築しなくても簡単なことなら結構いろいろできるのです。もちろん限界はあるでしょう（おそらく、その限界に縛られないために既存言語は最初に構文木を構築するのでしょう）。でも私は逆に考えて、限界があるのならいったんそれを受け入れて、その限界がどんなものなのか見極めてやろうと思いました。つまり、構文木を構築せずにどこまでできるか、それに挑戦しようというわけです（私はわざとやれる範囲を狭めて、それでその範囲内をやりつくすのが好きなので、こういう条件を設定するとより楽しく開発ができるのです）。

[3] HL-22aは、基本的に「単純で性能が出そうにないアルゴリズム」を採用しています。たとえばb+cという式を見たら、無条件にメモリ上に一時変数を用意して
```
MOV RAX,[b]
ADD RAX,[c]
MOV [tmp],RAX
```
を出力します。どのレジスタを使ったらいいかとか、そんなのは考えていません。RAXに固定です。・・・もしかしたら、これはa=b+c;の中のb+cかもしれないです。それだったら、[tmp]なんていらないはずです。直接[a]に代入すればいいですよね。でもそんな気の利いたことはしません。気の利いたことをするためには前後を確認しなければいけません。それをやったら複雑になるので、とりあえずは単純に、
```
MOV RAX,[b]
ADD RAX,[c]
MOV [tmp],RAX

MOV RAX,[tmp]
MOV [a],RAX
```
を出力するのです。こんな程度なら簡単です。

[4] でもそれだとさすがに性能が出ません（当然です）。それでレジスタ変数を導入します。ここで、aはR12で、bがR13で、cがR14だとしましょう。すると・・・こうなります。
```
MOV RAX,R13
ADD RAX,R14
MOV [tmp],RAX

MOV RAX,[tmp]
MOV R12,RAX
```
結局、命令数は全然減っていません。ひどいです。それでもメモリアクセスは減るので少し速くなります。そしてこれは[a]、[b]、[c]をR12、R13、R14に置換するだけでいいので、かなり簡単に導入できました。

[5] さてもっと性能を出す方法はないでしょうか。私は「? = ? + ?;」という形であるときだけ[tmp]を使わないという特例を作りました（すべての二項演算子について導入しました）。しかも、1つ目と2つ目の変数が同じで、かつそれがレジスタ変数なら、
```
ADD reg,?
```
という1命令だけを出力させるようにしました。・・・これは、その、なんというかズルです。
これは特例でしかないので、このパターンに合わなければ相変わらず非効率なコードしか出てきません。しかしこのパターンは単純なので、追加するのはすぐにできました。
そしてプログラムの重たいところだけをこの単純な式の組み合わせだけで書くようにしたところ、プログラムの実行速度は一気にとんでもないことになり、gcc-O3並みの速度が出てしまいました。
私は大いに満足しました。これです、これでいいのです。・・・誰がどんな風に書いても高速に実行してくれる超頭いい言語ではなく、腕のいいプログラマがいろいろ考えて工夫して書いた時だけ最高性能が出せるような、そんな言語を私は作りたかったのです。

[6] レジスタ変数がうまくいくかどうかは、どの変数をレジスタ変数にするかにかかっています。既存のコンパイラはそれをとてもうまく自動判定しています。でもHL-22aはそんなことはしません。プログラムを解析して変数の使用頻度を推測するなんて、そんなのは複雑の極みです。絶対にやりたくありません。
だからHL-22aではどの変数をレジスタ変数にしたらいいのか、ユーザがヒントを与えることになっています。それがなければすべての変数はメモリ割り当てのままになります。

↑

(3)

[5]の内容を補足します。

HL-22aで実行するmandel.cの中にはこんなループがあります。これは4重ループの中に書かれているので、ここの処理時間が全処理時間の99%を占めているだろうと思われます。

                   zx = cx; zy = cy;
                   for (n = 1; n < 447; n++) {
                       xx = mul64shr(zx, zx, 24);
                       yy = mul64shr(zy, zy, 24);
                       t = xx + yy;
                       if (t > 0x4000000) break;
                       zy = mul64shr(zy, zx, 23);
                       zx = xx + cx;
                       zy = zy + cy;
                       zx = zx - yy;
                   }
                   sn = sn + n;

ここで、
```
if (xx + yy > 0x4000000) break;
```
とは書かなかったことや、
```
zy = mul64shr(zy, zx, 23) + cy;
zx = xx - yy + cx;
```
とは書かなかったところが、ズルを有効活用しているポイントです。
ちなみに xx = mul64shr(zx, zx, 24); は、 xx = (zx * zx) >> 24; のことです。

なお、このプログラムでは、

zx, zy, xx, yy, t, cx, cy

がレジスタ変数になるように指示を与えています。そのため、

xx = mul64shr(zx, zx, 24); // MOV(xx, zx); IMUL(xx, zx); SAR(xx, 24);
yy = mul64shr(zy, zy, 24); // MOV(yy, zy); IMUL(yy, zy); SAR(yy, 24);
t = xx + yy;               // MOV(t, xx); ADD(t, yy); // ここはLEA命令を使えば1命令にできる（gccはちゃんとそうしている）。
if (t > 0x4000000) break;  // CMP(t, 0x4000000); JG(label_break);
zy = mul64shr(zy, zx, 23); // IMUL(zy, zx); SAR(zy, 23);
zx = xx + cx;              // MOV(zx, xx); ADD(zx, cx); // ここはLEA命令を使えば1命令にできる（gccはちゃんとそうしている）。
zy = zy + cy;              // ADD(zy, cy);
zx = zx - yy;              // SUB(zx, yy);

という機械語を生成しています。これは二か所のLEA命令の利用をサボっているところ以外はgcc-O3と同じ最速コードです。

↑

(4)

インタプリタを[3]のレベルのJITコンパイラへ	x86(32bit): +047行 (HL-9a→HL-13a)	x64(64bit): +127行 (HL-9a→HL-19a)
[3]レベルのJITコンパイラを[4]レベルへ改良	x86(32bit): +046行 (HL-13a→HL-14)	x64(64bit): +065行 (HL-19a→HL-20)
[4]レベルのJITコンパイラを[5]レベルへ改良	x86(32bit): +041行 (HL-14→HL-14a)	x64(64bit): +050行 (HL-20→HL-20a)
無駄なメモリアクセスを削減(*1)	x86(32bit): +106行 (HL-14a→HL-15a)	x64(64bit): +137行 (HL-20a→HL-21a)
コンパイル時の定数計算	x86(32bit): +053行 (HL-15a→HL-16)	x64(64bit): +053行 (HL-21a→HL-22)

*1: MOV [tmp],RAX / MOV RAX,[tmp] のパターンはさすがにひどいかもと思ったので、これが出力コード内に出現したら消してやることにしました。
あとx64ではADDやSUBなどの命令で使える即値は最大で32bitに制限されていることもあって、デフォルトではすべての定数はメモリ上において、メモリ変数のように扱っていましたが、これも値の範囲が問題なければ、ちゃんと即値のある命令を使うように修正しました。これも*1の改造に含まれます。

↑

こめんと欄

コメント	お名前	NameLink