以前 Microsoft が出した Mison という JSON の高速なパーサに関する論文を読んだ。
Mison は普通のパーサと違って1文字ずつ読んで構造を解釈するのでなく、bitmap をフィールドの位置の特定を高速化し、さらにある程度パターンが読めてきたらフィールド位置の投機的な推測まで行う(「これまでの傾向からいけば.x.y
は3番目にあるだろう」的な感じ)。JSON ログのストリーム処理のような、構造にブレが少なく、興味あるフィールドも固定されているのようなユースケースに向いているという触れ書き。
せっかく読んだのでなにかで実装していたいと思い、とりあえず Go で実装してみることにした。*1
進捗としては structual index を構築するところまではでき、与えられた queried fileds を取り出すところを実装中。
とりあえず現時点での疑問点は以下の通り
- queried fields 値は非 object な値を想定している?
- 「不正な JSON もある程度受け付けてしまう」という認識であっている?