Почему GNU находит так быстро по сравнению с графическими утилитами поиска файлов?

47

Я пытаюсь найти файл, который не существует в моем домашнем каталоге и во всех подкаталогах.

find ~/ -name "bogus"дает мне эту информацию через несколько секунд, но файловому менеджеру KDEdolphin понадобилось почти 3 минуты, чтобы сделать то же самое. Это соответствует моему предыдущему опыту работы с GNOMEbeagle .

Как findудается делать то же самое очень быстро, в то время как графический поиск (который более интуитивно понятен в использовании, чем параметры командной строки) отстает?

красный
источник
Я не знаю, что такое «Дельфин», но может быть, он тоже заглядывает в файлы?
Кусалананда
1
Это графический файловый менеджер из KDE: kde.org/applications/system/dolphin. Он имеет возможность поиска внутри файлов, но я не включил эту опцию во время этого короткого теста.
Красный
9
Вы искали в дельфине более одного раза? Это может быть "индексация" в первый раз. И "найти" тоже медленно. Попробуйте "найти", если файл старше, чем в прошлый раз, когда база данных для поиска была проиндексирована ;-)
Rinzwind
Я использую locateчаще, чем findэто, и это быстрее в огромной папке
phuclv
11
Хотя locateон действительно хорош для поиска файлов, это немного OT, потому что он использует совершенно другой подход: findинструменты GUI, такие как Dolphin, обходят дерево файлов по требованию, в то время locateкак используют ранее созданную структуру индекса.
Майкл Шеферс

Ответы:

68

Рассматривая Dolphin с Baloo, он ищет метаданные каждого файла в своей области поиска, даже если вы выполняете простой поиск по имени файла. Когда я отслеживаю file.soпроцесс, я вижу вызовы lstat, getxattrи getxattrснова для каждого файла, и даже для ..записей. Эти системные вызовы извлекают метаданные о файле, который хранится в другом месте, чем имя файла (имя файла хранится в содержимом каталога, но метаданные находятся в inode ). Многократный запрос метаданных файла является дешевым, поскольку данные будут находиться в кеше диска, но между запросом метаданных и отказом от метаданных может быть существенная разница.

findгораздо умнее Он пытается избежать ненужных системных вызовов. Он не будет вызываться, getxattrпотому что не выполняет поиск по расширенным атрибутам. Когда он пересекает каталог, ему может потребоваться вызвать lstatнесоответствующие имена файлов, потому что это может быть подкаталог для рекурсивного поиска ( lstatэто системный вызов, который возвращает метаданные файла, включая тип файла, такой как обычный / directory / symlink /…). Тем findне менее, имеет оптимизацию: он знает, сколько подкаталогов у каталога, по количеству ссылок , и останавливает вызов, lstatкак только узнает, что он прошел все подкаталоги. В частности, в листовом каталоге (каталог без подкаталогов),findпроверяет только имена, а не метаданные. Кроме того, некоторые файловые системы хранят копию типа файла в записи каталога, поэтому findдаже не нужно вызывать ее, lstatесли это единственная информация, которая ему нужна.

Если вы работаете findс опциями, которые требуют проверки метаданных, он будет делать больше lstatвызовов, но он все равно не будет делать lstatвызов файла, если ему не нужна информация (например, потому что файл исключен предыдущим условием). совпадение по названию).

Я подозреваю, что другие инструменты поиска с графическим интерфейсом, которые изобретают findвелосипед, также менее умны, чем утилита командной строки, которая подверглась десятилетиям оптимизации. Dolphin, по крайней мере, достаточно умен, чтобы использовать базу данных locate при поиске «везде» (с ограничением, которое не ясно в пользовательском интерфейсе, что результаты могут быть устаревшими).

Жиль "ТАК - перестань быть злым"
источник
22
GNU find настолько «умна», что пропускает некоторые файлы в некоторых типах файловых систем. Хорошо известная ошибка в GNU find заключается в том, что она делает недопустимое предположение о том, что счетчик ссылок на каталог: 2 + number of sub-directories.Это работает для файловых систем, которые реализуют ошибку проектирования из файловой системы UNIX V7, но не для всех файловых систем, поскольку это не является требованием POSIX. , Если вы хотите получить полезный номер производительности для GNU make, вам нужно указать -noleafпорядок, чтобы GNU make вел себя правильно.
Шили
12
@schily, у GNU, findвозможно, была эта ошибка давным-давно, но я сомневаюсь, что вы найдете случай, когда вам нужно указать -noleafвручную. AFAICT, по крайней мере в Linux getdents()(и readdir ()) сообщает, какие файлы являются файлами каталогов в UDF, ISO-9660, btrfs, которые не имеют вещественных .или ..записей и findведут себя там нормально. Знаете ли вы об одном случае, когда GNU findдемонстрирует проблему?
Стефан Шазелас
4
Просто используйте этот гнилой образ из Debian, чтобы создать файловую систему Rock Ridge с использованием «точек пересадки», и количество ссылок в каталоге является случайным значением. Поскольку Rock Ridge реализует счетчик ссылок и. / .., GNU find обычно не находит все файлы в такой файловой системе.
Шили
4
@ StéphaneChazelas: В прошлый раз, когда я проверял (для магистерской работы), ошибка была исправлена ​​путем утверждения ровно 2 означенного известного листа, а не <= 2. Файловые системы, которые не реализуют счетчик 2+, все возвращают 1 для счетчика ссылок каталога, поэтому все хорошо. Теперь, если когда-нибудь кто-нибудь создаст файловую систему, которая будет делать жесткие ссылки на каталоги, у которых нет этого свойства, у кого-то будет плохой день.
Джошуа
15
@schily, я не смог получить случайное количество ссылок с точками пересадки и RR с помощью genisoimage 1.1.11 в Debian, и даже если я отредактировал двоичное изображение iso для изменения количества ссылок на случайные значения, я все равно не вижу никаких проблема с GNU find. И в любом случае, strace -vпоказывает, что getdents()правильно возвращает d_type = DT_DIR для каталогов, поэтому в GNU find не нужно использовать трюк с подсчетом ссылок.
Стефан Шазелас