2010-02-19 ハッシュ計算の「体感的」高速化

FrontPage

http://www.faireal.net/ より 転載。

2010-02-19 ハッシュ計算の「体感的」高速化 †

ハッシュ計算を高速化したい場合に壁になる要素には、 計算そのものだけでなく、データを読み込む速度の問題がある。 例えばハードディスク上の巨大ファイルのMD5を求めるとき、MD5自体は高速なアルゴリズムでも、1ギガ、2ギガというデータをそこに素早く食べさせるのは別の問題だ。 逆にSHA-512のような遅いアルゴリズムの場合、ファイルの読み込むより計算自体で待たされるだろう。

自分が使っている方法は、発想としておそらく最もスタンダードだと思うが、 一つのスレッドで（ハッシュ値を求めたい）ファイルを一定サイズ単位でメモリーマップしてバッファを用意し、 もう一つのスレッドで計算するというもの。バッファを二本（以上）用意しておけば、表で一つのバッファを計算中に裏で次のバッファを読み込むというよくあるパターンの並列処理になる。

バッファのサイズなどパラメータをうまくチューニングすれば（理想的には動的にチューニングすれば）計算速度は最適になるだろう。 しかし、そのようなチューニングは必ずしも良いことばかりではない。 一般に「ハードディスクから読めるだけ速く読み取る」という操作になり、 現実的にハードディスクに負担がかかるからだ。 何ギガもある巨大ファイルの場合、どうせ一瞬では終わらないのだから、むしろ裏でゆっくりハードに優しく1ループごとに少しSleepしなから休み休み低プライオリティで計算する、 というアプローチ、称して「スリーピー・ハッシュ」があってもいい。（これは実装していないが。）

バッファのサイズなどパラメータをうまくチューニングすれば（理想的には動的にチューニングすれば）計算速度は最適になるだろう。 しかし、そのようなチューニングは必ずしも良いことばかりではない。 一般に「ハードディスクから読めるだけ速く読み取る」という操作になり、 現実的にハードディスクに負担がかかるからだ。 何ギガもある巨大ファイルの場合、どうせ一瞬では終わらないのだから、むしろ裏でゆっくりハードに優しく1ループごとに少しSleepしなから休み休み低プライオリティで計算する、 というアプローチ、称して「スリーピー・ハッシュ」があってもいい。（これは実装していないが。）

他方、ユーザーから見た「体感的」速度はまったく別の二通りの要素にも支配される。

一つは、プログレス表示。プログレスバーが動いていれば30秒くらい普通に待てるが、 何のフィードバックもないとちゃんと動作しているか心配になる。 心配しながらの待ち時間は感覚的には長いだろう。 従来ときどき使っていた HashCalc ではこの問題があった。 計算途中で中止もできない、シンプルなプログラムだった

もう一つは、ハッシュをファイル（例えば.md5ファイルや.sha1ファイル）に保存する場合、 ユーザーに保存するファイル名を選ばせているすきに、裏でどんどんハッシュ計算を進めてしまうべきだ。 ユーザーがキャンセルしたらハッシュは破棄すればいい。 うまくすると、ユーザーが保存するファイル名をどれにしようか迷っているうちに裏で計算が終了し、 よし決めたと選択した瞬間に一瞬で保存完了、つまり体感的に超高速化できる。 例えそこまでいかなくても、ユーザーが選んでいるアイドル時間を計算に回すのが合理的であることは言うまでもない。 しかしあまり行われていない。 有名な（自分も最近までよく使っていた）QuickSFVも、 ハッシュをとるファイルを選択してから、次に「どのファイル名でハッシュを保存するか」聞かれ、その間、裏で何もしてない。 本節の意味では悪い例だ。

最近の a3r では、そもそもユーザーに保存ファイル名を聞かないことを原則としている。 （a3r は字幕作成用のツールだが雑多なアクセサリー的機能があってハッシュ計算もできる。） 例えば、abc.txt のMD5を計算するとき「保存しますか」と尋ね、Yesなら何も聞かずに「abc.txt.md5に保存しました」と報告して終わり。 QuickSFV だって、どうせほとんどそのファイル名で保存するだけだから同じことだ。 もちろん「保存しますか」にユーザーが答えている間にも裏では計算している。

