Как быстрее составить список каталогов?

У меня есть несколько ситуаций, когда мне нужно рекурсивно перечислять файлы, но мои реализации были медленными. У меня есть структура каталогов с 92784 файлами.find перечисляет файлы менее чем за 0,5 секунды, но моя реализация на Haskell намного медленнее.

Моя первая реализация заняла чуть более 9 секунд, а следующая версия - чуть более 5 секунд, и сейчас у меня чуть меньше двух секунд.

listFilesR :: FilePath -> IO [FilePath]
listFilesR path = let
    isDODD "." = False
    isDODD ".." = False
    isDODD _ = True

    in do
        allfiles <- getDirectoryContents path
    dirs <- forM allfiles $ \d ->
      if isDODD d then
        do let p = path </> d
           isDir <- doesDirectoryExist p
           if isDir then listFilesR p else return [d]
        else return []
    return $ concat dirs

Тест занимает около 100 мегабайт памяти (+ RTS-s), и программа тратит около 40% в GC.

Я думал о том, чтобы сделать листинг в монаде WriterT с Sequence в качестве моноида, чтобы предотвратить создание конкататов и списков. Это вероятно, это помогает? Что еще я должен сделать?

Редактировать: Я отредактировал функцию, чтобы использовать readDirStream, и это помогает держать память нехваткой. Распределение еще происходит, но уровень производительности составляет> 95%, и он работает менее чем за секунду.

Это текущая версия:

list path = do
  de <- openDirStream path
  readDirStream de >>= go de
  closeDirStream de
  where
    go d [] = return ()
    go d "." = readDirStream d >>= go d
    go d ".." = readDirStream d >>= go d
    go d x = let newpath = path </> x
         in do
          e <- doesDirectoryExist newpath
          if e 
        then
          list newpath >> readDirStream d >>= go d
        else putStrLn newpath >> readDirStream d >>= go d 

Ответы на вопрос(4)

что она должна составить весь список содержимого каталога, прежде чем программа сможет что-либо с ними сделать. Ленивый ввод-вывод обычно вызывает недовольство, но использование unsafeInterleaveIO здесь значительно сокращает использование памяти.

listFilesR :: FilePath -> IO [FilePath]
listFilesR path = 
  let
    isDODD "." = False
    isDODD ".." = False
    isDODD _ = True
  in unsafeInterleaveIO $ do
    allfiles <- getDirectoryContents path
    dirs <- forM allfiles $ \d ->
      if isDODD d then
        do let p = path </> d
           isDir <- doesDirectoryExist p
           if isDir then listFilesR p else return [d]
        else return []
    return $ concat dirs
 Masse07 окт. 2010 г., 16:29
Это сбрило около 0,4 секунды и 20 мегабайт. Так немного лучше
Решение Вопроса

System.Directory.getDirectoryContents создает целый список и поэтому использует много памяти. Как насчет использованияSystem.Posix.Directory? System.Posix.Directory.readDirStream возвращает запись по одному.

Также,Библиотека FileManip может быть полезным, хотя я никогда не использовал его.

 ctrl-alt-delor04 сент. 2012 г., 23:54
@ Tsuyoshi Ито, как вы получаете счетчик жестких ссылок без статистики?
 Tsuyoshi Ito08 окт. 2010 г., 02:52
@mokus: Спасибо за информацию. В системах Posix чтение каталогаREADDIR не возвращает, является ли возвращаемая запись каталогом или нет, и поэтому вам необходим отдельный системный вызов (обычно stat или lstat), чтобы решить, является ли он каталогом. Следовательно, поведение описанной вами системы.Posix.Directory не является странным. В некоторых реализациях команды find используется метод подсчета жестких ссылок, чтобы пропустить ненужные вызовы stat, что ускоряет обход.
 Tsuyoshi Ito08 окт. 2010 г., 04:38
@mokus: Вау. Я не знал о поле d_type, но по крайней мереLinux а такжеFreeBSD И это тоже. Похоже, это де-факто стандарт.
 mokus08 окт. 2010 г., 03:01
В моей системе (Mac OS) «struct dirent» имеет поле «d_type», одним из возможных значений которого является «DT_DIR». Википедия намекает на то, что это необязательно в спецификации POSIX, но было бы убедительным аргументом для того, чтобы DirectoryStream предоставил операцию «isDir» или «fileType», которая бы использовала эту информацию, если она была доступна, и вызывала бы статистику в противном случае. Даже если это не обязательный стандарт, если у его платформы есть это, я был бы шокирован, если find не использует его.
 mokus08 окт. 2010 г., 01:09
Я сделал версию, используя System.Posix.Directory и итерированных, она мало что сделала, если вообще лучше. Одна странная вещь, которую я обнаружил, заключалась в том, что System.Posix.Directory, по-видимому, не обеспечивает ожидаемой функциональности. «readdir» возвращает указатель на «struct dirent», но, похоже, единственное, что вы можете получить из DirectoryStream, - это имя файла, что означает, что вам нужно сделать еще один вызов (предположительно, stat () через doDirectoryExist), чтобы выяснить, это каталог. Это также может быть частью проблемы - утилите find не нужно делать еще один системный вызов, чтобы определить, является ли он каталогом или нет.

ем? Я думал о службе / потоке асинхронного индексирования, который поддерживал бы актуальность этого кеша в фоновом режиме, возможно, вы могли бы сделать кеш как простую SQL-DB, которая затем дала бы вам хорошую производительность при выполнении запросов к нему?

Можете ли вы рассказать что-нибудь о своем «проекте / идее», чтобы мы могли предложить что-то альтернативное?

Я бы не стал использовать «полный индекс», поскольку я в основном создаю веб-сервисы, а «resposnetime» критикует меня, с другой стороны - если это начальный способ запуска нового сервера, я уверен, что клиенты не будут возражать жду этого в первый раз. Я бы просто сохранил результат в БД для последующего поиска.

 BerggreenDK09 окт. 2010 г., 03:34
хорошо - какую ОС вы собираете? Например. В Windows есть «события каталога» для новых файлов, переименования и т. Д. Если у вас есть какая-то «корневая» папка, вы можете установить «обработчик корневых событий» с рекурсивным срабатыванием. сам не пробовал, но я бы посмотрел в этом направлении после первой индексации каталога.
 ctrl-alt-delor04 сент. 2012 г., 23:49
В Linux есть глобальный файловый кеш, поэтому вам не нужно его писать, и он распределяется между приложениями. Он также имеет каталог событий.
 Masse08 окт. 2010 г., 06:19
Я всегда открыт для новых идей. Я пишу оболочку для Hyper Estraier, полнотекстового поискового движка, для использования на компьютере. Я опытный пользователь командной строки, поэтому я подумал о том, чтобы поработать с собирателями и искателями. На данный момент я преобразовал свой bash-скрипт в Haskell, но он по-прежнему использует команды estcmd для сбора и поиска, и системные вызовы процесса выглядят ужасно. А для родного собирателя мне нужно разобрать каждый файл хотя бы с первого прохода. Но я не могу придумать, как перечислить только файлы, которые были добавлены или изменены с прошлого раза.

что большая часть процессорного времени уходитgetDirectoryContents, doesDirectoryExist а также</>, Это означает, что только изменение структуры данных не очень поможет. Если вы хотите соответствовать производительностиfind Вы должны использовать функции более низкого уровня для доступа к файловой системе, вероятно, те, на которые указал Цуёси.

Ваш ответ на вопрос