Counting Bits in Python, C++ and Scala (Pt.2)

各プログラミング言語で バイナリファイルの中にある 1 のビットの数をカウントする (その2)

 

こちらのエントリの続き
mog project: Counting Bits in Python, C++ and Scala (Pt.1)

 

C++ 実測 (3)

方法(1)を途中の段階まで実施して配列を横断して加算していく方法。
Hacker's Delight の実装を参考にした。

8ビット単位まで各個計算を行うバージョンを METHOD 3、16ビット単位のバージョンを METHOD 4 としている。

コード

これまでのコードも含め、全体を掲載する。

#define METHOD 3

#include <fstream>
#include <vector>
#include <string>
#include <ctime>
#include <cassert>

using namespace std;

int const kChunkSize = 1 << 14;

// METHOD 1
int POP(unsigned long long x) {
  unsigned long long const y = 0x3333333333333333ULL;
  x -= (x >> 1) & 0x5555555555555555ULL;
  x = (x & y) + ((x >> 2) & y);
  x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0fULL;
  x += x >> 8;
  x += x >> 16;
  x += x >> 32;
  return x & 0x7f;
}

// METHOD 2
int table[1 << 16];

void init_table() {
  for (int i = 0; i < (1 << 16); ++i) table[i] = POP(i);
}

int POP2(unsigned long long x) {
  return table[x & 0xffff] +
      table[(x >> 16) & 0xffff] +
      table[(x >> 32) & 0xffff] +
      table[(x >> 48)];
}

// METHOD 3
int POP_ARRAY(unsigned long long a[], int n) {
  unsigned long long s, s8, x;
  unsigned long long const y = 0x3333333333333333ULL;

  s = 0;
  for (int i = 0; i < n; i += 31) {
    int lim = min(n, i + 31);
    s8 = 0;
    for (int j = i; j < lim; ++j) {
      x = a[j];
      x -= (x >> 1) & 0x5555555555555555ULL;
      x = (x & y) + ((x >> 2) & y);
      x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0fULL;
      s8 += x;
    }
    x = (s8 & 0x00ff00ff00ff00ffULL) + ((s8 >> 8) & 0x00ff00ff00ff00ffULL);
    x += x >> 16;
    x += x >> 32;
    s += x & 0xffff;
  }
  return s;
}

// METHOD 4
int POP_ARRAY2(unsigned long long a[], int n) {
  unsigned long long s, s16, x;
  unsigned long long const y = 0x3333333333333333ULL;

  s = 0;
  for (int i = 0; i < n; i += 4095) {
    int lim = min(n, i + 4095);
    s16 = 0;
    for (int j = i; j < lim; ++j) {
      x = a[j];
      x -= (x >> 1) & 0x5555555555555555ULL;
      x = (x & y) + ((x >> 2) & y);
      x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0fULL;
      x = (x + (x >> 8)) & 0x00ff00ff00ff00ffULL;
      s16 += x;
    }
    x = (s16 & 0x0000ffff0000ffffULL) + ((s16 >> 16) & 0x0000ffff0000ffffULL);
    x += x >> 32;
    s += x & 0xffffffff;
  }
  return s;
}

template <typename T, typename U>
double time_it(int iter, int count, T func, U val) {
  double elapsed = 1e30;
  for (int i = 0; i < iter; ++i) {
    clock_t t = clock();
    for (int j = 0; j < count; ++j) {
      func(val);
    }
    clock_t s = clock();
    elapsed = min(elapsed, static_cast<double>(s - t) / CLOCKS_PER_SEC);
  }
  return elapsed;
}

int count_bit(string path) {
  int ret = 0;
  unsigned long long x[kChunkSize];

  ifstream fin(path.c_str(), ios::in | ios::binary);
  while (true) {
    fin.read(reinterpret_cast<char *>(&x), sizeof(unsigned long long) * kChunkSize);
    if (fin.eof()) break;
#if METHOD == 1
    for (int i = 0; i < kChunkSize; ++i) ret += POP2(x[i]);
#elif METHOD == 2
    for (int i = 0; i < kChunkSize; ++i) ret += POP2(x[i]);
#elif METHOD == 3
    ret += POP_ARRAY(x, kChunkSize);
#elif METHOD == 4
    ret += POP_ARRAY2(x, kChunkSize);
#endif
  }
  fin.close();
  return ret;
}

int main(int argc, char *argv[]) {
  string paths[] = {"00.bin", "01.bin", "02.bin", "03.bin", "04.bin", "05.bin",
      "06.bin", "07.bin", "08.bin", "09.bin", "10.bin", "11.bin"};
  string prefix = "../data/";
  int expected[] = {0, 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000,
      100000000, 1000000000, 1 << 30};

  init_table();
  for (int i = 0; i < 12; ++i) {
    string path = prefix + paths[i];
    assert(count_bit(path) == expected[i]);
    printf("%s: %f sec\n", paths[i].c_str(), time_it(3, 10, count_bit, path));
  }
  return 0;
}

 

実行結果

00.bin: 0.571133 sec
01.bin: 0.563557 sec
02.bin: 0.562696 sec
03.bin: 0.559637 sec
04.bin: 0.563524 sec
05.bin: 0.567378 sec
06.bin: 0.567318 sec
07.bin: 0.563231 sec
08.bin: 0.561556 sec
09.bin: 0.563927 sec
10.bin: 0.566986 sec
11.bin: 0.563692 sec

1 回の処理あたり 約 56ms。テーブル検索版よりも速い結果となった。

 

C++ 実測 (4)

実測(3) の配列横断処理を行う前処理の単位を 8ビットから 16ビットに変更して計測。
コードの1行目を #define METHOD 4 とする

実行結果

00.bin: 0.646128 sec
01.bin: 0.645220 sec
02.bin: 0.640301 sec
03.bin: 0.638049 sec
04.bin: 0.636916 sec
05.bin: 0.634473 sec
06.bin: 0.638034 sec
07.bin: 0.649389 sec
08.bin: 0.642163 sec
09.bin: 0.639769 sec
10.bin: 0.635853 sec
11.bin: 0.637499 sec

1 回の処理あたり 約 63ms。8ビット版よりも遅くなってしまった。

 

 

Scala の並列処理の実測はまた後日。