Mengapa GNU menemukan sangat cepat dibandingkan dengan utilitas pencarian file grafis?

47

Saya mencoba mencari file yang tidak ada di direktori home saya dan semua subdirektori.

find ~/ -name "bogus"memberi saya informasi itu setelah beberapa detik, namun manajer file KDEdolphin membutuhkan hampir 3 menit untuk melakukan hal yang sama. Ini sesuai dengan pengalaman saya sebelumnya dengan GNOMEbeagle .

Bagaimana cara findmelakukan hal yang sama dengan sangat cepat sementara pencarian grafis (yang lebih intuitif untuk digunakan daripada parameter commandline) siput di belakang?

Merah
sumber
Saya tidak tahu apa itu "Lumba-lumba", tetapi apakah itu mungkin juga melihat ke dalam file?
Kusalananda
1
Ini adalah manajer file grafis dari KDE: kde.org/applications/system/dolphin. Ini memiliki kemampuan untuk mencari file di dalam, tetapi saya tidak mengaktifkan opsi itu selama pengujian singkat ini.
Merah
9
Apakah Anda mencari lebih dari sekali di lumba-lumba? Mungkin "mengindeks" pertama kali. Dan "menemukan" juga lambat. Coba "cari" jika file lebih lama dari terakhir kali database untuk lokasi diindeks ;-)
Rinzwind
Saya menggunakan locatelebih sering daripada finddan lebih cepat di folder besar
phuclv
11
sementara locatesangat bagus untuk menemukan file, ini sedikit OT, karena menggunakan pendekatan yang sama sekali berbeda: finddan alat GUI seperti Dolphinmelintasi pohon file sesuai permintaan, sementara locatemenggunakan struktur indeks yang dibuat sebelumnya.
Michael Schaefers

Jawaban:

68

Melihat Dolphin dengan Baloo secara khusus, tampaknya mencari metadata setiap file dalam domain pencariannya, bahkan jika Anda melakukan pencarian nama file sederhana. Ketika saya melacak file.soproses, saya melihat panggilan ke lstat, getxattrdan getxattrlagi untuk setiap file, dan bahkan untuk ..entri. Panggilan sistem ini mengambil metadata tentang file yang disimpan di lokasi yang berbeda dari nama file (nama file disimpan dalam isi direktori, tetapi metadata berada di inode ). Meminta metadata file berkali-kali adalah murah karena data akan berada di cache disk, tetapi mungkin ada perbedaan yang signifikan antara meminta metadata dan tidak meminta metadata.

findjauh lebih pintar. Mencoba menghindari panggilan sistem yang tidak perlu. Itu tidak akan memanggil getxattrkarena tidak mencari berdasarkan atribut yang diperluas. Ketika melintasi direktori, mungkin perlu memanggil lstatnama file yang tidak cocok karena itu mungkin subdirektori untuk mencari secara rekursif ( lstatadalah panggilan sistem yang mengembalikan metadata file termasuk jenis file seperti biasa / direktori / symlink / ...). Namun findmemiliki pengoptimalan: ia tahu berapa banyak subdirektori yang dimiliki suatu direktori dari jumlah tautannya , dan ia berhenti memanggil lstatbegitu ia mengetahui bahwa subdirektori melintasi semua subdirektori. Secara khusus, dalam direktori daun (direktori tanpa subdirektori),findhanya memeriksa nama, bukan metadata. Selain itu beberapa sistem file menyimpan salinan jenis file dalam entri direktori sehingga findbahkan tidak perlu memanggil lstatjika hanya itu informasi yang diperlukan.

Jika Anda menjalankan finddengan opsi yang perlu memeriksa metadata, itu akan membuat lebih banyak lstatpanggilan, tetapi itu tetap tidak akan membuat lstatpanggilan pada file jika tidak memerlukan informasi (misalnya karena file tersebut dikecualikan oleh kondisi sebelumnya sesuai dengan namanya).

Saya menduga bahwa alat pencarian GUI lain yang menemukan kembali findroda sama kurang pintar dari utilitas baris perintah yang telah mengalami beberapa dekade optimasi. Dolphin, setidaknya, cukup pintar untuk menggunakan basis data lokasi jika Anda mencari "di mana-mana" (dengan batasan yang tidak jelas di UI bahwa hasilnya mungkin kedaluwarsa).

Gilles 'SANGAT berhenti menjadi jahat'
sumber
22
GNU find sangat "pintar" sehingga melewatkan beberapa file pada beberapa tipe sistem file. Bug yang terkenal di GNU temukan adalah ia membuat asumsi ilegal bahwa jumlah tautan sebuah direktori adalah 2 + number of sub-directories.Ini berfungsi untuk filesystem yang mengimplementasikan bug desain dari UNIX V7 filesystem, tetapi tidak untuk semua filesystem, karena ini bukan persyaratan POSIX . Jika Anda ingin mendapatkan nomor kinerja yang berguna untuk pembuatan GNU, Anda perlu menentukan -noleafuntuk memberi tahu GNU agar berperilaku dengan benar.
schily
12
@ findmungkin , GNU mungkin sudah memiliki bug itu sejak lama, tapi saya ragu Anda akan menemukan case di mana Anda perlu menentukan -noleafdengan tangan saat ini. AFAICT, di Linux setidaknya getdents()(dan readdir ()) memberi tahu file mana yang merupakan file direktori pada UDF, ISO-9660, btrfs yang tidak memiliki entri .atau nyata ..dan findberperilaku OK di sana. Apakah Anda tahu satu kasus di mana GNU findmenunjukkan masalahnya?
Stéphane Chazelas
4
Cukup gunakan genisoimage busuk ini dari debian untuk membuat sistem file Rock Ridge menggunakan "graft-points" dan jumlah tautan dalam direktori adalah nilai acak. Karena Rock Ridge mengimplementasikan jumlah tautan dan / .., penemuan GNU biasanya tidak akan menemukan semua file pada sistem file seperti itu.
schily
4
@ StéphaneChazelas: Terakhir kali saya memeriksa (untuk tesis master saya), bug diperbaiki dengan menyatakan tepat 2 berarti leaf diketahui daripada <= 2. Sistem file yang tidak menerapkan 2+ counter semua mengembalikan 1 untuk jumlah link direktori jadi semuanya baik-baik saja Sekarang jika suatu hari seseorang membuat sistem file yang melakukan tautan keras ke direktori yang tidak memiliki properti ini, seseorang akan mengalami hari yang buruk.
Joshua
15
@schily, saya tidak bisa mendapatkan jumlah tautan acak dengan graft-points dan RR dengan genisoimage 1.1.11 di Debian dan bahkan jika saya biner-edit gambar iso untuk mengubah jumlah tautan menjadi nilai acak, saya masih tidak melihat adanya masalah dengan GNU find. Dan bagaimanapun, strace -vmenunjukkan bahwa getdents()dengan benar mengembalikan d_type = DT_DIR untuk direktori, jadi GNU menemukan tidak harus menggunakan trik penghitungan tautan.
Stéphane Chazelas