JSONデコード: C++
数日前に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.192 | 0.000 |
read-json(lisp) | 0.636 | 0.208 |
json(C++) | 0.816 | 0.327 ※メモリ解放所要時間 |
比較2: 小さなJSONデータのパース速度
【条件】
8KB程度のJSONデータ*2に対して、それぞれ1000回ずつパースを行う。
【結果】
処理時間(秒) | 処理時間中のGC時間(秒) | |
read-char(lisp) | 0.119 | 0.000 |
read-json(lisp) | 0.262 | 0.008 |
json(C++) | 0.108 | 0.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列に変換する部分の処理時間は含まれていないので、実際の場面では、もう少し余計に時間が掛かるものと思われる。
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