2017/03/07


おなじみC/C++から使えるJSONライブラリを紹介するコーナー。まずは過去のまとめ。

ずいぶんと前から GitHub Trend の C++ 言語枠には登場していましたが、このコーナーでレビューしてませんでした。

GitHub - nlohmann/json: JSON for Modern C++

JSON for Modern C++

https://github.com/nlohmann/json

特徴(目指すところ)は以下の通り。

  • Python の様な操作感で、ファーストクラスオブジェクトの様に扱える事
  • シングルヘッダで他のライブラリに依存しない事
  • テストカバレッジ 100% を目指す

触ってみた感じ picojson に近いです。picojson よりもオペレータが沢山定義されているのでバイナリにした際には picojson よりも大きくなるかもしれません。今日はこの json.hpp を使って、wandbox の shebang コマンドを作ってみました。

wandbox は画面で入力したソースコードを多種多様なコンパイラやインタプリタを使って実行してくれるウェブサービスです。API が公開されているので扱いやすいインタフェースを自分で作る事ができます。

wandbox/API.rst at master - melpon/wandbox - GitHub

API API home is melpon.org/wandbox/api GET /list.json List compiler informations. Parameter Nothing....

https://github.com/melpon/wandbox/blob/master/kennel2/API.rst
#include <iostream>
#include <fstream>
#include "json.hpp"
#include <curl/curl.h>

size_t
write_cb(char *ptr, size_t size, size_t nmemb, std::string *strm) {
  size_t len = size * nmemb;
  strm->append(ptr, len);
  return len;
}

int
main(int argc, char* argv[]) {
  if (argc < 3) {
    std::cerr << "usage: " << argv[0] << " [compiler] [file] [arguments...]" << std::endl;
    return 1;
  }
  std::stringstream ss;
  if (std::string(argv[2]) != "-") {
    std::ifstream in(argv[2], std::ifstream::in);
    std::string line;
    std::getline(in, line);
    ss << in.rdbuf();
  } else {
    ss << std::cin.rdbuf();
  }

  nlohmann::json obj;
  obj["code"] = ss.str();

  ss.str("");
  ss.clear(std::stringstream::goodbit);
  obj["compiler"] = argv[1];
  for (int i = 3; i < argc; i++) {
    if (i > 3)  ss << "\n";
    ss << argv[i];
  }
  obj["runtime-option-raw"] = ss.str();

  ss.str("");
  ss.clear(std::stringstream::goodbit);
  ss << obj;

  std::string chunk;

  CURLcode ret;
  CURL *curl = curl_easy_init();
  if (curl == NULL) {
    std::cerr << "curl_easy_init() failed" << std::endl;
    return 1;
  }
  std::string data = ss.str();

  struct curl_slist *headerlist = NULL;
  headerlist = curl_slist_append(headerlist, "Content-Type: application/json");

  curl_easy_setopt(curl, CURLOPT_HTTPHEADER, headerlist);
  curl_easy_setopt(curl, CURLOPT_URL, "http://melpon.org/wandbox/api/compile.json");
  curl_easy_setopt(curl, CURLOPT_POST, 1);
  curl_easy_setopt(curl, CURLOPT_POSTFIELDS, data.c_str());
  curl_easy_setopt(curl, CURLOPT_WRITEFUNCTION, write_cb);
  curl_easy_setopt(curl, CURLOPT_WRITEDATA, &chunk);
  ret = curl_easy_perform(curl);
  curl_easy_cleanup(curl);

  if (ret != CURLE_OK) {
    std::cerr << "curl_easy_perform() failed" << std::endl;
    curl_easy_strerror(ret);
    return 1;
  }

  obj = nlohmann::json::parse(chunk);
  try {
    std::cout << obj["program_message"].get<std::string>();
  } catch(std::exception& e) {
    std::cerr << obj["compiler_message"].get<std::string>() << std::endl;
  }

  int code;
  ss.str("");
  ss.clear(std::stringstream::goodbit);
  ss << obj["status"];
  ss >> code;
  return code;
}

