splitOn的内存占用？

Question

我编写了一个文件索引程序，它应该将成千上万的文本文件行读取为记录，并最终通过指纹对这些记录进行分组。它使用 Data.List.Split.splitOn 来在制表符处拆分行并检索记录字段。该程序消耗了 10-20 GB 的内存。

也许我无法做太多来减少那么大的内存占用，但我无法解释为什么像 splitOn (breakDelim) 这样的函数会消耗那么多内存：

    Mon Dec  9 21:07 2019 Time and Allocation Profiling Report  (Final)

       group +RTS -p -RTS file1 file2 -o 2 -h

    total time  =        7.40 secs   (7399 ticks @ 1000 us, 1 processor)
    total alloc = 14,324,828,696 bytes  (excludes profiling overheads)

COST CENTRE                          MODULE                    SRC                                                %time %alloc

fileToPairs.linesIncludingEmptyLines ImageFileRecordParser     ImageFileRecordParser.hs:35:7-47                    25.0   33.8
breakDelim                           Data.List.Split.Internals src/Data/List/Split/Internals.hs:(151,1)-(156,36)   24.9   39.3
sortAndGroup                         Aggregations              Aggregations.hs:6:1-85                              12.9    1.7
fileToPairs                          ImageFileRecordParser     ImageFileRecordParser.hs:(33,1)-(42,14)              8.2   10.7
matchDelim                           Data.List.Split.Internals src/Data/List/Split/Internals.hs:(73,1)-(77,23)      7.4    0.4
onSublist                            Data.List.Split.Internals src/Data/List/Split/Internals.hs:278:1-72            3.6    0.0
toHashesView                         ImageFileRecordStatistics ImageFileRecordStatistics.hs:(48,1)-(51,24)          3.0    6.3
main                                 Main                      group.hs:(47,1)-(89,54)                              2.9    0.4
numberOfUnique                       ImageFileRecord           ImageFileRecord.hs:37:1-40                           1.6    0.1
toHashesView.sortedLines             ImageFileRecordStatistics ImageFileRecordStatistics.hs:50:7-30                 1.4    0.1
imageFileRecordFromFields            ImageFileRecordParser     ImageFileRecordParser.hs:(11,1)-(30,5)               1.1    0.3
toHashView                           ImageFileRecord           ImageFileRecord.hs:(67,1)-(69,23)                    0.7    1.7

或者说，相比于Text，类型[Char]的内存效率太低了，导致splitOn占用了大量内存吗？

更新1（用户HTNW建议使用+RTS -s）

  23,446,268,504 bytes allocated in the heap
  10,753,363,408 bytes copied during GC
   1,456,588,656 bytes maximum residency (22 sample(s))
      29,282,936 bytes maximum slop
            3620 MB total memory in use (0 MB lost due to fragmentation)

                                     Tot time (elapsed)  Avg pause  Max pause
  Gen  0     45646 colls,     0 par    4.055s   4.059s     0.0001s    0.0013s
  Gen  1        22 colls,     0 par    4.034s   4.035s     0.1834s    1.1491s

  INIT    time    0.000s  (  0.000s elapsed)
  MUT     time    7.477s  (  7.475s elapsed)
  GC      time    8.089s  (  8.094s elapsed)
  RP      time    0.000s  (  0.000s elapsed)
  PROF    time    0.000s  (  0.000s elapsed)
  EXIT    time    0.114s  (  0.114s elapsed)
  Total   time   15.687s  ( 15.683s elapsed)

  %GC     time      51.6%  (51.6% elapsed)

  Alloc rate    3,135,625,407 bytes per MUT second

  Productivity  48.4% of total user, 48.4% of total elapsed

处理后的文本文件比通常小（UTF-8编码，37MB），但仍然使用了3GB内存。

更新2（代码的关键部分）

解释： fileToPairs 处理一个文本文件。它返回一个键值对列表（键：记录的指纹，值：记录本身）。

sortAndGroup associations = Map.fromListWith (++) [(k, [v]) | (k, v) <- associations]

