XOR で変数を交換する

『xor を使うと temporary 領域なしで値を交換できる話』だと思った人、 残念でした。そういう話ではありません。 話は逆です。『そげなことは無駄だよ』という話。

本当にちゃんと交換できるの?

 次の関数は pointer a と pointer b が指している先の値を交換するものです。 この関数は常に正しいかどうか、わかりますか?

    void
    swap( int *a, int *b )
    {
        *a      ^= *b;
        *b      ^= *a;
        *a      ^= *b;
    }
  

  実は正しくありません。

a や b が指している先が本当に int とは限らない。

 Cにおいてはポインターに限らず、 ほとんどあらゆるものが自動的にキャストされます。 キャストした結果が int と一致するとは限りません。 いらんところまで交換されてはたまりません。

 また、*a や *b の先が bitfield の一部の場合もこれはうまく動きません。 「ビットへのポインター」は存在しませんから。

a と b の指している領域がどこかで重複していると失敗する。

 もっとも極端な場合、a == b だった場合について考えます。 *a ^= *b; を実行すると、a が指している先は 0 になります。 b も同じ所を指していますから、そこも 0 になります…。

 こうなったら、もとの *a, *b に関する情報は完全に消滅します。

 これらの問題を回避しようとすると、 temporary 領域を準備して、 それを利用して交換した方が早く、 安全に値の交換を行なえることになってしまいます。

本当に交換する必要がある?

 『でも、整数レジスターの値ならば…』などと言う、 あきらめの悪い人には次の話を。

 レジスターの値を本当に交換する必要は、実はとんでもなく少ないのです。 大抵の交換要求はリソースマッピングの不備から来るもので、 リソースマッピングの再スケジューリングを行なえば不要になってしまいます。 唯一回避できない場合と言うのは、 条件に応じて交換する必要がある場合です。 たとえば r1 と r2 に値が入っているとして、

        if ( r1 < r2 ) {
                swap( r1, r2 );
        }
   
などと言われたら、r1 と r2 の中身は交換せざるをえません。

 では、レジスターの中身を、どうしても交換するしかない時は、 XOR を用いた手法は有効でしょうか? 答はここでさえ NO です。

 最近の CPU はレジスターリネーミング機構というものが入っています。 ニーモニック上32個のレジスターが使えるとするなら、 内部的には40 個ぐらいレジスターを持っておいて、 必要に応じてその 40 個の中の適切なレジスターを、 ニーモニック上のレジスターに割り振るのです。

 最近の高周波数で動く多段パイプラインを多用した CPU では、 この機構が有効に作用します。 例えば

        r3 = r1 * r2;           …(1)
        r1 = 30;                …(2)
   
のようなコードの場合を考えます。 レジスターリネーミング機能がないと (1) の r1 が解放されるまで、 つまり r3 の計算が終るまで (2) の処理は実行できません。

 しかし、レジスターリネーミング機能を使って、 (1) の r1 と (2) の r1 を 『ニーモニック上は同じレジスターID を持っているが、 実際には別のレジスター』 に割り振った場合、この2つは並列して処理することが可能になります。

 この点に立って XOR を使う場合と、そうじゃない場合について考えてみます。

 まず、もし、レジスターネームをユーザー側が自由に差し替えられるならば、 これを行なえば良いのであって数値の交換は不要だ、ということになります。 XOR を実行するよりもこちらの方が絶対早いはずです。

       r3       = r1;…(1)
       r1       = r2;…(2)
       r2       = r3;…(3)
   
という処理は(1)と(2) の r1 を別の実レジスターにマップすることが可能です。 また(2)と(3) の r2 も別の実レジスターにマップすることが可能です。 うまく実行が重複するならば、(1)と(2)は並列で処理でき、 (1) の実行完了と同時に(3) をスタートすることができますから、 事実上2命令分の時間で実行が完了します。

       r1       = r1 ^ r2;…(1)
       r2       = r1 ^ r2;…(2)
       r1       = r1 ^ r2;…(3)
   
の場合、(1)の左辺の r1 と(2)の右辺の r1 は同じものでなくてはなりません。 (2)の左辺の r2 と (3)の右辺の r2 も同じものでなくてはなりません。 ということは (1) を完了してからでないと (2) が、 (2) を完了してからでないと (3) が、 それぞれ実行できないということになります。 つまりまるまる3命令分の時間が必要だと言うことです。

 レジスターマッピングを工夫して temporary 領域を準備する方が、 XOR で3命令分をまるまる取るよりも早くなる場合の方が多いのです。

 XOR を使って値を交換するテクニックは、 もはや使えないテクニックになったと言えましょう。