a21_opt
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
開始行:
* プログラミング言語における最適化について
-(by [[K]], 2021.10.04)
** (0)
-この記事は、以下の2つの話からの派生記事です。
--「10日くらいでできる！プログラミング言語自作入門」 → [[...
--HLX-002 → [[a21_hlx002]]
** (1)
-プログラミング言語（コンパイラ）で最適化というと、「静的...
--そのためにLLVMをバックエンドに選ぶ人もいるくらいです。
-しかし[[HLX>a21_hlx002]]で最適化についてあれこれと実験し...
-どうにかしてその「感じ」をうまく伝えたいです。
** (2)
-最適化はいろいろありますが、派手な効果が出ると私が思って...
--[1]コンパイル時に答えが確定しているものは、定数に置き換...
--[2]結果が利用されない命令は消す。
--[3]決して通ることがない命令列は消す。
--[4]ループをアンロールする。
-これに加えて、最適化を楽しむために、「最適化を頑張らない...
-それぞれ説明します。
** (3-1) コンパイル時に答えが確定しているものは、定数に置...
-これは簡単です。
a = 1 + 2 + b;
-みたいなのがあれば、
a = 3 + b;
-に置き換える、というだけの話です。1+2の部分を3に置き換え...
~
-さらに、
a = 1;
b = a + 2;
-というのがあれば、
a = 1;
b = 3; // まず 1 + 2 に置き換えられて、それが計算されて3...
-に置き換えることもします。これは文脈上、「b = a + 2;」の...
-ちなみに、
a = 1;
label:
b = a + 2;
-であれば、「b = 3;」にはできません。なぜならlabelへgoto...
-ここを頑張って、「labelから合流した時も含めて、この文脈...
-そんな「がんばらない」最適化でも、しないよりはずっといい...
~
-この最適化が最も成果を上げるのは、条件分岐命令が事前に判...
if (a == 0) { b = 1; } else { b = 2; }
-もしここでaの値が文脈上確定するのなら、if文の条件式の結...
----
-この最適化を実現するアルゴリズムは簡単です。
-プログラムを上から順番に見ていくことにします。
-もし変数に定数が代入されたら、この変数の値は〇〇である、...
-もし定数ではない値が代入されたら、もう変数の値は不定なの...
-テーブルに登録された変数を参照された場合は、それを全部定...
-ラベル定義文やforやwhileの先頭は繰り返しやcontiuneで合流...
-置換の結果（もしくは置換する前から）式の一部または全部が...
-こうして最後までプログラムをチェックし終わったら、それで...
-ちなみにプログラム内で一度でもポインタを取得した変数（p ...
-ここも頑張ればもっと最適化がうまくなるのですが、それをや...
----
-ここでは説明のためにC言語のままで処理するかのように書き...
** (3-2) 結果が利用されない命令は消す。
-以下のプログラムがあったとします。
a = 1;
printf("%d", a);
a++;
printf("%d", a);
a++;
printf("%d", a);
-このプログラムを最適化すると(3-1)のルールにより、
a = 1;
printf("%d", 1);
a = 2;
printf("%d", 2);
a = 3;
printf("%d", 3);
-となります。
-そして、これを見ると、もはや「a = 1;」と「a = 2;」は何の...
-ということでこれを消します。
printf("%d", 1);
printf("%d", 2);
a = 3;
printf("%d", 3);
-この例では最適化の結果として「結果が利用されない命令」が...
~
-なお、この最適化は連鎖性があります。
a = x;
b = a + 2;
c = b * 3;
-みたいな場合、この先でaもbもcも使わないのであれば、まず...
----
-この最適化を実現するアルゴリズムは簡単です。
-プログラムを上から順番に見ていくことにします（下から順番...
-何か変数に「代入する命令」があったとき、その直後からその...
-もし誰からも参照されないまま、新しい別の値を代入する命令...
-悩ましいのは分岐命令や条件分岐命令にぶつかったときです。...
-それで、上記の判定で「結果は使われていない」と判断できた...
----
-ここでは説明のためにC言語のままで処理するかのように書き...
** (3-3) 決して通ることがない命令列は消す。
-たとえば
a = 0;
for (i = 0; i < 10; i++) {
printf("%d", i);
if (a == 0) continue;
printf("hello");
}
-このプログラムの中で、 printf("hello"); は一度も実行され...
-こういうのを見つけた場合は、邪魔なので消してしまいます。
----
-この最適化を実現するアルゴリズムは簡単です。
-gotoやbreakやcontinueなどが、条件なしで現れた場合、それ...
-ということで、次の合流可能性があるところ（ラベルがあると...
----
-ここでは説明のためにC言語のままで処理するかのように書き...
** (3-4) ループをアンロールする。
-以下のようなループがあったとします。・・・1から10までの...
s = 0;
for (k = 1; k <= 10; k++) {
s += k;
}
-これはwhileを使って書き直すとこうなります。
s = 0; k = 1;
while (k <= 10) {
s += k; k++;
}
-ここで、whileを5回分だけアンロールしてみましょう。
s = 0; k = 1;
if (k > 10) goto skip; s += k; k++;
if (k > 10) goto skip; s += k; k++;
if (k > 10) goto skip; s += k; k++;
if (k > 10) goto skip; s += k; k++;
if (k > 10) goto skip; s += k; k++;
while (k <= 10) {
s += k; k++;
}
skip:
-その上で、(3-1)を適用するとこうなります。
s = 0; k = 1;
s = 1; k = 2;
s = 3; k = 3;
s = 6; k = 4;
s = 10; k = 5;
s = 15; k = 6;
while (k <= 10) {
s += k; k++;
}
-さらに(3-2)を適用するとこうなります。
s = 15; k = 6;
while (k <= 10) {
s += k; k++;
}
-さらにさらに、もし最初から10回分以上のアンロールをして、...
s = 55;
-だけになります（kがここ以外では使われない変数で、消され...
----
-どうですか。最初に示したループが「s = 55;」まで最適化で...
** (3-9) 最適化処理の規模
-ちなみにHLXでは、上記の(3-1)～(3-4)の最適化に加えてさら...
-だから最適化はそれほど大変な処理ではありません（深入りし...
** (4) 最適化で難しいと感じたところ
-[1]ループのアンロールをどのくらいやるべきなのか判断する...
--上記の例のように、うまくいったときの効果が大きくて面白...
--アンロールしないほうがいいループはたくさんあります。・...
--HLXでは、プログラム内に「これは〇〇回アンロールすべし」...
-[2]どの変数をレジスタ変数にするべきか？
--変数をどのようにレジスタに割り当てるかは、かなり性能に...
--ということでHLXでは、プログラマがどの変数をレジスタに割...
-[3]純関数はどれか？
--プログラム内で、 y = f(x); みたいな記述があって、しかし...
--それでそういうときにf(x)の呼び出しが消せるかどうかは、f...
--コンパイラからすると、ある関数が純関数かどうかは容易に...
--HLXでもこの最適化はやりたいと思っていますが、与えられた...
** (5) 最適化を頑張るとどこまでできるか #1
-ここで標準関数のprintfやputsに似た、my_printf、my_putsと...
-本家のprintfやputsのまま話を進めたかったのですが、そうす...
-ここで、こんなことを妄想します。
my_printf("My name is %s.\n", nam);
が
my_puts("My name is ");
my_puts(nam);
my_puts(".\n");
に変換されたらいいのにな・・・。
-この妄想の背景として、printf族は実行時に複雑なフォーマッ...
-上記の妄想のようにprintf族を使わない形に変換できれば、実...
-ここでmy_printf()がこんな実装だったとしましょう。
void my_printf(const char *fmt, ...)
{
va_list ap;
va_start(ap, fmt);
int i = 0;
while (fmt[i] != 0) {
if (fmt[i] != '%') {
putchar(fmt[i++]);
} else if (fmt[i + 1] == 's') {
my_puts(va_arg(ap, const char *));
i += 2;
} else if (fmt[i + 1] == 'c') {
putchar(va_arg(ap, int));
i += 2;
} else if (fmt[i + 1] == '%') {
putchar('%');
i += 2;
}
// すみません、説明のための手抜きなのでいろいろ...
}
va_end(ap);
}
-この定義に対して my_printf("My name is %s.\n", nam); を...
putchar('M'); putchar('y'); putchar(' '); ... putchar('i...
my_puts(nam);
putchar('.'); putchar('\n');
-あとは連続するputcharをmy_putsにまとめる最適化さえつけて...
my_puts("My name is ");
my_puts(nam);
my_puts(".\n");
-が得られるのです。これはいい！！
** (6) 最適化を頑張るとどこまでできるか #2
-C言語は変数が型を持つ言語（静的型付き言語）ですが、世の...
-もしC言語で動的型付き言語みたいなことをするとしたら、以...
typedef struct Var_ {
int t; // 0:int, 1:char *, 2:double,...
union {
int i;
char *s;
double d;
};
} Var;
void func()
{
Var a, b, c, d;
a.t = 0; a.i = 2;
b.t = 1; b.s = "hello";
c.t = 2; c.d = 3.14;
// 以下、型を気にせずに共通の演算ができる（print, ad...
VarPrint(a);
VarPrint(b);
VarPrint(c);
d = VarAdd(a, b); // d = "2hello" になる.
...
}
-この中で、VarPrint()やVarAdd()は内部にif（もしくはswitch...
-そしてこの「型に応じた処理のための分岐」が、実行速度を目...
-こんなプログラムでも、もし構造体のメンバに対して「この文...
-ということで、上記の(3-1)～(3-4)の最適化だけでも、十分に...
-どうかその雰囲気が伝わりますように・・・。
//** (4) 最適化の具体例
//-ここまで何度も、この程度でいい、そんなに頑張らなくてい...
* こめんと欄
#comment
終了行:
* プログラミング言語における最適化について
-(by [[K]], 2021.10.04)
** (0)
-この記事は、以下の2つの話からの派生記事です。
--「10日くらいでできる！プログラミング言語自作入門」 → [[...
--HLX-002 → [[a21_hlx002]]
** (1)
-プログラミング言語（コンパイラ）で最適化というと、「静的...
--そのためにLLVMをバックエンドに選ぶ人もいるくらいです。
-しかし[[HLX>a21_hlx002]]で最適化についてあれこれと実験し...
-どうにかしてその「感じ」をうまく伝えたいです。
** (2)
-最適化はいろいろありますが、派手な効果が出ると私が思って...
--[1]コンパイル時に答えが確定しているものは、定数に置き換...
--[2]結果が利用されない命令は消す。
--[3]決して通ることがない命令列は消す。
--[4]ループをアンロールする。
-これに加えて、最適化を楽しむために、「最適化を頑張らない...
-それぞれ説明します。
** (3-1) コンパイル時に答えが確定しているものは、定数に置...
-これは簡単です。
a = 1 + 2 + b;
-みたいなのがあれば、
a = 3 + b;
-に置き換える、というだけの話です。1+2の部分を3に置き換え...
~
-さらに、
a = 1;
b = a + 2;
-というのがあれば、
a = 1;
b = 3; // まず 1 + 2 に置き換えられて、それが計算されて3...
-に置き換えることもします。これは文脈上、「b = a + 2;」の...
-ちなみに、
a = 1;
label:
b = a + 2;
-であれば、「b = 3;」にはできません。なぜならlabelへgoto...
-ここを頑張って、「labelから合流した時も含めて、この文脈...
-そんな「がんばらない」最適化でも、しないよりはずっといい...
~
-この最適化が最も成果を上げるのは、条件分岐命令が事前に判...
if (a == 0) { b = 1; } else { b = 2; }
-もしここでaの値が文脈上確定するのなら、if文の条件式の結...
----
-この最適化を実現するアルゴリズムは簡単です。
-プログラムを上から順番に見ていくことにします。
-もし変数に定数が代入されたら、この変数の値は〇〇である、...
-もし定数ではない値が代入されたら、もう変数の値は不定なの...
-テーブルに登録された変数を参照された場合は、それを全部定...
-ラベル定義文やforやwhileの先頭は繰り返しやcontiuneで合流...
-置換の結果（もしくは置換する前から）式の一部または全部が...
-こうして最後までプログラムをチェックし終わったら、それで...
-ちなみにプログラム内で一度でもポインタを取得した変数（p ...
-ここも頑張ればもっと最適化がうまくなるのですが、それをや...
----
-ここでは説明のためにC言語のままで処理するかのように書き...
** (3-2) 結果が利用されない命令は消す。
-以下のプログラムがあったとします。
a = 1;
printf("%d", a);
a++;
printf("%d", a);
a++;
printf("%d", a);
-このプログラムを最適化すると(3-1)のルールにより、
a = 1;
printf("%d", 1);
a = 2;
printf("%d", 2);
a = 3;
printf("%d", 3);
-となります。
-そして、これを見ると、もはや「a = 1;」と「a = 2;」は何の...
-ということでこれを消します。
printf("%d", 1);
printf("%d", 2);
a = 3;
printf("%d", 3);
-この例では最適化の結果として「結果が利用されない命令」が...
~
-なお、この最適化は連鎖性があります。
a = x;
b = a + 2;
c = b * 3;
-みたいな場合、この先でaもbもcも使わないのであれば、まず...
----
-この最適化を実現するアルゴリズムは簡単です。
-プログラムを上から順番に見ていくことにします（下から順番...
-何か変数に「代入する命令」があったとき、その直後からその...
-もし誰からも参照されないまま、新しい別の値を代入する命令...
-悩ましいのは分岐命令や条件分岐命令にぶつかったときです。...
-それで、上記の判定で「結果は使われていない」と判断できた...
----
-ここでは説明のためにC言語のままで処理するかのように書き...
** (3-3) 決して通ることがない命令列は消す。
-たとえば
a = 0;
for (i = 0; i < 10; i++) {
printf("%d", i);
if (a == 0) continue;
printf("hello");
}
-このプログラムの中で、 printf("hello"); は一度も実行され...
-こういうのを見つけた場合は、邪魔なので消してしまいます。
----
-この最適化を実現するアルゴリズムは簡単です。
-gotoやbreakやcontinueなどが、条件なしで現れた場合、それ...
-ということで、次の合流可能性があるところ（ラベルがあると...
----
-ここでは説明のためにC言語のままで処理するかのように書き...
** (3-4) ループをアンロールする。
-以下のようなループがあったとします。・・・1から10までの...
s = 0;
for (k = 1; k <= 10; k++) {
s += k;
}
-これはwhileを使って書き直すとこうなります。
s = 0; k = 1;
while (k <= 10) {
s += k; k++;
}
-ここで、whileを5回分だけアンロールしてみましょう。
s = 0; k = 1;
if (k > 10) goto skip; s += k; k++;
if (k > 10) goto skip; s += k; k++;
if (k > 10) goto skip; s += k; k++;
if (k > 10) goto skip; s += k; k++;
if (k > 10) goto skip; s += k; k++;
while (k <= 10) {
s += k; k++;
}
skip:
-その上で、(3-1)を適用するとこうなります。
s = 0; k = 1;
s = 1; k = 2;
s = 3; k = 3;
s = 6; k = 4;
s = 10; k = 5;
s = 15; k = 6;
while (k <= 10) {
s += k; k++;
}
-さらに(3-2)を適用するとこうなります。
s = 15; k = 6;
while (k <= 10) {
s += k; k++;
}
-さらにさらに、もし最初から10回分以上のアンロールをして、...
s = 55;
-だけになります（kがここ以外では使われない変数で、消され...
----
-どうですか。最初に示したループが「s = 55;」まで最適化で...
** (3-9) 最適化処理の規模
-ちなみにHLXでは、上記の(3-1)～(3-4)の最適化に加えてさら...
-だから最適化はそれほど大変な処理ではありません（深入りし...
** (4) 最適化で難しいと感じたところ
-[1]ループのアンロールをどのくらいやるべきなのか判断する...
--上記の例のように、うまくいったときの効果が大きくて面白...
--アンロールしないほうがいいループはたくさんあります。・...
--HLXでは、プログラム内に「これは〇〇回アンロールすべし」...
-[2]どの変数をレジスタ変数にするべきか？
--変数をどのようにレジスタに割り当てるかは、かなり性能に...
--ということでHLXでは、プログラマがどの変数をレジスタに割...
-[3]純関数はどれか？
--プログラム内で、 y = f(x); みたいな記述があって、しかし...
--それでそういうときにf(x)の呼び出しが消せるかどうかは、f...
--コンパイラからすると、ある関数が純関数かどうかは容易に...
--HLXでもこの最適化はやりたいと思っていますが、与えられた...
** (5) 最適化を頑張るとどこまでできるか #1
-ここで標準関数のprintfやputsに似た、my_printf、my_putsと...
-本家のprintfやputsのまま話を進めたかったのですが、そうす...
-ここで、こんなことを妄想します。
my_printf("My name is %s.\n", nam);
が
my_puts("My name is ");
my_puts(nam);
my_puts(".\n");
に変換されたらいいのにな・・・。
-この妄想の背景として、printf族は実行時に複雑なフォーマッ...
-上記の妄想のようにprintf族を使わない形に変換できれば、実...
-ここでmy_printf()がこんな実装だったとしましょう。
void my_printf(const char *fmt, ...)
{
va_list ap;
va_start(ap, fmt);
int i = 0;
while (fmt[i] != 0) {
if (fmt[i] != '%') {
putchar(fmt[i++]);
} else if (fmt[i + 1] == 's') {
my_puts(va_arg(ap, const char *));
i += 2;
} else if (fmt[i + 1] == 'c') {
putchar(va_arg(ap, int));
i += 2;
} else if (fmt[i + 1] == '%') {
putchar('%');
i += 2;
}
// すみません、説明のための手抜きなのでいろいろ...
}
va_end(ap);
}
-この定義に対して my_printf("My name is %s.\n", nam); を...
putchar('M'); putchar('y'); putchar(' '); ... putchar('i...
my_puts(nam);
putchar('.'); putchar('\n');
-あとは連続するputcharをmy_putsにまとめる最適化さえつけて...
my_puts("My name is ");
my_puts(nam);
my_puts(".\n");
-が得られるのです。これはいい！！
** (6) 最適化を頑張るとどこまでできるか #2
-C言語は変数が型を持つ言語（静的型付き言語）ですが、世の...
-もしC言語で動的型付き言語みたいなことをするとしたら、以...
typedef struct Var_ {
int t; // 0:int, 1:char *, 2:double,...
union {
int i;
char *s;
double d;
};
} Var;
void func()
{
Var a, b, c, d;
a.t = 0; a.i = 2;
b.t = 1; b.s = "hello";
c.t = 2; c.d = 3.14;
// 以下、型を気にせずに共通の演算ができる（print, ad...
VarPrint(a);
VarPrint(b);
VarPrint(c);
d = VarAdd(a, b); // d = "2hello" になる.
...
}
-この中で、VarPrint()やVarAdd()は内部にif（もしくはswitch...
-そしてこの「型に応じた処理のための分岐」が、実行速度を目...
-こんなプログラムでも、もし構造体のメンバに対して「この文...
-ということで、上記の(3-1)～(3-4)の最適化だけでも、十分に...
-どうかその雰囲気が伝わりますように・・・。
//** (4) 最適化の具体例
//-ここまで何度も、この程度でいい、そんなに頑張らなくてい...
* こめんと欄
#comment
ページ名:
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
