エイリアス

キーワード

ポインタ, 最適化

これだけは覚えよう

同じ空間を指すポインタをエイリアスと言う
エイリアスはない方がいい (同じ空間を指すポインタをなくす)

エイリアスって?

エイリアス(alias)を辞書で引くと、「別名」と出てきます。

我々が使っているプロセッサは、値を操作するときにはレジスタを使用します(Load/Store architecture)。そのため、C言語やJavaのような高級言語を処理する言語処理系(コンパイラ+リンカ)は、変数に対してレジスタを割り付ける作業を行います。例えば、i = j + kという式がある場合、i→R0, j→R1, k→R2を割り付け、「R1←j (R1にjの内容をロード)」「R2←k (R2にkの内容をロード)」「R0←R1+R2 (R1+R2を計算しR0に結果を出す)」「i←R0 (R0の内容をiに格納)」といったコードを実行します。変数名に対してレジスタを割り当てていけばよいので、性能を追求しなければこの作業はそれほど難しい作業ではないように思えます。

次に、ポインタを使った場合を考えます。

int value = 1;
int * p_i = &value, * p_j = &value, * p_k = &value;

*p_i = *p_j + *p_k;
*p_i = *p_j + *p_k;

このプログラムはポインタを使ってvalue *= 2を2回やっているので、最終的なvalueの値は4になります。

しかし、実際にレジスタを割り付けていくとおかしなことが起こります。計算をするためにはレジスタを割り当てないとならないので、コンパイラは計算式*p_i = *p_j + *p_kに対して、*p_i→R0, *p_j→R1, *p_k→R2と割り当てます。また*p_i,*p_j,*p_kを読み出すためにR3,R4,R5を使うとしましょう。するとこういう感じになります。

R3 ← p_iの値 = valueのアドレス
R4 ← p_jの値 = valueのアドレス
R5 ← p_kの値 = valueのアドレス
R1 ← メモリ内容(R4) = valueの値 = 1
R2 ← メモリ内容(R5) = valueの値 = 1
R0 ← R1 + R2 = 1 + 1 = 2
メモリ内容(R3) = valueの値 ← R0 = 2
R0 ← R1 + R2 = 1 + 1 = 2
メモリ内容(R3) = valueの値 ← R0 = 2

このようにC言語などのポインタを扱う言語にとって、レジスタ割り付けは関単な作業ではありません。なぜかと言うと、「ポインタ変数としては別変数だけど、同じ場所を指しているかもしれない」からです。同じ場所を指すポインタ変数が2つある場合、一方に加えた修正が他方にも影響します。コンパイラはこの影響も考えてコードを作る必要があります。

このように、ある特定のメモリ空間や変数に対して、複数の変数からアクセスできる場合、それらの変数をエイリアスと呼びます。先ほどの例の場合では、「*p_i, *p_j, *p_kはvalueのエイリアス」といいます。「関数にエイリアスがある」とは、通常「関数内にエイリアスを持つ変数がある」ことを言います。関数自体の別名があるということではありません。エイリアスの存在によって本来あるべき動作とは異なる動作をすることを、「エイリアスによる影響」とか「エイリアスによる誤動作」とか言います。

エイリアスとオーバヘッド

コンパイラはエイリアスによる影響からコードを守るため (ユーザが期待するような挙動をさせるため)に、いろんな作業を行ないます。

一番ポピュラーなのが、「メモリに代入したときに、影響を受ける変数を全て無効にする」という方法です。しかしこれは非常に大きなオーバヘッドを生じます。下に擬似コードを載せます。

R3 ← p_iの値 = valueのアドレス
R4 ← p_jの値 = valueのアドレス
R5 ← p_kの値 = valueのアドレス
R1 ← メモリ内容(R4) = valueの値 = 1
R2 ← メモリ内容(R5) = valueの値 = 1
R0 ← R1 + R2 = 1 + 1 = 2
メモリ内容(R3) = valueの値 ← R0 = 2

# ここでメモリに格納したので、メモリに関係するレジスタR1,R2を無効にする
R1 ← メモリ内容(R4) = valueの値 = 2
R2 ← メモリ内容(R5) = valueの値 = 2
R0 ← R1 + R2 = 2 + 2 = 4
メモリ内容(R3) = valueの値 ← R0 = 4

