高速なrotate関数
高速なrotate関数
以前ここの掲示板でrotateが話題になったことがあり、いくつかの実装方法が出ていたと思います。
それでどの実装が一番高速であるのか?が少し気になっていました。
私もいくつか考えたのですが、同じような方法しか考え付かなかったので
色々な意見を出してもらえたら(かつ競争ができたら)と思い投稿をしました。
みんなが同じ環境ではないので基準が必要だと思います。
独習Cで共用体を使ったrotateがあったので、この実装を基準にし、(一番遅い実装だとおもうので)
何倍の速度が出たか?
を、速度の指標(Speed)として行こうかと思います。
コードの条件としては
1:C99の規格にそったものであること。
2:unsigned char 用の左回転関数を実装すること。
3:インターフェイスは void rotate(unsigned char *)であること。
4:添付ファイルrotate.cのrotate()を変更すること。
ぐらいでしょうか。
#活性化の助けになってくれればよいと思います。
それでどの実装が一番高速であるのか?が少し気になっていました。
私もいくつか考えたのですが、同じような方法しか考え付かなかったので
色々な意見を出してもらえたら(かつ競争ができたら)と思い投稿をしました。
みんなが同じ環境ではないので基準が必要だと思います。
独習Cで共用体を使ったrotateがあったので、この実装を基準にし、(一番遅い実装だとおもうので)
何倍の速度が出たか?
を、速度の指標(Speed)として行こうかと思います。
コードの条件としては
1:C99の規格にそったものであること。
2:unsigned char 用の左回転関数を実装すること。
3:インターフェイスは void rotate(unsigned char *)であること。
4:添付ファイルrotate.cのrotate()を変更すること。
ぐらいでしょうか。
#活性化の助けになってくれればよいと思います。
Re:高速なrotate関数
基準
平均 :3.667800秒
自作
平均 :0.813200秒
speed 4.510
コード:
平均 :3.667800秒
自作
平均 :0.813200秒
speed 4.510
コード:
void rotate(unsigned char *c) { if(signed char(*c)<0){ *c = (*c)<<1; *c = *c | 1; }else{ *c = (*c)<<1; } }
Re:高速なrotate関数
そんな早くはないですが。
基準 平均 3.14980
自作 平均 0.6468
Speed 4.8698
基準 平均 3.14980
自作 平均 0.6468
Speed 4.8698
[color=#d0d0ff" face="monospace]
void rotate(unsigned char *c)
{
unsigned char v = *c;
unsigned char b = v & (1 << (CHAR_BIT-1));
*c = unsigned char((v << 1) | b >> (CHAR_BIT-1));
}[/color]
# rotateの意図はこれで合ってます?Re:高速なrotate関数
> そんな早くはないですが。
と思いましたが、うちの CPUでこれ以上早く動くコードってあるのでしょうか、と。
asmコードも一緒に出してみたのですが、これ以上どう縮めたらいいのかちょっと
すぐには思いつきません。
と思いましたが、うちの CPUでこれ以上早く動くコードってあるのでしょうか、と。
asmコードも一緒に出してみたのですが、これ以上どう縮めたらいいのかちょっと
すぐには思いつきません。
[color=#d0d0ff" face="monospace]
mov al, BYTE PTR [ecx]
mov dl, al
shr dl, 7
shl al, 1
or dl, al
mov BYTE PTR [ecx], dl[/color]
Re:高速なrotate関数
>C++でコンパイルしたのではないですか?
コンパイルした環境はVS2005 です。
拡張子を .c。。。ではなくて.cppにしていました。
すみません。
修正したものをあげておきます。
といってもキャストの仕方を変えただけですが。
コンパイルした環境はVS2005 です。
拡張子を .c。。。ではなくて.cppにしていました。
すみません。
修正したものをあげておきます。
といってもキャストの仕方を変えただけですが。
Re:高速なrotate関数
rotate を main より先に記述してもよいのであれば...
基準 平均 1.281200
自作 平均 0.143800
Speed 8.909597
です。
ある程度チューニングしていくと、関数の呼び出しにかかる時間が一番コストがかかるようになります。
コンパイルには Cygwin上のGCC 3.4.4 を使用し、-std=c99 -O2 オプションを付けました。
inline void rotate(unsigned char *c) { unsigned int temp = *c; *c = temp << 1 | (temp >> (CHAR_BIT - 1)); }とすることで、
基準 平均 1.281200
自作 平均 0.143800
Speed 8.909597
です。
ある程度チューニングしていくと、関数の呼び出しにかかる時間が一番コストがかかるようになります。
コンパイルには Cygwin上のGCC 3.4.4 を使用し、-std=c99 -O2 オプションを付けました。
Re:高速なrotate関数
インライン関数を使うかどうかは別として、処理系によっては、
プロセッサによっては、1ビットのシフト命令しかない場合があるからです。
# そんなプロセッサの場合は、専用のローテート命令を使った方がよいのでしょうが、C99の範囲ということなので...
void rotate(unsigned char *c) { unsigned int temp = *c << 1; if (temp > UCHAR_MAX) temp |= 1; *c = temp; }とした方が高速になる場合があります。
プロセッサによっては、1ビットのシフト命令しかない場合があるからです。
# そんなプロセッサの場合は、専用のローテート命令を使った方がよいのでしょうが、C99の範囲ということなので...
Re:高速なrotate関数
>ある程度チューニングしていくと、関数の呼び出しにかかる時間が一番コストがかかるようになります
私の環境VS2005 Microsoft Visual Studio 2005 Standard E
ではややインラインした方が時間がかかるようです。
0.88→0.90
と約0.02秒よけいに時間がかかるようです。
コンパイラオプションは/O2です。
コンパイラオプションを/O2 /Oyにしたら
0.93→0.89
とインラインにしたら速くなるようです。
コンパイラオプションが面白いと思った瞬間です。
#C99対応のコンパイラを使ってないのにC99を指定してた。 自分の環境ぐらいは把握しておかないと。
私の環境VS2005 Microsoft Visual Studio 2005 Standard E
ではややインラインした方が時間がかかるようです。
0.88→0.90
と約0.02秒よけいに時間がかかるようです。
コンパイラオプションは/O2です。
コンパイラオプションを/O2 /Oyにしたら
0.93→0.89
とインラインにしたら速くなるようです。
コンパイラオプションが面白いと思った瞬間です。
#C99対応のコンパイラを使ってないのにC99を指定してた。 自分の環境ぐらいは把握しておかないと。
Re:高速なrotate関数
> 0.88→0.90
> と約0.02秒よけいに時間がかかるようです。
> コンパイラオプションは/O2です。
>
> コンパイラオプションを/O2 /Oyにしたら
>
> 0.93→0.89
> とインラインにしたら速くなるようです。
この程度では有意な差とはいえません。
実際に、Visual C++ 2005 で __forceinline を付けた場合と付けない場合それぞれについて、/O2 でコンパイル結果を確認しましたが、いずれもインライン置換されていました。
ところで、GCCがなぜこんなに速いのか、コンパイル結果を確認してみました。
すると、rotate に渡している ch を、rotate 呼出し後に使用していないため、rotate の呼出しおよびループ自体がなくなっていました(速いはずです)。
正確に計測するためには、最後に ch の値を出力するなど、何らかの方法で使用する必要がありそうです。
また、I/Oが時間を食うことは間違いないので、
> と約0.02秒よけいに時間がかかるようです。
> コンパイラオプションは/O2です。
>
> コンパイラオプションを/O2 /Oyにしたら
>
> 0.93→0.89
> とインラインにしたら速くなるようです。
この程度では有意な差とはいえません。
実際に、Visual C++ 2005 で __forceinline を付けた場合と付けない場合それぞれについて、/O2 でコンパイル結果を確認しましたが、いずれもインライン置換されていました。
ところで、GCCがなぜこんなに速いのか、コンパイル結果を確認してみました。
すると、rotate に渡している ch を、rotate 呼出し後に使用していないため、rotate の呼出しおよびループ自体がなくなっていました(速いはずです)。
正確に計測するためには、最後に ch の値を出力するなど、何らかの方法で使用する必要がありそうです。
また、I/Oが時間を食うことは間違いないので、
puts(sName);は、最初の clock の呼び出しより前に行った方がよいでしょう。
Re:高速なrotate関数
> プロセッサによっては、1ビットのシフト命令しかない場合があるからです。
2倍したらよいのでは?
Z80 等のときはそういう手もよく使ってましたけど。
2倍したらよいのでは?
Z80 等のときはそういう手もよく使ってましたけど。
Re:高速なrotate関数
> > プロセッサによっては、1ビットのシフト命令しかない場合があるからです。
> 2倍したらよいのでは?
1ビットのシフト命令は大抵あります。
それに、左シフトは2倍、というより、同じ値同士の加算で済みますが、右シフトはそうはいきません。
問題は、7ビットの右シフトのようなことが、単一の命令ではできないことが多いということです。
結果として、1ビットずつ7回シフトするようにしてみたり、4ビット + 2ビット + 1ビットというように3回シフトさせてみたりすることになります。除算を使うのは論外です。
> 2倍したらよいのでは?
1ビットのシフト命令は大抵あります。
それに、左シフトは2倍、というより、同じ値同士の加算で済みますが、右シフトはそうはいきません。
問題は、7ビットの右シフトのようなことが、単一の命令ではできないことが多いということです。
結果として、1ビットずつ7回シフトするようにしてみたり、4ビット + 2ビット + 1ビットというように3回シフトさせてみたりすることになります。除算を使うのは論外です。