7.18.2013

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
コード
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。 

$ 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 関数を使うだけ。

コード
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チェックしないと正しい値にならない。

コード
#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)

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

コード
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実測を行う予定)はまた次回。

0 件のコメント:

コメントを投稿