バージョン管理システムのdiffのパフォーマンス測定

日誌

最近、C++でdiffを書いているせいか、バージョン管理システムで使われているdiffのパフォーマンスが気になったので、調べてみた。バージョン管理システムにおいてdiffはかなり重要である。というのも、diffもしくはそれに相当する処理は単に差分を表示する際だけでなく、updateやmerge時の差分適用など、至るところで行われるので、diffが遅いとバージョン管理システムにおけるありとあらゆる動作が遅くなってしまうからだ。

測定に使用したバージョン管理システム

測定に使用したバージョン管理システムは以下の通り。

ちなみに上記のソフトを選択した理由は単に自分が普段から検証も含めて使用しているというだけです。

準備

まず、以下のような2種類のファイルの組合せを用意する。

Type ファイルAの行数 ファイルBの行数 追加 削除
S 9107 10452 1855 510
L 9107 9770 9767 9105

Type Sは2つのファイルの差分が小さい場合の組合せ、
Type Lは2つのファイルの差分が大きい場合の組合せ、
「追加」と「削除」はSES(Short Edit Script)における「追加」と「削除」の数を表す。これで、リポジトリにファイルAをコミットした後、ファイルAの内容をファイルBに差し替えた状態で、

$ time svn diff A # Subversion
$ time mtn diff A # Monotone
$ time git diff A # Git
$ time hg  diff A # Mercurial

という具合にdiffを実行する。バージョン管理システムによってはdiffを外部のプログラムに差し替えることができるものがあるが、この測定では基本的に各バージョン管理システムに内蔵されているdiffを使用。

環境

測定結果

測定結果は以下の通り。

バージョン管理システム名 アルゴリズム Type S's Time(sec) Type L's Time(sec)
Subversion O(NP) 0.162 1.912
Monotone O(NP) 0.546 14.800
Git O(ND) 0.141 0.473
Mercurial Gestalt Approach 0.222 0.465

Type Sに対しては(monotoneは比較的遅いが)どれも十分速く動作した。ただ、差分の量が大きくなると、結構な差が出てくる。特にO(NP)を採用しているSubversionとMonotoneはほかのと比べて、ファイル間の差分が大きい時の速度の劣化が激しい。これはO(NP)のアルゴリズムが、2つの要素列が似通っている場合に効率的に差分を計算する構造になっていることに起因する。つまり全然違う要素列を比較したら途端に遅くなる。(しかし、Monotoneはちと遅すぎな気が。14秒って)

Gitのdiffが速い理由

2つの要素列が似通っている場合に効率的に動作するという点では、O(ND)も同様なのだが、Gitで使われているLibXDiffはGNU diffutilsと同じく、O(ND)のアルゴリズムに対して、ヒューリスティクスを用いて精度を落とすと同時に計算量を落としているので、かなり速い。しかし、ヒューリスティクスを用いるということは正確な解が得られなくなる可能性があるわけなのだが、これって単純に正確なLCSやSESが得られないというだけで、差分の適用自体は問題なくできるという理解でいいのかな？いや、そうじゃないとpatch当てれなくて困るから大丈夫なんだと思いますが。あと、この方法ってO(NP)にも応用できないかなあ？

Mercurialのdiff

Mercurialで使われているGestalt Approachについては、まだ、あんまり真面目に資料読んでないので、実際の計算量とかはよくわかってないけど、上記の実験結果を見る限りではGitとほぼ同じ。Mercurialのdiffは実はPythonに標準搭載されているdifflibをそのまま使っているんだが*1、このdifflib、最初からUnified Formatをサポートしたりしていて、実はかなり便利だったりする。しかも速いし。

*1:difflibはimportしてるけど、unified_diffは使っていない