人間の手で最適化すると、こういうコードになります。プログラマとしては、上のコードと下のコードを比較すると、ちょっとしょぼ～んとなります。

R3 ← p_iの値 = valueのアドレス
R1 ← メモリ内容(R4) = valueの値 = 1
R1 ← R1 + R1 = 1 + 1 = 2
R1 ← R1 + R1 = 2 + 2 = 4
メモリ内容(R3) = valueの値 ← R1 = 4

これほどの違いがあると、「これは人間の手でやったらこういうコードになったんだよ」とあきらめかけてしまうところもありますが、実は、さっきのプログラムをポインタを使わずに書いた場合、普通のコンパイラでもこのくらいの最適化をかましてくれます。

R3 ← p_iの値 = valueのアドレス
R1 ← メモリ内容(R4) = valueの値 = 1
R1 ← R1 << 2
メモリ内容(R3) = valueの値 ← R1 = 4

以上のように、あまりポインタを多用すると、コンパイラは「エイリアスによる影響があるかもしれない」と恐れ、非常に遅いコードを生成してしまいます。これは全てのポインタを使ったメモリ格納時に起こるため、エイリアスが全くない場合でも念のためにもう一回メモリからロードしなおす命令を差し込んだりします。コンパイラにとってエイリアスは非常に頭の痛い問題なのです

ちなみに、エイリアスはこんな些細なプログラムでも発生する可能性があります。

int配列の初期化
void foo(int * dest, size_t size)
{

size_t i;

for(i=0;i<size;++i)

*(dest++) = global_initial_value;
}

このコードでは、「*destへ代入したことによってglobal_initial_valueの値が変わるかもしれない」とコンパイラが考えます。結果として、global_initial_valueを毎回読み直すプログラムになるので、キャッシュなしプロセッサの場合には非常に遅いプログラムになります。

int配列の初期化
void foo(int * dest, size_t size) { size_t i; for(i=0;i<size;++i) *(dest++) = global_initial_value; }

コンパイラオプション

多くのコンパイラは、「エイリアスがないことを仮定してコード生成する」という最適化オプションを持っています。このオプションを使用すると、ポインタを使用した場合でも余計なオーバヘッドを生ずることなくコード生成が行なえますが、エイリアスがある場合はとんでもないコードが出力されます。

エイリアスがないと仮定するオプション
GNU Compiler Collection -fargument-noalias, -fargument-noalias-global

Visual C++ /Oa

たとえ一箇所でもエイリアスが存在する場合、その全てのコードをエイリアスがあることを仮定してコンパイルしなければなりません。そのためプログラマは「全てのエイリアスを除去するつもり」でコードを書く必要があります。「最適化をするとプログラムが動かなくなる」というケースのほとんどは、プログラム中にエイリアスがあるにもかかわらず、最適化オプションに「エイリアスがないと仮定してコンパイル」を追加したことが原因です。

エイリアスがないと仮定するオプション
GNU Compiler Collection	-fargument-noalias, -fargument-noalias-global
Visual C++	/Oa

コンパイラで遊ぼう

ではコンパイラを使ってエイリアス体験をしましょう．

まずはプログラムを用意します．このプログラムは，配列の要素のすべてにある値を加える関数addと、そのサンプルプログラムです．ただし，増加値はポインタ渡しで受け取ります．

サンプルプログラム
#include <stdio.h>
#include <stdlib.h>

void add(int * dest, size_t size, int * value)
{
size_t i;
for(i=0;i<size;++i)
*(dest++) += *value;
}
int main(void)
{
int i;
int array[10];

memset(array, 0, sizeof(array));

array[4] = 100;
add(array, 10, &array[4]);

for(i=0;i<10;++i)
printf("array[%d] = %d\n", i, array[i]);

return EXIT_SUCCESS;
}

このプログラムのadd関数では、エイリアスが存在します。それは、引数destと引数valueが同じ場所を指しているかもしれないからです。事実、サンプルプログラムのmain関数では嫌がらせのようにエイリアスを渡しています。

このプログラムを実行すると、本来ならa[0]～a[3]までが100になり、a[4]からa[9]までが200になります。これは、a[4]を計算するまでは*value(=a[4])の値は100なので+100されますが、a[4]を計算した直後から*valueの値が200となるため、a[5]以降は+200になるためです。

