簡潔トライの実装に含まれる簡潔ビットベクトルの性能比較

はじめに

先日（12/10）DSIRNLP という勉強会で紹介されていた，簡潔トライの実装に含まれる簡潔ビットベクトルの実験結果が予想とかけ離れていたので，自身でも調べてみることにしました．

• partake.in
• DSIRNLP#2で発表しました「作ろう！簡潔ビットベクトル」 - EchizenBlog-Zwei

実験設定

比較した実装は元の実験と同じです．

• ux-trie: http://code.google.com/p/ux-trie/
• rx: http://code.google.com/p/mozc/
• marisa-trie: http://code.google.com/p/marisa-trie/

実験環境の CPU は Intel(R) Core(TM) i7-2640M CPU @ 2.80GHz stepping 07 です．物理メモリの容量は十分にあり，ディスク I/O は発生しない状況でした．

実験においては，ランダムなビット列から簡潔ビットベクトルを構築してから，ランダムな位置のビットを読み出す時間（get_bit），ランダムな入力に対する rank1 にかかる時間（rank1），ランダムな入力に対する select1 にかかる時間（select1）を求めました．ビット列に含まれる 1 の割合を 0.1 や 0.9 に変化させても大きな影響はないようなので，0.5 の結果のみを示します．

ビット列の大きさは 2^10 〜 2^30 まで変化させました．時間については，あらかじめ用意しておいた 2^22 個のクエリを実行するのにかかる時間を計測し，クエリあたりの実行時間を求めました．実験結果として示している値は，11 回の試行により求めた値の中央値です．

実験結果

実験結果は Google Docs にまとめてあります．シートが 3 つあり，それぞれ get_bit, rank1, select1 に対応しています．

• succint-bit-vectors-performance-benchmark
  • https://docs.google.com/spreadsheet/ccc?key=0AkoLhpFvWG_sdEdDc3ZyVkJQT3VKcU1ac0Q1bFUtWVE

横軸がビット列の大きさ（ビット），縦軸が実行時間（マイクロ秒）を示しています．どの操作に関しても marisa-trie の簡潔ビットベクトルが最速という結果になりました．

DSIRNLP#2で発表しました「作ろう！簡潔ビットベクトル」 - EchizenBlog-Zwei に示されている実験結果では 1000 万クエリで 20 秒程度になっていますが，こちらの実験結果では 1 クエリで 1 マイクロ秒を超えるケースはありませんでした．ビット列の大きさが 2^27 ≒ 1.34 億ビットの実験結果に絞ってみると，rank1 は 1000 万クエリあたり 0.4 〜 1.4 秒の範囲に，select1 は 1000 万クエリあたり 1.1 〜 4.2 秒の範囲に収まっています．

おわりに

実験環境が異なるにしても，実験結果にこれほどの差が出ているのは不思議です．

ランダムなクエリというのは非現実的な設定ですから，参考程度にしていただいた方が良いと思います．

ソースコード

実験に用いたソースコードを以下に示します．

ux-trie は Subversion のリポジトリから最新版を取得してインストールした状態で使いました．

rx は mozc に含まれる rx.h と rx.c のコピーを作成して "rx.c" の方を #include するようにしました．rx.c を別にコンパイルしない理由は，簡潔ビットベクトルを操作する関数が static になっているからです．static を外すという手もありますが，インライン化できなくなる可能性があるので却下しました．

marisa も Subversion のリポジトリにある最新版を使っていますが，普通にインストールしても marisa/grimoire/ 以下のヘッダは隠蔽されてしまうので，リポジトリのディレクトリ以下の lib/ をインクルードパスに設定してコンパイルしました．

#include <sys/time.h>

#include <cassert>
#include <cstdint>
#include <iostream>
#include <sstream>
#include <vector>

#include <ux/ux.hpp>
#include "rx.c"
#include <marisa/grimoire/vector.h>

namespace {

const std::size_t MIN_NUM_BITS = 1U << 10;
const std::size_t MAX_NUM_BITS = 1U << 30;
const std::size_t NUM_TRIALS = 11;
const std::size_t NUM_QUERIES = 1 << 22;

class Timer {
 public:
  Timer() : base_(get_time()) {}

  double elapsed() const {
    return get_time() - base_;
  }

  void reset() {
    base_ = get_time();
  }

 private:
  double base_;

  static double get_time() {
    struct timeval tv;
    ::gettimeofday(&tv, NULL);
    return tv.tv_sec + (tv.tv_usec * 0.000001);
  }

