C++ API Documentation

Draw a sketch

#include <iostream>
#include <string>

#include <madoka.h>

int main(int argc, char *argv[]) {
  madoka::Sketch sketch;
  sketch.create();

  std::string key;
  while (std::getline(std::cin, key)) {
    sketch.inc(key.c_str(), key.length());
  }
  sketch.save(argv[1]);
  return 0;
}

$ g++ draw-a-sketch.cc -lmadoka
$ ./a.out SKETCH < KEYSET

手始めにスケッチを描いてみます．サンプルは，標準入力（std::cin）からキーを一つずつ読み込み，スケッチ（madoka::Sketch）を描いた後，完成したスケッチをコマンドの第一引数（argv[1]）で指定されたファイルに保存しています．注目すべき箇所は以下の通りです．

サンプルのビルドには -lmadoka というオプションが必要なことに注意してください．Madoka がインストールされている環境であれば，pkg-config madoka --libs によってオプションを得ることができます．

Look at a sketch

#include <iostream>
#include <string>

#include <madoka.h>

int main(int argc, char *argv[]) {
  madoka::Sketch sketch;
  sketch.load(argv[1]);
  // sketch.open(argv[1]);

  std::string key;
  while (std::getline(std::cin, key)) {
    std::cout << key << ": "
              << sketch.get(key.c_str(), key.length()) << std::endl;
  }
  return 0;
}

$ g++ look-at-a-sketch.cc -lmadoka
$ ./a.out SKETCH < KEYSET

次に，描いたスケッチを眺めます．サンプルでは，コマンドの第一引数（argv[1]）で指定されたファイルからスケッチを入力し，標準入力（std::cin）から読み込んだキーに対応する値をスケッチから読み取っています．注目すべき箇所は以下の通りです．

h3. Use other brushes

#include <iostream>

#include <madoka.h>

int main(int argc, char *argv[]) {
  madoka::Sketch sketch;
  sketch.create();

  sketch.set("QB", 2, 10);
  std::cout << "QB: "
            << sketch.add("QB", 2, 5) << std::endl;
  sketch.set("QB", 2, 7);
  std::cout << "QB: "
            << sketch.get("QB", 2) << std::endl;
  return 0;
}

$ g++ use-other-brushes.cc -lmadoka
$ ./a.out
QB: 15
QB: 15

madoka::Sketch が提供する描画用の関数には，inc() のほかに set() と add() があります．サンプルはそれぞれの役割を示しています．

サンプルにおいて，最初の set() は "QB" に対応する値を 0 から 10 に更新します．次に，add() が 5 を加算するため，"QB" に対応する値は 15 になります．二回目の set() に指定された値（7）は 15 より小さいため，値の更新はおこなわれず，get() の戻り値は 15 となります．

Customize a sketch

#include <iostream>

#include <madoka.h>

int main(int argc, char *argv[]) {
  const madoka::UInt64 MY_WIDTH = 1ULL << 24;
  const madoka::UInt64 MY_MAX_VALUE = 10;

  madoka::Sketch sketch;
  sketch.create(MY_WIDTH, MY_MAX_VALUE);

  std::cout << "width: " << sketch.width() << std::endl;
  std::cout << "max_value: " << sketch.max_value() << std::endl;
  std::cout << "size: " << sketch.file_size() << std::endl;
  return 0;
}

$ g++ customize-a-sketch.cc -lmadoka
$ ./a.out
width: 16777216
max_value: 15
size: 25165904

Count-Min sketch は確率的なデータ構造なので，スケッチによって得られる値には誤差が含まれます．そして，誤差の大きさは，スケッチを作成するときに指定するパラメータである width と depth，およびに入力するキーの分布に依存します．そのため，Count-Min sketch の性能を引き出すには，適切なパラメータを与えることが重要になります．

基本的に，正確なスケッチを描くには大きな width が必要となり，入力するキーが多ければ大きな width が必要となります．しかし，width を大きくすると，メモリ使用量が増えるだけでなく，キャッシュミスも増えてしまいます．

残るパラメータである depth については，width と同じく精度に影響を与える存在であるものの，Madoka では固定値を採用しています．具体的には madoka::SKETCH_DEPTH （3）です．この値は，実装の都合と実験の結果を勘案して選択しました．

depth の固定によってパラメータを減らした代わりに，Madoka は新たなパラメータとして max_value を採用しています．max_value はスケッチに保存できる値の上限であり，小さい値を指定することによってスケッチのメモリ使用量を抑えることができます．

特製のスケッチが欲しいときは，create() に対して width と max_value を指定します．以下の情報を参考に，いろいろと試してみてください．

