ファイル構成がファイルアクセス効率に与える影響

ディレクトリ構造のファイル構成は、ファイルアクセス効率に大きな影響を与える可能性があります（引用する）。たとえば、2つのディレクトリAとがBそれぞれ10 ^ 6個のファイルを含み、前者の場合は1つのディレクトリで構成され、後者の場合は10 ^ 3個のサブディレクトリで構成されているとします。前者の場合、すべてのファイルを計算または一覧表示する速度はかなり遅くなります。私のシステムでは：

ファイルを生成します。

$ mkdir A; pushd A; seq -w 1E6 | xargs touch; popd
$ mkdir B; pushd B; seq -w 1E3 | xargs mkdir; for d in *; do pushd "$d"; seq -w 1E3 | xargs touch; popd; done; popd

ファイルのリスト：

$ for d in A B; do
    time for i in {1..100}; do
        {
            echo 3 | sudo tee /proc/sys/vm/drop_caches
            find "$d" -type f
        }
    done >/dev/null
done

# case A (0 subdirectories)
real    4m49.805s
user    1m43.696s
sys     1m13.540s

# case B (1000 subdirectories)
real    3m32.338s
user    0m40.824s
sys     1m13.176s

違いはディスクキャッシュに関係なく再現可能であり、コマンドによって変わりませんfind（たとえば、同じサイズの違いを見つけることを使用ls -RU）。どちらの場合も、カーネルスペースの時間は同じであるため、カーネル（およびファイルシステムメカニズム）の責任が軽減されます。別に分析はしなかったがメインシステムコールはほぼ確実に行われており、readdir()アイノードgetdents()数は両方の場合とも同じ（0.1％以内）するためファイルのサイズやかかる時間もそうです。カーネルがこれらの呼び出しを異なる方法で行うため、同じです。したがって、実行時間の違いはユーザー空間コードに起因する可能性があります。

いくつかのGNU coreutils（例sort：）にスレッドサポートが追加されました。私のシステムには4つのハードウェアスレッドがあり、GNU（私のシステムバージョンは4.7.0-git）にマルチスレッド機能があるかどうかわからないため、単一のハードウェアスレッドに明示的にバインドされたfindプロセスを使用して違いがあることを確認しました。

$ cat find.sh
#!/bin/bash
for i in {1..100}; do
  {
    echo 3 | sudo tee /proc/sys/vm/drop_caches
    find "$1" -type f
  }
done >/dev/null

$ for d in A B; do time taskset -c 0 ./find.sh "$d"; done

# case A (0 subdirectories)
real    4m7.827s
user    1m31.080s
sys     0m55.660s

# case B (1000 subdirectories)
real    2m53.059s
user    0m33.256s
sys     0m52.772s

したがって、私の最初の質問は次のように具体化できます。純粋にファイルシステム構成の違いによるアクセス時間の違いにより、ユーザースペースが非効率なのはなぜですか？これらの非効率性を理解すると、ファイルアクセスルーチンをよりよく実装できます。

編集する：ext4私はLinuxカーネルを実行しているコンピュータでファイルシステムを使用していますが、4.9.0-4-amd64選択したファイルシステムによって答えがどれだけ異なるかを知りたいです。