  // Disallows copy and assignment.
  Timer(const Timer &);
  Timer &operator=(const Timer &);
};

std::uint32_t xor128() {
  static std::uint32_t x = 123456789;
  static std::uint32_t y = 362436069;
  static std::uint32_t z = 521288629;
  static std::uint32_t w = 88675123;

  const std::uint32_t t = x ^ (x << 11);
  x = y;
  y = z;
  z = w;
  w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
  return w;
}

void generate_data(std::size_t size, double ones_ratio,
                   std::vector<bool> *bits,
                   std::vector<std::uint32_t> *point_queries,
                   std::vector<std::uint32_t> *rank_queries,
                   std::vector<std::uint32_t> *select_queries) {
  bits->resize(size);
  point_queries->resize(NUM_QUERIES);
  rank_queries->resize(NUM_QUERIES);
  select_queries->resize(NUM_QUERIES);
  const std::uint64_t threshold = (1ULL << 32) * ones_ratio;
  std::size_t num_ones = 0;
  for (std::size_t i = 0; i < bits->size(); ++i) {
    const bool bit = xor128() < threshold;
    (*bits)[i] = bit;
    if (bit) {
      ++num_ones;
    }
  }
  for (std::size_t i = 0; i < point_queries->size(); ++i) {
    (*point_queries)[i] = xor128() % bits->size();
  }
  for (std::size_t i = 0; i < rank_queries->size(); ++i) {
    (*rank_queries)[i] = xor128() % bits->size();
  }
  for (std::size_t i = 0; i < select_queries->size(); ++i) {
    (*select_queries)[i] = xor128() % num_ones;
  }
}

void benchmark_ux(const std::vector<bool> &bits,
                  const std::vector<std::uint32_t> &point_queries,
                  const std::vector<std::uint32_t> &rank_queries,
                  const std::vector<std::uint32_t> &select_queries) {
  ux::BitVec bv;
  for (std::size_t i = 0; i < bits.size(); ++i) {
    bv.push_back(bits[i]);
  }

  ux::RSDic dic;
  dic.build(bv);

  {
    std::vector<double> times;
    for (std::size_t i = 0; i < NUM_TRIALS; ++i) {
      Timer timer;
      uint64_t total = 0;
      for (std::size_t j = 0; j < point_queries.size(); ++j) {
        total += dic.getBit(point_queries[j]);
      }
      times.push_back(timer.elapsed());
      assert(total != uint64_t(-1));
    }
    std::cout << '\t'
              << (times[times.size() / 2] / rank_queries.size() * 1000000.0);
  }

  {
    std::vector<double> times;
    for (std::size_t i = 0; i < NUM_TRIALS; ++i) {
      Timer timer;
      uint64_t total = 0;
      for (std::size_t j = 0; j < rank_queries.size(); ++j) {
        total += dic.rank(rank_queries[j], 1);
      }
      times.push_back(timer.elapsed());
      assert(total != uint64_t(-1));
    }
    std::cout << '\t'
              << (times[times.size() / 2] / rank_queries.size() * 1000000.0);
  }

  {
    std::vector<double> times;
    for (std::size_t i = 0; i < NUM_TRIALS; ++i) {
      Timer timer;
      uint64_t total = 0;
      for (std::size_t j = 0; j < select_queries.size(); ++j) {
        total += dic.select(select_queries[j] + 1, 1);
      }
      times.push_back(timer.elapsed());
      assert(total != uint64_t(-1));
    }
    std::cout << '\t'
              << (times[times.size() / 2] / select_queries.size() * 1000000.0);
  }
}

void benchmark_rx(const std::vector<bool> &bits,
                  const std::vector<std::uint32_t> &point_queries,
                  const std::vector<std::uint32_t> &rank_queries,
                  const std::vector<std::uint32_t> &select_queries) {
  typedef struct bv BitVector;

  std::vector<uint8_t> bytes(bits.size() / 8, 0);
  for (std::size_t i = 0; i < bits.size(); ++i) {
    bytes[i / 8] |= bits[i] << (i % 8);
  }
  BitVector *dic = bv_alloc(&bytes[0], bytes.size());

  {
    std::vector<double> times;
    for (std::size_t i = 0; i < NUM_TRIALS; ++i) {
      Timer timer;
      uint64_t total = 0;
      for (std::size_t j = 0; j < point_queries.size(); ++j) {
        total += bv_get(dic, point_queries[j]);
      }
      times.push_back(timer.elapsed());
      assert(total != uint64_t(-1));
    }
    std::cout << '\t'
              << (times[times.size() / 2] / rank_queries.size() * 1000000.0);
  }

  {
    std::vector<double> times;
    for (std::size_t i = 0; i < NUM_TRIALS; ++i) {
      Timer timer;
      uint64_t total = 0;
      for (std::size_t j = 0; j < rank_queries.size(); ++j) {
        total += bv_rank(dic, rank_queries[j], 1);
      }
      times.push_back(timer.elapsed());
      assert(total != uint64_t(-1));
    }
    std::cout << '\t'
              << (times[times.size() / 2] / rank_queries.size() * 1000000.0);
  }

  {
    std::vector<double> times;
    for (std::size_t i = 0; i < NUM_TRIALS; ++i) {
      Timer timer;
      uint64_t total = 0;
      for (std::size_t j = 0; j < select_queries.size(); ++j) {
        total += bv_select(dic, select_queries[j], 1);
      }
      times.push_back(timer.elapsed());
      assert(total != uint64_t(-1));
    }
    std::cout << '\t'
              << (times[times.size() / 2] / select_queries.size() * 1000000.0);
  }

  bv_free(dic);
}

void benchmark_marisa(const std::vector<bool> &bits,
                      const std::vector<std::uint32_t> &point_queries,
                      const std::vector<std::uint32_t> &rank_queries,
                      const std::vector<std::uint32_t> &select_queries) {
  marisa::grimoire::BitVector dic;
  for (std::size_t i = 0; i < bits.size(); ++i) {
    dic.push_back(bits[i]);
  }
  dic.build(true, true);

  {
    std::vector<double> times;
    for (std::size_t i = 0; i < NUM_TRIALS; ++i) {
      Timer timer;
      uint64_t total = 0;
      for (std::size_t j = 0; j < point_queries.size(); ++j) {
        total += dic[point_queries[j]];
      }
      times.push_back(timer.elapsed());
      assert(total != uint64_t(-1));
    }
    std::cout << '\t'
              << (times[times.size() / 2] / rank_queries.size() * 1000000.0);
  }

  {
    std::vector<double> times;
    for (std::size_t i = 0; i < NUM_TRIALS; ++i) {
      Timer timer;
      uint64_t total = 0;
      for (std::size_t j = 0; j < rank_queries.size(); ++j) {
        total += dic.rank1(rank_queries[j] + 1);
      }
      times.push_back(timer.elapsed());
      assert(total != uint64_t(-1));
    }
    std::cout << '\t'
              << (times[times.size() / 2] / rank_queries.size() * 1000000.0);
  }

  {
    std::vector<double> times;
    for (std::size_t i = 0; i < NUM_TRIALS; ++i) {
      Timer timer;
      uint64_t total = 0;
      for (std::size_t j = 0; j < select_queries.size(); ++j) {
        total += dic.select1(select_queries[j]);
      }
      times.push_back(timer.elapsed());
      assert(total != uint64_t(-1));
    }
    std::cout << '\t'
              << (times[times.size() / 2] / select_queries.size() * 1000000.0);
  }
}

}  // namespace

