C/MigemoのOCaml実装を作ってみた #OCaml

Tableauで利用するSQLのチューニングはつかれました（挨拶

タイトルのとおりですが、Ruby/MigemoのC言語実装である C/Migemo のOCaml実装を作成しました。

こんな感じで使えます。

module M = Migemocaml

let migemo_dict = "migemo-dict"
let hira_to_kata = "hira2kata.dat"
let roma_to_hira = "roma2hira.dat"
let han_to_zen = "han2zen.dat"

let () = match M.Dict_tree.load_dict migemo_dict with
    | None -> begin Printf.printf "Dict can not load: %s\n" dict_file; exit 1 end
    | Some migemo_dict -> begin
        let hira_to_kata = M.Dict_tree.load_conv @@ Filename.concat !dict_dir hira_to_kata
        and romaji_to_hira = M.Dict_tree.load_conv @@ Filename.concat !dict_dir roma_to_hira
        and han_to_zen = M.Dict_tree.load_conv @@ Filename.concat !dict_dir han_to_zen
        in
        let migemo = M.Migemo.make ~dict:migemo_dict ?hira_to_kata ?romaji_to_hira ?han_to_zen () in
        Printf.printf "Result of query: aiueo -> %s\n" @@ M.Migemo.query ~query:"aiueo" migemo
      end

ここでは、なんで作ったのか？というのをつらつらと書いていこうかと思います。

Migemoとは

Emacs/Vimなどを利用している日本人の方は、一回は見たことがある（気がする）とは思います。

Ruby/Migemoのサイト

非常に簡単に紹介すると、ローマ字で入力した日本語をいい感じに検索できるようにできるライブラリです。簡単すぎてミスリードしそうですが。

日本人で日本語を利用する場合、大体はいれといた方がいい、と言われるソフトウェアです。

なんでOCaml実装を作ったのか？

もともとC言語版であるC/Migemoを年単位で利用していましたし、 fenrirというファイラだったり、内骨格というファイラだったりでサポートされているのを利用していたりしました。

これらは、公式ページで配布されているDLLを利用していますし、Emacs/Vimであれば各環境向けにコンパイルされた実行ファイルを利用しています。

C言語で作成されているため、各環境向けのライブラリがあれば、利用する言語から呼び出すことは難しくはありません。

それでもOCaml実装を作成したのは、非常に個人的な理由があります。

OCamlのシングルバイナリを配布したい
OCamlをマルチプラットフォームで配布したい
環境別にライブラリを用意するのがしんどい
- amd64だったりdarwinだったりMsys2だったり
- Pure OCamlなライブラリだったら、そのままコンパイルするだけ

これらを解決する一番簡単な手段は何か？としたときに、 C/MigemoをOCamlで実装してしまえばいいやん と（何故か）なったので、実装してみました。

正直、かなり枯れたライブラリであるC/Migemoを利用しない、ということ自体がリスクです。が、最悪自分で利用するだけなので、まぁ自分でなんとかすればいいや、という軽い感じで作ってしまったというのが実際です。

OCaml実装の目標

Migemoは実際には正規表現を生成するためのライブラリなので、実際の検索速度は、正規表現を実行するライブラリの速度に左右されます。

蛇足ですが、移植する前は、てっきりMigemo自体で検索もしていると勘違いしていたので、移植しようとソースを見たときに「あれ？少なくね？」となりました。観察してればそんなことないだろうに・・・

しかし、Migemoでの正規表現生成が遅ければ更に遅くなるので、最低限C/Migemoと遜色の無い速度にすることを最低限の目標としました。

それに加えて、

可能な限り依存ライブラリを減らす
- 理想はpervasiveだけに依存
- C stubも利用しない
C/Migemoの辞書をそのまま利用する
- ここを再実装する必要はないと感じたので・・・

ということも目標として掲げました。（どこにも書いてないけど

実装してみて

結論としては、以下のような実装にすることができました。

外部依存ライブラリゼロ
- 実際にはMenhirとocamllexを利用していますが、parser/lexerの生成に利用しただけで、実行時には不要です
C/Migemoの辞書に100%対応
- ローマ字/ひらがな/カタカナ変換にも対応しています
UTF-8のみのサポート
- SJIS/EUC-JPは完全に捨てました。一応対応できるような余地は残してはいますが・・・
速度
- 後ほど。

実装に当たっては、C/Migemoの実装を盛大に ~~パクって~~ 参考にさせていただきました。久しぶりにC言語のpointerを使いまくったソースを読んだら疲れました・・・。

肝心の速度ですが、ものすごい荒いベンチマークでは、正規表現の生成だけみれば、C/Migemoとほぼ変わらない速度にできました。（ocamlopt版

