Let's start Scheme

2018-09-16

JSON パーサ

JMESPathの実装をしていてJSONのパーサをPEGで書いた方が便利だなぁということに気付いたので実装してみた。仕様は最新のJSONの仕様(RFC8259)を参照することにした(別にjson.orgのでもよかったんだけど、なんとなく。どうせ一緒だろ?)。

どうでもいいのだが、「\」を使った文字列のエスケープがかなり制限されてる気がする。「\a」とか「\c(意味のないエスケープ)」とかは仕様に従うならイリーガルになるっぽい。どうしようかな?

書きあえるにあたって気になるのはもちろんパフォーマンス。以前使っていたPackratの実装だと現在の実装に比べて30倍程度遅い(参照: JSONパーサの性能改善)。ということで書いた後にベンチマークをとってみる。こんな感じのコードで測る。結論だけ先に言えば、現在の実装はかなり速いので、いろんな角度で速度を計測した。I/O有、I/O無等。
(import (rnrs)
 (text json parser)
 (text json)
 (sagittarius generators)
 (util file)
 (srfi :127)
 (time))

(define (parse parser) (call-with-input-file "large.json" parser))
(define-syntax time-parse
  (syntax-rules ()
    ((_ parser)
     (begin
       (newline) (display 'parser) (display " from file")
       (time (parse parser))
       (let ((in (open-string-input-port (file->string "large.json"))))
  (newline) (display 'parser) (display " in memory")
  (time (parser in)))))))

(time-parse json-read)
(time-parse parse-json)

(call-with-input-file "large.json"
  (lambda (in)
    (let ((lseq (lseq-realize (generator->lseq (port->char-generator in)))))
      (time (json:parser lseq)))))
結果は以下:
% sash -Lsitelib bench.scm
json-read from file
;;  (parse json-read)
;;  0.313142 real    0.313000 user    0.000000 sys

json-read in memory
;;  (json-read in)
;;  0.097882 real    0.109000 user    0.000000 sys

parse-json from file
;;  (parse parse-json)
;;  0.484309 real    0.531000 user    0.000000 sys

parse-json in memory
;;  (parse-json in)
;;  0.337894 real    0.344000 user    0.000000 sys

;;  (json:parser lseq)
;;  0.269573 real    0.266000 user    0.000000 sys
最初の二つが、現状の実装I/O有、I/O無。続いてPEG版のI/O有、I/O無、正格評価。何をどうひっくり返しても手作りの温かみのある実装に勝てないという結論に至る。I/O有で60%、I/O無で2.5倍のパフォーマンス劣化になることが問題になるかならないかというのもある。PEG(というかパーサコンビネータ)の性質上ある程度の性能劣化はしょうがないかなぁと思っていたが、ここまであるとなぁ。先にPEGの最適化をするべきかもしれない…

余談だが、PEGを使うとJSONパーサが30分程度で書けることが分かった。そろそろ手放せなくなってきたしドキュメント書かないとなぁ。