haskell - 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

还是 [Char]类型的内存效率太低(与 Text相比)，导致 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编码，37 MB)。但是仍然使用3 GB的内存。

UPDATE 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)

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)

意思是每次迭代都会在堆上分配100多个字节，尽管实际上只是执行比较，减法，乘法和递归调用，

这就是@HTNW的意思，它表示GHC计划中的总分配是“工作”的量度。一个不分配的GHC程序可能什么也没做(同样，有一些罕见的例外)，一个典型的正在做某事的GHC程序在不进行垃圾收集时，通常会以相对恒定的速率每秒几千兆字节分配。因此，总分配与总运行时间的关系比其他任何事情都多，并且它不是评估代码效率的特别好指标。最大驻留时间也不能很好地衡量整体效率，但是如果您发现空间泄漏会随着输入大小的增加而线性增长(或更糟)，则有助于评估是否存在空间泄漏。无论输入大小如何，程序都应在恒定内存中运行。

对于大多数程序， +RTS -s输出中最重要的真实效率指标可能是底部的“生产率”比率-它是程序花费在垃圾收集上的时间。而且，诚然，您程序的48％的生产率非常糟糕，从技术上来说，这可能意味着它分配了过多的内存，但可能仅分配了其应有数量的两倍或三倍，因此，也许应该“仅”为此工作负载分配大约7-8 Gig而不是23 Gig(因此，运行时间大约为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个Gig:

  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，但运行速度非常快(大约是天真的C getchar / putchar实现的四分之一)，生产率为84％，同时在堆上分配了约5 Gig。

如果您只带上程序并将其“转换为 Text”，很可能会发现它比原始程序更慢，而且占用更多内存!尽管 Text可能比 String效率更高，但它是一个复杂的程序包，而且 Text对象在切片和切块后相对于分配的行为方式(例如，将大 Text文件切成小段时)小小的 Text字段)使正确设置变得更加困难。

因此，请注意以下几点:

总分配是效率的不好衡量。大多数编写良好的GHC程序可以并且应该每秒分配几GB的运行时间。

由于GHC编译代码的工作方式，许多无害的Haskell函数将分配大量内存。这不一定表示该功能有问题。

split包为所有形式的列表拆分操作提供了一个灵活的框架，但是考虑到它的设计速度，它可能不是处理制表符分隔文件的最佳方法。

String数据类型可能会导致严重的低效率，但并不总是效率低下，而且Text是一个复杂的程序包，不会作为插件替代来解决您的String性能问题。

最重要的是:

除非您的程序达到其预期目的的速度太慢，否则它的运行时统计信息和Text相对于String的理论优势在很大程度上是无关紧要的。