int main(int argc, char *argv[]) {
  double ONES_RATIO = 0.5;
  for (int i = 1; i < argc; ++i) {
    std::stringstream s;
    s << argv[i];
    s >> ONES_RATIO;
    if ((ONES_RATIO < 0.0) || (ONES_RATIO > 1.0)) {
      std::cerr << "error: invalid ONES_RATIO: " << ONES_RATIO << std::endl;
      return -1;
    }
  }

  std::cerr << "MIN_NUM_BITS: " << MIN_NUM_BITS << std::endl;
  std::cerr << "MAX_NUM_BITS: " << MAX_NUM_BITS << std::endl;
  std::cerr << "NUM_TRIALS: " << NUM_TRIALS << std::endl;
  std::cerr << "NUM_QUERIES: " << NUM_QUERIES << std::endl;
  std::cerr << "ONES_RATIO: " << ONES_RATIO << std::endl;

  std::cout << "#bits"
               "\tux(get)\tux(rank)\tux(select)"
               "\trx(get)\trx(rank)\trx(select)"
               "\tmarisa(get)\tmarisa(rank)\tmarisa(select)" << std::endl;
  for (std::size_t num_bits = MIN_NUM_BITS;
       num_bits <= MAX_NUM_BITS; num_bits <<= 1) {
    std::vector<bool> bits;
    std::vector<std::uint32_t> point_queries;
    std::vector<std::uint32_t> rank_queries;
    std::vector<std::uint32_t> select_queries;
    generate_data(num_bits, ONES_RATIO, &bits,
                  &point_queries, &rank_queries, &select_queries);

    std::cout << num_bits;
    benchmark_ux(bits, point_queries, rank_queries, select_queries);
    benchmark_rx(bits, point_queries, rank_queries, select_queries);
    benchmark_marisa(bits, point_queries, rank_queries, select_queries);
    std::cout << std::endl;
  }

  return 0;
}