使い方は shebang として設定するだけで、第一引数にコンパイラもしくはインタプリタ名を設定します。

#!/usr/bin/wandbox-run clang-head

#include <stdio.h>

int
main(int argc, char* argv[]) {
  puts("hello clang");
  return 0;
}

こんな風に書いて実行権限を付けて実行すれば hello clang が表示されます。C言語のソースなのにコンパイラをインストールしなくても実行できて便利ですね(そうでもない)。なお扱えるコンパイラやインタプリタは wandbox から参照して下さい。ソースコードは以下に置いておきます。

mattn/wandbox-run · GitHub
https://github.com/mattn/wandbox-run

2017/02/27


元ネタはずいぶんと昔の記事なのだけど。

編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー

■ 編集距離 (Levenshtein Distance) 昨日 最長共通部分列問題 (LCS) について触れました。ついでなので編集距離のアルゴリズムについても整理してみます。 編集距離 (レーベン...

http://d.hatena.ne.jp/naoya/20090329/1238307757

思い付きはまったく関係ない所から。

これを週末にやってました。naoya さんの記事にも書かれている通り、Levenshtein Distance の実装はとてつもなく簡単。

GitHub - mattn/go-lsd
https://github.com/mattn/go-lsd

ついでにこれを使った grep コマンド作ったら面白いんじゃないかと思って O(N^2) になる事覚悟の上で実装してみた。

実装にあたってまず Unicode のクラスを識別する物を作った。

GitHub - mattn/go-unicodeclass

Unicode class package

https://github.com/mattn/go-unicodeclass

これは与えらえた rune が Unicode のどの部類に属するかを返すためのライブラリ。Vim のコードを一部参考にしました。もともとは bufio/scanner で与える区切り文字(デフォルトは改行)を Unicode のクラス区切りに出来ないかと思って実装しました。こんな風に使えます。

scan := bufio.NewScanner(strings.NewReader("本日は晴天なり"))
scan.Split(unicodeclass.SplitClass)
var got []string
for scan.Scan() {
    got = append(got, scan.Text())
}
// "本日", "は", "晴天", "なり"

まぁ結果的に言えば後で追加した unicodeclass.Split で十分事足りましたが。で、出来上がったのが lsdgrep。

GitHub - mattn/lsdgrep

lsdgrep Fuzzy Grep using Levenshtein String Distance

https://github.com/mattn/lsdgrep

これを使えば例えば

俺の名前は伊藤直哉だ
もしかしたら俺は伊藤直かもしれない
ちょっと待ってくれ佐藤直哉をお忘れではないか
こんばんわ佐藤B作です

こんなテキストに対して lsdgrep -d 3 伊藤直哉 を実行すると以下の様に「伊藤直哉」に近い単語がマッチする。しかも色付き!(ポイント高い)

lsdgrep

距離が3なのでマッチする単語も荒い。距離を1にするとそこそこ近い物がマッチする。

lsdgrep

いつもの事ながら研究材料なので実用的なものを作るつもりは無い。


2017/02/11


巷の噂で Ruby の Array#<<Array#push よりも速いと聞いたので調べてみた。まずはベンチマークを取ってみた。

require 'benchmark'

Benchmark.bm 10 do |r|
  r.report "push" do
    8000000.times do; [].push(1); end
  end
  r.report "<<" do
    8000000.times do; [] <<1end
  end
end

結果は以下の通り。

                 user     system      total        real
push         1.570000   0.000000   1.570000 (  1.579687)
<<           1.280000   0.000000   1.280000 (  1.288951)

確かに Array#<< の方が速い。実際何が違うのか調べてみる。

array.c のソースを見ると、確かに <<push は違う処理が行われていた。

<< の処理

<<rb_ary_push が呼び出されていて、pushrb_ary_push_m が呼び出されている。rb_ary_push (push と言いながら <<)は以下のコード。
VALUE
rb_ary_push(VALUE ary, VALUE item)
{
    long idx = RARRAY_LEN(ary);
    VALUE target_ary = ary_ensure_room_for_push(ary, 1);
    RARRAY_PTR_USE(ary, ptr, {
        RB_OBJ_WRITE(target_ary, &ptr[idx], item);
    });
    ARY_SET_LEN(ary, idx + 1);
    return ary;
}

ary_ensure_room_for_push で追加する領域を伸張し、RB_OBJ_WRITE で格納、ARY_SET_LEN で配列長を再設定している。RARRAY_PTR_USE は Array の実装で少量の場合とそうでない場合に VALUE の格納方法を変えており、それをシームレスに扱うためのマクロになっている。RB_OBJ_WRITE は実際は rb_obj_write でありコードは以下の通りになっている。

static inline VALUE
rb_obj_write(VALUE a, VALUE *slot, VALUE b, RB_UNUSED_VAR(const char *filename), RB_UNUSED_VAR(int line))
{
#ifdef RGENGC_LOGGING_WRITE
    RGENGC_LOGGING_WRITE(a, slot, b, filename, line);
#endif

    *slot = b;

#if USE_RGENGC
    rb_obj_written(a, RUBY_Qundef /* ignore `oldv' now */, b, filename, line);
#endif
    return a;
}

世代別 GC は有効なのでライトバリアされる事になる。

static inline VALUE
rb_obj_written(VALUE a, RB_UNUSED_VAR(VALUE oldv), VALUE b, RB_UNUSED_VAR(const char *filename), RB_UNUSED_VAR(int line))
{
#ifdef RGENGC_LOGGING_OBJ_WRITTEN
    RGENGC_LOGGING_OBJ_WRITTEN(a, oldv, b, filename, line);
#endif

#if USE_RGENGC
    if (!RB_SPECIAL_CONST_P(b)) {
        rb_gc_writebarrier(a, b);
    }
#endif

    return a;
}

push の処理

rb_ary_push_mrb_ary_cat をそのまま呼び出し

VALUE
rb_ary_cat(VALUE ary, const VALUE *argv, long len)
{
    long oldlen = RARRAY_LEN(ary);
    VALUE target_ary = ary_ensure_room_for_push(ary, len);
    ary_memcpy0(ary, oldlen, len, argv, target_ary);
    ARY_SET_LEN(ary, oldlen + len);
    return ary;
}

ary_ensure_room_for_push で伸長し、ary_memcpy0 で空いたところにコピーし、ARY_SET_LEN で配列長を再設定。<< とほぼ同じ。ただ ary_memcpy0 は単なる memcpy ではない。

static void
ary_memcpy0(VALUE ary, long beg, long argc, const VALUE *argv, VALUE buff_owner_ary)
{
#if 1
    assert(!ARY_SHARED_P(buff_owner_ary));

    if (argc > (int)(128/sizeof(VALUE)) /* is magic number (cache line size) */) {
        rb_gc_writebarrier_remember(buff_owner_ary);
        RARRAY_PTR_USE(ary, ptr, {
            MEMCPY(ptr+beg, argv, VALUE, argc);
        });
    }
    else {
        int i;
        RARRAY_PTR_USE(ary, ptr, {
            for (i=0; i<argc; i++) {
                RB_OBJ_WRITE(buff_owner_ary, &ptr[i+beg], argv[i]);
            }
        });
    }
#else
    /* giveup write barrier (traditional way) */
    RARRAY_PTR(buff_owner_ary);
    MEMCPY(RARRAY_PTR(ary)+beg, argv, VALUE, argc);
#endif
}

Array#push は一度に複数個の値を追加できる。

a = []
a.push 1,2,3,4,5

この個数が一定以上であればこのコードは異なる処理を行う。VALUE は実際は単なるポインタでしかない。uintptr_t なので8バイト。つまり push で一度に16個足すと rb_gc_writebarrier_remember でライトバリア用のマーキングが行われ、先ほど説明した RARRAY_PTR_USE で直接 VALUE のメモリを得て MEMCPY でメモリを書き込む。

反対側は << をループで回したのと同じコードになる。

ちなみに一度に2個の要素を追加するベンチマークも取ってみた。

require 'benchmark'

Benchmark.bm 10 do |r|
  r.report "push" do
    8000000.times do; [].push(1,2); end
  end
  r.report "<<" do
    8000000.times do; [] <<1<<2end
  end
end
                 user     system      total        real
push         1.570000   0.000000   1.570000 (  1.584534)
<<           1.620000   0.000000   1.620000 (  1.634777)

2個目から push の方が速くなった。

分かったこと

この2つを見て、<<push の速さを決める条件が3つある事が分かった。

  • 1個だけで << もしくは push する
  • 2個以上16個未満で push する
  • 16個以上で push する

最初の場合、<<push はフェアになる。ただし push の場合は上記の通り、一定個数以上で別の処理を行う為に条件文が1箇所あるのと1個の為にforループを回す処理がある。よって上記のベンチマーク結果の様に若干ではあるが << の方が速くなる。

次に16個未満の場合。コードの例だと以下。

require 'benchmark'

Benchmark.bm 10 do |r|
  r.report "push v1" do
    8000000.times do; [].push 0,1,2,3,4,5,6,7,8,9end
  end
  r.report "<< v1" do
    8000000.times do; [] <<0<<1<<2<<3<<4<<5<<6<<7<<8<<9end
  end
  r.report "push v2" do
    8000000.times do; [].push(0).push(1).push(2).push(3).push(4).push(5).push(6).push(7).push(8).push(9); end
  end
  r.report "<< v2" do
    8000000.times do; (((((((((([]<<0)<<1)<<2)<<3)<<4)<<5)<<6)<<7)<<8)<<9); end
  end
end

この場合、<< は一度に1つしか追加できないので <<push はフェアではない。

                 user     system      total        real
push v1      5.220000   0.010000   5.230000 (  5.276128)
<< v1        6.990000   0.000000   6.990000 (  7.050749)
push v2     10.000000   0.010000  10.010000 ( 10.098266)
<< v2        6.980000   0.000000   6.980000 (  7.198814)

純粋にインタプリタが実行する量に比例してしまう為、当然の事ながら push が速くなる。

最後に push の量が16個以上の時とそうでない場合。

require 'benchmark'

Benchmark.bm 10 do |r|
  r.report "push v1" do
    8000000.times do; [].push 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19end
  end
  r.report "push v2" do
    8000000.times do; [].push(0,1,2,3,4,5,6,7,8,9).push(0,1,2,3,4,5,6,7,8,9); end
  end
end

push を2回実行しているのでCの世界とRubyの世界を1回多く回っている分、フェアではないけれどベンチマークを取ってみた。

                 user     system      total        real
push v1      5.760000   0.000000   5.760000 (  5.817951)
push v2      6.320000   0.010000   6.330000 (  6.404566)

想像通り、16個以上の場合の方が早くなった。

まとめ

今回の調査で以上の事が分かった。

Array に要素を足す場合

  • 1個であれば << の方が速い
  • 2個以上であれば push の方が速い

ただしベンチマーク結果から分かる様に、ループ回数が多いので差が出ている様に見えるが実際大した差ではないので書きやすい方で書いたらいい。

なお、mruby の場合 <<処理push処理は同じだった。ベンチマークも想像通り。

5000000.times do; [].push(0,1,2,3,4,5,6,7,8,9); end
5000000.times do; [].push 0<<1<<2<<3<<4<<5<<6<<7<<8<<9end
$ time bin/mruby.exe push1.rb

real    0m5.574s
user    0m0.000s
sys     0m0.015s

$ time bin/mruby.exe push2.rb

real    0m9.412s
user    0m0.015s
sys     0m0.000s