main = do
  CommandLineArguments{..} <- cmdArgs $ CommandLineArguments {
    ignored_paths_file = def &= typFile,
    files = def &= typ "FILES" &= args,
    number_of_occurrences = def &= name "o",
    minimum_number_of_occurrences = def &= name "l",
    maximum_number_of_occurrences = def &= name "u",
    number_of_hashes = def &= name "n",
    having_record_errors = def &= name "e",
    hashes = def
  }
    &= summary "Group image/video files"
    &= program "group"

  let ignoredPathsFilenameMaybe = ignored_paths_file
  let filenames = files
  let hashesMaybe = hashes

  ignoredPaths <- case ignoredPathsFilenameMaybe of
    Just ignoredPathsFilename -> ioToLines (readFile ignoredPathsFilename)
    _ -> return []

  recordPairs <- mapM (fileToPairs ignoredPaths) filenames

  let allRecordPairs = concat recordPairs
  let groupMap = sortAndGroup allRecordPairs
  let statisticsPairs = map toPair (Map.toList groupMap) where toPair item = (fst item, imageFileRecordStatisticsFromRecords . snd $ item)

  let filterArguments = FilterArguments {
    numberOfOccurrencesMaybe = number_of_occurrences,
    minimumNumberOfOccurrencesMaybe = minimum_number_of_occurrences,
    maximumNumberOfOccurrencesMaybe = maximum_number_of_occurrences,
    numberOfHashesMaybe = number_of_hashes,
    havingRecordErrorsMaybe = having_record_errors
  }
  let filteredPairs = filterImageRecords filterArguments statisticsPairs

  let filteredMap = Map.fromList filteredPairs
  case hashesMaybe of
        Just True -> mapM_ putStrLn (map toHashesView (map snd filteredPairs))
        _ -> Char8.putStrLn (encodePretty filteredMap)

- ideaboxer

---

[Char] 不够高效，应尽可能避免使用。 - user1198582

在一台64位机器上， [Char] 每个字符至少使用24个字节！请使用 Data.Text。 - luqui

total alloc 不是实际使用的内存量。尽管将其保持在较低水平是有好处的，但实际的最大内存由 +RTS -s 中的“maximum residency” 给出。总分配通常是“工作”的度量，大部分是临时对象。无论如何，在这里看到实际的代码是必要的。此外，粗心/自动化 profiling 可能会阻止重要的优化。+RTS -s 可以在没有 profiling 的情况下工作，请检查（当然需要重新编译并关闭 profiling）。根据 @luqui 的说法，每行 1,000 个字符的 100,000 行仍然 <3GB 在 NF [Char] 中，这可能意味着某些问题。 - HTNW

也许你应该展示代码中关键的部分，你认为会占用大量内存。这样做也有助于社区避免使用这种方法。一旦你提出了一个明确的问题，我相信会有人指出正确的方向并给出实质性的答案。 - Redu

@luqui，是的，这只适用于ASCII或类似编码；其他任何编码都需要40个字节。 - dfeuer

Answer 1

我相信您已经意识到，这里并没有足够的信息来帮助您使程序更加高效。也许在Code Review网站上发布一些（完整的、自包含的）代码会有所帮助。

然而，我认为我可以回答你关于为什么splitOn分配了那么多内存的具体问题。实际上，splitOn或它的实现并没有什么特别之处。许多直接的Haskell函数都将分配大量内存，这本身并不表明它们编写不良或运行效率低下。特别地，splitOn的内存使用情况似乎类似于基于分隔符拆分字符串的其他直接方法。

首先要理解的是，GHC编译的代码与您可能见过的其他编译的代码工作方式不同。如果您了解很多C语言并且理解堆栈帧和堆分配，或者如果您研究过一些JVM实现，您可能会合理地预期，其中某些理解将转化为GHC可执行文件，但您大错特错了。

GHC程序更或多或少就是一种为分配堆对象的引擎，除了一些例外情况外，这就是它真正要做的事情。几乎每个传递给函数或构造函数的参数（以及构造函数本身的应用），都会分配至少16个字节的堆对象，通常更多。例如一个简单的函数：“

fact :: Int -> Int
fact 0 = 1
fact n = n * fact (n-1)

如果关闭优化，它将被编译为以下所谓的“STG”形式（简化了实际的-O0 -ddump-stg输出）：

fact = \n -> case n of I# n' -> case n' of
  0# -> I# 1#
  _ -> let sat1 = let sat2 = let one = I#! 1# in n-one
                  in fact sat2;
       in n*sat1

在代码中的每个 let 都会进行堆分配（16+字节），并且在 (-) 和 (*) 调用中可能还有更多的堆分配。使用以下命令编译和运行此程序：

main = print $ fact 1000000

提供：

 113,343,544 bytes allocated in the heap
  44,309,000 bytes copied during GC
  25,059,648 bytes maximum residency (5 sample(s))
      29,152 bytes maximum slop
          23 MB total memory in use (0 MB lost due to fragmentation)

意味着每次迭代在堆上分配了一百多个字节，尽管它只是执行比较、减法、乘法和递归调用。

