プログラマ専用SNS ミクプラ

以前ここの掲示板でrotateが話題になったことがあり、いくつかの実装方法が出ていたと思います。
それでどの実装が一番高速であるのか？が少し気になっていました。

私もいくつか考えたのですが、同じような方法しか考え付かなかったので
色々な意見を出してもらえたら(かつ競争ができたら)と思い投稿をしました。

みんなが同じ環境ではないので基準が必要だと思います。
独習Cで共用体を使ったrotateがあったので、この実装を基準にし、(一番遅い実装だとおもうので)
何倍の速度が出たか?
を、速度の指標(Speed)として行こうかと思います。

コードの条件としては

1:C99の規格にそったものであること。
2:unsigned char 用の左回転関数を実装すること。
3:インターフェイスは　void rotate(unsigned char *)であること。
4:添付ファイルrotate.cのrotate()を変更すること。

ぐらいでしょうか。


#活性化の助けになってくれればよいと思います。

基準
平均 :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;
	}
}

　そんな早くはないですが。

基準 平均 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の意図はこれで合ってます？

＞　そんな早くはないですが。
　と思いましたが、うちの 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]

基準として提示されたプログラムは、main関数がC99ではコンパイルできません。
C++でコンパイルしたのではないですか？

＞C++でコンパイルしたのではないですか？

コンパイルした環境はVS2005 です。
拡張子を　.c。。。ではなくて.cppにしていました。

すみません。

修正したものをあげておきます。
といってもキャストの仕方を変えただけですが。

rotate を main より先に記述してもよいのであれば...

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 オプションを付けました。

インライン関数を使うかどうかは別として、処理系によっては、

void rotate(unsigned char *c)
{
  unsigned int temp = *c << 1;
  if (temp > UCHAR_MAX) temp |= 1;
  *c = temp;
}

とした方が高速になる場合があります。
プロセッサによっては、1ビットのシフト命令しかない場合があるからです。
# そんなプロセッサの場合は、専用のローテート命令を使った方がよいのでしょうが、C99の範囲ということなので...

＞ある程度チューニングしていくと、関数の呼び出しにかかる時間が一番コストがかかるようになります

私の環境VS2005 Microsoft Visual Studio 2005 Standard E

ではややインラインした方が時間がかかるようです。
0.88→0.90
と約0.02秒よけいに時間がかかるようです。
コンパイラオプションは/O2です。

コンパイラオプションを/O2 /Oyにしたら

0.93→0.89
とインラインにしたら速くなるようです。
コンパイラオプションが面白いと思った瞬間です。

#C99対応のコンパイラを使ってないのにC99を指定してた。　自分の環境ぐらいは把握しておかないと。

> 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が時間を食うことは間違いないので、

puts(sName);

は、最初の clock の呼び出しより前に行った方がよいでしょう。

> プロセッサによっては、1ビットのシフト命令しかない場合があるからです。
２倍したらよいのでは？
Z80 等のときはそういう手もよく使ってましたけど。

> > プロセッサによっては、1ビットのシフト命令しかない場合があるからです。
> ２倍したらよいのでは？

1ビットのシフト命令は大抵あります。
それに、左シフトは２倍、というより、同じ値同士の加算で済みますが、右シフトはそうはいきません。

問題は、7ビットの右シフトのようなことが、単一の命令ではできないことが多いということです。
結果として、1ビットずつ7回シフトするようにしてみたり、4ビット + 2ビット + 1ビットというように3回シフトさせてみたりすることになります。除算を使うのは論外です。

おお、右シフトの方でしたか。
だから、ここの変更だったわけですね。
temp > UCHAR_MAX
注目点が違ってました。失礼しました。