/*****************************************/ /* */ /* 重複ファイル削除ツール */ /* ------- UnDup.exe ------- */ /* Technical Reference Note */ /* */ /*****************************************/ 【 はじめに 】 　この文書は「重複ファイル検索・削除 UnDup」を公開するにあたり、その 内部動作等について記したものであり、本来はβ版を公開する際に特典(と言 えるかどうかわからないが)として配布するために書かれたものである。 　死蔵しててもなんなので、詳細ページにて此の度公開することにした。また 公開にあたり、今後機会があるごとに、色々とコメントを増やしていこうと思 う。 【 重複ファイルの検出アルゴリズム 】 似たようなプログラムがいくつかあるのを私も知っているが、その中でも、 この『 UnDup.exe 』は検出速度が最速、あるいはそれに近いものと自負して いる。その辺は実際に比べてみるとわかると思うが、ここで本プログラムで 採用した重複ファイルの検出アルゴリズムを公開し、高速化のためにどんな 工夫をこらしているかを明らかにしようと思う。（要するに、自慢したいだ けなんだが、どっかにもっと優れた手法があったりして、とんだ赤っ恥をか くことになるかも知れんのだが．．．） 基本的に重複ファイルの検出の際には次のような手順を踏む。 (1) 検索対象ファイルのリストアップ (2) 対象ファイルをサイズでソートする (3) 同じサイズのファイルを比較する (1)は誰が作っても似たような形になるだろうが、本プログラムでは少しでも 高速化するために直接Win32APIを叩いている。Borlandのランタイムを経由す るよりはオーバーヘッドが小さくなる事を期待しているのだが、実際目に見え る様な違いはない。逆に、ファイル数による制限をなくしかつ省メモリ化する ために、ファイル名の保持にリスト構造を用い、適時GlobalAlloc()によって 動的メモリを確保しているので、少し遅いくらいかもしれない。ちなみに一つ のファイル当たり(40＋ファイル名の長さ)バイトを消費するが、名前はフル パス名ではなく、また固定長配列ではなく可変長文字列として扱っているので 無駄は少ない。 (2)もきちんとソートの理屈を知っているプログラマなら、ほとんど差が出る事 はない。QuickSortクラスの高速ソート法を使っていれば、数万件でも今のCPU なら一瞬である。本プログラムでは InsertionSortをベースに二分探索を組み 合わせている(ShellSortと言うらしい)ので、MoveMemory()を煩雑に呼ぶ分 QuickSortなどに比べ若干のロスがあるが、リストにファイルを追加していきな がら逐次ソートする事ができるので、(1)のプロセスとの整合性が高い点を買っ て採用した。 (3)がおそらく高速化の工夫が最も生きる所ではないかと思う。基本的には、 　(a) いかにファイルの読込みを少なくするか 　(b) いかにメモリの比較回数を少なくするか が鍵である。通常、ファイルアクセスはメモリアクセスの数十倍は遅いので、 (a)の方が(b)よりも重要である。 本プログラムではファイルを一度に全て読込まないで、少しずつ分割して読込 んでは比較することで、(a)の問題に対処している。途中で不一致が判明した ファイルはそれ以上読込まなくて済むので、全体としてファイル読込みの量は 減るはずである。この時、異なった場所にあるファイルを繰り返しアクセスし 続けるのでランダムアクセスによる負荷がかかるのが問題になる（ハードディ スクの先読みキャッシュが効けばある程度は軽減してくれる筈だが）。そこで、 内容が異なっている場合には最初の方で違いが現れる事が多いので、最初の１ 回目は32KBだけ読込んで比較を行ない、それが一致していれば最後まで一致し ている事の方が多いので、バッファを増やして128KBずつ比較を行なう様にし ている。(Ver.1.3から二回目以降のバッファサイズは動的可変になった） ファイル全体を全て読込まない事によるもう一つのメリットは、ファイル一つ 当りのバッファが小さくて済むので、比較対象のファイルを全てメモリに取り 込んで比較する事が出来る、つまり、同じファイルを何回も読込み直す必要が 無い事である。キャッシュが効いていれば何回も読み直す事になってもロスは 小さいかも知れないが、数メガバイトのファイルだったり、ファイルが何百個 もある場合には、あまりキャッシュには期待できない。 もちろん(b)のメモリ上での比較回数を減らす事も重要であるので、これについ ても工夫をしている。Ｃ言語には標準関数としてmemcmp()というメモリ比較関数 が用意されているが、これは単にメモリ内容の一致だけでなく、その大小を戻り 値として返すようになっているのを利用するのである。今、 　　　　Ａ,Ｂ,Ｃ,Ｄ,Ｅ,Ｆ,Ｇ,Ｈ,Ｉ,Ｊ の10個のファイルがあったとして、まずＡをＢ〜Ｊと比較する。この時の戻り値 r によって、 　　　　r=0 (ＡＣＤＦ), r>0 (ＢＧＪ), r<0 (ＥＨＩ) と３つに分ける事ができたとすれば、ＢはＧ,Ｊとだけ比較すれば良く、ＥはＨ,Ｉ とだけ比較すればよい。以下同様で、判定に一致・不一致だけを使うよりも飛躍 的に演算時間を短縮する事ができる。コーディングとしては、ちょうどQuickSort を使っている様な感じになる。(Ver.1.3以降では更にコレを発展させている） また、さらに高速化する方法もある事はある。memcmp()をオーバーライドして、戻 り値に何バイト(ワード)目で違いが現われたかも返すようにすれば良い。上の場合、 もしＡに対してＢ、Ｇを比較した時の戻り値が異なれば、次の段階でＢとＧの比較 を行わなくて済むし、同じだったとしても、最初の何バイトかは比較する必要がな くなる。ただし今の所、本プログラムでは採用していない。メモリ上での比較作業 は律速段階ではない上に、アセンブラレベルで最適化されている筈(Borlandがちゃ んと仕事をしていれば)のランタイムをＣで書き直すだけの効果があるかどうかわか らないからである。 アルゴリズムレベルではなく、実装段階で工夫すればさらに高速化できる手法もあ る。ファイルを読込む処理を非同期化するのである。ＡとＢを読込んだ後、Ｃを読 込んでいる待ち時間を使ってＡとＢの比較を行なう様にすれば、実質的にメモリ上 での比較にかかる時間はゼロになる。コーディングが面倒くさいので本プログラム では採用していないが、Win32APIのマニュアルを読んだ限りでは、やろうとしてや れない事はないと思う。 まあ要するに現状でも充分に速いだろうと言うことで、現在の関心はいかに消費メ モリを小さくするかにある。これも実は検索速度に影響する。メモリを大量消費す ればスワップアウトが発生し、速度が劇的に遅くなるからである。まあ最近のマシ ンは256MBとか512MBのメモリを当然のように積んでおり数十MBのメモリ消費はあま り気にする必要が無いかもしれないが、私の身の回りには32MBしか積んでいない MMX-Pentiumマシンもまだ現役で動いている。しかも計測制御に使っているために、 大量の測定データが皆同じファイルサイズだったりするのでタチが悪い。これを何 とかするのが、当面の課題である。ま、そう言う環境では実行しなければ良い、 と言うのが最も手っ取り早い解決法なのではあるが．．．。 2002.11.02 Sim-G 殆どの場合は現状でも問題は全くないが、数百KBの同じ大きさのファイルが大量 (数百〜数千)にあるとメモリを大量消費してシステムエラーが起きたり不安定に なる怖れはある。上記の様なケースはけして特殊ではなく、ゲームのセーブデー タなどでも容易に起こりうる事に、今ごろになって気がついた。これは何とかし なければなるまい。 基本的な対策は、メモリサイズを制限してそれを超えた部分は必要になる度に何 度も再読込みをする様に仕様を変更する事と、なるべくそういう事が起きないよ うに効率的なメモリ使用をする事、memcmp()の戻り値を利用して比較の回数を少 しでも減らす事などである。メモリ管理システムの導入やら何やらで大幅な改造 と、オーバーヘッドにより若干の速度低下が予測されるが仕方がないだろう。 一回目の比較の時のバッファは、小さなファイルにはファイルサイズをそのまま、 64KBを超える時は32KBとした。バッファサイズの上限を4MBとしても、最低でも 64個までは再読込みの必要なしに比較処理が行える。比較して同じだったファイ ル用のバッファは他のファイルで再利用できるので、実際にはもっと多くのファ イルに対して再読込み無しで対処できる。また、バッファサイズの上限値はデ フォルトは16MBにしてあるが、ユーザーの環境に応じて変更できる。ただし、あ えてＵＩは用意せず、上級者向けオプションとして設定ファイルを直接変更して もらうようにした。 また今回から、従来は32KB以上のファイルは問答無用で２回に分けて比較を行っ ていたのを改め、64KBまでは１回で済ませるようにした。ＨＤＤの内部転送速度 が約33MB/秒だとして32KBの追加読込みには1msしかかからないのに、平均シーク 時間は10ms程度と10倍もあることを考慮した。上記の変更によりメモリに余裕が できたので可能になった。２回目以降の読込みサイズは可変で、比較すべきファ イル数が減っているので、再読込み無しで対処できる最大サイズを割り当ててい る(下限64KB、上限512KB）。 2002.11.05 Sim-G (Ver.1.3β3) 自宅に置いてある旧世代化しつつあるマシン(P3-748MHz, BX-mother+ATA66)でイン タ−ネットのキャッシュ(Ijie5webでローカル化)を検索してみた所、約５千フォル ダ、18万ファイルで検索に１時間以上時間がかかった。とは言え、もう高速化でき そうな所はほとんど無い。せいぜい、ソートをより高速な物に改めるぐらいだが、 １時間が59分30秒になった所でたいして変わりがないわけで。 Vectorとか見ていると、この種の重複ファイルの検索削除ツールは意外にたくさん あることに気づく。何かの参考にはなりはしないかと一応ＤＬして見るものの、た いして得られる物はない。強いてあげれば、ファイル名や拡張子で検索対象を事前 に絞っておく事ぐらいで、こいつは諸刃の剣だから積極的に採用する気はない。 （例えば拡張子で縛ると、とかみたいなパターンで検出 できないケースが出てくる）UnDupなら最初の32KBだけ読込んだ時に違う事が判明 するので、時間のロスになりにくいと言う事情もある。 ちなみにCRCを使って重複を判別している物をいくつか見かけた。が、はっきり言っ て遅いと思う。CRCを計算するために一度すべてのファイルを読込まなくてはならず、 絞りこんだ後でもう一度読込んで比較しなくてはならないからだ。ケースにもよる が、実は何も考えずに総当たりで検索するのと比べても、あまり変わらないのではな いか？良くて50%の高速化がせいぜいで、悪ければ逆にロスが出る事もある(重複ファ イルが100個ある時とか)のでは、如何かと思う。 またファイルサイズが数ＭＢならすべて一度にメモリに読込んでCRCの計算ができる が、数百ＭＢもある時はどうしてるのだろうか？（まあこの辺は単純な総当たり式 でも同じことだが） 話がそれたが、結局の所、これ以上の高速化を進めるためにはきちんと統計でも取っ て、バッファサイズを最適化するぐらいしか思いつかない。さて、どうしたものか。 2002.11.27 Sim-G (Ver.1.3d) 上で書いたCRCを使った判別法についてだが、最初に全てのCRCを計算するのではなく、 総当たり的に比較する過程で一度読込んだファイルのCRCを計算しておき、２度目に 読込む前に予備的にチェックする手法ならば、ロスは出ない事に気づいたので訂正し ておく。ただ、本プログラムでやっている様にmemcmp関数の戻り値をCRCの変わりに 使っても、予備的チェックとしては必要充分な精度が得られると思う。勿論、CRC値を 使った方が精度が高いのは言わずもがなだが、計算に伴うオーバーヘッドが常に存在 する事を鑑みると、平均してしまえば速度はそれ程変わらないと思う。 2002.11.28 Sim-G うーん。検索速度が遅いと言われてしまった。このアルゴリズムには結構自信があった んだが。やはりシーク時のペナルティが予想以上に大きいと言うことか。最初の読込み サイズを32KB固定から可変にして、シーク回数をなるべく減らすようにすれば効果はあ るかな。Aikoって言うのが速いらしいが、どういうアルゴリズムなのだろうか。対象の 指定形式が違うので直接速度を比較できないが、まさかCRCチェックだけで本文の比較 をしていない訳ではないよな。 2003.01.06 Sim-G 簡易検索として、32bit-CRCを利用した検査法を追加した。一度ファイルを全て読込んで CRCを計算し、CRCの比較のみを行なう。巨大なファイルは1MBずつに分割して行なう。 同時に完全一致検索の方もバッファの割り当て方法を再変更し、１回目の読込みを可変 (最大256KB)にして速度の向上を図った。 [テスト１] MMX-Pentium 266MHz, EDO-RAM 32MB Windows95(OSR2) HD-Bench Read 10MB/S 760MB 約1000フォルダ,18000ファイル (内容：Program＆実験dataが主) 996種,2400ファイルの重複を発見。(簡易検索でも同結果) 簡易検索　約205秒 / 完全一致 約190秒 (最大バッファ：4MB） [テスト２] Athron1800+(Pa) DDR-SDRAM 256MB Windows2000(SP3) HD-Bench Read 18MB/S (a)660MB 約2000フォルダ,16000ファイル(内容：JPEG画像ファイル) 53種,114ファイルの重複を発見。(簡易検索でも同結果) 簡易検索　約68秒 / 完全一致 約68秒 (最大バッファ：4MB） (b)1.7GBB 約3000フォルダ,27000ファイル(内容：JPEG画像ファイル) 726種,1583ファイルの重複を発見。(簡易検索でも同結果) 簡易検索　約120秒 / 完全一致 約120秒 (最大バッファ：4MB） テスト１では簡易検索よりも完全検索の方が速い結果となった。理由として考えられる のは、ハードディスクのシーケンシャルアクセスが遅い(ランダムアクセスの負担が相 対的に小さい)事が考えられる。まあ５年前の古いコンピュータだし。 2003.01.18 Sim-G 結局の所、検索速度で何が重要かというとHDDからの読込み速度に尽きるわけで、さら に分析すれば、シーク(ランダムアクセス)時間と転送時間の短縮が重要と言うことにな る。これまでは再読込みを徹底して回避する事により転送時間の短縮を狙っていたのだ が、思ったように速度が上がらないのはファイルをぶつ切りでアクセスするためにラン ダムアクセスが増え、足を引っ張っているのだと考えられる。これは当初からある程度 は予想してはいたものの、実際にやってみると予想以上にシークに費やされる時間が多 かったと言うことだ。また実際にやってみると小さいファイル(128KB)が意外に多かっ たために、ほとんど一度で読込みが出来、CRCを使うやり方に比べてもシーク回数はそれ 程増えずに、CRCを使った簡易検索よりも速い事があるのだろう。 さて、この分析を踏まえ、さらなる高速化を目指すためには、アルゴリズムを根本的に 変えて、シーク時間を減らす方向にチューンすべきだろうという事になった。シークを 減らすには、なるべくディスクの近いところにあるファイルをアクセスするように心が ける事で、FAT(ないしそれに相当するもの)を見ずに完全にそれを行なう事はできない が、簡易的には同じディレクトリの物は同じ辺りに配置されている事が多い(デフラグ 直後はまさにこの状態)ので、検索のスケジュールを調整する事にした。 具体的には、ソートを行って検索すべきファイルを減らした後で、今まではファイルサ イズの順番に従って検索していたのを、ディレクトリの並び順にCRCを計算していって メモリに記録し、後でファイルサイズ順にCRCを比較していく事にした。テスト環境で は従来の完全比較に比べ半分以下の時間ですみ、簡易検索の後に残った重複している可 能性のあるファイルを完全検索しても充分にお釣りがくる結果となった。そこで、これ をVer.1.4β2で実装した。実際にはＭＯの様な極端にシークが遅いのでランダムアクセ スが大きな負担にならない様なメディアや、ほとんどが重複していて簡易検索では候補 を絞れないためその後の完全検索で時間がかかり過ぎる場合など、この新方式では高速 化されないケースもあるため、β3では完全検索を従来のもの(1pass)と新採用の方式(2 pass)から選べるようにした。 まだ細かいところで高速化の余地は残っているものの、大局的にみてこれ以上大幅に速 度を向上させることは無理だと思う。言い方を変えれば、重複ファイル検索の速度につ いては、このUnDupは最速のフリーソフトであると言うことだ。市販ソフトや海外製、 それに一部のシェアウェアには試していないものもあるが、私が試した範囲では間違い ないと思う。もしこれより速いソフトがあるのならば教えて欲しい。 2003.03.26 Sim-G 「同一フォルダ内の重複をチェックしない」オプションについて検討してみる。実際に 同様のツールであるAikoなどはこの形式を採用している(と思う)。まずどの様な時にこ のオプションを有効利用できるかと言うと、画像などを溜め込んでいる人が事前に チェック済みのフォルダに新たな画像を追加する前に、既に持っている画像と同じ物を 消去するケースだろうか。この場合、保存フォルダ内の重複はチェック済みだからそれ を省略すれば高速化が期待できる計算になる。 では実際にこのオプションでどれほどの高速化が見込めるのであろうか。まず2passの 完全検索を行なう場合、もっとも時間がかかるのは対象ファイルを一個ずつ読込んで CRCを計算する部分である。この部分は上記オプションでは全く高速化されない。A,B,C の３つのファイルが同一フォルダにあったとして、別フォルダにDと言うファイルがあ ればA,B,Cそれぞれは重複していなくてもDと一致する可能性があるかぎりA〜CのCRCを 計算しておかなければならないからだ。そしてCRCによる予備比較の段階でA,B,Cが重複 していない事はわかるので、その後の完全比較でA〜C間の重複を検査することはない。 つまり2passでの完全検索は、Dが存在しない時以外は全く高速化されない。 1passの完全検索の場合は、ランダムアクセスのペナルティが大きいため、もう少し高 速化が見込めるだろうが、基本的な事情は同じである。Dと同サイズならA〜Cを実際に 読込んで中身を調べる必要がある。律速段階はファイルの読込みであり、一度読込んで しまえばD対A〜C(組み合わせは３通り)に加えA〜C間(組み合わせは３通り)の比較を行 なう必要があるが、メモリ間の比較で済むから大きな時間のロスではない。アルゴリズ ムによっては比較時に再読込みを何度も行なう様な物があり、この場合は非常に問題と なるのだが、UnDupでは基本的に再読込みは発生しない。結局、やはりDが存在するかぎ りほとんど高速化される事はないのである。 それでも数十万に及ぶ非常に巨大なファイル倉庫に数千個のファイルを追加していく様 な場合には、上記のＤの様なファイルが存在する確率が相対的に小さいので、それなり の高速化は期待できるだろう。と言うよりむしろ、そのような場合にしか高速化は期待 できないと言うことである。 以上の分析を元に、予備検索の一部として「重複検査済みフォルダの指定」を加える事 にした。最初のオプションだと追加ファイル間での重複は検査できないこと、ファイル 倉庫に使うフォルダは頻繁に変更することはない事を勘案した。運用上の考慮事項とし ては、少数のファイルを煩雑に追加していく場合、最初のファイル検索に取られるペナ ルティが馬鹿にならない事。かといって追加ファイルを貯めすぎると、上記Ｄの様な ファイルが増えてあまり高速化されない事を指摘しておく。なお、「JPEGヘッダを無視 する」設定をオンにしている場合、ファイル検索時にJPEGファイルは全てヘッダサイズ を調べておく必要があり、そこに一番時間が掛かっているので、このオプションで全く 高速化される事は無いことも追記しておく。 2003.04.01 Sim-G 今は簡易検索にCRC32を使って行っているが、MD5を使えば精度が向上するのではないか と言う点を検討してみる。まず検出精度についてだが、理論上もちろんMD5の方が精度が 高いのは事実だが、誤検出の可能性を完全にゼロにする事はできないので完全一致検索 を代替する事はできない。完全検索を必要とする者にとっては、100%でない以上、99% だろうが99.99%だろうが、使えないことに変わりはない。 速度面に関しては、何度も述べている様にファイルの読込みが律速であるので、CRC32 もMD5もあまり変わらない。問題はメモリ使用量である。MD5は128bitなので格納に16 バイトを要する。百万ファイルあれば16MBも必要になるのである。メモリ環境にもよる が、あまりメモリを使い過ぎるとスワップが発生するので、なるべく避けたい。と言う わけで、精度が落ちる事は承知のうえで、格納に４バイトで済むCRC32を採用したので ある。ちなみに、Ver.1.4β3までは最大メモリ使用量が64MBしかなかった(β4からは無 制限)と言う事情もある。また、私は測定データとして同サイズの異なるファイルを１ 万個近く持っているため、CRC16では簡易検索としては不十分であった。 2003.04.02 Sim-G 512KB目まではまったく同一で、その後の数バイトだけ内容が異なる数千個のファイル。 UnDupで検索を行なうにはあまりに苛酷な条件であり、はっきりいって一種の嫌がらせか とも思えるが、まあ世の中には色んな可能性があり、業務でそう言うデータを扱ってい る人もいるかもしれないわけで、対策は考えなくてはならない。 まず重要な問題点はこの一種のベンチマークテストにより、メモリ管理＋ファイル再読 込みの手続きにバグがあり、充分なメモリを割り当てておかないと検索そのものが正確 に行われないと言うことが判明した事だ。これは当然ながら修正しなくてはならない。 普通に使っていると、再読込みはほとんど発生しないために今迄見つからなかったバグ である。 　（再読込が発生した時に、オープン後にファイルポインタの位置を正しく戻していな 　　かった事が原因だと判明。Ver.1.5β4あたりで修正しました） 次に、UnDupのアルゴリズム上、この条件では細かいシークが大量に発生する事になり、 検索速度が異常に遅くなる点も改善しなくてはならない。少々面倒な事になるが、再読 込みが確実に発生する程に同サイズのファイルが沢山あるケースでは、一定数の重複を 見込んで初期バッファサイズを少し大きめに取っておく事、再読込みを減らすために CRCを使った管理を行なう事などを考えた方が良いのだろうか。 2003.08.10 Sim-G 現行では内容比較時にはmemcmp()の戻り値を保存して、それをメモリの指標代わりにし て再読込みの回数を減らしている。本来は読込んだ内容の指標にはきちんとCRCを計算し ておいた方が良いのだが、その手間を省いて少しでも高速化しようと言う意図である。 ほとんどの場合はこの方法で問題は無いが、特殊なケースで、例えばサイズが同じで任 意の位置で１つだけデータ(DWORD)の値が１だけ違う様なファイルが沢山ある場合には、 memcmp()の戻り値は全部同じになってしまうので問題がある。位置を返さない事と、最 初の相違点での差だけしかわからないので、その後のデータについての情報が得られな いのが問題である。 一応、再読込みが発生したらCRCを計算して保存しておく様な比較ルーチンを作ってはみ たが、通常のケースではメリットが全く無いのでVer.1.5で投入は見送る事にした。 2003.11.10 Sim-G ファイルのソート方法であるが、上には律速でないのであまりこだわる必要はないと書 いたが、数十万のファイルを扱う場合、後段の内容比較に１時間以上とられるので確か に律速ではないが、やはりソートに数分もかかるのはあまりよろしくない。現行の改良 型InsertSortは、コードが簡単、ワークメモリが不要、安定、データ追加時の逐次ソー トが可能と言うメリットがあるが、もっと高速のソート法に変更する事にした。 ヒープ、クイック、マージの各種ソート法をベースに安定化し、ワークサイズを最小に する様に色々と改良してみた。速度的には安定化QuickSortが平均的に最も優れていたの だが、アルゴリズム上再帰が必須(=メモリスタックを消費)であり、データによっては ハマる(異常に遅くなる)事があり、データの２倍のワークを必要とする。ヒープはワーク は不要で再帰もいらないが、安定なものを作る事はできなかったし、クイックに比べれば 速度的に劣る。結局、マージソートを採用し、ワークが不要なものも作ってみたが遅かっ たので、データサイズと同じだけワークを使用するものを採用する事にした。 2004.04.11 Sim-G 高速化の試みとしては、既に壁にぶち当たっていると思う。現状で改善できる事はなくも 無いが、たぶん１割高速化できれば御の字だろう。 ・(2003.11.19)の様に、CRCを指標に使い再読込みを減らす 　⇒大半のデータでは現状と変わりない。逆にオーバーヘッドもあり得る ・ファイル読込みを非同期化し、比較中にディスクから読み取る 　⇒HDDやOSの持つキャッシュが、既にその役割を果たしている 　　(効果が無いとは言わないが、手間をかける割に効果は薄いのではないか） ・インテリジェントなメモリ割り当てを行って効率化する。 　⇒無駄を減らすのは良いことだが、面倒。頭が痛い。 検索時のメモリバッファを増やすのは、ある程度までは有効ではあるが限界がある。必要 以上に取り過ぎれば、OS側のメモリを圧迫し、スワップが発生したりして却って遅くなり かねない。デフォルトの 4〜16MBで充分だろう。メモリに関してはむしろ最低限を確保す れば、後はOSに委ねてキャッシュなどに使ってもらった方がトータルでのスループットは 良くなると考えている。メモリ指定に「最小サイズ」があるのはこのためである。通常は このサイズしか使用しない筈である。基本的にはギガバイトクラスのファイルがあろうと、 1MBあれば一度に512KBずつ読込んで比較できるので充分である。「最大サイズ」が有効に なるのは同サイズのファイルが大量にある時で、再読込みを避けるためにはなるべく多く のファイルを同時にメモリに置く必要がある。１ファイルあたり128KBとして、4MBで32ファ イル分しかないので、それを越えると再読込みが発生して遅くなるので、メモリを最大サ イズまで確保する事で、その可能性を減らそうとするわけである。まあこの辺りでもう少 し改善の余地があって、割り当てられたメモリに対して、バッファサイズと個数の組合わ せを工夫すればまだ早くする事はできるかな、と考えないでもないが、最適解を探すのは とっても面倒くさい話である。 それよりも最近は別のアプローチの方に目がいっている。まずは直接検索ルーチンをいじ るのではなく、別の部分の無駄を減らす事である。メモリに関しては、Ver.1.5bまでにほ ぼ達成できたが、最初に作ったファイルリストから不要なものを除いてメモリを解放する 事(β6)で、例えば10万個のファイルから比較の候補が2万個程度が見つかったとすれば、 残り8万個に割り当てられた4MB程度のメモリを解放する事ができる。またVer.1.5から採用 したStringGridがまたメモリを馬鹿食いするので、これもオブジェクトの管理をライブラ リではなく直接行なう事で削減することができた(1.5b)。その分のメモリをOSが適切に使 用してくれれば、あるいは明示的にUnDupに割り当てても良いが、少しは早くなるのではな いかと期待しているのだが、どうだろうか。 さらに、簡易検索を現行のCRC32からMD5に代えて確実性を増やして完全一致検索を代替で きれば、それでも結果として高速化は達成できる。現行のCRC32でも、精度的にほとんど問 題になる事はないのだが、万が一の不安が無いとは言えない。128bitの精度を持つMD5なら 業務等でのクリティカルな作業以外には充分であろう。ただ残念ながら、必ずしも簡易検 索が完全一致検索に比べて早いわけではない。と言うか、サイズが同じファイルは全て最 後まで読込んでしまうので、むしろ遅いかもしれない。結局、これも高速化の決め手には ならない様である。 2004.07.24 Sim-G 検索速度速度向上のために残されている事は、もう少し低レベルで制御を行なう事で読込 みの高速化を図る事があげられる。上で述べたように、非同期で読込みするのが一つの手 で、マルチスレッド化して読込みを完了した物から比較を行っていけば、複数のドライブ にまたがる検索の場合は、大幅に速度向上が期待できる。ただし同じドライブから読込む 場合にはシークが発生して逆効果なので、その辺を判断して調整しなければならない。物 理ドライブと論理ドライブが一致すると仮定した上で、ある程度はドライブ側のキャッシュ が効くとして、１ドライブあたり２スレッドまでなら良いだろうか。 OSのキャッシュを介さず直接読込むのはどれだけ効果があるのだろうか。この場合、再読 込みが発生するとそれが丸々ペナルティとなるため、その可能性を最小限に抑えるために、 あらかじめ充分なメモリを確保しておく必要がある。結局の所、その領域をOSに任せるか、 自分で制御するかの違いに他ならないのだが、他のプログラムへの影響なども考えると、 まあ微妙な所ではある。あと、読込みサイズはなるべくクラスタサイズの整数倍になる方 が良いのだが、JPEGヘッダを無視する時はどうしてもヘッダサイズだけズラして読込む必 要があるため、そのあたりの制御にも気を使う必要がありそうだ。 2004.11.19 Sim-G このドキュメントについて何かコメントがおありの方は、下記のメールアドレスにご 連絡下さい。 HGA01077@nifty.ne.jp 特にプログラマの方、より良い(高速な)検索方法をご存じの方、何かアドバイスで もあれば、大いに歓迎いたします。