Почему для обхода файловой системы предпочтительнее поиск-в-ширину?

Это перевод Why is breadth-first searching better for file system tree walking? Автор: Реймонд Чен.

Ранее, Эрик Липперт обсудил один сценарий, где поиск-в-ширину лучше, чем поиск-в-глубину. Сегодня, я расскажу о ещё одном случае.

Если вы посмотрите на старые функции перечисления файлов в MS-DOS, то вы обнаружите, что у вас есть функции типа "Найти первый файл" и "Найти следующий файл", но нет функции "Завершить поиск". Это потому что функции перечисления в MS-DOS хранили своё состояние целиком в записи для поиска. Файловая система FAT была достаточна проста, чтобы необходимое состояние поиска могло уместиться в зарезервированных байтах, так что не было нужды в привлечении внешних данных (если вы делали что-то странное, типа удаления каталога, в котором было активно перечисление, то функции перечисления начинали возвращать мусор. Это рассматривалось как ответственность приложения в те дни. Да уж, в однозадачной системе жизнь намного проще).

Однако, перемещение этих функций в сетевой протокол или файловые системы, отличные от FAT, создавало проблемы. Когда вы перечисляли файлы по сети, серверу нужно было выделять дополнительную память для отслеживания перечисления, память, которую нужно освободить, когда перечисление завершится. Аналогично, файловые системы, отличные от FAT, могли иметь дополнительное состояние для отслеживания, которое (1) не влезало в зарезервированное пространство в записи поиска, (2) вообще не должно было храниться в записи поиска (потому что это была бы дыра в безопасности) или (3) не могло храниться в записи поиска (потому что ядру нужно было обновлять его асинхронно, когда менялось состояние каталога).

Поскольку в MS-DOS не было функции "Завершить поиск", то как эти альтернативные файловые системы знали, когда можно безопасно освобождать память, ассоциированную с поиском? Ясновидение пока не жизнеспособный вариант, так что файловым системам пришлось угадывать.

Обычно, файловое перечисление рассматривается "покинутым", если оно не было использовано "длительное время" или же у нас слишком много активных файловых перечислений.

Давайте посмотрим, как поиск-в-глубину сравним с поиском-в-длину по этому показателю.

В типичном сценарии поиска-в-глубину, вы рекурсивно входите в подкаталог, как только вы его встречаете. Поэтому, если у вас есть, скажем, шесть уровней вложенности рекурсии, то у вас получается шесть активных перечислений - по одному на каждый уровень. Самое последнее является активным, а самое корневое - наименее активным. Всё это означает, что перечисление в корне имеет наибольшую вероятность стать "покинутым", потому что его долго не трогают и/или у нас будет слишком много активных перечислений (слишком глубокая рекурсия).

С другой стороны, с поиском-в-ширину, когда вы находите каталог, он не обрабатывается сразу же, а сохраняется в списке для последующего рассмотрения. Соответственно, в каждый момент времени у нас есть только одно активное перечисление и оно завершается до того, как стартует следующее. Это означает, что маловероятно, что перечисление будет помечено как "покинутое".

Эта проблема не является исключительно теоретической. Если вы производите поиск-в-глубину по огромному дереву на сетевом пути из MS-DOS программы, то вы вполне можете увидеть, что перечисления останавливаются до того, как они вернут все объекты, потому что простаивающие перечисления удаляются сервером. Вы также можете увидеть это и в Windows программе, если вы будете перечислять что-то на сервере, который был спроектирован для MS-DOS клиентов (и который, поэтому, не реализует FindClose).

Вы всё ещё можете использовать поиск-в-глубину, но при этом избегать проблемы остановки перечислений. Вместо немедленного рекурсивного входа каталог - сохраняйте его в список. После завершения перечисления пройдитесь по списку и вызовите рекурсивную функцию для каждого каталога в списке. Таким способом вы всё ещё будете производить поиск-в-глубину, но вы просто откладываете рекурсивный вызов до завершения перечисления.

Этот трюк с "отложенной рекурсией" используется Проводником для избегания проблемы преждевременного закрытия перечислений на старых серверах.

Примечание переводчика: в примере Эрика также используется эта техника.