Mengapa `ditemukan. -tipe f` membutuhkan waktu lebih lama dari `find .`?

15

Sepertinya findharus memeriksa apakah jalur yang diberikan sesuai dengan file atau direktori tetap untuk berjalan secara rekursif isi direktori.

Inilah beberapa motivasi dan apa yang telah saya lakukan secara lokal untuk meyakinkan diri saya bahwa find . -type fsebenarnya lebih lambat daripada find .. Saya belum menggali kode sumber menemukan GNU.

Jadi saya membuat cadangan beberapa file di $HOME/Workspacedirektori saya , dan mengecualikan file yang merupakan dependensi dari proyek saya atau file kontrol versi.

Jadi saya menjalankan perintah berikut yang dijalankan dengan cepat

% find Workspace/ | grep -v '/vendor\|/node_modules/\|Workspace/sources/\|/venv/\|/.git/' > ws-files-and-dirs.txt

finddisalurkan ke grepbentuk yang buruk, tetapi sepertinya cara paling langsung untuk menggunakan filter regex yang dinegasikan.

Perintah berikut hanya menyertakan file dalam output dari find dan memakan waktu lebih lama.

% find Workspace/ -type f | grep -v '/vendor\|/node_modules/\|Workspace/sources/\|/venv/\|/.git/' > ws-files-only.txt

Saya menulis beberapa kode untuk menguji kinerja kedua perintah ini (dengan dashdan tcsh, hanya untuk mengesampingkan efek yang mungkin dimiliki shell, meskipun seharusnya tidak ada). The tcshhasil telah dihilangkan karena mereka pada dasarnya sama.

Hasil yang saya dapatkan menunjukkan penalti kinerja 10% untuk -type f

Berikut ini output dari program yang menunjukkan jumlah waktu yang dibutuhkan untuk menjalankan 1000 iterasi dari berbagai perintah.

% perl tester.pl
/bin/sh -c find Workspace/ >/dev/null
82.986582

/bin/sh -c find Workspace/ | grep -v '/vendor\|/node_modules/\|Workspace/sources/\|/venv/\|/.git/' > /dev/null
90.313318

/bin/sh -c find Workspace/ -type f >/dev/null
102.882118

/bin/sh -c find Workspace/ -type f | grep -v '/vendor\|/node_modules/\|Workspace/sources/\|/venv/\|/.git/' > /dev/null

109.872865

Diuji dengan

% find --version
find (GNU findutils) 4.4.2
Copyright (C) 2007 Free Software Foundation, Inc.

Di Ubuntu 15.10

Inilah skrip perl yang saya gunakan untuk pembandingan

#!/usr/bin/env perl
use strict;
use warnings;
use Time::HiRes qw[gettimeofday tv_interval];

my $max_iterations = 1000;

my $find_everything_no_grep = <<'EOF';
find Workspace/ >/dev/null
EOF

my $find_everything = <<'EOF';
find Workspace/ | grep -v '/vendor\|/node_modules/\|Workspace/sources/\|/venv/\|/.git/' > /dev/null
EOF

my $find_just_file_no_grep = <<'EOF';
find Workspace/ -type f >/dev/null
EOF

my $find_just_file = <<'EOF';
find Workspace/ -type f | grep -v '/vendor\|/node_modules/\|Workspace/sources/\|/venv/\|/.git/' > /dev/null
EOF

my @finds = ($find_everything_no_grep, $find_everything,
    $find_just_file_no_grep, $find_just_file);

sub time_command {
    my @args = @_;
    my $start = [gettimeofday()];
    for my $x (1 .. $max_iterations) {
        system(@args);
    }
    return tv_interval($start);
}