なお「abc.txt.md5」が既に存在する場合は、上書きせず、明示的に保存するファイル名を尋ねる。 また保存しますかにNoと答えることもありで、ハッシュ値自体はダイアログに表示されるうえ、自動的にクリップボードにも送られるので、 ファイルに保存する必要がなければしないでいい。 ハッシュはCRC、MD5、SHA1、SHA2系、RIPMD-160に対応した。 （SHA2系はMSのDLLに依存するため、Windows XP SP3以降に限る。） SFVファイルは互換形式でもUTF-8形式でも書ける（これもQuickSFVの問題点だった）。 以上によって、長らく使っていた QuickSFV と HashCalc の必要な機能は完全に越えたので、 もうそれらは自分には必要なくなった。 それとは別にHashTab は便利なので引き続き使っている。

SFV、MD5、SHA1などのハッシュファイルを検証できるのはもちろん、Verifyメニューで Magical Girl Firefox - 08 [89AB0123].avi のようなファイル名を直接選択しても、 ファイル名の89AB0123の部分がCRCだと認識して検証してくれる。 逆に、Magical Girl Firefox - 08.avi のようなファイルを、CRC付きの Magical Girl Firefox - 08 [89AB0123].avi に一発リネームするメニュー項目もある。

これらの実装をしているうちに、_wcsicmp がちょっと問題になった。 複数のファイルを選択して、それぞれのハッシュを一つのMD5ファイルなどに保存するとき、 ハッシュのリストはファイル名でソートして、例えばabc順にきちんと並べて保存するのが良いだろう。 Windowsアプリなのでファイル名の大文字小文字は区別しない。 そういうソート自体は、基本的には、qsortと文字列比較関数で簡単にできるが、 _wcsicmpのような関数は、デフォルトでは"C"ロケールになっている。 そうすると、 ä0001.txt, ä0002.txt, Ä0003.txt, ä0004.txt のようなファイル名を期待通りにソートできない。 "C"ロケールでは Ää の大文字小文字関係が認識されないからだ。 Ää は常識的にもちろん大文字小文字の関係であり、 Windows自身のファイルシステムでもÄ.txtとä.txtは同じで別々に存在できない。 要するに、デフォルト状態の _wcsicmp では適切なソートにならない。

USなどのロケールを選択することで、この問題はすぐ解決するが具体的にどのロケールにするべきか。 もちろんユーザーのロケールだ。 となると、また疑問がわく。 ドイツ語だったら ä は a の前にソートするかもしれないが、 フィンランド語だったら a は z の後にソートすることになる（少なくとも辞書順で考えると）。 では _wcsicmp の代わりに _wcsicoll を使うか。

ロケールをグローバルに切り替えると、明らかに別の問題が発生する。 a3r は全体としてUSロケールで走っている。ファイル名をソートするときだけロケールを切り替えると、 一般論として別のスレッド（例えばステータスバーの時計）に影響してしまう。 実際にはスレッド単位で変えられるが、気持ちのいい方法でない。 だから qsort にもう一つ引数を渡せて、qsort内部で _l 付きの関数を呼び出せる qsort_s が一つの解決法だ。 a3r では現在別の方法を使っている。 qsort の中で、APIレベルの CompareStringW を呼び出すのだ。 _wcsicoll_l は結局 CompareStringW のラッパーなので、 _wcsicoll_l でロケール引数を慎重に扱うくらいなら、 最初から CompareStringW を LOCALE_USER_DEFAULT で呼び出せばいいのではと考えた。 （LOCALE_USER_DEFAULTから実際のロケールへの内部的なマップは、低コストで無視できると想定した。） これを NORM_IGNORECASE で走らせると、狙い通りにロケールがドイツだと ä と a は隣に、 フィンランドだと ä は z の後に、大文字小文字を区別せずソートしてくれる。 ただ、そこでまた謎があって、仕様書的には LINGUISTIC_IGNORECASE の方がより適切に見えるが、 実際には LINGUISTIC_IGNORECASE だとうまく動作しない。調べているうちに、Vista でドイツ語ソートが壊れた（XP以下との互換性が失われた）問題も分かった。 自分はXPを使っているので、Vista以降では違う点があるかもしれない。 文字関係は、奥が深くて、面白いけれど、本当に難しい。

2007年の報告、CompareString / String.Compare works different on XP - Vista with German "Umlauts" öäüßÖÄÜ。 Miscrosoftの開発者ブログでの、どこで間違ったかの説明。 All right, mistakes were made #1 (a.k.a. Expanding the EXPANSION table)