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

JSONデコード: トップダウン

common lisp algorithm speed

JSONのパーサを作ってみた。
参考にしたのは、ここここ


今回作成したのはトップダウン(再帰下降)型のパーサ。
ボトムアップ版もいつか作ってみたいという思いを込めて、タイトルに「トップダウン」と入れておく。
割合高速。

実装

ほぼJSONの仕様(?)通りに実装したつもり。 ※ 数値の扱いを除く

packageは定義していないが、使用者が操作する必要があるのは、read-json関数*read-buffer*変数のみ。

以下ソースコード
参照: nlet

;; inline宣言
(declaim (inline  char2hex read-char-skip-whitespace 2byte-code-char
                  char-json-whitespace? char-json-bool? char-json-number?))
 
;; パース時に使用するバッファ
;; サイズはプログラムが管理してくれないので、パース中に範囲外アクセスエラーが出る場合は、
;; 以下のように十分なサイズの配列でこの変数をバインドして、再度パースを行う必要がある
;; (let ((*read-buffer* (make-array large-size :element-type 'character))
;;    (read-json input-stream))
(defvar *read-buffer* (make-array 8192 :element-type 'character))

;;; 述語関数群
(defun char-json-whitespace? (ch)
  (case ch ((#\Space #\Tab #\Return #\Newline) t)))

(defun char-json-bool? (ch)
  (case ch (#.(coerce (remove #\Space (remove-duplicates "true false null")) 'list) t)))

(defun char-json-number? (ch)
  (case ch (#.(coerce "0123456789.eE-+" 'list) t)))

;;; read関連のutility関数群
;; 文字読み込み関数  ※先頭の空白文字は飛ばす
(defun read-char-skip-whitespace (input-stream)
  (loop FOR     ch = (read-char input-stream)
        WHILE   (char-json-whitespace? ch)
        FINALLY (return ch)))

;; 関数fnがnilを返すまで文字列を読み込む
(defun read-while (fn in &aux (i -1))
  (declare (fixnum i) (function fn)
           ((simple-array character) *read-buffer*))
  (loop FOR     ch = (read-char in nil #\Space)
        WHILE   (funcall fn ch)
        DO      (setf (aref *read-buffer* (incf i)) ch)
        FINALLY (unread-char ch in))
  (subseq *read-buffer* 0 (1+ i)))

;;; JSONパース関数群 
;; json
(defun read-json (in)
  (read-value (read-char-skip-whitespace in) in))

;; value
(defvar num-prefixs '(#\0 #\1 #\2 #\3 #\4 #\5 #\6 #\7 #\8 #\9 #\-))
(defun read-value (ch in)
  (case ch
    ((#\{)         (read-object  ch in))
    ((#\[)         (read-array   ch in))
    ((#\")         (read-string  ch in))
    (#.num-prefixs (read-number  ch in))
    (t             (read-boolean ch in))))

;; true,false,null
(defun read-boolean (ch in)
  (let ((tkn (read-while #'char-json-bool? in)))
    (case ch
      (#\t (and (string= tkn "rue")  (return-from read-boolean t)))
      (#\f (and (string= tkn "alse") (return-from read-boolean nil)))
      (#\n (and (string= tkn "ull")  (return-from read-boolean nil))))
    (error "~A~A is undefined literal" ch tkn)))

;; number  ※ read-from-stringにほぼ全てを任せているので、JSONには定義されていない数値も(common lispの数値として合法なら)読み込めてしまう
(defun read-number (ch in)
  (unread-char ch in)
  (let ((num (read-from-string (read-while #'char-json-number? in))))
    (check-type num number)
    num))

;; string
(defun read-string (ch in &aux (i -1))
  (declare (optimize (speed 3) (debug 0) (safety 0))
           (ignore ch) (fixnum i)
           ((simple-array character) *read-buffer*))
  (nlet self ((ch #1=(read-char in t)))
    (case ch
      ;; エスケープ文字
      (#\\ (setf (aref *read-buffer* (incf i))
                 (let ((ch2 (read-char in)))
                   (case ch2
                     (#\b #\Backspace) (#\f #\Page)   (#\t #\Tab)
                     (#\n #\Newline)   (#\r #\Return)
                     (#\u (read-utf16-char in))
                     (t ch2))))
           (self #1#))
      ;; 文字列終了
      (#\")
      ;; 通常の文字
      (t (setf (aref *read-buffer* (incf i)) ch)
         (self #1#))))
  (subseq *read-buffer* 0 (1+ i)))

;; 文字を16進数と解釈して数字に変換する
(defun char2hex (ch)
  (ecase ch
    (#\0 0) (#\1 1) (#\2 2) (#\3 3) (#\4 4) 
    (#\5 5) (#\6 6) (#\7 7) (#\8 8) (#\9 9)
    ((#\a #\A) 10)
    ((#\b #\B) 11)
    ((#\c #\C) 12)
    ((#\d #\D) 13)
    ((#\e #\E) 14)
    ((#\f #\F) 15)))

;; UTF-16beの値を、characterに変換する  
;; sbclの場合は、code-charを呼び出すだけで大丈夫
;; ※ 処理系依存部分
(defun 2byte-code-char (2byte-code)
  (code-char 2byte-code))

;; "\u0061"といったようなエスケープされたユニコード文字を読み込む
(defun read-utf16-char (in)
  '#1=(the (unsigned-byte 8) (char2hex (read-char in t)))
  (2byte-code-char (logior (ash #1# 12) (ash #1# 8) (ash #1# 4) #1#)))

;; pair = "key":value
(defun read-pair (ch in)
  (assert (char= ch #\") () "object key must start with ~S ." #\")
  (cons (prog1 (intern (string-upcase (read-string #\" in)) :keyword)
          (assert (char= (read-char-skip-whitespace in) #\:) () 
                  "object key and value must be delimited by ~S ." #\:))
        (read-value (read-char-skip-whitespace in) in)))

;; object, array
           ;; 共通部分
(macrolet ((common-block (read-fn end-ch &rest err-msgs)
             `(let ((ch #1=(read-char-skip-whitespace in)))
                (unless (char= ch ,end-ch)
                  (do ((seq (list (,read-fn ch in)) (cons (,read-fn #1# in) seq))
                       (ch #1# #1#))
                      ((char/= ch #\,)
                       (assert (char= ch ,end-ch) () ,@err-msgs)
                       (nreverse seq)))))))
  ;; object
  (defun read-object (ch in)
    (declare (optimize (speed 3) (debug 0) (safety 0))
             (ignore ch))
    (common-block read-pair  #\} "missing close brace (~S)." #\}))

  ;; array
  (defun read-array (ch in)
    (declare (optimize (speed 3) (debug 0) (safety 0))
             (ignore ch))
    (common-block read-value #\] "missing close bracket (~S)." #\])))

使用例

> (with-input-from-string (in "[1,\"2\",-3.2,true]") (read-json in))
--> (1 "2" -3.2 t)  ; 配列はlistとして返す

> (with-input-from-string (in "{\"1\":2, \"3\":4}") (read-json in))
--> ((1 . 2) (3 . 4)) ; オブジェクトは連想リストとして返す

> (with-input-from-string (in "[1,{\"2\":3},4]") (read-json in))
--> (1 ((:|2| . 3)) 4)

比較

今回作成したJSONパーサの処理速度を、cl-json(common lispJSONライブラリ)及びJsonCpp(C++の...)と比較してみる。

テスト用のC++ソースは以下の通り。 ※JsonCppがインストールされていることが前提
参照: mmap_t

// COMPILE: g++ -O3 -otest test.cc -l json
// USAGE:   test json_filepath loop_count
#include <json/json.h>
#include "mmap_t.h"

main(int argc, char** argv){
  Json::Reader reader;
  Json::Value  value;

  mmap_t mm(argv[1]);
  for(int i=0; i < atoi(argv[2]); i++)
    reader.parse((const char*)mm.ptr, (const char*)mm.ptr+mm.size, value);  
}


cl-jsonとread-jsonでは、以下のようにしてテストを行う。

;; 補助関数: ファイル読み込み
(defun read-file (path)
  (with-output-to-string (out)
    (with-open-file (in path)
      (let ((io (make-echo-stream in out)))
	(unwind-protect
	    (loop while (read-line io nil nil))
          (close io))))))

(defun test-json-parser (fn json-file loop-count)
  (let ((json-text (read-file json-file)))
    (time 
      (dotimes (i loop-count)
        (with-input-from-string (in json-text)
          (funcall fn in))))))
   
;; cl-json
(require :cl-json)
> (test-json-parser #'json:decode-json "/path/to/json" 10)

;; read-json
> (test-json-parser #'read-json "/path/to/json" 10)

;; 参考までに、単純にread-charを繰り返すだけの関数も定義し、比較する
(defun read-char-loop (input-stream)
  (loop while (read-char input-stream nil nil)))

> (test-json-parser #'read-char-loop "/path/to/json" 10)
比較1: 大きなJSONデータのパース速度

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


【結果】

処理時間(秒)処理時間中のGC時間(秒)
JsonCpp3.263計測不能
read-char0.1920.000
read-json0.6360.208
cl-json7.4870.893

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

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


【結果】

処理時間(秒)処理時間中のGC時間(秒)
JsonCpp0.317計測不能
read-char0.1190.000
read-json0.2620.008
cl-json1.5130.040

###

実装した機能が最低限ということもあってか、JsonCppよりも、今回実装したread-json関数の方が速かった。

単純にread-charを繰り替えした場合に比べても(GC時間の除けば)、約2倍程度の時間しか掛かっていないので、結構良い感じに実装できたのではないだろうか。

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

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