【高速化】ビット演算　0x02

1 名前：デフォルトの名無しさん [2006/09/16(土) 09:46:26 ] 前スレ ビット演算 pc8.2ch.net/test/read.cgi/tech/1123918075/ 関連スレ アセンブラ…　(゜□゜) ↑アッー！↓ pc8.2ch.net/test/read.cgi/tech/1148402614/ 関連情報 Hacker's Delight ttp://www.hackersdelight.org/ ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか ttp://www.amazon.co.jp/exec/obidos/ASIN/4434046683 ビットを数える・探すアルゴリズム ttp://www.nminoru.jp/~nminoru/programming/bitcount.html Bitboard ttp://en.wikipedia.org/wiki/Bitboard 384 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 12:34:23 ] >>383 Intel 系の浮動小数点ユニットは 拡張倍精度（80ビット/仮数部64ビット）で行われてるから大丈夫。 385 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 12:44:20 ] >>384 まじか！と思って何年も開いていない重たいバインダーを紐解いてみたら、たしかにそう書かれているな。 しかも本当は63ビット精度なのに、ケチりビットをケチらない荒技で対処してるし・・・。 そのうえx87コプロに限ればつねに拡張倍精度で計算されることになってたりして、もうね、馬(ry。 386 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 13:02:46 ] 56 = 7*2^3 だから x % 56 = (x % 7)<<3 + (x & 7) x/7 を round(2^32/7 )>>32 で近似したのが >>367 387 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 13:07:24 ] しかし、1/7って面白いなぁ。10進だけでなく16進でも綺麗な循環小数になるんだな。 388 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 13:08:10 ] もしかして >>375 のような事しても idiv 使うより速いって事はありえるのか？ 389 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 16:51:54 ] >>388 実際に速度を比較してみれば？ Cの場合、&より+の方が優先順位が高いので、 >>375の&演算には括弧が必要だね。 390 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 17:06:59 ] そうだね。 391 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 18:03:24 ] やってみた。 function getRDTSC: int64; asm　　　DW　　$310F //RDTSC end; var ww:Integer; procedure TForm1.Button1Click(Sender: TObject); const CNT=100000; var t1,t2,t3:int64; i,a:Integer; begin t1:=getRDTSC; 　for i := 1 to CNT do　begin 　　a := i; 　　a := ((a shr 15) and 7) + (a and ((1 shl 18) - 1)); 　　a := ((a shr 9) and 7) + (a and 4095); 　　a := ((a shr 3) and 7) + (a and 63); 　　a := ((a shr 3) and 7) + (a and 63); 　　while a >= 56 do a := a - 56; 　　ww:=a; {mod と同じになるように} 　end; t2:=getRDTSC; 　for i := 1 to CNT do　ww:=i mod 56;{ローカル変数に代入すると最適化で消えるので} t3:=getRDTSC; Memo1.Lines.Add(format('T2-T1 %10d',[t2-t1])); Memo1.Lines.Add(format('T3-T2 %10d',[t3-t2])); end; --------------- T2-T1 1610740 T3-T2 4317497 間違いでなければ　mod 命令より速い 392 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 18:06:18 ] そうだね。 393 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 18:09:15 ] 上の and 7 は　 and -8 の間違いだった 394 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 18:33:37 ] でも、掛算を使うのはさらに半分だった。 for i := 1 to CNT do begin a := i shr 3; asm 　　 mov eax,$24924925; 　　 IMUL a; 　　 mov a,EDX; end; ww := i - ((a * 7) shl 3); // if ww<> (i mod 56) then Memo1.Lines.Add( 'Err'); end; t4 := getRDTSC; T2-T1 169613675 T3-T2 436034967 T4-T3 86040347 395 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 18:40:43 ] 　結局 idiv : ビット演算 : 掛算の　重さは　およそ　5 : 2 : 1 だった。 ビット演算　思ったよりガンバレるな。 396 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 19:24:47 ] これを高級言語で書いたら他の人に白い目で見られるだけならまだいいんだけど ひどい場合は書き直しすら命じられまする(´・ω・`) 397 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 19:44:35 ] そうだね。 398 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 20:36:07 ] >>396 高級言語の目的の一つが可読性の向上だからね。 コメントで解説いれても却下される場合すらあると思うよ。 399 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 20:48:20 ] 除算命令がないCPUなら有効だろうけど x % 60 が欲しい時とか、いちいち変換が大変だよな 400 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 21:47:03 ] 導出は機械的なプロセスだから、スクリプトみたいなのでサクッと求めるといいと思う。 可能なら、最適化の一環としてコンパイラに組み込むのがベストだが。 401 名前：デフォルトの名無しさん mailto:sage [2007/06/22(金) 23:23:02 ] だから、掛け算化はgccでもやってるって。 402 名前：デフォルトの名無しさん mailto:sage [2007/06/23(土) 00:18:01 ] >>401 ほんとにやってる？やらない場合も多いけど 絶対さぼってる 403 名前：デフォルトの名無しさん mailto:sage [2007/06/23(土) 01:26:20 ] 昔のx86みたいにALUしかないCPUはそういう風にやってたのかぁ、勉強になりました。 404 名前：デフォルトの名無しさん mailto:sage [2007/06/23(土) 01:29:46 ] >>403 定数割り算の掛け算化が行われない例があれば、逆に教えて欲しい。 まさか、最適化オプションを指定しないとしてくれないなんて言わないよね。 405 名前：デフォルトの名無しさん mailto:sage [2007/06/23(土) 01:31:50 ] >>404 深く考えず単純に引き算かと 今考えると空恐ろしいやり方だｗ 406 名前：デフォルトの名無しさん mailto:sage [2007/06/25(月) 10:58:28 ] >404は>402宛てなんだろうなぁ。それはいいけど、>405は何を言いたいのだろう…… 407 名前：デフォルトの名無しさん mailto:sage [2007/06/25(月) 19:13:34 ] きっと8086には除算命令が無いと思ってるんだろう。 408 名前：デフォルトの名無しさん mailto:sage [2007/06/25(月) 19:57:27 ] Pen3では除算を浮動小数点ユニットでされるというのを見て、 浮動小数点ユニットが無い時には除算も無かったと思ったのかな 除算そのものはシフト減算比較の繰り返しで出来るから サイクル数さえ必要なだけかければマイクロプログラム方式ならそうコストかからない 掛け算と変わらない。 409 名前：405 mailto:sage [2007/06/26(火) 07:50:34 ] >>406 あ、ほんとだね >>407,408 んにゃ、引き算の連続で商余求めてたのかなと 410 名前：デフォルトの名無しさん mailto:sage [2007/06/26(火) 08:23:37 ] これは固定での剰余だから高速化出来るのであって 変数での剰余になると、結局コードで書いても加え戻し法(復元法)とかになるので 除算命令使った方がやっぱり速い。 411 名前：デフォルトの名無しさん mailto:sage [2007/06/28(木) 00:42:51 ] DSP(やCell)では逆数をニュートン法で求めるのが定番 412 名前：デフォルトの名無しさん mailto:sage [2007/07/08(日) 16:40:57 ] 8086で除算命令使うとCPUの方で乗算とシフト命令に解釈しなおす訳？ ということは除算命令自体はマクロになるのかな 413 名前：デフォルトの名無しさん mailto:sage [2007/07/08(日) 18:16:20 ] は？ 414 名前：デフォルトの名無しさん mailto:sage [2007/07/08(日) 19:57:33 ] 除算命令に出くわして、せっせとメモリ中のコードを書き換える、けなげな86の姿を想像した・・・ 415 名前：デフォルトの名無しさん mailto:sage [2007/07/11(水) 22:50:58 ] 言う事聞かない奴隷なんかいらない 416 名前：デフォルトの名無しさん [2007/07/21(土) 07:45:05 ] >>412 マイクロプログラムで処理してるんだろ ＞8086のマイクロコードは、命令長が21ビットで、プログラムサイズは504ステップであった 417 名前：デフォルトの名無しさん mailto:sage [2007/07/21(土) 10:07:54 ] そろそろダンゴさんに〆てもらうか。 418 名前：デフォルトの名無しさん mailto:sage [2007/07/21(土) 21:50:22 ] うむ 419 名前：デフォルトの名無しさん [2007/08/03(金) 07:04:32 ] あ 420 名前：デフォルトの名無しさん mailto:sage [2007/08/03(金) 11:40:01 ] ダゴンを深淵から呼びだしては駄目だ 421 名前：だんごの輪島 [2007/08/03(金) 12:15:43 ] ん? 422 名前：デフォルトの名無しさん mailto:sage [2007/08/03(金) 21:06:03 ] は？ 423 名前：デフォルトの名無しさん [2007/08/12(日) 09:53:59 ] は 424 名前：デフォルトの名無しさん mailto:sage [2007/08/12(日) 10:01:53 ] ビッチ演算 425 名前：デフォルトの名無しさん mailto:sage [2007/08/12(日) 14:27:31 ] ビット大佐 426 名前：デフォルトの名無しさん [2007/08/14(火) 10:07:39 ] age 427 名前：デフォルトの名無しさん mailto:age [2007/08/14(火) 11:48:05 ] あ 428 名前：デフォルトの名無しさん mailto:sage [2007/08/16(木) 20:39:50 ] 〆 429 名前：デフォルトの名無しさん [2007/08/18(土) 23:05:50 ] あｇｗ 430 名前：デフォルトの名無しさん mailto:sage [2007/08/18(土) 23:09:42 ] ぬるぽ 431 名前：デフォルトの名無しさん [2007/08/20(月) 01:29:30 ] ちょっとスレの趣旨と違うと思うんだけど、適当なところが無かったので、 アドバイス頼む。 アドレスのアライメントをチェックするためにポインタをintにキャストして &でビットテストしてる。 extern char *p; if(((int)p & 3) == 0){ //32bit境界にある処理… } だけどアドレスをintにキャストするのは64bit時代的に行儀悪いみたい。 でもアドレスをビットテストしたいという状況は普通にあると思うんで、 こういう場合C系的にはどう書くのが上手な作法なの？ 432 名前：デフォルトの名無しさん mailto:sage [2007/08/20(月) 01:38:30 ] >>431 Linux界隈じゃ unsigned long へのキャストが一般的とされてるが 個人的には嫌い 433 名前：デフォルトの名無しさん mailto:sage [2007/08/20(月) 01:40:50 ] intptr_t / uintptr_t を使えばいいんじゃない？ 434 名前：デフォルトの名無しさん mailto:sage [2007/08/20(月) 08:48:31 ] 下位ビットだけ入ればいいので、charでもいい 435 名前：デフォルトの名無しさん mailto:sage [2007/08/20(月) 23:58:10 ] さすがにそれはありえないだろ? 436 名前：デフォルトの名無しさん mailto:sage [2007/08/21(火) 00:11:51 ] なぜそう思うの？ 437 名前：デフォルトの名無しさん mailto:sage [2007/08/21(火) 00:33:14 ] バイトオーダー 438 名前：デフォルトの名無しさん mailto:sage [2007/08/21(火) 00:37:00 ] バイトオーダーは関係ないかと 439 名前：・∀・）っ-○◎● mailto:sage [2007/08/21(火) 00:52:14 ] WindowsならUINT_PTRにキャスト 440 名前：デフォルトの名無しさん mailto:sage [2007/08/21(火) 01:00:01 ] ダンゴさんがピシっと〆めたな。 441 名前：・∀・）っ-○◎● mailto:sage [2007/08/21(火) 01:19:06 ] うんこうんこうんｋ 442 名前：デフォルトの名無しさん [2007/09/09(日) 23:01:40 ] う 443 名前：デフォルトの名無しさん [2007/09/09(日) 23:35:23 ] ん 444 名前：デフォルトの名無しさん mailto:sage [2007/09/09(日) 23:37:25 ] ち 445 名前：デフォルトの名無しさん [2007/09/09(日) 23:45:20 ] ゃ 446 名前：デフォルトの名無しさん [2007/09/16(日) 06:34:05 ] あ 447 名前：デフォルトの名無しさん mailto:sage [2007/09/19(水) 12:28:31 ] は 448 名前：デフォルトの名無しさん mailto:sage [2007/09/19(水) 12:32:11 ] た 449 名前：デフォルトの名無しさん mailto:sage [2007/09/19(水) 13:50:16 ] ぼ 450 名前：デフォルトの名無しさん mailto:sage [2007/09/19(水) 23:03:56 ] ぬ 451 名前：デフォルトの名無しさん mailto:sage [2007/09/19(水) 23:56:29 ] る 452 名前：デフォルトの名無しさん [2007/09/20(木) 00:04:43 ] ぽ 453 名前：デフォルトの名無しさん mailto:sage [2007/09/20(木) 18:42:49 ] >>450-452 ｶﾞ 454 名前：デフォルトの名無しさん mailto:sage [2007/09/22(土) 00:43:27 ] pc11.2ch.net/test/read.cgi/tech/1142467359/555 これもっと簡単にならないかな？ 455 名前：デフォルトの名無しさん mailto:sage [2007/09/22(土) 07:06:58 ] >>454 -------------------- int my_fputwc(wint_t c, FILE *fp) { wint_t r = fputwc(c, fp); return (r == WEOF) ? EOF : r; } int wtbl[0x10000]; void dokkade_jikkou(void ) { int i; for (i = 0; i < 0x10000; i++) wtbl[i] = i; wtbl[0xffff] = EOF; } int my_fputwc(wint_t c, FILE *fp) return wtbl[fputwc(c, fp);]; } みたいなこと(WEOF(wint_tの0xffff)をEOF(intの-1)に変換) をもっとスマートに行う方法ないですかね。 ---------これで何の不満があるんだ？----------- wtbl[0xffff] = EOF; for (i = 0; i < 0xffff; i++) wtbl[i] = i; } -------------------- 456 名前：デフォルトの名無しさん [2007/09/27(木) 20:24:00 ] age 457 名前：デフォルトの名無しさん [2007/09/29(土) 23:03:31 ] int rotate_0_9(int a){a++;return(a+(((a+6)>>4)+(((a+6)>>4)<<1))<<1)&15;} or int rotate_0_9(int a){a++;return(a+((a+6)>>4)*6)&15;} 引数が0〜8の時1を加算し、引数が9の時0を返す。 458 名前：デフォルトの名無しさん mailto:sage [2007/09/29(土) 23:17:24 ] return ++a%9; 459 名前：デフォルトの名無しさん mailto:sage [2007/09/29(土) 23:39:43 ] % はビット演算じゃないだろう 460 名前：デフォルトの名無しさん mailto:sage [2007/09/29(土) 23:58:36 ] int rotate_0_9(int a){return a<9?a+1:0;} 461 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 00:06:34 ] DAA 462 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 00:15:35 ] >>457 >>458 >>460 どれが速い？ 463 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 00:20:18 ] 実測あるのみ 464 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 00:34:05 ] 試してみた！ cl /O2 rot9.c rot9 rotate_0_9_457_1 1873 msec rotate_0_9_457_2 1272 msec rotate_0_9_458 4016 msec rotate_0_9_460 641 msec >>460が圧倒的だった(俺もそう思ってた) ソースに続く 465 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 00:34:50 ] >>464のソース (VC6SP4) ---------------------------- #include <windows.h> #include <stdio.h> int rotate_0_9_457_1(int a){a++;return(a+(((a+6)>>4)+(((a+6)>>4)<<1))<<1)&15;} int rotate_0_9_457_2(int a){a++;return(a+((a+6)>>4)*6)&15;} int rotate_0_9_458(int a){return ++a%9;} int rotate_0_9_460(int a){return a<9?a+1:0;} //#define COUNT_TIMES 0x7fffffff #define COUNT_TIMES 0x7ffffff #define TEST(func) \ dwTime = GetTickCount(); \ for(i = 0, count = 0; count < COUNT_TIMES ; count++) { \ i=func(i); \ } \ printf( # func " %d msec\n", GetTickCount() - dwTime); main() { int i, count; DWORD dwTime; SetPriorityClass(GetCurrentProcess(), HIGH_PRIORITY_CLASS); Sleep(100); TEST(rotate_0_9_457_1) Sleep(100); TEST(rotate_0_9_457_2) Sleep(100); TEST(rotate_0_9_458) Sleep(100); TEST(rotate_0_9_460) return 0; } ---------------------------- 466 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 00:38:34 ] printf( # func " %d msec (i:%d)\n", GetTickCount() - dwTime, i); と変更して計算結果も表示してみたら>>457の最初の式の結果がおかしい事に 気付いたんだけど。 rotate_0_9_457_1 1862 msec (i:0) rotate_0_9_457_2 1272 msec (i:7) rotate_0_9_458 3986 msec (i:7) rotate_0_9_460 671 msec (i:7) 467 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 00:40:00 ] int rotate_0_9_467(int a){ static int t[10]={1,2,3,4,5,6,7,8,9,0}; return t[a]; } 表引き。 これもやってみてくれ。 468 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 00:49:01 ] >>457 やってみるよ。 457_1のiの推移 0 2 6 14 4 10 12 0 2 6 14 4 10 12 0 2 6 14 4 10 12 0 2 6 14 無茶苦茶だった。 469 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 00:55:09 ] rotate_0_9_457_1 1893 msec (i:0) rotate_0_9_457_2 1272 msec (i:7) rotate_0_9_458 3996 msec (i:7) rotate_0_9_460 661 msec (i:7) rotate_0_9_467 621 msec (i:7) テーブル引きのがわずかに速いね。 >>460と>>467が微差だったんでカウンタ倍にしてみた。 #define COUNT_TIMES 0xfffffffに変更。 rotate_0_9_457_1 3535 msec (i:2) rotate_0_9_457_2 2553 msec (i:5) rotate_0_9_458 7991 msec (i:5) rotate_0_9_460 1332 msec (i:5) rotate_0_9_467 1202 msec (i:5) 計ったPCはThinkPad X31 (PenM1.6G Banias) XPSP2 470 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 00:57:00 ] あと>>458は0〜8の繰り返しで条件が違うんで int rotate_0_9_458(int a){return ++a%10;} に修正してる 471 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 01:13:29 ] _rotate_0_9_457_2 PROC NEAR ; 13 : int rotate_0_9_457_2(int a){a++;return(a+((a+6)>>4)*6)&15;} mov ecx, DWORD PTR _a$[esp-4] inc ecx lea eax, DWORD PTR [ecx+6] sar eax, 4 lea eax, DWORD PTR [eax+eax*2] lea eax, DWORD PTR [ecx+eax*2] and eax, 15 ret 0 _rotate_0_9_457_2 ENDP 掛け算消えるんだね _rotate_0_9_458 PROC NEAR ; 14 : int rotate_0_9_458(int a){return ++a%10;} mov eax, DWORD PTR _a$[esp-4] mov ecx, 10 inc eax cdq idiv ecx mov eax, edx ret 0 _rotate_0_9_458 ENDP 見るからに遅そうな 472 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 01:16:44 ] _rotate_0_9_460 PROC NEAR ; 15 : int rotate_0_9_460(int a){return a<9?a+1:0;} mov eax, DWORD PTR _a$[esp-4] cmp eax, 9 jge SHORT $L53312 inc eax ret 0 $L53312: xor eax, eax ret 0 _rotate_0_9_460 ENDP 普通だね _rotate_0_9_467 PROC NEAR ; COMDAT mov eax, DWORD PTR _a$[esp-4] mov eax, DWORD PTR _?t@?1??rotate_0_9_467@@9@9[eax*4] ret 0 _rotate_0_9_467 ENDP 短いね この短さがテーブル参照のオーバーヘッドを相殺してる？ けどaが10以上だったら脂肪 473 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 01:27:47 ] まあ表引きはキャッシュから外れた時にペナルティがあるから 平均的には>460がいいんだろうな。 474 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 02:05:05 ] >>473 確かに、別の環境だと逆転してたり。 #Celeron 430@2.4G XPSP2 rotate_0_9_457_1 1750 msec (i:2) rotate_0_9_457_2 1359 msec (i:5) rotate_0_9_458 2969 msec (i:5) rotate_0_9_460 719 msec (i:5) rotate_0_9_467 860 msec (i:5) #Core2Duo 4300@3.2G XPSP2 rotate_0_9_457_1 1281 msec (i:2) rotate_0_9_457_2 1000 msec (i:5) rotate_0_9_458 2172 msec (i:5) rotate_0_9_460 516 msec (i:5) rotate_0_9_467 656 msec (i:5) 475 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 04:40:29 ] ％は割り算があるから遅いってことか。0〜9ではなく0〜2^n-1の場合にかぎり使えばいいかな。 でも実際の仕事では0〜99のローテートでも％で書いたりするなあ。 476 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 08:29:40 ] 剰余は定数除算よりも更に遅い。 477 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 09:14:40 ] その剰余をビット演算でなんとか．．． 478 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 10:11:46 ] このスレの355から、剰余をビット演算でする方法が書かれているよ。 入力が必ず0〜9なら a=((a+7)&15)-6; 　// 0〜8 が 1〜9 9が-6 (aの符号拡張か　4bitの算術右シフト結果)のビット反転と and 479 名前：457 mailto:sage [2007/09/30(日) 23:43:50 ] ふぬぅ、やっぱ分岐しない上にテーブルも使わない奴は遅いな。 480 名前：デフォルトの名無しさん mailto:sage [2007/09/30(日) 23:45:02 ] 逆に考えて、分岐する上にテーブルも使う奴は・・・ すまん、逆に遅くなりそうだ。 481 名前：デフォルトの名無しさん [2007/10/01(月) 16:44:48 ] modも内部的には分岐してるだろ。RISCならよくわかる。 482 名前：デフォルトの名無しさん mailto:sage [2007/10/01(月) 17:41:59 ] え〜(*o*) それは２のｎ乗の場合とそうでないので分けてるとか？ 483 名前：ヽ・´∀｀・,,）っ━━━━━━┓ mailto:sage [2007/10/04(木) 02:56:19 ] 剰余　＝　披除数 − (除数 ＊ 商) 一般的には商と剰余は同時に求めることが可能 484 名前：デフォルトの名無しさん [2007/10/21(日) 17:07:33 ] age

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef