7.22.2013

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 としている。

コード

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#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 の並列処理の実測はまた後日。

投稿者 mog project 時刻: 3:12
ラベル: , ,

0 件のコメント:

コメントを投稿

登録: コメントの投稿 (Atom)