くにゅくにゅの雑記帳

実験ノート的なやつ

変数のスワップと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

まとめ

  1. だいたいにおいてコンパイラの方が賢い。変な小細工は使うな。普通に書け。
  2. Cは変なポインタでを自由に作れるのでコンパイラの最適化がしづらい言語である。
  3. 複数のポインタが関与する場合で空間が重複する可能性がないなら restrict を使え。
  4. このあたりの考慮が足りないと,かっこよく書いたつもりが結果的に最悪のコードになる。