読者です 読者をやめる 読者になる 読者になる

JSONデコード: C++

common lisp C++ algorithm speed

数日前にcommon lispでJSONパーサを実装したが、そのC++版を書いてみた。

実装的には、common lisp版とほとんど変わらないが、サロゲート・ペアに対応したり、エンコード関数も(おまけ程度)に作成したり、と若干以前よりは高機能になっている。

ソースコードは、全部で350行程度あるので、それは末尾に掲載するとして、先にcommon lisp版との処理速度を比較してみる。

テスト用のコードは以下の通り。
参照: mmap_t

// json.cc
// COMPILE: g++ -O3 -ojson json.cc
// USAGE  : json <json-file> <loop-count>
#include <iostream>
#include "mmap_t.h"
#include "json.h"

main(int argc, char** argv) {
  mmap_t mm(argv[1]);
  const char* beg=(const char*)mm.ptr;

  int loop_count = atoi(argv[2]);
  
  for(int i=0; i < loop_count; i++) {
    // デコード
    json::value v = json::decode(beg,beg+mm.size);
    
    // エンコード
    // std::coutに、JSON形式で出力する
    // json::encode(v,std::cout);

    // メモリ解放
    v.delete_all();
  }
}

比較結果

common lisp用のテストコード等はこっちを参照

比較1: 大きなJSONデータのパース速度

【条件】
1.5MB程度のJSONデータ*1に対して、それぞれ10回ずつパースを行う。


【結果】

処理時間(秒)処理時間中のGC時間(秒)
read-char(lisp)0.1920.000
read-json(lisp)0.6360.208
json(C++)0.8160.327 ※メモリ解放所要時間

比較2: 小さなJSONデータのパース速度

【条件】
8KB程度のJSONデータ*2に対して、それぞれ1000回ずつパースを行う。


【結果】

処理時間(秒)処理時間中のGC時間(秒)
read-char(lisp)0.1190.000
read-json(lisp)0.2620.008
json(C++)0.1080.006 ※メモリ解放所要時間

####

大きなJSON文字列に対しては、common lisp版の方が速く、小さなJSON文字列に対してはC++版の方が速い結果となった。
もう少し大きな差が出るかと思っていたのだが、C++版とcommon lisp版で、それほど極端な違いはなかった。


ただ、二つ目の比較では、common lisp(read-char関数を使い)文字列を単純に走査している間に、C++ではJSONのパースも含めた処理が終わってしまっている。
(一つ目の結果で何故common lisp版の方が速かったのかは詳しく調べてないので分からないが)*3これを見るとやはり、基本的な操作の部分で、common lisp(sbcl)C++に比べて(速度的には)不利な感じがする。
あと、上の結果には、common lispでバイト列をcharacter列に変換する部分の処理時間は含まれていないので、実際の場面では、もう少し余計に時間が掛かるものと思われる。

C++ソースコード

ソースコード
いつものことながら、テストが足りないので、バグがありそう...。

UTF16→UTF8変換

// ucs2_to_utf8.h
// JSONの"\u0061"のような形式にエンコードされたUTF16文字のパース用
#ifndef UCS2_TO_UTF8_H
#include <string>

inline void ucs2_to_utf8(char fst, char snd, std::string &to) {
  if(static_cast<unsigned char>(fst)>=0x08) {
    to += 0xE0 | (0xF0&fst)>>4;
    to += 0x80 | (0x0F&fst)<<2 | (0xC0&snd)>>6;
    to += 0x80 | 0x3F&snd;
  } else if(fst!=0 || static_cast<unsigned char>(snd)>=0x80) {
    to += 0xC0 | (fst&0x7)<<2 | (snd&0xC0)>>6;
    to += 0x80 | 0x3F&snd;
  } else {
    to += snd;
  }
}

inline void surrogate_ucs2_to_utf8(char fst, char snd, char thd, char fth, std::string &to) {
  to += 0xF0 | 0x03&fst;
  to += 0x80 | ((0xFC&snd)>>2)+0x10;
  to += 0x80 | (0x03&snd)<<4 | (0x03&thd)<<2 | (0xC0&fth)>>6;
  to += 0x80 | 0x3F&fth;
}

// XXX: チェック不足
inline bool is_surrogate(char ch) {
  return static_cast<unsigned char>(ch)>=0xD8;
}

#endif

JSON

あんまり、使いやすさとかは考えていない。
上のテストコードと、valueクラス、encode関数を見れば、だいたい使い方は分かる(かもしれない)。

// json.h
#ifndef JSON_H

#include "ucs2_to_utf8.h"
#include <string>
#include <vector>
#include <map>
#include <cassert>
#include <ostream>

