ディレクトリの中にある大量の小さなファイルを高速に読み込む方法 - 射撃しつつ前転 改

ディレクトリの中にある大量のファイルを高速に読み込む方法が知りたかったので、実験してみた。想定しているシチュエーションは、一つ一つのファイルは数KB程度だが数が多い、という場合である。適当な順番でアクセスすると、ランダムアクセスになってしまいとても時間がかかる。個々のファイルを読み込む順番はどうでも良く、すべてのファイルを処理することさえできればいいので、原理的にはシーケンシャルアクセスで処理できてしかるべきである。 まず、ファイルシステムについて。HDDやSSDなどのハードウェアにアクセスする際には、ファイル名などという概念はもちろん存在しない。ファイル名と実際のディスク上の対応を管理するのがファイルシステムの主な役割である。ファイルシステムは、ファイル名からそのファイルに対応するブロック番号（メモリアドレスみたいなもんだな）を調べて、そのブロック番号を指定してHDDやSSDにアクセスす

[fcicq]

inode number can be sorted. http://web.archive.org/web/20120522053813/http://kodou.net/~tkng/dirdump.c

[yass]

" ということで、inode番号はext3ではブロック番号の近似として十分に使え、inode番号でソートすることで、ファイル数が多い場合のディレクトリ内のファイル読み込みを高速化することができた。"

[naoh16]

ファイルリストを作るときにinode順にすれば読み込みが早くなるかもしれない。

[diary193]

「inode番号はext3ではブロック番号の近似として十分に使え、inode番号でソートすることで、ファイル数が多い場合のディレクトリ内のファイル読み込みを高速化することができた」

[toton]

"圧倒的な速度差（23.6倍！）が得られた"、inode順に読む、ユーザースペースでのI/Oスケジューリング,

[sotarok]

inode順にソート

[tl_bkmk]

ブロック番号が近い順に並べてアクセスすれば、読み取りヘッダを移動させる時間が減るので、読み取りが高速に行える。

[karronoli]

小さなっていうのはHDDのキャッシュサイズ依存かー。それを超えたとしてもいくらか効果はありそう。

[hiroyadoraemon]

inode

[amachang]

inode 番号でソートしてアクセスするだけで 20 倍速く読める。／お手軽！

[tomoemon]

hdd

[T-miura]

STATのNCQがある程度ヘッドの動きが少ないよう、シーケンシャル的にしてくれると思っているのだが？それを超えた単位でのアクセス制御・・・？

[decoy2004]

36秒と850秒という、圧倒的な速度差（23.6倍！）が得られた。

[oza_x86]

inode番号の順番 = 対応するファイルの物理ブロックの順番 という条件が成立するときに、HDDのヘッダの動きを最適化するアプローチ. 要検証.

[suu-g]

勉強になる、たのしい、255人目のぶくま

[omaya]

逆にファイルシステムがファイル名をヒントにして実体の配置を考慮するようなものはあるかなぁ。

[ko-ya_ithaqua]

http://blog.livedoor.jp/dankogai/archives/51239267.html

[takeshiketa]

ダンコガイの説とどっちが正解かな

[tzt]

ファイルシステムを使った時点で負けと言う気もする。

[inurota]

これは素晴らしい

[asari3]

とある連想検索エンジンを使うときに使えるかもと思った

[llill]

汎用系を思わせるtips

[Fu-ki]

[I/O][file]

[seiunsky]

inodeでシーケンシャルにアクセスしてディスクアクセスを高速化する

[tacroe]

inode番号はext3ではブロック番号の近似として十分に使え、inode番号でソートすることで、ファイル数が多い場合のディレクトリ内のファイル読み込みを高速化する

[nakag0711]

ウイルススキャナとかはやっぱりこれやってるのかね

[potato777]

[I/O]

[otonasi_kaoru]

面白い

[k12u]

すごい

[chroQ]

へぇ。ext2系だけかと思ったらReiserFSにも使えるんだ。でもReiserってinode持ってるんだっけ？全く覚えてないなー。