とやると、JASRACから物言いがきちゃうかな＞志村さん:)

といっても、ここでは枕木の数でもレールの継ぎ目の数でもなく、

TAKESAKO @ Yet another Cybozu Labs: Binary Hacks と 64bit popCount 問題
64bitの数値の中で1になっているビット数を数える

のですが。

ちょっとMMX/SSE/3DNow!は専門外、というかOS Xでどうやるのかがまだよく分かっていないので。

自分でも試してみたのですが、実に面白い結果が出ました。

ここでは、なぜかベンチマークから抜けていた一番「すぐに思いつく」実装と、一番「定義通り」の実装を加えています。

unsigned charにcastしてバイト列として数える 
int popCount64bitC(unsigned long long x) { 
    unsigned char     *p = (unsigned char *)&x;
    return popTable[p[0]] + popTable[p[1]] + popTable[p[2]] + popTable[p[3]]
         + popTable[p[4]] + popTable[p[5]] + popTable[p[6]] + popTable[p[7]];
}
文字通りbitを一つ一つ丁寧に数える 
int popCount64bitO(unsigned long long x) { 
    int i;
    int ret = 0;
    for (i = 0; i < 64; i++){
        ret += (x & 0x1);
        x >>= 1;
    }
    return ret;
}

それを、以下のようにbenchmarkしてみました。

#include <stdio.h>
#include <stdlib.h>
#include <sys/times.h>
#include <sys/resource.h>

#include "popcount_init.c"
#include "popcount_a.c"
#include "popcount_b.c"
#include "popcount_c.c"
#include "popcount_o.c"

#define MILLION 1000000
#define MAXU64  0xffffffffffffffffULL

double ud(struct rusage *s, struct rusage *e){
    double d = e->ru_utime.tv_sec - s->ru_utime.tv_sec;
    d *= MILLION;
    d += e->ru_utime.tv_usec - s->ru_utime.tv_usec;
    return d / MILLION;
}

double sd(struct rusage *s, struct rusage *e){
    double d = e->ru_stime.tv_sec - s->ru_stime.tv_sec;
    d *= MILLION;
    d += e->ru_stime.tv_usec - s->ru_stime.tv_usec;
    return d / MILLION;
}

int main(int argc, char **argv){
    struct rusage ru_s, ru_e;
    int repeat = 100*MILLION;
    int i;
    int popcount = 0;
    init_popTable();
    if (argc > 1){
        repeat = atol(argv[1]);
    }
    printf("repeat = %d\n", repeat);

    getrusage(0, &ru_s);
    for(i = 0; i < repeat; i++) popcount = popCount64bitA(MAXU64 - i);
    getrusage(0, &ru_e);
    printf("popcount(0x%qx) = %d\n", MAXU64 - i, popcount);
    printf("A :user: %g, system: %g\n", ud(&ru_s, &ru_e), sd(&ru_s, &ru_e));

    getrusage(0, &ru_s);
    for(i = 0; i < repeat; i++) popcount = popCount64bitB(MAXU64 - i);
    getrusage(0, &ru_e);
    printf("popcount(0x%qx) = %d\n", MAXU64 - i, popcount);
    printf("B: user: %g, system: %g\n", ud(&ru_s, &ru_e), sd(&ru_s, &ru_e));

    getrusage(0, &ru_s);
    for(i = 0; i < repeat; i++) popcount = popCount64bitC(MAXU64 - i);
    getrusage(0, &ru_e);
    printf("popcount(0x%qx) = %d\n", MAXU64 - i, popcount);
    printf("C: user: %g, system: %g\n", ud(&ru_s, &ru_e), sd(&ru_s, &ru_e));

    getrusage(0, &ru_s);
    for(i = 0; i < repeat; i++) popcount = popCount64bitO(MAXU64 - i);
    getrusage(0, &ru_e);
    printf("popcount(0x%qx) = %d\n", MAXU64 - i, popcount);
    printf("O: user: %g, system: %g\n", ud(&ru_s, &ru_e), sd(&ru_s, &ru_e));

    return 0;
}

そして、その結果。MacBook Pro 2.0GHz上。

% gcc -O0 -W -Wall popcount.c
% ./a.out 10000000
repeat = 10000000
popcount(0xffffffffff67697f) = 50
A :user: 0.448425, system: 0.001029
popcount(0xffffffffff67697f) = 50
B: user: 0.525935, system: 0.001246
popcount(0xffffffffff67697f) = 50
C: user: 0.282275, system: 0.000749
popcount(0xffffffffff67697f) = 50
O: user: 3.0922, system: 0.006753
% gcc -O6 -W -Wall popcount.c
% ./a.out 10000000
repeat = 10000000
popcount(0xffffffffff67697f) = 50
A :user: 0.137518, system: 0.000396
popcount(0xffffffffff67697f) = 50
B: user: 0.224507, system: 0.000559
popcount(0xffffffffff67697f) = 50
C: user: 0.200149, system: 0.000528
popcount(0xffffffffff67697f) = 50
O: user: 1.33571, system: 0.003054

見ての通り、Optimizeするのとしないのとでは大違いで、Optimizeする前は、Unsigned Charとして扱った方が早いという以外な結果が出たのです。そして、どちらの場合も、BよりAの方が早い。これってCacheにLookup Tableが乗り切るかどうかの差にも思えてきました。

いや、64bitなので、32bit Registerに乗り切らないからという理由もありえる。というわけで、32bit版でやってみたのが以下です。

% gcc -O0 -W -Wall popcount.c
% ./a.out 10000000
repeat = 10000000
popcount(0xff67697f) = 18
A :user: 0.17685, system: 0.000537
popcount(0xff67697f) = 18
B: user: 0.181075, system: 0.000551
popcount(0xff67697f) = 18
C: user: 0.159041, system: 0.000483
popcount(0xff67697f) = 18
O: user: 1.17174, system: 0.002695
% gcc -O6 -W -Wall popcount.c
% ./a.out 10000000
repeat = 10000000
popcount(0xff67697f) = 18
A :user: 0.047296, system: 0.000216
popcount(0xff67697f) = 18
B: user: 0.074523, system: 0.000146
popcount(0xff67697f) = 18
C: user: 0.105888, system: 0.000279
popcount(0xff67697f) = 18
O: user: 0.564702, system: 0.001144

こちらでも、BよりAの方が早いのです。-Sの出力を見てみてもちょっとわからないなー。

Dan the Occasional Binarian