サンプルでは，特製のスケッチを作成した後，そのサイズを出力しています．スケッチのサイズについては，max_value が madoka::SKETCH_MAX_MAX_VALUE であれば width x 8 によって，max_value が madoka::SKETCH_MAX_MAX_VALUE でなければ width x depth x log2(max_value + 1) / 8 によって計算できます．

Clear a sketch

#include <iostream>

#include <madoka.h>

int main(int argc, char *argv[]) {
  madoka::Sketch sketch;
  sketch.create();

  sketch.set("Sayaka", 6, 100);
  sketch.clear();
  std::cout << "Sayaka: "
            << sketch.get("Sayaka", 6) << std::endl;
  return 0;
}

$ g++ clear-a-sketch.cc -lmadoka
$ ./a.out
Sayaka: 0

madoka::Sketch にはスケッチを白紙の状態に戻すためのインタフェースがあります．サンプルでは，作成したスケッチに更新を加えてから白紙に戻し，更新によって 100 になった値が 0 に戻っていることを確認しています．

Copy a sketch

#include <iostream>

#include <madoka.h>

int main(int argc, char *argv[]) {
  madoka::Sketch sketch;
  sketch.create();

  sketch.set("Kyoko", 5, 100);

  madoka::Sketch snapshot;
  snapshot.copy(sketch);

  sketch.add("Kyoko", 5, 50);

  std::cout << "Kyoko (original): "
            << sketch.get("Kyoko", 5) << std::endl;
  std::cout << "Kyoko (snapshot): "
            << snapshot.get("Kyoko", 5) << std::endl;
  return 0;
}

$ g++ copy-a-sketch.cc -lmadoka
$ ./a.out
Kyoko (original): 150
Kyoko (snapshot): 100

madoka::Sketch にはスケッチを複製するためのインタフェースがあります．サンプルでは，スケッチの複製をスナップショットとして残し，オリジナルのスケッチを更新しています．

サンプルでおこなっているように，copy() はメモリ上でスナップショットを作成する用途に使えます．スナップショットをファイルとして残したいときは，save() を使う方が簡単です．

Apply a filter

#include <iostream>

#include <madoka.h>

madoka::UInt64 divide_by_2(madoka::UInt64 value) {
  return value / 2;
}

int main(int argc, char *argv[]) {
  madoka::Sketch sketch;
  sketch.create();

  sketch.set("Kaname", 6, 8);
  sketch.set("Madoka", 6, 15);

  sketch.filter(divide_by_2);
  // sketch.filter([](madoka::UInt64 value) { return value / 2; });

  std::cout << "Kaname: "
            << sketch.get("Kaname", 6) << std::endl;
  std::cout << "Madoka: "
            << sketch.get("Madoka", 6) << std::endl;
  return 0;
}

$ g++ apply-a-filter.cc -lmadoka
$ ./a.out
Kaname: 4
Madoka: 7

madoka::Sketch にはフィルタという機能があり，誤差の抑制や減衰のシミュレーションなどに利用できます．サンプルでは，スケッチに含まれるすべての値を 1/2 にするフィルタを適用しています．

フィルタ機能を用いれば， Lossy Conservative Updates を実装することができます．また，カウンタが飽和したときに全体を 1/2 にすることでスケッチの延命を図るという使い方があります．さらに，すべての値を対数に変換することで圧縮するなどの使い方もあります．

Shrink a sketch

#include <iostream>

#include <madoka.h>

madoka::UInt64 logarithmize(madoka::UInt64 value) {
  return 63 - ::__builtin_clzll(value | 1);
}

int main(int argc, char *argv[]) {
  madoka::Sketch sketch;
  sketch.create(100);

  sketch.set("Akemi", 5, 256);
  sketch.set("Homura", 6, 16777216);

  madoka::Sketch new_sketch;
  new_sketch.shrink(sketch, 10, 15, logarithmize);

  std::cout << "width: "
            << new_sketch.width() << std::endl;
  std::cout << "max_value: "
            << new_sketch.max_value() << std::endl;

  std::cout << "Akemi: "
            << new_sketch.get("Akemi", 5) << std::endl;
  std::cout << "Homura: "
            << new_sketch.get("Homura", 6) << std::endl;
  return 0;
}

$ g++ shrink-a-sketch.cc -lmadoka
$ ./a.out
width: 10
max_value: 15
Akemi: 8
Homura: 15

madoka::Sketch にはスケッチを縮小するためのインタフェースがあります．スケッチの縮小は width と max_value の設定にも関わる機能です．

たとえば，スケッチに割り当てた width もしくは max_value が大きすぎると分かったときは，スケッチを縮小することができます．正確には，新たに小さなスケッチを作成して，既存のスケッチを構成する値を新しいスケッチに対して設定しなおすという手順になります．

