FsAttoparsecとattoの内部構造が変わった話とか
私が FsAttoparsec を実装し始めた5月頃、実は本家 attoparsec は内部構造を新しいものに変更していたということに先月末気が付きました*1。 どういう変更かというのは
A major upgrade to attoparsec: more speed, more power | teideal glic deisbhéalach
これ読めばいいと思います。
というわけで、attoparsec の F# 移植である FsAttoparsec や Scala 移植で最近もメンテナンスされている atto も追随させたいと思って修正することにしました。
内部の状態に position を持たせる
とはいえ、F# や Scala は Haskell ではないし、パフォーマンス調査するのも面倒だなーということで内部構造のみ変更することにしました。 そのあたりの変更部分は
https://github.com/pocketberserker/FsAttoparsec/commit/5082a9aa6102b39ee31264aa734117b925be5c52
と
new internal design · 5082a9a · pocketberserker/FsAttoparsec · GitHub
で確認できます。 大雑把にいうと内部状態に position を持つようにしたのでいろいろ取れるようになったね、という。
ちなみにこの内部設計、attoparsec 的には第3世代らしい(前述の記事参照)。
atto のアレなところ?
attoparsec のセールスポイントの一つに"不完全な入力でも動作する"というものがあります。 が、atto の parse メソッドと parseOnly メソッドはその中で feed メソッドを呼び出してしまっているため、このポイントをつぶしているようにも見えるのでした。
(というかこれに気が付かずテストがこけて何事かと思った)
雑感
正直、 attoparsec みたいな実装は rankNtype があって濃度解析のような最適化が組み込まれていて Trampoline を差し込まなくてもスタックオーバーフローにならない言語でないと速度改善は厳しいのかなと。
いやまぁ、インターフェースのメソッドを inline 指定できるとか高速に動作する Trampoline があれば問題ないのですけど、それはちょっと難しそうだしなぁ…。
クラスベースでCPSな実装にした場合のパフォーマンス改善はなかなか難しい問題な気がしてます。
