学生プログラマの為の最速swapping入門
前回の記事 http://d.hatena.ne.jp/studiokingyo/20040322 もう一年以上前か･･･
あの時は私はアセンブラを覚えていなかった。
それでもあのスワップ方法は早いと思っていた。
しかし、それを揺るがす記事を目撃してしまった。
http://d.hatena.ne.jp/Will_NET/20051228
である。
なる･･･、最近のハイエンドCPUでは･･･そうなんですか？
いや、ハイエンドかどうか分からないけど2532MHzはハイエンドですよね！？ですよね！！？（それとも1000MHzでハイエンドだと思っている私は時代に遅れているのかしら？）
とにかく、レポートをどうぞ。
どんな風にSWAP処理するか！それが課題だ！
提案その１：足したり引きいたり駆け引きswap
平均 102.666...
#define SWAP_NUM(a,b) \
(a) = (b) - (a) ;\
(b) -= (a) ;\
(a) += (b)
google:dkutil_cstd*1のmacro.hに宣言されている整数専用スワップマクロ
速度的にはほとんど１位を取っている。C言語onlyな割にはかなり優秀。
だが、&a==&bの条件の時は上手くswappingできない。*2
提案その２：一時変数に身を任せるswap
平均325.5
#define SWAP_TEMP(a,b)\
register uint32 t=a;\
a=b;\
b=t;
register宣言したにもかかわらずそんなに早くない･･･何故？
ランキングも毎回2番目か3番目だった。時に1番のタイムより5倍くらいの処理時間がかかることもあった。
多分速度測定プログラムが最適化されていないからだと思う。
提案その３：すべては早く満足を得るためswap
平均101.666...
#define SWAP_FAST32(a,b)\
_asm mov eax,a\
_asm mov ebx,b\
_asm mov a,ebx\
_asm mov b,eax
アセンブラで記述したもの。一番速い時もあれば一番遅い時もあった。
アセンブラなのだからこれはあたりまえと取っておくべきか？
追記：後でアセ値を見てみようと思う。
さらに追記：すでにアセ値を公開している方がいらっしゃいました。http://d.hatena.ne.jp/blueWiz/19051229
提案その４：なんかもう疲れてきた時にのswap
#define SWAP_XOR(a,b)\
a = a ^ b;\
b = a ^ b;\
a = a ^ b;
平均104
http://blog.livedoor.jp/dankogai/archives/50290837.html*3
より引用。この方法は私は初めて見た。
とまぁ･･･速度の面から見ると私の環境ではこうなってしまったのですが･･･どうするべきか･･･。
これも、&a==&bの条件の時は上手くswappingできない。
ちなみに、私はxorによるswapは使わない。なんか嫌。
トラウマになっているコードはこれ。（dKingyoUtility2より）
THE KING OF ABNORMAL SWAPPING!!!見たときは度肝を抜かれた。
///アホな方法での整数専用スワップ
#define IDIOTICAL_SWAP(a,b) a^=b^=a^=b
が
両方とも同じ値?いや変数の場合0になってしまう危険性を孕んでいるからだ。(と、どこかのサイトに書いてあった気がする）（追記：&a==&bの時らしいです。さらに匿名で 『ちなみにa^=b^=a^=bは１つの式の中に同じ変数に対して副作用が何回も出てくるのでC/C++の規格からしてみればこの式を行ってどうなるかは未定義となっていますよ。』とのコメントいただいた。感謝。*4
以上、学生プログラマの為の最速swapping入門？だったが･･･。
><
><
結論
SWAP_NUM()を使うのが良いんじゃないかな？と思いますよ。(前回の記事と回答が同じだが･･･）
なのでやっぱ最速を目指すならテクニシャンが一番！SWAP_FAST32()で攻めてみようね＾＾
例によってコンパイルできない速度測定プログラムをアップしてみた。
#define SWAP_NUM(a,b) \
(a) = (b) - (a) ;\
(b) -= (a) ;\
(a) += (b)#define SWAP_FAST32(a,b)\
_asm mov eax,a\
_asm mov ebx,b\
_asm mov a,ebx\
_asm mov b,eax#define SWAP_TEMP(a,b)\
register uint32 t=a;\
a=b;\
b=t;#define SWAP_XOR(a,b)\
a = a ^ b;\
b = a ^ b;\
a = a ^ b;
#ifdef _DEBUG
#define DEBUG_CODE(x) { x ;}
#else
#define DEBUG_CODE(x)
#endifvoid swap_test(){
using namespace dkutil;
typedef ranking_timer2 swap_ranking_timer;
swap_ranking_timer timer;
realtime_lock lock;
uint32 a=rand(),b=rand();
uint32 c=rand(),d=c;
uint32 x,y;
const size_t count = 1024 * 1024;
{
register size_t i;
swap_ranking_timer::scoped_timer("SWAP_NUM",&timer);
for(i=0;i<count;i++)
{
DEBUG_CODE( (x = a) );
DEBUG_CODE( (y = b) );
SWAP_NUM(a,b);
DEBUG_CODE(dkcmASSERT(x==b && y==a) );
}
}{
register size_t i;
swap_ranking_timer::scoped_timer("SWAP_FAST32",&timer);
for(i=0;i<count;i++)
{
DEBUG_CODE( (x = a) );
DEBUG_CODE( (y = b) );
SWAP_FAST32(a,b);
DEBUG_CODE(dkcmASSERT(x==b && y==a) );
}
}{
register size_t i;
swap_ranking_timer::scoped_timer("SWAP_TEMP",&timer);
for(i=0;i<count;i++)
{
DEBUG_CODE( (x = a) );
DEBUG_CODE( (y = b) );
SWAP_TEMP(a,b);
DEBUG_CODE(dkcmASSERT(x==b && y==a) );
}
}
{
register size_t i;
swap_ranking_timer::scoped_timer("SWAP_XOR",&timer);
for(i=0;i<count;i++)
{
DEBUG_CODE( (x = a) );
DEBUG_CODE( (y = b) );
SWAP_XOR(a,b);
DEBUG_CODE(dkcmASSERT(x==b && y==a) );
}
}
#ifdef _DEBUG
{
register size_t i;
for(i=0;i<count;i++)
{
(x = c);
(y = d);
SWAP_NUM(c,d);
dkcmASSERT(x==d && y==c);(x = c);
(y = d);
SWAP_FAST32(c,d);
dkcmASSERT(x==d && y==c);(x = c);
(y = d);
SWAP_TEMP(c,d);
dkcmASSERT(x==d && y==c);(x = c);
(y = d);
SWAP_XOR(c,d);
dkcmASSERT(x==d && y==c);//cc
(x = c);
(y = c);
SWAP_FAST32(c,c);
dkcmASSERT(x==c && y==c);
(x = c);
(y = c);
{SWAP_TEMP(c,c);}
dkcmASSERT(x==c && y==c);/*
エラーでひっかかる。
(x = c);
(y = c);
SWAP_XOR(c,c);
dkcmASSERT(x==c && y==c);(x = c);
(y = c);
SWAP_NUM(c,c);
dkcmASSERT(x==c && y==c);
*/
}
}
#endif
}
*1:google:dkutil_cに同梱されているstdlib.hやmemory.hの関数をなるたけ最適化しようとしたライブラリ
*2:恥ずかしながらこの事実は今日知った。
*3:ちなみにココの記事の文体を多少オマージュしております。
*4:恥ずかしながらまだC++の規格を読んでいなかったりする。http://www.open-std.org/jtc1/sc22/wg21/を今度呼んでみたいと思います。が･･･英語が･･･ 読む前にまずは英語を･･･おｒｚ！！！