这就是@HTNW所说的GHC程序的总分配量是“工作”的度量意义。一个没有分配的GHC程序可能什么都没做(再次强调，有些例外情况除外)，而一个典型的GHC程序在不进行垃圾回收时通常会以每秒数千兆字节的相对恒定速率进行分配。因此，总分配量与总运行时间有关，它不是评估代码效率的特别好的指标。最大驻留空间也是一种衡量整体效率的差劲指标，尽管它可以帮助评估是否存在空间泄漏，如果发现它随输入大小成线性增长(或更糟)，而您期望该程序应该使用恒定内存来运行，则可以判断是否存在空间泄漏。

对于大多数程序，在+RTS -s输出中最重要的真正的效率指标可能是底部的"生产率"速率 —— 程序在非垃圾回收时所花费的时间。而且，诚然，你的程序的生产率为48%是相当糟糕的，这可能意味着它在技术上分配了过多的内存，但它可能只分配了两到三倍的量，所以，猜测可能应该将其“仅”分配约7-8 Gigs左右的内存来处理这个工作负载(因此运行时间约为5秒而不是15秒)。

考虑以下简单的breakDelim实现。

breakDelim :: String -> [String]
breakDelim str = case break (=='\t') str of
  (a,_:b) -> a : breakDelim b
  (a,[])  -> [a]

并且在一个简单的制表符转逗号分隔文件转换器中使用它，就像这样：

main = interact (unlines . map (intercalate "," . breakDelim) . lines)

然后，没有优化的情况下，对一个包含10000行，每行有1000个3字符字段的文件运行它，它会分配高达17 GB的内存：

  17,227,289,776 bytes allocated in the heap
   2,807,297,584 bytes copied during GC
         127,416 bytes maximum residency (2391 sample(s))
          32,608 bytes maximum slop
               0 MB total memory in use (0 MB lost due to fragmentation)

对其进行剖析时，它将很大程度上归咎于 breakDelim：

COST CENTRE MODULE    SRC                    %time %alloc

main        Main      Delim.hs:8:1-71         57.7   72.6
breakDelim  Main      Delim.hs:(4,1)-(6,16)   42.3   27.4

在这种情况下，使用-O2编译没有太大的区别。重要的效率指标——生产力只有46%。所有这些结果似乎都符合你在程序中看到的情况。 split包具有很多优点，但是通过查看代码，很明显没有花费太多精力使其特别高效或快速，因此并不奇怪splitOn的性能并不比我自己设计的breakDelim函数更强。如我之前所说，splitOn没有任何特殊之处，使它特别占用内存——我的简单的breakDelim有类似的行为。

关于String类型的低效率问题，它经常会出现问题。但是，它也可以以列表融合的方式参与优化，而Text无法做到。上面的实用程序可以简化为以下形式：

main = interact $ map (\c -> if c == '\t' then ',' else c)

使用了`String`类型实现，但速度相当快（大约只有naive C `getchar`/`putchar`实现的四分之一），生产率为84％，同时在堆上分配了约5个Gigs的空间。

如果你只是把你的程序“转换为`Text`”，很可能会发现它比原来的程序更慢，更占用内存！虽然`Text`有比`String`更高的性能潜力，但它是一个复杂的包，在对切片的`Text`对象进行分配时（例如将一个大`Text`文件切成小的`Text`字段时），使得它更难以正确处理。

因此，有一些需要注意的问题：

- 总分配量不是衡量效率的好方法。大多数编写良好的GHC程序可以并且应该在运行时每秒分配数GB。 - 由于GHC编译代码的工作方式，许多无害的Haskell函数将分配大量的内存。这并不一定表明函数存在问题。 - `split`包提供了一个灵活的框架，可用于各种酷炫的列表拆分操作，但它不是为了速度而设计的，并且可能不是处理制表符分隔文件的最佳方法。 - `String`数据类型具有可怕的低效性潜力，但并不总是低效的，而`Text`是一个复杂的包，不能作为修复你的`String`性能问题的即插即用替代品。

最重要的是：

- 除非你的程序对其预期目的来说太慢了，否则其运行时统计数据和`Text`相对于`String`的理论优势大都不相关。

- K. A. Buhr

---

谢谢您提供详细的解释。您会如何编写一个（比我的更高效的）程序，将记录按其字段之一分组？我认为这是一个相当常见和简单的任务。 - ideaboxer

我会建议先看一下 cassava 包来解析分隔文本。它是基于高性能的 Attoparsec 解析器构建的，并且已经被设计成高效的。它可以将记录解析为 Vector 的 Text（或 Vector 的 ByteString 或任意代数数据类型），并且应该能够处理我上面提到的大部分棘手的分配问题。 - K. A. Buhr

我只是用 cassava 替换了 splitOn，现在它只使用了 4 GB 的内存。虽然仍然很多，但比以前好多了。 - ideaboxer