namespace json{
  // json用のstreamクラス
  class stream {
  public:
    stream(const char *beg, const char* end) 
      : cur_(beg), end_(end) {}

    char read()       { assert(!eof()); return *cur_++; }
    void unread()     { --cur_; }
    char peek() const { return cur_[0]; }
    char prev() const { return cur_[-1]; }
    bool eof()  const { return !(cur_ < end_); }
    const char* ptr() const { return cur_; }

    char read_skip_ws(){ skip_ws(); return read(); }
    void skip_ws() { 
      for(;;++cur_)
        switch(*cur_){
        case ' ': case '\t': case '\r': case '\n':
          break;
        default:
          return;
        }
    }
    
    bool token_end() const { 
      if(eof())
        return true;

      switch(*cur_) {
      case ' ': case '\t': case '\r': case '\n': 
      case '}': case ']':  case ',':
        return true;
      }
      return false;
    }
  private:
    const char *cur_;
    const char *end_;
  };
  
  // valueの型判別用の列挙型
  namespace type {
    enum ENUM {null,boolean,number,string,array,object};
  }

  // jsonのvalueクラス
  class value{
  public:
    value(type::ENUM t_, void* p_) :type(t_),p(p_) {}
    value(){}

    // pを指定された型にキャストする
    // ex] val.get<boolean>()
    template<class T>
    T get() { return static_cast<T>(p); }

    // value用に確保したメモリを再帰的に解放する
    void delete_all();

    type::ENUM type;

  private:
    void* p;
  };

  // json用に型を再定義
  typedef int                         null;
  typedef bool                        boolean;
  typedef double                      number;
  typedef std::string                 string;
  typedef std::vector<value>          array;
  typedef std::map<std::string,value> object;

  void value::delete_all(){
    switch(type){
    case type::string: delete get<string*>(); break;
    case type::number: delete get<number*>(); break;
    case type::array:
      {
        array* a = get<array*>();
        for(array::iterator it=a->begin(); it!=a->end(); ++it)
          it->delete_all();
        delete a;
      }
      break;
    case type::object:
      {
        object* o = get<object*>();
        for(object::iterator it = o->begin(); it != o->end(); ++it)
          it->second.delete_all();
        delete o;
      }
    }
  }

  // parse系の関数
  value parse_number(stream &in) {
    const char* beg=in.ptr()-1;
    for(char c=in.prev(); !in.eof(); c=in.read()) {
      switch(c){
      case '0': case '1': case '2': case '3': case '4':
      case '5': case '6': case '7': case '8': case '9':
      case '+': case '-': case '.': case 'e': case 'E':
        break;
      default:
        goto end;
      }
    }
  end:
    in.unread();

    string buf(beg,in.ptr());
    char* endp;
    double d = strtod(buf.c_str(), &endp);
    assert(endp==buf.c_str()+buf.size());
    return value(type::number,new double(d));
  }

  value parse_null(stream &in) {
    if(in.read()=='u' && in.read()=='l' &&
       in.read()=='l' && in.token_end()) {
      return value(type::null,0);
    }
    assert(false);
  }

  value parse_bool(stream &in, bool maybe_true) {
    if(maybe_true) {
      if(in.read()=='r' && in.read()=='u' &&
         in.read()=='e' && in.token_end()) {
        return value(type::boolean, reinterpret_cast<void*>(true));
      }
    } else {
      if(in.read()=='a' && in.read()=='l' &&
         in.read()=='s' && in.read()=='e' &&
         in.token_end()) {
        return value(type::boolean, reinterpret_cast<void*>(false));
      }
    }
    assert(false);
  }

  // 文字を16進数を解釈して、対応する数値を返す
  inline char char_to_hex(stream &in) {
    switch(in.read()) {
#define MAP(c,n) case c: return n;
#define MAP2(c1,c2,n) case c1: case c2: return n;
      MAP('0',0); MAP('1',1); MAP('2',2); MAP('3',3); MAP('4',4);
      MAP('5',5); MAP('6',6); MAP('7',7); MAP('8',8); MAP('9',9);
      MAP2('a','A',10); MAP2('b','B',11); MAP2('c','C',12); 
      MAP2('d','D',13); MAP2('e','E',14); MAP2('f','F',15);
#undef MAP
#undef MAP2
    default:
      assert(false);
    }
  }

  // 16進数表記の文字を二つ読み込み、数値(8bit)に変換する
  inline char read_hex(stream &in) {
    return char_to_hex(in)<<4|char_to_hex(in);    
  }

