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() をするようになる。

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

前回

コメント

コメントをどうぞ

※メールアドレスとURLの入力は必須ではありません。 入力されたメールアドレスは記事に反映されず、ブログの管理者のみが参照できます。

※なお、送られたコメントはブログの管理者が確認するまで公開されません。

名前:
メールアドレス:
URL:
コメント:

トラックバック

このエントリのトラックバックURL: http://uyota.asablo.jp/blog/2007/06/05/1556826/tb

※なお、送られたトラックバックはブログの管理者が確認するまで公開されません。