で、コンパイルして実行するとこうなります。

実行結果
mira:/home/takayuki$ gcc -O a.c
mira:/home/takayuki$ ./a.out
array[0] = 100
array[1] = 100
array[2] = 100
array[3] = 100
array[4] = 200
array[5] = 200
array[6] = 200
array[7] = 200
array[8] = 200
array[9] = 200

次に、エイリアスが無いと仮定してコンパイルして実行するとこうなります。

実行結果
mira:/home/takayuki$ gcc -O a.c -fargument-noalias
mira:/home/takayuki$ ./a.out
array[0] = 100
array[1] = 100
array[2] = 100
array[3] = 100
array[4] = 200
array[5] = 100
array[6] = 100
array[7] = 100
array[8] = 100
array[9] = 100

次にadd関数のプログラムコードを載せます。Intel x86のgccでコンパイルしたので、x86命令になっています。太字部分はfor文の内側に相当する部分です。

-fargument-noalias 普通にコンパイル
push %ebp push %ebp

mov %esp,%ebp mov %esp,%ebp

push %ebx push %esi

mov 0x8(%ebp),%edx push %ebx

mov 0xc(%ebp),%ebx mov 0x8(%ebp),%edx

xor %ecx,%ecx mov 0xc(%ebp),%ebx

cmp %ebx,%ecx mov 0x10(%ebp),%esi

jae 804840f xor %ecx,%ecx

mov 0x10(%ebp),%eax cmp %ebx,%ecx

mov (%eax),%eax jae 8048410

add %eax,(%edx) mov (%esi),%eax

add $0x4,%edx add %eax,(%edx)

inc %ecx add $0x4,%edx

cmp %ebx,%ecx inc %ecx

jb 8048405 cmp %ebx,%ecx

pop %ebx jb 8048404

leave pop %ebx

ret pop %esi

leave

ret

エイリアスがあるほうだと、ループの最初にmov命令を使ってvalueの値を読み直しています。一方、無いと仮定したほうはその命令がループの外に追い出されています。また無いと仮定したことで使用するレジスタの数が1つ少なくなり、関数のプロローグ/エピローグコード中にあるpush/popの数も少なくなっています。削除されている%esiレジスタは、エイリアスがあると仮定しているコードでは引数valueの値を格納しています。

エイリアスが無ければ、destへの格納によってvalueが示すアドレスの値は変化しません。そうなればループ内に置いてもループ外においても結果は同じなので、コンパイラは積極的にループ外に置こうとします。この最適化を「共通部分式の除去」と呼びます。

このように、ちょっとしたことでプログラムの動作速度やサイズは減らすことができます。最後の最後で実行速度を稼がなければいけなくなったときのために、また最適化で動かなくなるコードを作らないようにするために、日頃からエイリアスの無いコードを心がけると良いかもしれません。

サンプルプログラム
#include <stdio.h> #include <stdlib.h> void add(int * dest, size_t size, int * value) { size_t i; for(i=0;i<size;++i) (dest++) += value; } int main(void) { int i; int array[10]; memset(array, 0, sizeof(array)); array[4] = 100; add(array, 10, &array[4]); for(i=0;i<10;++i) printf("array[%d] = %d\n", i, array[i]); return EXIT_SUCCESS; }

実行結果
mira:/home/takayuki$ gcc -O a.c mira:/home/takayuki$ ./a.out array[0] = 100 array[1] = 100 array[2] = 100 array[3] = 100 array[4] = 200 array[5] = 200 array[6] = 200 array[7] = 200 array[8] = 200 array[9] = 200

実行結果
mira:/home/takayuki$ gcc -O a.c -fargument-noalias mira:/home/takayuki$ ./a.out array[0] = 100 array[1] = 100 array[2] = 100 array[3] = 100 array[4] = 200 array[5] = 100 array[6] = 100 array[7] = 100 array[8] = 100 array[9] = 100