  // "\uXXXX"形式の文字列を読み込む(UTF-8に変換する)
  void parse_escaped_utf16_char(stream &in, string &s) {
    char fst = read_hex(in);
    char snd = read_hex(in);

    if(is_surrogate(fst)) {
      assert(in.read()=='\\' && in.read()=='u');
      surrogate_ucs2_to_utf8(fst,snd,read_hex(in),read_hex(in),s);
    } else {
      ucs2_to_utf8(fst,snd,s);
    }
  }

  value parse_string(stream &in, string &s) {
    const char* beg=in.ptr();
    for(char c=in.read();; c=in.read()) {
      switch(c) {
      case '\\':
        s.append(beg,in.ptr()-1);
        switch(in.read()) {
        case 'b': s += '\b'; break; case 'f': s += '\f'; break;
        case 't': s += '\t'; break; case 'r': s += '\r'; break;
        case 'n': s += '\n'; break;
        case 'u': parse_escaped_utf16_char(in, s); break;
        default:  s += in.prev(); 
        }
        beg=in.ptr();
        break;
      case '"':
        s.append(beg,in.ptr()-1);
        return value(type::string, &s);
      }
    }
  }

  value parse_value(stream &in);
  value parse_array(stream &in) {
    array *as = new array;
    if(in.read_skip_ws()!=']') {
      in.unread();
      do{
        as->push_back(parse_value(in));
      }while(in.read_skip_ws()==',');
      assert(in.prev()==']');
    }
    return value(type::array, as);
  }

  value parse_object(stream &in) {
    string buf;

    object *obj = new object;
    if(in.read_skip_ws()!='}') {
      in.unread();
      do{
        assert(in.read_skip_ws()=='"');
        parse_string(in,buf);
        assert(in.read_skip_ws()==':');
        (*obj)[buf]=parse_value(in);
        buf.clear();
      }while(in.read_skip_ws()==',');
      assert(in.prev()=='}');
    }
    return value(type::object, obj);
  }

  value parse_value(stream &in) {
    switch(in.read_skip_ws()) {
    case '{': return parse_object(in);                break;
    case '[': return parse_array(in);                 break;
    case '"': return parse_string(in, *(new string)); break;
    case 't': return parse_bool(in,true) ;            break;
    case 'f': return parse_bool(in,false);            break;
    case 'n': return parse_null(in);                  break;
    default:  return parse_number(in);                break;
    }
  }

  // decode
  value decode(const char *beg, const char *end) {
    stream in(beg,end);
    return parse_value(in);
  }

  void escape_output(const string& s, std::ostream& out) {
    bool need_escape=false;
    for(unsigned i=0; i < s.size(); i++) 
      switch(s[i]){
      case '\\': case '"': 
        need_escape=true;
        goto end;
      }
  end:
    out << '"';
    if(need_escape) {
      for(unsigned i=0; i < s.size(); i++) {
        switch(s[i]){
        case '\\': case '"':
          out << '\\';
        }
        out << s[i];
      }
    } else {
      out << s;
    }
    out << '"';
  }

  // encode
  void encode(value val, std::ostream& out) {
    switch(val.type) {
    case type::null:    out << "null";                            break;
    case type::boolean: out << val.get<boolean>()?"true":"false"; break;
    case type::number:  out << *val.get<double*>();               break;
    case type::string:  escape_output(*val.get<string*>(),out);   break;

    case type::array:
      {
        const array* as = val.get<array*>();
        out <<"[";
        for(array::const_iterator it=as->begin(); it!=as->end(); ++it){
          if(it!=as->begin())
            out << ",";
          encode(*i, out);
        }
        out <<"]";
      }
      break;
    case type::object:
      {
        const object* obj = val.get<object*>();
        bool first=true;
        out <<"{";
        for(object::const_iterator it=obj->begin(); it != obj->end(); ++it) {
          if(!first)
            out <<',';
          first=false;
          escape_output(it->first,out);
          out <<":";
          encode(it->second,out);
        }
        out <<"}";
      }
    }
  }
}
#endif

*1:夏目漱石の『こころ』をMeCab形態素解析した結果をJSON形式で保存したもの

*2:googleのWEB検索APIが返すJSON

*3:調べたわけではないので、単なる憶測だが、比較1で用いたJSONデータには、細かい配列(mecabの結果)が大量に含まれていたのが、関係があるかもしれない。JSON配列の表現として、C++ではstd::vectorを使っているの対して、common lispではlistを用いている。listの方が(印象的に)軽いし、動的な追加でも(あらかじめ必要なサイズが分からなくても)特に遅くなることがない。後は(結果にもそれらしい数字が出ているが)GCによるメモリ管理が効を奏した部分もあるのかもしれない。