Haskell 优化 : how to stop list from performing allocations?

Question

在这个程序中:

module Main where
import Data.IntSet
main = do
   print $ size
         $ {-# SCC "fromAscList" #-} fromAscList
         $ {-# SCC "generate_list" #-} [1..1000]

(编译运行stack ghc Main.hs -- -prof -fprof-auto && ./Main +RTS -p)

我从 GHC 分析器中得到了这个输出(为简洁起见进行了编辑):

    total alloc =     202,704 bytes  (excludes profiling overheads)

COST CENTRE   MODULE           SRC                    %time %alloc

generate_list Main             Main.hs:6:40-48          0.0   39.5
fromAscList   Main             Main.hs:(5,38)-(6,48)    0.0   36.2
main          Main             Main.hs:(3,1)-(6,48)     0.0    5.0

                                          individual      inherited
COST CENTRE       MODULE                %time %alloc   %time %alloc

  main            Main                   0.0    0.1     0.0   75.8
   fromAscList    Main                   0.0   36.2     0.0   75.7
    generate_list Main                   0.0   39.5     0.0   39.5

这似乎表明 [1..a'] 在整个程序过程中分配了 80Kb(202,704 字节的 39.5%)，然后 fromAscList 是再次分配相同的金额。 (一个分配给输入的 Int，另一个分配给存储的 Int？)

两个问题:

1. 这些是来自 generate_list 的“真实”分配，还是重复使用同一 block 内存？ (我想知道堆分配是否会成为瓶颈。)
2. 如果重复使用堆，是否有办法将未装箱的值 1..1000 直接流式传输到 fromAscList？

Answer 1

您应该使用 fromDistinctAscList，否则每个下一个 Int 都必须与其前身进行比较，以确定是添加它还是跳过它，这肯定会招致您的开销观察。 (虽然我没有看过源代码，但这种情况似乎是合理的猜测，而且我们很难期望在这种情况下以最佳方式分配内存。)

试试这段代码:

main = do
   print $ size
         $ {-# SCC "fromDistinctAscList" #-} fromDistinctAscList
         $ {-# SCC "generate_list" #-} [1..1000]

我观察到的性能在内存方面提高了大约 36%。 (这个数字似乎与你的一致。)这是分析报告的相关部分:

COST CENTRE            MODULE                SRC                        no.     entries  %time %alloc   %time %alloc
....
  main                 ListAlloc             ListAlloc.hs:(5,1)-(8,55)  276          1    0.0    0.2     0.0   62.5
   fromDistinctAscList ListAlloc             ListAlloc.hs:(7,46)-(8,55) 278          1    0.0    1.1     0.0   62.4
    generate_list      ListAlloc             ListAlloc.hs:8:40-55       279          1    0.0   61.2     0.0   61.2
...

关于分配的实际情况，我不确定我是否理解这个问题，但是，通过 +RTS -S 查看垃圾回收，两种变体一直在几乎相同的内存中运行，呈线性增长由于 IntMap 的增长。似乎所有其他计算都是在相当小的常量内存中完成的。