如何更快地列出目录？

Question

我有几种情况需要递归列出文件，但我的实现速度很慢。我的目录结构中有92784个文件。find在不到0.5秒的时间内列出了文件，但我的Haskell实现要慢很多。

我的第一个实现需要超过9秒才能完成，下一个版本需要超过5秒，而我目前的实现则少于2秒。

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），程序在GC中花费了约40%的时间。

我考虑使用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 

- Masse

Answer 1

我认为System.Directory.getDirectoryContents会构建整个列表，因此会使用大量内存。那么使用System.Posix.Directory如何？System.Posix.Directory.readDirStream逐个返回条目。

此外，FileManip库可能也很有用，尽管我从未使用过。

- Tsuyoshi Ito

---

我使用了System.Posix.Directory和迭代器来制作一个版本，但它并没有表现得更好。我发现一个奇怪的事情是，System.Posix.Directory似乎没有提供我期望的功能。 "readdir"返回一个指向"struct dirent"的指针，但似乎从DirectoryStream中唯一可以获取的是文件名 - 这意味着您必须进行另一个调用（可能是通过doesDirectoryExist调用stat()）才能找出它是否是目录。这也可能是问题的一部分 - find不需要进行另一个系统调用来发现它是否是目录。 - mokus

@mokus：感谢提供信息。在Posix系统中，使用readdir读取目录不会返回返回的条目是否为目录，因此需要单独的系统调用（通常是stat或lstat）来判断它是否为目录。因此，您所描述的System.Posix.Directory的行为并不奇怪。一些find命令的实现使用硬链接计数技巧来省略不必要的stat调用，从而加快遍历速度。 - Tsuyoshi Ito

在我的系统（Mac OS）上，“struct dirent”有一个字段“d_type”，其中一个可能的值是“DT_DIR”。 维基百科暗示这在POSIX规范中是可选的，但这肯定会成为DirectoryStream提供'isDir'或'fileType'操作的有力理由，如果可用则使用该信息并调用stat。即使它不是必需的标准，如果他的平台有它，我会很惊讶find没有使用它。 - mokus

@mokus：哇，我不知道d_type字段，但至少Linux和FreeBSD也有它。看起来这是一种事实标准。 - Tsuyoshi Ito

@Tsuyoshi Ito 您如何在不使用stat的情况下获取硬链接计数？ - ctrl-alt-delor

Answer 2

对代码进行性能分析后发现大部分 CPU 时间花费在 getDirectoryContents、doesDirectoryExist 和 </> 上。 这意味着仅仅更改数据结构不会有太大帮助。如果你想达到与 find 相同的性能，应该使用更低级别的文件系统访问函数，可能是 Tsuyoshi 指出的那些函数。

- Daniel

Answer 3

一个问题是它必须构建整个目录内容列表，然后程序才能对它们进行任何操作。懒惰I/O通常被认为不好，但在这里使用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

- sabauma

---

那样可以减少约0.4秒和20兆字节。所以稍微好一点。 - Masse

Answer 4

是否可以使用某种缓存系统与读取结合使用？我在考虑一个异步索引服务/线程，它会在后台保持此缓存最新，也许您可以将缓存作为简单的SQL-DB，这样在对其进行查询时会给您带来一些良好的性能？

您能详细说明一下您的“项目/想法”，以便我们提出替代方案吗？

我个人不会选择“完整索引”，因为我主要构建基于Web的服务，“响应时间”对我至关重要，另一方面，如果这是启动新服务器的初始方式，我相信客户不介意等待第一次。我只会将结果存储在数据库中以供以后查找。

- BerggreenDK

---

我总是乐于接受新的想法。我正在为Hyper Estraier编写一个包装器，这是一个全文搜索引擎，用于桌面使用。我是一个重度命令行用户，所以我考虑做一个本地的gatherer和searcher。目前，我已经将我的bash脚本转换为Haskell，但它仍然使用estcmd命令进行收集和搜索，并且系统进程调用很丑陋。对于本地gatherer，我需要至少使用第一遍解析每个文件。但我想不出一种只列出自上次以来添加或修改的文件的方法。 - Masse

好的 - 你要为哪种操作系统构建？例如，Windows有“目录事件”用于新文件、重命名等。如果你有某种“根”文件夹，你可能可以放置一个“根事件处理程序”，并进行递归触发。我自己没有尝试过，但在第一次索引目录后，我会朝那个方向寻找。 - BerggreenDK

Linux拥有全局文件缓存，因此您无需编写自己的缓存，并且它在应用程序之间共享。它还具有目录事件。 - ctrl-alt-delor