番人

自作diffを少しでも速くするため、番人(sentinel)を試してみた時の話。
ここで言う「番人」とはループ内の条件判定の回数を減らすための特殊なデータを指す。


O(NP)のアルゴリズムを使った典型的なdiffプログラムには
以下のようなループ処理を行う箇所がある。

while (x < M && y < N && A[x] == B[y]) {
  ++x;++y;
}

Mは要素列Aの長さ、Nは要素列Bの長さで、
AとBのx番目とy番目の要素が同一である限りループを回す。
ただ、xとyの値が要素列の長さを超えてしまってはいけないので、
そのための条件判定(x < M && y < N)も必要になる。

しかし、AとBの最後に番人を配置すれば、
上記のループは以下のように書き直すことができる。

while (A[x] == B[y]) {
  ++x;++y;
}

実際の番人の値は、例えばAとBで互いに存在しない値を割り当てる。
これで条件判定が2つ減った。O(NP)の性質上、
上記のループ処理は結構な回数で実行されるので、
ここを最適化する余地はある(とさっきまで思っていた)。


以下のファイルの組合せに対して実行。

ファイル名と行数 追加 削除
a.txt:6351 b.txt:6463 1426 1314
c.txt:9107 d.txt:10452 1820 475


で、結果だが、全然速くならなかった。
そしてコードを元に戻してGCCの最適化オプションである-O2を指定したら0.1秒以上ぐらい速くなった。