-fargument-noalias	普通にコンパイル
push %ebp	push %ebp
mov %esp,%ebp	mov %esp,%ebp
push %ebx	push %esi
mov 0x8(%ebp),%edx	push %ebx
mov 0xc(%ebp),%ebx	mov 0x8(%ebp),%edx
xor %ecx,%ecx	mov 0xc(%ebp),%ebx
cmp %ebx,%ecx	mov 0x10(%ebp),%esi
jae 804840f	xor %ecx,%ecx
mov 0x10(%ebp),%eax	cmp %ebx,%ecx
mov (%eax),%eax	jae 8048410
add %eax,(%edx)	mov (%esi),%eax
add $0x4,%edx	add %eax,(%edx)
inc %ecx	add $0x4,%edx
cmp %ebx,%ecx	inc %ecx
jb 8048405	cmp %ebx,%ecx
pop %ebx	jb 8048404
leave	pop %ebx
ret	pop %esi
	leave
	ret

余談 - restrictキーワード

C言語にはいくつか種類のようなものがあります。K&R Cとか、ANSI-Cとか。今一番多く使用されているのは、たぶん1990年に標準化された ANSI-C(ISO:IEC 9899:1990)だと思います。そんなC言語はちょこちょこと仕様が改定されていて、1999年にも手直しが加えられています。この最新のC言語仕様はよくANSI-C/99(ISO:IEC 9899:1999)と呼ばれています。

このANSI-C/99には、restrictというキーワードが追加されています。これは、引数で使用すると「エイリアスは無い」という意味になります。先ほどのコンパイラオプションの場合、すべてのコードが対象になるため、コード中のすべてのエイリアスを除去しないと使用できません。一方、restrictはエイリアスの存在を引数毎にコンパイラに教えることができます。

サンプルプログラム
void add(int * restrict dest, size_t size, int * restrict value)
{
size_t i;
for(i=0;i<size;++i)
*(dest++) += *value;
}

gccもversion 3以降からANSI-C/99に対応しています。試しに使ってみると面白いかもしれません。なお、ANSI-C/99をコンパイルするときには、オプションに-std=c99を追加します。

サンプルプログラム
void add(int * restrict dest, size_t size, int * restrict value) { size_t i; for(i=0;i<size;++i) (dest++) += value; }

余談その２ - memmoveとmemcpy

標準Cライブラリの中には、メモリ内容をコピーする命令が2つあります。ひとつがmemcpyで、もうひとつがmemmoveです。両方とも、コピー元/コピー先のポインタとコピーする長さを与えると、メモリ内容をコピーしてくれます。

なぜ同じ機能の関数が2つもあるのか非常に気になると思います。しかし両者はエイリアスという点から見るとまったくの別関数です。memmoveは引数にエイリアスが渡されることを仮定しているのに対し、memcpyはエイリアスがこないと仮定しているという違いがあります。

memmove関数はエイリアスがあることを仮定しているので、「コピー先メモリに書き込んだら、コピー元の内容が壊れるかもしれない」と思いながらコピーをしていきます。速度よりも安全性を重要視します。具体的には、コピー元アドレスがコピー先アドレスよりも前にある場合、先頭から順にコピーを行うとコピー元の内容を破壊してしまいます。そのため後ろからコピーしていきます。逆にコピー元アドレスがコピー先アドレスよりも後にある場合、前からコピーしていきます。

memcpy関数はエイリアスが無いと仮定しているので、どうコピーしたところでコピー元の内容は変わらないと思っています。なので、できる限り高速にコピーをしようとします。Intel x86の場合だと「ストリングス命令」というメモリコピー命令を使って実行していきます。もしエイリアスがあってコピー元の内容を壊してしまったとしたら、それはプログラマの責任です。その代わり、エイリアスの心配をしなくて良い分だけ高速に動作するという特徴もあります。

エイリアスの存在によって、関数の振る舞いが大きく変わってしまうこともよくあります。最適化の効果を期待するなら、関数内でマルチバージョニングするよりも、memcpy/memmoveのように関数ごと分けてしまったほうが性能は向上します。これは、コンパイラが「引数がエイリアスかもしれない」と判断すると、エイリアスが無い部分でもエイリアスの存在を仮定したコードを生成するためです。

キーワード

これだけは覚えよう

エイリアスって?

エイリアスとオーバヘッド

コンパイラオプション

コンパイラで遊ぼう

余談 - restrictキーワード

余談 その２ - memmoveとmemcpy

余談その２ - memmoveとmemcpy