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

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

 

目的

128 MB のバイナリファイル中にある 1 のビットの数を知りたい。
なお、128 MB = 2^7 MB = 2^17 KB = 2^27 Byte = 2^30 Bit なので求める値は 0 以上 2^30 以下となる。 

これを、並列処理なしの Python, C++, 並列処理ありの Scala でコードを書き、
手元の Mac で所要時間を調べてみる。

 

おことわり
実施環境も処理内容も、(私自身の勉強のために)とりあえず今作れるもので試しただけですので
言語自体の性能を比較する意図はございません。

  

データ作成

実測の前に、1のビットが n 個含まれるランダムなバイナリデータを予め用意しておく。

これは Python で、bitarray ライブラリを利用して行った。
さらに、大きな bitarray に対して random.shuffle を行うと所要時間が恐ろしく長くなるので
2^12 ビットのサイズのバケットを予めランダムに作っておくことで処理時間を短縮した。

参考:
mog project: Python: Random Partition of Integer 

 

bitarray のインストール

bitarray 0.8.1 : Python Package Index

$ sudo pip install bit array

コード

make_test_file.py

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

import random import math import timeit from bitarray import bitarray from random_partition import random_partition   ARRAY_SIZE = 1 << 30 CHUNK_SIZE = 1 << 12   TEST_COUNTS = [     (0, '00.bin'), (1, '01.bin'), (10, '02.bin'), (100, '03.bin'),     (1000, '04.bin'), (10000, '05.bin'), (100000, '06.bin'),     (1000000, '07.bin'), (10000000, '08.bin'), (100000000, '09.bin'),     (1000000000, '10.bin'), (1 << 30, '11.bin')]     def make_bitarray(size, count):     assert(count <= size)       ret = bitarray(size)     if count == size:         ret.setall(True)     else:         ret.setall(False)         if count != 0:             ret[:count] = True             random.shuffle(ret)     return ret     def make_file(count, path):     # Create buckets.     num_buckets = int(math.ceil(float(ARRAY_SIZE) / CHUNK_SIZE))     buckets = random_partition(num_buckets, count, CHUNK_SIZE)       # Write to file.     with open(path, 'wb') as fh:         for b in buckets:             make_bitarray(CHUNK_SIZE, b).tofile(fh)     print('Created: %s' % path)     if __name__ == '__main__':     timeit.__dict__.update(make_file=make_file)     for t in TEST_COUNTS:         time = timeit.Timer('make_file(%d, "%s")' % (t[0], t[1])).timeit(1)         print('%f sec' % time)

 

実行結果

AWS (t1.micro) で一晩コトコト煮込んだデータ。(約7.2時間)
gzip 圧縮して全部で 41 MB。 

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

$ python ./make_test_file.py Created: 00.bin 3.845612 sec Created: 01.bin 3.803929 sec Created: 02.bin 3.650161 sec Created: 03.bin 4.306574 sec Created: 04.bin 10.518001 sec Created: 05.bin 47.784271 sec Created: 06.bin 213.532356 sec Created: 07.bin 716.523029 sec Created: 08.bin 4907.577745 sec Created: 09.bin 8589.099633 sec Created: 10.bin 11360.644969 sec Created: 11.bin 30.384724 sec

Python 実測

bitarray の count 関数を使うだけ。

コード

count_bit.py

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

import timeit from bitarray import bitarray     TEST_COUNTS = [     (0, '00.bin'), (1, '01.bin'), (10, '02.bin'), (100, '03.bin'),     (1000, '04.bin'), (10000, '05.bin'), (100000, '06.bin'),     (1000000, '07.bin'), (10000000, '08.bin'), (100000000, '09.bin'),     (1000000000, '10.bin'), (1 << 30, '11.bin')] PATH_PREFIX = '../data/'     def count_bit(path):     x = bitarray()     with open(path, 'rb') as fh:         x.fromfile(fh)     return x.count()   if __name__ == '__main__':     for t in TEST_COUNTS:         path = PATH_PREFIX + t[1]         assert(count_bit(path) == t[0])         timeit.__dict__.update(count_bit=count_bit)         time = min(timeit.Timer('count_bit("%s")' % path).repeat(3, 10))         print('%s: %f sec' % (t[1], time))

 

実行結果

00.bin: 1.858225 sec 01.bin: 1.860906 sec 02.bin: 1.858306 sec 03.bin: 1.846741 sec 04.bin: 1.853473 sec 05.bin: 1.840856 sec 06.bin: 1.836229 sec 07.bin: 1.852755 sec 08.bin: 1.864767 sec 09.bin: 1.851672 sec 10.bin: 1.839153 sec 11.bin: 1.824429 sec

1 回の処理あたり 約 185ms。
ちなみにそのおよそ半分がファイル読み込みに要する時間。

 

C++ 実測 (1)

まずは普通のカウント方法で。
一度にストリームから読み込むサイズは試行錯誤の末、2^14 (個の long long int) に落ち着いた。

if stream は read() した後で EOFチェックしないと正しい値にならない。

コード

count_bit.cpp

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

#include <fstream> #include <vector> #include <string> #include <ctime> #include <cassert>   using namespace std;   int const kChunkSize = 1 << 14;   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; }   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;     for (int i = 0; i < kChunkSize; ++i) ret += POP(x[i]);   }   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};     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.821018 sec 01.bin: 0.808333 sec 02.bin: 0.809245 sec 03.bin: 0.809044 sec 04.bin: 0.809715 sec 05.bin: 0.809076 sec 06.bin: 0.813601 sec 07.bin: 0.813362 sec 08.bin: 0.812772 sec 09.bin: 0.808916 sec 10.bin: 0.811492 sec 11.bin: 0.811594 sec

1 回の処理あたり 約 81ms。

 

C++ 実測 (2)

テーブル検索を行うバージョン。

コード

1 2 3 4 5 6 7 8 9 10 11 12

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)]; }

 

実行結果

00.bin: 0.608648 sec 01.bin: 0.598598 sec 02.bin: 0.597612 sec 03.bin: 0.601898 sec 04.bin: 0.600394 sec 05.bin: 0.596191 sec 06.bin: 0.595793 sec 07.bin: 0.600928 sec 08.bin: 0.615904 sec 09.bin: 0.622860 sec 10.bin: 0.629954 sec 11.bin: 0.600881 sec

1 回の処理あたり 約 60ms。だいぶ速くなった。

 

 

残り(C++で配列中のビットを累積的に調べる/Scala実測を行う予定)はまた次回。