WGC1 第3章2進数の算術演算子とビット演算 3.4.4 ANDを使用したモジュロnカウンタの作成
モジュロnカウンタの実行速度
実験コード
#include <stdlib.h> #include <stdio.h> #include <limits.h> #include <time.h> int main(int argc, char *argv[]){ int cntr = 0; int i = 0; int n = 0; time_t time_start; time_t time_end; if (argc !=2) { printf("usage: modulo_counter N-counter\n"); return 1; } n = atoi(argv[1]); time(&time_start); for (i=0; i < INT_MAX; i++){ cntr = (cntr + 1) %n; } time(&time_end); printf("MOD time= %#f(sec)\n", difftime(time_end, time_start)); time(&time_start); for (i=0; i < INT_MAX; i++){ cntr = cntr + 1; if ( cntr >= n){ cntr = 0; } } time(&time_end); printf("PLUS time= %#f(sec)\n", difftime(time_end, time_start)); time(&time_start); for (i=0; i < INT_MAX; i++){ cntr = (cntr + 1) & (n-1); } time(&time_end); printf("AND time= %#f(sec)\n", difftime(time_end, time_start)); return 0; }
コンパイル
[oc@centos5 modulo_counter]$ gcc -O0 modulo_counter.c -o modulo_counter
実行シェル
cnt=0; while [ $cnt -ne 10 ]; do ./modulo_counter 32 2>/dev/null; cnt=`expr $cnt + 1`; done echo "-----" cnt=0; while [ $cnt -ne 10 ]; do ./modulo_counter 31 2>/dev/null; cnt=`expr $cnt + 1`; done
結果
2^nの場合実行速度
MOD time= 57.000000(sec) PLUS time= 5.000000(sec) AND time= 4.000000(sec) MOD time= 155.000000(sec) PLUS time= 5.000000(sec) AND time= 4.000000(sec) MOD time= 56.000000(sec) PLUS time= 88.000000(sec) AND time= 5.000000(sec) MOD time= 55.000000(sec) PLUS time= 4.000000(sec) AND time= 5.000000(sec) MOD time= 139.000000(sec) PLUS time= 5.000000(sec) AND time= 4.000000(sec) MOD time= 55.000000(sec) PLUS time= 6.000000(sec) AND time= 4.000000(sec) MOD time= 135.000000(sec) PLUS time= 5.000000(sec) AND time= 4.000000(sec) MOD time= 55.000000(sec) PLUS time= 5.000000(sec) AND time= 5.000000(sec) MOD time= 141.000000(sec) PLUS time= 5.000000(sec) AND time= 5.000000(sec) MOD time= 56.000000(sec) PLUS time= 4.000000(sec) AND time= 5.000000(sec)
2^n以外の場合の実行速度
MOD time= 134.000000(sec) PLUS time= 5.000000(sec) AND time= 5.000000(sec) MOD time= 56.000000(sec) PLUS time= 4.000000(sec) AND time= 4.000000(sec) MOD time= 138.000000(sec) PLUS time= 5.000000(sec) AND time= 4.000000(sec) MOD time= 57.000000(sec) PLUS time= 5.000000(sec) AND time= 86.000000(sec) MOD time= 56.000000(sec) PLUS time= 5.000000(sec) AND time= 4.000000(sec) MOD time= 138.000000(sec) PLUS time= 5.000000(sec) AND time= 4.000000(sec) MOD time= 63.000000(sec) PLUS time= 5.000000(sec) AND time= 6.000000(sec) MOD time= 124.000000(sec) PLUS time= 6.000000(sec) AND time= 4.000000(sec) MOD time= 64.000000(sec) PLUS time= 6.000000(sec) AND time= 5.000000(sec) MOD time= 149.000000(sec) PLUS time= 6.000000(sec) AND time= 5.000000(sec)
AND計算は結果がNGになる
n=31の場合
i=0, cntr=0 i=1, cntr=0 i=2, cntr=0 i=3, cntr=0 i=4, cntr=0 i=5, cntr=0 i=6, cntr=0 i=7, cntr=0 i=8, cntr=0 i=9, cntr=0 i=10, cntr=0 i=11, cntr=0 i=12, cntr=0 i=13, cntr=0 i=14, cntr=0 i=15, cntr=0 i=16, cntr=0 i=17, cntr=0 i=18, cntr=0 i=19, cntr=0 i=20, cntr=0 i=21, cntr=0 i=22, cntr=0 i=23, cntr=0 i=24, cntr=0 i=25, cntr=0 i=26, cntr=0 i=27, cntr=0 i=28, cntr=0 i=29, cntr=0 i=30, cntr=0 i=31, cntr=0
n=30の場合
i=0, cntr=1 i=1, cntr=0 i=2, cntr=1 i=3, cntr=0 i=4, cntr=1 i=5, cntr=0 i=6, cntr=1 i=7, cntr=0 i=8, cntr=1 i=9, cntr=0 i=10, cntr=1 i=11, cntr=0 i=12, cntr=1 i=13, cntr=0 i=14, cntr=1 i=15, cntr=0 i=16, cntr=1 i=17, cntr=0 i=18, cntr=1 i=19, cntr=0 i=20, cntr=1 i=21, cntr=0 i=22, cntr=1 i=23, cntr=0 i=24, cntr=1 i=25, cntr=0 i=26, cntr=1 i=27, cntr=0 i=28, cntr=1 i=29, cntr=0 i=30, cntr=1 i=31, cntr=0
奇数の場合は0、偶数の場合は、0・1、0・1・2・3、0・1・2・3・4・5・6・7
(n=12、24、48、96、、、、のときに増える)
コメント
mod計算、加算、AND演算での比較。以前担当していた製品のときは、ここまで、
シビアな実行速度を求められたことはなかったから、意識したことなかった。
現在担当してる製品だと、この辺は、理解はしてる必要はあるんだろうな。
AND > PLUS > MOD
MOD計算は、AND、PLUSに比べると10倍ぐらい遅いことになる。
ムラがあるのは、VMware上だからかな？