サンプルでは，"Akemi: 256" と "Homura: 16777216" を描き込んだスケッチを縮小しています．新しいスケッチの width と max_value はそれぞれ 10 と 15 です．logarimize() をフィルタとして適用しているため，新しいスケッチから読み取ることができる値は対数になります．たとえば，"Akemi: 256" は "Akemi: 8" となります．ただし，新しいスケッチの max_value は 15 であることから，"Homura: 16777216" は "Homura: 15" となります．

スケッチを縮小できるという特徴により，描画の時点では大きめの width と max_value を採用し，描画の後で用途に応じた width と max_value を選ぶという使い方ができます．また，対数への圧縮や閾値による二値化など，さまざまな使い方が考えられます．

Merge sketches

#include <iostream>

#include <madoka.h>

int main(int argc, char *argv[]) {
  madoka::Sketch sketch_1, sketch_2;
  sketch_1.create();
  sketch_2.create();

  sketch_1.inc("Tomoe", 5);
  sketch_1.inc("Mami", 4);
  sketch_2.inc("Mami", 4);

  madoka::Sketch sketch;
  sketch.copy(sketch_1);
  sketch.merge(sketch_2);

  std::cout << "Tomoe: "
            << sketch.get("Tomoe", 5) << std::endl;
  std::cout << "Mami: "
            << sketch.get("Mami", 4) << std::endl;
  return 0;
}

$ g++ merge-sketches.cc -lmadoka
$ ./a.out
Tomoe: 1
Mami: 2

madoka::Sketch はスケッチの合成をサポートしています．スケッチの合成はベクトルの加算と同様の操作であり，一方のスケッチ（右）を構成する値を他方のスケッチ（左）を構成する値に足し合わせます．

サンプルでは，"Mami: 1" を描き込んだスケッチ同士を合成しています．そのため，合成により得られたスケッチからは "Mami: 2" を読み取ることができます．このサンプルでは copy() を使うことで元のスケッチを残していますが，上書きが問題にならない状況であれば，直接 merge() を呼び出しても問題ありません．

スケッチを合成する機能により，分散してスケッチを描画することができます．たとえば，入力を分割することができれば，それぞれに対するスケッチを描画してから合成することにより，最終的には一つのスケッチを得ることができます．

Estimate the inner product

#include <cmath>
#include <iostream>

#include <madoka.h>

int main(int argc, char *argv[]) {
  madoka::Sketch sketch_1, sketch_2;
  sketch_1.create();
  sketch_2.create();

  sketch_1.add("Charlotte", 9, 3);
  sketch_1.add("Oktavia", 7, 2);
  sketch_2.add("Gretchen", 8, 5);
  sketch_2.add("Charlotte", 9, 4);

  double length_1, length_2;
  double inner_product =
      sketch_1.inner_product(sketch_2, &length_1, &length_2);
  length_1 = std::sqrt(length_1);
  length_2 = std::sqrt(length_2);

  std::cout << "inner_product: " << inner_product << std::endl;
  std::cout << "length_1: " << length_1 << std::endl;
  std::cout << "length_2: " << length_2 << std::endl;
  std::cout << "cosine: "
            << (inner_product / length_1 / length_2) << std::endl;
  return 0;
}

$ g++ estimate-the-inner-product.cc -lmadoka
$ ./a.out
inner_product: 12
length_1: 3.60555
length_2: 6.40312
cosine: 0.519778

Count-Min sketch は内積の推定をサポートしています．madoka::Sketch には，内積の推定とともにスケッチの長さ（仮）を推定できるインタフェースがあります．実際にスケッチの長さという概念が存在するわけではありませんが，コサイン類似度の推定に用いることができます．

サンプルでは，描画したスケッチの内積を求めています．また，inner_product() の結果を用いてコサイン類似度を推定しています．

Configure memory mapping

namespace madoka {

enum FileFlag {
  FILE_CREATE    = 1 << 0,
  FILE_TRUNCATE  = 1 << 1,
  FILE_READONLY  = 1 << 2,
  FILE_WRITABLE  = 1 << 3,
  FILE_SHARED    = 1 << 4,
  FILE_PRIVATE   = 1 << 5,
  FILE_ANONYMOUS = 1 << 6,
  FILE_HUGETLB   = 1 << 7,
  FILE_PRELOAD   = 1 << 8
};

}  // namespace madoka

create(), open(), load(), save(), copy(), shrink() は path と flags を引数として指定できるようになっています．path に対して NULL を指定したときは，ファイルとの関連付けをせずにメモリを確保します．flags にはファイルの操作やマッピングの作成に関する振る舞いを指定することができます．

Use huge pages

#include <iostream>

#include <madoka.h>

