Date: 2014-3-21
Tags: python, sphinx

Sphinxメンテナ日記: make gettextが超遅い話 (Issue #1426)

前置き: Sphinxのメンテナになって1年以上たったけど、その間に実装したこととか気づいたこととかもう忘れてきてるので、都度メモしておこうと思い立ちました。ということで、Sphinxメンテナ日記をつけることにしました。前置き終わり。

Sphinxのmake gettextはどうして遅いの？

元ネタ: Issue #1426

Sphinxのi18n機能 を使うために、 make gettext コマンドでドキュメントからpot/poファイルを作成します。 このとき make gettext の実行にかかる時間は、対象のドキュメント1ファイルあたりの大きさの2乗に比例します。 というのが Issue #1426 の話。

make gettext で生成されるpotファイルは以下のようになっています。

# a5600c3d2e3d48fc8c261ea0284db79b
#: ../../builders.rst:4
msgid "Available builders"
msgstr "利用可能なビルダー"

ここについてる # a5600c3d2e3d48fc8c261ea0284db79b は、この文字列に対して付けられるUUIDなのですが、 2回目以降の make gettext 実行時には前回のキャッシュ(_build/.doctrees)に保存されているrawsource(生文字列) と、新しくビルドしようとしているドキュメントのrawsourceとを全ノード間でレーベンシュタイン距離を計算して 一致するノードには新しいUUIDを付けないようにしています。

potファイルの用語で言うと、前回のpotファイル内の全てのmsgidと、今回のpotファイルの全てのmsgidの組み合わせについて、 msgidの値の類似度をレーベンシュタイン距離という計算方法を使って誤差率を算出しています。誤差率なので、完全一致したら0%。 あるmsgidの文字列が100文字あって1文字だけ違ったら(typoを直したとか)、誤差率1%という結果になります。 ソースはここ: https://bitbucket.org/birkenfeld/sphinx/src/73418c51/sphinx/versioning.py#cl-102

この結果を使って、新旧msgidの誤差率65%未満のもっとも誤差の低いものを同一とみなし、前回と同じUUIDをmsgidの前の行に付けて 出力しています。誤差が65%以上なら不一致とみなし、新しいUUIDを付けて出力します。

現在の実装で残念なのは以下の点です

  • 一度全てのmsgidの組について一致率を計算するので、O(n^2)の実装になっている。 ある時点のPython公式ドキュメントの一番大きいpotファイルはmsgidを15,000以上持っているので、 make gettext すると225,000,000組以上の誤差計算を実行する。

  • この誤差計算をOFFにするオプションが無い

  • make clean すると「前回の.doctrees」は消え、UUIDは失われ、全msgidについて新しいUUIDが生成されてしまう

  • 実際のところ transifex などのサービスを使って翻訳するので誤差とかどうでもいい

ということで改善案を考えてみました。

  1. 誤差率を計算しないオプションを追加する

  2. 誤差計算する場合、完全一致をPythonの辞書とか使って先に取り除く

  3. 誤差計算する場合、かつ.doctreesが無い場合、かつ出力先にpotがある場合、pot内のmsgidと突き合わせる

1をやれば大体の人が嬉しいはず。2をやれば互換性維持しつつ現実的な時間で終わる。3やればちゃんと運用もできるはず。

ということで、気が向いたらやります。

ちなみに

gettextでUUIDを出力するかどうかを指定する gettext_uuid オプションが pull request #217 で提案され取り込まれたので、 Sphinx-1.3から提供されます。しかし、これでOffにしても誤差率の計算自体は行うため、速度的なメリットはありません。

参考