読者です 読者をやめる 読者になる 読者になる

WGC1 第3章2進数の算術演算子とビット演算 3.4.4 ANDを使用したモジュロnカウンタの作成

C

モジュロ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上だからかな?










Randall Hyde、鵜飼 文敏、まつもと ゆきひろ、後藤 正徳、トップスタジオ