以下が実際に実行時間を取得したときのものです。内容としては、ランダムなwordを100個生成して、それに対応する正規表現を生成し終わるまでの時間を計測しています。

複数回やってないし平均も中央も何も取ってないので参考値ですが・・・。ちなみに、C/Migemoでは辞書の読み込みのみに約0.3秒、migemocamlでは約1.6秒かかるので、下の時間からその時間を引いた時間が、実際にクエリを作成した時間になります。

Benchmark for C/Migemo
Word size: 2
C/Migemo:

real    0m1.259s
user    0m1.160s
sys     0m0.066s
Migemocaml:

real    0m2.653s
user    0m2.521s
sys     0m0.083s
Word size: 4
C/Migemo:

real    0m1.549s
user    0m1.488s
sys     0m0.046s
Migemocaml:

real    0m2.668s
user    0m2.575s
sys     0m0.066s
Word size: 8
C/Migemo:

real    0m1.408s
user    0m1.364s
sys     0m0.030s
Migemocaml:

real    0m2.857s
user    0m2.730s
sys     0m0.092s
Word size: 16
C/Migemo:

real    0m2.204s
user    0m2.149s
sys     0m0.033s
Migemocaml:

real    0m3.592s
user    0m3.454s
sys     0m0.083s

C/Migemoは内部で二分木構造を利用しており、Migemocamlでもそのデータ構造を踏襲しています。この木構造が速度の秘訣っぽいです（Ruby/Migemo版は見てないので、どうなってるかわかりませんが・・・

苦労した/楽だった点

苦労したところ：

unsigned char* を直接いじるパース処理の移植
- C/Migemo自体、特に外部依存を持っておらず、辞書の読み込みなども全部自前で実装されています。ここをocamllex/menhirに移植するのが、かなり辛いところでした。結構アクロバティックな実装（個人的な感想です）になってしまった感がありますが、menhir/ocamllexがあって助かりました。
- 現在は、C/Migemoがスクリプトで生成した辞書を無加工で読み込むことができるようになっています。生成スクリプトは独自、だと普通に使いづらいというか面倒なので。
whileループで実装されたものを末尾再帰になるように構成し直す
- 型パズルならぬ再帰パズルじみていて面白くも辛い点でした。いい訓練になるので、whileループの移植はおすすめです。
- （OCamlの場合、whileループもあるので、ref + whileループでそのまんま実装するという荒業もできます。

楽だったところ：

memory管理からの解放
- C/Migemoのソースの、おおよそ1/4弱（個人的な感覚）が、データ構造のmalloc/free管理で占められていました
- OCamlの方が高いレイヤーにあるので、これはやっぱり楽になります
nullフリー
- やはりnullチェックからは逃げられないC言語ですが、OCamlではnullという概念自体が無いので、ここもチェックを大幅に簡略化できました
- その分、Some/Noneのmatchが増えているので、実はあんまり変わんないという説も

あんまり変わんなかったところ：

文字列操作
- OCamlのstring型は、最近のモダン言語とは違って、原則単なるバイト列＝unsigned char* と変わりません
- なので、境界を意識しながらなんやかやする必要はありますし、ちゃんとUTF-8のバイトであることを把握したりする必要があります

今回の移植では、どうしても文字列操作の比重が多いので、なんかあんまり楽になった気が・・・。

これから

最低限の実装と、性能の確保はできたので、基本的には個人で利用していこうと思っています。（生成される正規表現が基本的に同一なのは確認しています

ただ、以下の点は改善していきたいところです。

辞書の読み込み速度改善
- profileを取ったところ、GCと文字列の部分参照、辞書の構築処理そのものに時間がかかっているところまではわかっています
- GCを何とかするのは割と難しいのですが、辞書の構築処理については改善できそうな目処は立っています
- ただ、辞書は大抵最初に一回読み込んでしまえば終わりなので、正直優先度は高くないです
ドキュメント
- 自分が利用するのでも、書いておかないと確実に忘れることうけあいなので

まとめ

C言語実装をOCamlに移植する場合、ポインタを駆使して記述されたものを翻訳する作業が必要です。むしろ仕様だけからOCaml版を作成する方が、OCamlとして正統な作り方になるかもしれません。

しかし、OCamlはいい意味で懐の広い言語なので、C言語っぽく書きつつあとでなんとかする、というのが容易いです。普通にFFIを書くのが一番手っ取り早いのは認めます・・・。

広く使われているライブラリを、別の言語で再実装してみる、というのは学びが多いと思います。自分で利用したいという欲求を満たすためだけに再実装するのもどうかと思いますが、小さいライブラリを移植してみたりするのもいいんじゃないかと思います。