int main(int argc, char *argv[]) {
  madoka::Sketch sketch;
  sketch.create(0, 0, NULL, madoka::FILE_HUGETLB);

  if (sketch.flags() & madoka::FILE_HUGETLB) {
    std::cout << "HugeTLB: on" << std::endl;
  } else {
    std::cout << "HugeTLB: off" << std::endl;
  }
  return 0;
}

$ g++ use-huge-pages.cc -lmadoka
$ grep HugePages_Free /proc/meminfo
HugePages_Free:        0
$ ./a.out
HugeTLB: off
$ sudo sysctl -w vm.nr_hugepages=512
vm.nr_hugepages = 512
$ grep HugePages_Free /proc/meminfo
HugePages_Free:      512
$ ./a.out
HugeTLB: on

概略を述べると，Count-Min sketch とは depth 個のハッシュ表を組み合わせたデータ構造です．そして，madoka::Sketch では depth を 3 に固定しているため，get() 以外の基本操作 set(), inc(), add() は 3 回の ランダムアクセス をおこないます．

スケッチの描画はランダムアクセスを必要とするため，スケッチが CPU キャッシュ に収まらなければ，キャッシュミスが発生するようになり， メモリのレイテンシ がボトルネックになります．さらにスケッチを大きくすると， TLB ミスが発生するようになり，描画のスループットを低下させてしまいます．

madoka::FILE_HUGETLB は HugePage の使用を許可するフラグです．HugePage を使えば，スケッチの描画における TLB ミスを減らすことができます．スケッチの作成に際して madoka::FILE_HUGETLB を指定すると，HugePage の使用を試みます．このとき，HugePage が使えない状況であれば，通常のページを使います．

サンプルは HugePage の使い方を示しています．まず，/proc/meminfo を見ることにより，HugePage が有効になっているかどうかを確認できます．無効になっているときは，/proc/sys/vm/nr_hugepages を編集することで有効にすることができます．HugePage を有功にするには root 権限が必要なことに注意してください．HugePage の有効な環境を用意できれば，madoka::Sketch で HugePage を使うことができます．ただし，ファイルと関連付けたスケッチについては，ファイルシステムが HugePage をサポートしていない限りは HugePage を使うことができません．詳細については， HugePage のサポートに関する情報 を参照してください．

Specify a seed

madoka::Sketch では，ハッシュ関数および疑似乱数生成器の種を指定することができます．指定方法は create() の第五引数です．既に存在するスケッチの種を変更することはできません．種の異なるスケッチ同士を合成することはできないという制約があるため，デフォルトの種に統一しておいた方が使いやすくなります．基本的に使わない機能です．

Get information of a sketch

Catch an exception

#include <iostream>

#include <madoka.h>

int main(int argc, char *argv[]) {
  madoka::Sketch sketch;
  try {
    sketch.create(madoka::SKETCH_MAX_WIDTH + 1);
  } catch (const madoka::Exception &ex) {
    std::cerr << "error: "
              << ex.what() << std::endl;
    return -1;
  }
  return 0;
}

$ g++ catch-and-exception.cc -lmadoka
$ ./a.out
error: madoka/sketch.cc:453: width > SKETCH_MAX_WIDTH

Madoka はエラーが起きると例外を投げます．例外のクラスは madoka::Exception です．サンプルは例外の捕まえ方を示しています．

サンプルでは，指定した width が大きすぎるため，create() が例外を投げます．エラーが起きたときは madoka::Sketch の内容が更新されないようになっています．

Draw a croquis

#include <iostream>

#include <madoka.h>

int main(int argc, char *argv[]) {
  madoka::Croquis<float> croquis;
  croquis.create();

  croquis.set("Madoka", 6, 1.25);
  croquis.set("Hiroshi", 7, 2.5);
  croquis.add("Madoka", 6, 0.5);

  std::cout << "Madoka: "
            << croquis.get("Madoka", 6) << std::endl;
  std::cout << "Hiroshi: "
            << croquis.get("Hiroshi", 7) << std::endl;
  return 0;
}

$ g++ draw-a-croquis.cc -lmadoka
$ ./a.out
Madoka: 1.75
Hiroshi: 2.5

madoka::Croquis は madoka::Sketch を単純化したクラスです．inc(), copy(), filter(), shrink(), merge(), inner_product() は使えません．その代わり，テンプレート引数によって値の型を指定することができます．

サンプルでは，madoka::Croquis</code> とすることにより， [浮動小数点数](https://ja.wikipedia.org/wiki/%E6%B5%AE%E5%8B%95%E5%B0%8F%E6%95%B0%E7%82%B9%E6%95%B0) を値の型として使っています．使い方は madoka::Sketch とほぼ同じですが，丸めによる誤差があるため，小さい値を add() に渡すと切り捨てられる可能性があることに注意してください．