Пишем замену find(1) на golang под Linux

[snizovtsev]

Я использую fzf — find и grep/ag в одном флаконе с интеграцией в vim и кучей плюшек. Тоже написано на Go и работает очень быстро.

[Stronix]

Таким образом вы лишаетесь кроссплатформенности. А как насчёт быстродействия Walk?

[youROCK]

Walk использует Readdirnames, так что производительность особо не отличается.

[youROCK]

На других платформах можно использовать generic-код, это ничему не противоречит

[galaxy]

Нас всячески отговаривают использовать этот системный вызов, но ту же утилиту find это ни капельки не смущает.

Удивительно, не правда ли? Учитывая, что getdents — нынче единственный системный вызов для чтения директории

[youROCK]

Дело в том, что find явно не просто зовет readdir, ибо «знает», какие файлы являются директориями, не делая stat

[galaxy]

Почему? В линуксе readdir возвращает тип файла в структуре: http://linux.die.net/man/3/readdir

[youROCK]

Чорт. Ну ок, тогда find, видимо, просто использует linux-specific поля readdir. В go в readdir ничего такого нет :(

[youROCK]

Вернее, filemode есть и есть метод IsDir(), но это достигается вызовом Stat(). Если говорить про Readdirnames(), то там только имена.

[icoz]

Что-то мне подсказывает, что у find исходники есть, и там можно посмотреть на происходящее.
Но из всего описанного я делаю вывод, что стандартная библиотека go ещё не до конца оптимизирована… Либо нужна параллельная реализация, которая будет тратить память, но буферизировать данные, полученные от системы.

[stalkerg]

Надо быть аккуратным вот с этим:
http://linux-tips.org/t/readdir-function-on-xfs-filesystem-not-working-properly/115

[mbait]

сканирование изменений в директории

по аналогии с утилитой find

find(1) умеет сканировать изменения, или я не так понял?

[b1rdex]

Видимо речь про diff списка файлов.

[youROCK]

Не умеет, разве что с фильтром по mtime можно получить нечто похожее. Я имел в виду, что на основе списка файлов можно определять изменения, если где-то хранить предыдущее состояние, как это делает git, например

[mbait]

Если речь идёт о периодическом сканировании, скажем, раз в день, то непонятно, зачем делать быстрее, чем find. Если нужно непрерывно это делать, но полное сканирование это очень плохой подход — медленный и нагружает диск и ядро. Смотрите inotify(7) и другие подобные инструменты.

Но сама тема разбора программ из coreutils однозначно интересна. Я когда-то разбирал sort(1), чтобы посмотреть, как она делает сортировку по кускам.

[stalkerg]

Предупреждаю т.к. недавно наткнулся: в любимой под Linux файловой системе XFS это работать не будет, без спец настройки ФС. :(
В итоге кусок кода на stat переводил обратно (но там время обхода не кретично).

[youROCK]

В документации об этом написано, и в этом случае должен возвращаться DT_UNKNOWN. В полном коде примера есть кусок, который делает stat(), когда получает такое значение

[nikitadanilov]

Oдно ограничение вашего кода (и исходного и модифицированного), которого нет у find(1), это невозможность работать с деревом, в котором длина путей превышает MAXPATHLEN. Поэтому find делает fchdir в директорию и из нее. Ну и при DT_UNKNOWN делать stat. У find есть еще одна оптимизация: от смотрит на nlink *родительской* директории. Это число на 1 больше числа поддиректорий (из-за dotdot). Поэтому если nlink == 1, то поддиректорий гарантировано нет (это самый распространенный случай — большинство директорий листьевые) и делать stat в случае DT_UNKNOWN не нужно.

[youROCK]

Кстати говоря, ограничения на MAXPATHLEN не должно быть, если не требуется делать Stat (т.е. на семейсте файловых систем ext, например). Я использую openat, а имя директории передаю только для того, чтобы напечатать его на экран.

В целом, я не буду спорить, что код (причём полная версия, а не та, что в статье) обрабатывает DT_UNKNOWN весьма неоптимально, и я даже перепутал Stat() с Lstat(), когда это делал.

Про значение nlink для директорий никогда не задумывался, спасибо! Впрочем, если вы не собираетесь получать DT_UNKNOWN (т.е. если ваши ФС это ext* или btrfs), то эта оптимизация не нужна :).

[nikitadanilov]

Кстати, ext* может быть создана без флага filetype (mkfs -O ^filetype). Этом случае всегда возвращается DT_UNKNOWN.

[youROCK]

Проверил на файловой системе ext3, создал директорию, на которую stat(2) ругается с ENAMETOOLONG, и конечная версия утилиты распечатала дерево целиком, и результат не отличается от find.

[Woodroof]

Есть ещё fts, и там тоже есть флаг FTS_NOSTAT, чтобы не делать stat при проходе по иерархии.

[pixelcube]

youROCK яп убрал еще рекурсию и аллоки в каждой итерации

[youROCK]

Да, убрать аллокации, возможно, помогло бы. Но если это всё аллоцируется на стеке (что надо проверить), то выигрыш по сути будет нулевой.

[pixelcube]

Если уберете рекурсию — стек будет много меньше.