高速なrotate関数

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
組木紙織

高速なrotate関数

#1

投稿記事 by 組木紙織 » 16年前

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

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

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

コードの条件としては

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

ぐらいでしょうか。


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

組木紙織

Re:高速なrotate関数

#2

投稿記事 by 組木紙織 » 16年前

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

Justy

Re:高速なrotate関数

#3

投稿記事 by Justy » 16年前

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

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

Justy

Re:高速なrotate関数

#4

投稿記事 by Justy » 16年前

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

#5

投稿記事 by たかぎ » 16年前

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

組木紙織

Re:高速なrotate関数

#6

投稿記事 by 組木紙織 » 16年前

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

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

すみません。

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

たかぎ

Re:高速なrotate関数

#7

投稿記事 by たかぎ » 16年前

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

たかぎ

Re:高速なrotate関数

#8

投稿記事 by たかぎ » 16年前

インライン関数を使うかどうかは別として、処理系によっては、
void rotate(unsigned char *c)
{
  unsigned int temp = *c << 1;
  if (temp > UCHAR_MAX) temp |= 1;
  *c = temp;
}
とした方が高速になる場合があります。
プロセッサによっては、1ビットのシフト命令しかない場合があるからです。
# そんなプロセッサの場合は、専用のローテート命令を使った方がよいのでしょうが、C99の範囲ということなので...

組木紙織

Re:高速なrotate関数

#9

投稿記事 by 組木紙織 » 16年前

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

私の環境VS2005 Microsoft Visual Studio 2005 Standard E

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

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

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

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

たかぎ

Re:高速なrotate関数

#10

投稿記事 by たかぎ » 16年前

> 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 の呼び出しより前に行った方がよいでしょう。

Hermit

Re:高速なrotate関数

#11

投稿記事 by Hermit » 16年前

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

たかぎ

Re:高速なrotate関数

#12

投稿記事 by たかぎ » 16年前

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

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

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

Hermit

Re:高速なrotate関数

#13

投稿記事 by Hermit » 16年前

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

閉鎖

“C言語何でも質問掲示板” へ戻る