データの入れ替え・退避変数・多重代入

これは何？

で退避変数が必要だと教科書に書いてあるとか、そのあたりが面白かったので調べた。

多重代入での入れ替え

Python, Go, Ruby, Perl なんかは多重代入がある。

配列の要素を入れ替えるのであれば

python,go,ruby

a[i], a[j] = a[j], a[i]

のように書ける。

引用元の記事では

もちろん、パフォーマンスを考えると多重代入より退避変数を使ったほうがいいでしょう。

となっているが、手元で試したところ

処理系	結果
Python 3.10	速度差観測できず
Go 1.19 on mac (Apple M1)	速度差観測できず
ruby 3.2.0	多重代入のほうが遅い
jruby-9.4.0.0	どっちが速いこともある
perl 5.30	条件によっては多重代入が速い

となった。

当初「多重代入で書いたほうが速いケースもありそうだと思っているが、そういうパターンは今のところ見つかっていない。」と書いていたが。

perl ならもしかして、と思って調べたら、やはり多重代入が速いパターンがあることがわかった。
jruby でも JIT の効き具合 (?) によっては多重代入のほうが速いこともある模様。

多重代入が速いケース

perl を書いたことがそもそもほとんどないので変なこと書いてるかもしれないけど、こんなパターン。

perl

use Time::HiRes;
use feature ':5.30';

my $a = [];
for( $i=0 ; $i<9999 ; $i++ ){
    push(@$a, reverse(((9999-$i) x 9)." "));
}
my $start_time = Time::HiRes::time;  
my $i=0, $j=0;
for( $i=0 ; $i<@$a ; $i++){
    for( $j=0 ; $j<@$a ; $j++){
        if ($a->[$i] le $a->[$j]){
            ($a->[$i],$a->[$j]) = ($a->[$j],$a->[$i])
        }
    }
}
my $end_time = Time::HiRes::time;
say $a->[0], $a->[1];
printf("%0.3f\n",($end_time - $start_time)*1e3);

この

多重代入

            ($a->[$i],$a->[$j]) = ($a->[$j],$a->[$i])

を

退避変数

            my $tmp = $a->[$i];
            $a->[$i] = $a->[$j];
            $a->[$j] = $tmp;

にしたバージョンと比較すると

バージョン	処理時間
多重代入	11537.572
退避変数	12770.551

などとなり、わずかに退避変数のほうが遅い。

多重代入以外の方法

C++ の場合

例えば a, b が std::vector の場合、

c++で素朴な入れ替え

{
  auto tmp=a; // 甲
  a=b; // 乙
  b=tmp; // 丙
} // 丁

などと書くと 甲 の部分でメモリの動的確保、乙・丙 の部分では開放＋確保、丁 の辺りでメモリ解放が発生して大変遅い（最適化器に気づかれてなんとかなる可能性もある）。

それは困るので std::swap という関数があって

c++

std::swap(a, b);

と書く。std::swap の中身は引数の型によって色々なんだけど、中身は「c++で素朴な入れ替え」と書いたものとは異なる実装になっている。

中身については、 C++ の標準としては特に定めていない。退避変数を使っているのかどうかをユーザーは気にしなくていいし、処理系によって変わるかもしれないので特段の事情がない限り気にしても無駄ということではある。

それと。32bit 整数などの入れ替えは、ソースコード上は実質的に「c++で素朴な入れ替え」と書いたものと同じ内容になるが、これをコンパイル・最適化すると tmp が失われることはわりとしばしばあると思う。

その場合も「退避変数を使っている」と言えるのかどうか。

Java の場合

Java の場合、ruby などの a[i], a[j] = a[j], a[i] に当たる処理を

Java

Collections.swap(a, i, j);

と書くことができる。
Collections.swap 内はどうせ「c++で素朴な入れ替え」で書いたのと同じような内容だろうと思っていたんだが、 実装 を見ると

Java

l.set(i, l.set(j, l.get(i)));

と、ちょっとおもしろいことが書いてある。これは、List の set が変更前の値を返すという仕様になっているから実現できる。

はたしてこれは「片方のデータを一時的に退避させておく専用の変数」を利用していることに該当するだろうか？

アセンブラの場合

元記事の コメント に

多重代入だって、実際に動作するときは（アセンブラ、マシン語レベルでは）退避変数は必要でしょうし

とあるので、CPU に依存した話を書いておく。

入れ替え命令

x86 の命令セットには XCHG があるので レジスタ-レジスタ間と、レジスタ-メモリ 間 の入れ替えには、値の退避は全く必要ない。

古い ARM の命令セットにも SWP があるので、レジスタ-メモリ間の入れ替えには値の退避は全く必要ない。でも ARMv7 辺りで無くなったらしい。

メモリ-メモリ 間の入れ替え命令がある CPU は見つけられなかったが、そういう CPU もありそうだと思っている。

入れ替え命令が無くても

整列の話なので、C などで書くと

Cなど

if (a[j] < a[i]){
  T tmp = a[i];
  a[i] = a[j];
  a[j] = tmp;
}

という具合になるけど、これをアセンブラにすると（以下、← は代入、; から改行までコメント）

擬似アセンブラ

R0 ← a[i]          ; a[i] で示されるメモリの値を レジスタ R0 にロード
R1 ← a[j]          ; a[j] で示されるメモリの値を レジスタ R1 にロード
Flag ← R1<R0       ; R1<R0 の評価結果をフラグに入れる
JumpUnlessFlag END ; Flag が false なら END にジャンプ
a[i] ← R1          ; R1 の値を a[i] で示されるメモリに書き込む
a[j] ← R0          ; R0 の値を a[j] で示されるメモリに書き込む
END

のような感じになると思う (CPUや比較したい内容によってはだいぶ雰囲気が変わると思う)。

多くの場合レジスタの値をメモリに書くことになるんだけど、そのレジスタの値は入れ替えのためにわざわざロードする必要はなく、比較のためにすでにロード済みの値をそのまま書けば良い。

私としては全然「片方のデータを一時的に退避させておく専用の」変数やレジスタを使っている気がしない。
※ いやこれも退避だよ、という意見があってもいい。

まとめ

多重代入による入れ替えと、一時変数への退避による入れ替えの速度差は、あったりなかったり。
処理系や処理内容によって、どちらが速いこともある。

試した範囲では、Python だと速度差を観測できなかった。

多重代入以外でも、ユーザーコードからは一時変数への退避がまったく見えないような入れ替え方をする局面もある。

アセンブラでも「片方のデータを一時的に退避させておく専用の」変数が必要という気分ではない。

実際 CPU が行う計算で退避変数・退避レジスタ が使われるかどうかは CPU や文脈、そして「退避」の意味による。