変数のスワップとrestrict修飾子
C言語で2つの変数の値を相互に入れ替えるには,先に上書きされる変数の値を,いったん別の変数に待避する実装が素直ですが,追加の変数を用いずにこれを行うアルゴリズムがときどき話題に上ります。具体的には,XORを3回重ねる方法がよく知られているほか,条件次第では加減算を使っても同様の結果を得ることができます。しかし,実際のところこれらはどうコンパイルされるのでしょうか。一時変数を使う方法,XOR,加減算の3種を比べてみました。
比較用コードにおいて,スワップしたあとの値で未知の関数 dummy(a, b) を呼び出しているのは,a と b を実際に逆にすることから逃げられないようにするためです。これは,つまるところスワップ前の値で dummy(b, a) の呼び出しを行うという問題なのですが,引数の渡し方が呼び出し規約として決まっている以上は,レジスタ渡しであれスタック渡しであれ,マシン語レベルで値を入れ替えを行わざるを得ません。
int dummy(int, int); int swap_temp(int a, int b) { int c; c = a; a = b; b = c; return dummy(a, b); } int swap_xor(int a, int b) { a = a ^ b; b = b ^ a; a = a ^ b; return dummy(a, b); } int swap_add(int a, int b) { a = a + b; b = a - b; a = a - b; return dummy(a, b); }
コンパイラには clang x86-64 7.0.0 を使い,現実的な結果を得るため -O を付けて最適化をかけています。その結果,すべて同じコードに落ちました。
swap_temp: # @swap_temp mov eax, edi mov edi, esi mov esi, eax jmp dummy # TAILCALL swap_xor: # @swap_xor mov eax, edi mov edi, esi mov esi, eax jmp dummy # TAILCALL swap_add: # @swap_add mov eax, edi mov edi, esi mov esi, eax jmp dummy # TAILCALL
やっていることは,引数 a と b を逆にして dummy() を呼ぶため,edi と esi を入れ替えているだけです。この際,edi の値を eax に待避させているので,結果的には普通に一時変数を使うアルゴリズムに収束していることがわかります。いまどきのプロセッサは mov よりも,余計な演算する方が効率が悪いので,当然といえば当然の結果です。
「うんうん,いまどきのコンパイラはちゃんと最適化してくれて賢いね~」という話で終わってしまってはつまらないので,もう少し深掘りしてみます。
メモリの場合
こうしたローカルな変数の値をスワップしたいという場面は,実際にはほとんどないのではないかと思います。なぜなら変数 a と b を逆に使う実装とすればよいことで,変数の値そのものを入れ替えなくても同じ結果が得られるためです。しかし,メモリ上に保持されている値なら,2つをどうしても入れ替えたいという要求が,あるいはあるかもしれません。そこで,int のポインタを受け取って,その参照先の値を入れ替えるという実装で,上記と同様の比較をしてみました。
void swap_temp_mem(int *a, int *b) { int c; c = *a; *a = *b; *b = c; } void swap_xor_mem(int *a, int *b) { *a = *a ^ *b; *b = *b ^ *a; *a = *a ^ *b; } void swap_add_mem(int *a, int *b) { *a = *a + *b; *b = *a - *b; *a = *a - *b; }
しかし,なんということでしょう。
swap_temp_mem: # @swap_temp_mem mov eax, dword ptr [rdi] mov ecx, dword ptr [rsi] mov dword ptr [rdi], ecx mov dword ptr [rsi], eax ret swap_xor_mem: # @swap_xor_mem mov eax, dword ptr [rsi] xor eax, dword ptr [rdi] mov dword ptr [rdi], eax xor eax, dword ptr [rsi] mov dword ptr [rsi], eax xor dword ptr [rdi], eax ret swap_add_mem: # @swap_add_mem mov eax, dword ptr [rsi] add eax, dword ptr [rdi] mov dword ptr [rdi], eax sub eax, dword ptr [rsi] mov dword ptr [rsi], eax sub dword ptr [rdi], eax ret
一時変数を用いた実装は素直な形になっていますが,XORと加減算によるものは,Cで書いた内容がほぼそのままマシン語になっただけで,まったく最適化されていません。演算のたびにいちいちメモリアクセスを行っており,見るからに非効率なコードです。
なぜ最適化されないか
これが最適化されなかった原因は,ポインタ a と b とがそれぞれ参照しているメモリ空間が,オーバーラップしている可能性をコンパイラが否定できなかったためと考えられます。ある演算に関与するポインタが2つ以上あるときには,これらのポインタが同一である場合や,一部分が重複している場合についても考慮しなければならず,コンパイラは思い切った最適化を行うことができません。なぜなら,コンパイラとしては,以下のようなケースに対しても正しい答えを出すコードを吐かなければならないからです。
// sizeof(int) == 4 と仮定する char array[6]; int swap_caller(void) { int *a, *b; a = (int *)&array[0]; b = (int *)&array[2]; swap_XXX_mem(a, b); }
この例では,メモリ上で2バイト分が重複している int のポインタ a と b を意図的に作っています。array[] の初期値を同一の非零の値として,ここから swap_temp_mem と swap_xor_mem と swap_add_mem をそれぞれ呼び出したとき,これらは(説明がめんどくさい複雑な作用が生じて)3つとも異なる結果となります,というか,ならなければ正しくありません。このために,コンパイラはこれをただのスワップとして最適化することができないのです。
それでも最適化をするために
しかし,このようなメモリ空間の重複は,理論的には起こりうるとしても実際のプログラムでは起こらないことが保証できるケースは多々あります。にも関わらず,起こらないレアケースのために,本来ならば行える最適化が行われないのは大変にもったいないことで,ある意味でCコンパイラの最適化を阻害する最大要因となっています。そこで使うのが restrict 修飾子です。restrict 修飾されたポインタは空間の重複がないものとして最適化してよいと,コンパイラに伝えることができます。実際にやってみました。
void swap_temp_mem_restr(int * restrict a, int * restrict b) { int c; c = *a; *a = *b; *b = c; } void swap_xor_mem_restr(int * restrict a, int * restrict b) { *a = *a ^ *b; *b = *b ^ *a; *a = *a ^ *b; } void swap_add_mem_restr(int * restrict a, int * restrict b) { *a = *a + *b; *b = *a - *b; *a = *a - *b; }
restrict 修飾の結果,コンパイラは本来の意図をくんでくれて,すべてただのスワップに最適化されました。
swap_temp_mem_restr: # @swap_temp_mem_restr mov eax, dword ptr [rdi] mov ecx, dword ptr [rsi] mov dword ptr [rdi], ecx mov dword ptr [rsi], eax ret swap_xor_mem_restr: # @swap_xor_mem_restr mov eax, dword ptr [rdi] mov ecx, dword ptr [rsi] mov dword ptr [rsi], eax mov dword ptr [rdi], ecx ret swap_add_mem_restr: # @swap_add_mem_restr mov eax, dword ptr [rdi] mov ecx, dword ptr [rsi] mov dword ptr [rsi], eax mov dword ptr [rdi], ecx ret