for my $shell (["/bin/sh", '-c']) {
    for my $command (@finds) {
        print "@$shell $command";
        printf "%s\n\n", time_command(@$shell, $command);
    }
}
Gregory Nisbet
sumber
2
Sepertinya findharus memeriksa apakah jalur yang diberikan sesuai dengan file atau direktori tetap untuk berjalan secara rekursif isi direktori. - harus memeriksa apakah itu direktori, tidak perlu memeriksa apakah itu file. Ada jenis entri lain: pipa bernama, tautan simbolik, blok perangkat khusus, soket ... Jadi, meskipun mungkin sudah melakukan pemeriksaan untuk melihat apakah itu direktori, itu tidak berarti ia tahu apakah itu file biasa.
RealSkeptic
busybox find, diterapkan pada direktori acak dengan dir, 4,3 k dan file 2,8 k berjalan bersamaan dengan -type fdan tanpa itu. Tetapi pada saat pertama kernel Linux memuatnya ke dalam cache dan penemuan pertama lebih lambat.
1
Dugaan pertama saya adalah bahwa -type fopsi menyebabkan findpanggilan stat()atau fstat()atau apa pun untuk mengetahui apakah nama file sesuai dengan file, direktori, symlink, dll. Saya melakukan stracepada find . dan find . -type fdan jejak hampir identik, hanya berbeda dalam write()panggilan yang memiliki nama direktori di dalamnya. Jadi, saya tidak tahu, tetapi saya ingin tahu jawabannya.
Bruce Ediger
1
Tidak benar-benar jawaban untuk pertanyaan Anda, tetapi ada timeperintah builtin untuk melihat berapa lama perintah untuk dieksekusi, Anda tidak benar-benar perlu menulis skrip khusus untuk diuji.
Elronnd

Jawaban:

16

GNU find memiliki optimasi yang dapat diterapkan find .tetapi tidak untuk find . -type f: jika ia tahu bahwa tidak ada entri yang tersisa dalam direktori adalah direktori, maka itu tidak repot untuk menentukan jenis file (dengan statpanggilan sistem) kecuali salah satu kriteria pencarian membutuhkannya. Memanggil statdapat memakan waktu yang dapat diukur karena informasi biasanya di inode, di lokasi terpisah pada disk, daripada di direktori yang berisi.

Bagaimana bisa tahu? Karena penghitungan tautan pada direktori menunjukkan berapa banyak subdirektori yang dimilikinya. Pada sistem file Unix yang umum, jumlah tautan direktori adalah 2 ditambah jumlah direktori: satu untuk entri direktori pada induknya, satu untuk .entri, dan satu untuk ..entri di setiap subdirektori.

The -noleafpilihan mengatakan findtidak menerapkan optimasi ini. Ini berguna jika finddipanggil pada beberapa sistem file di mana jumlah tautan direktori tidak mengikuti konvensi Unix.

Gilles 'SO- berhenti menjadi jahat'
sumber
Apakah ini masih relevan? Melihat findsumbernya, ia hanya menggunakan fts_open()dan fts_read()memanggil saat ini.
RealSkeptic
@RealSkeptic Apakah ini berubah dalam versi terbaru? Saya belum memeriksa sumbernya, tetapi secara eksperimental, versi 4.4.2 di stabil Debian memang mengoptimalkan statpanggilan ketika tidak membutuhkannya karena jumlah tautan direktori, dan -noleafopsi ini didokumentasikan dalam manual.
Gilles 'SANGAT berhenti menjadi jahat'
Itu mengoptimalkan statbahkan dalam fts...versi - itu melewati bendera yang sesuai untuk itu untuk fts_openpanggilan. Tapi yang saya tidak yakin masih relevan adalah cek dengan jumlah tautan. Ia memeriksa bukan apakah catatan fts yang dikembalikan memiliki salah satu dari bendera "direktori". Mungkin itu fts_readsendiri yang memeriksa tautan untuk mengatur bendera itu, tetapi findtidak. Anda dapat melihat apakah versi Anda bergantung ftsdengan menelepon find --version.
RealSkeptic
@Gilles, Apakah findsecara teoritis dapat menentukan kapan semua entri dalam direktori adalah direktori juga dan menggunakan informasi itu?
Gregory Nisbet
@GregoryNisbet Secara teori ya, tetapi kode sumber (sekarang saya sudah memeriksa) tidak melakukan itu, mungkin karena itu kasus yang jauh lebih jarang.
Gilles 'SANGAT berhenti menjadi jahat'