fision を高速化2007年06月05日 12時48分04秒

fision: 同一内容のファイルを単一 i-node にまとめるプログラムを更新した。もし、興味のある方は、fision-20070604.tar.bz2 に公開されている。

久しぶりにディスクの容量が、窮地に陥った。消しても、消しても、まだ容量が足りないのだ。そこで、同じ内容のファイルを i-node を同じにして、消してしまおうという魂胆だ。

前回は、実際に動作するのを確認するための作業だったので、非効率なところは目をつぶっていた。今回は、久しぶりに使うとは言え、遅さに閉口したので、高速化を試みた。

このプログラムは、最初に全てのディレクトリを走査して、全てのファイルの名前を探す。その時にファイルは、デバイス ID とファイルのサイズを元に分類される。この二つが片方を削除して i-node を入れ換えるための最低条件だからだ。ここの部分は、単純に配列を作って、新しい組合せの度に最後に追加していただけだった。そのため、検索が遅い。実際に、この部分のディスクの利用率は 1% を切り、CPU が 100% を占めているのだった。

そこで、この部分を新しい対を追加する度に qsort でソートして、bsearch で検索をするようにした。bsearch だけあって、10 倍以上速くなったが、それでもまだディスクの利用率が低い。まあ、一つ新しい対を入れる度に qsort をしているのだから当り前だ。クイックソートは、どの様な値であっても、効率を損なわずに log(N) でソートできる。しかし、既にソートしてあっても、log(N) がかかるのである。ソートするデータに関しての知識が無い場合は、効率がいいのだが、今回の条件には当てはまらない。

そこで更に、binsert を作成。二分木検索で、挿入場所を探して入れる。基本的に二分木検索なので log(N) で済む。qsort から約 N 倍の効率化だ。

これで、ディスクの利用率が最低でも 60% になった。このプログラムは三段階に分かれて実行されるが、第一段階に劇的な効果をもたらした。

もう一つ、気が付いたのが、第二と第三段階でスワップアウトがかなり多い。そこから推測出来るのが、free でメモリを開放した後の NULL の代入だ。もし、一度スワップアウトされたページが、スワップから読み込まれることがある。もし、次にスワップアウトされるまでに、メモリに変更が無かった場合は、わざわざスワップ領域にこのデータを書き込まなくても、既にスワップに残っているので、メモリ上からそのまま破棄できる。これは、システム依存だ。加えて、しっかり free() をしないで終了する行儀の悪いプログラムになってしまう。しかし、その為に延々と待ち続けるのも、時間の無駄なので、free を無効にした。-DFREEをすると、行儀良く free() をするようになる。

もし、興味のある方は自己責任で試して頂きたい。

前回