haskell - 在 Haskell 中对键/值对进行分组时发生空间泄漏

Question

我遇到了一个问题，我的代码创建了太多 thunk(超过 270MB)，因此在按键对值进行分组时在 GC 中花费了太多时间(超过 70%)。我想知道按键对值进行分组的最佳方法是什么。

问题是我有由向量表示的键和值，我想按保留顺序的键对值进行分组。例如:

输入:

keys = 1 2 4 3 1 3 4 2 1 
vals = 1 2 3 4 5 6 7 8 9

输出:

1 = 1,5,9
2 = 2,8
3 = 4,6
4 = 3,7

编译选项:

ghc --make -03 -fllvm histogram.hs

在命令式编程中，我只会使用多重映射，所以我决定使用哈希表，其中关联值是 [Int] 来存储分组值。我希望有更好的 FP 解决方案。

{-# LANGUAGE BangPatterns #-}
import qualified Data.HashMap.Strict as M
import qualified Data.Vector.Unboxed as V

n :: Int
n = 5000000

kv :: V.Vector (Int,Int)
kv = V.zip k v
 where
    k = V.generate n (\i -> i `mod` 1000)
    v = V.generate n (\i -> i)

ts :: V.Vector (Int,Int) -> M.HashMap Int Int
ts vec =
    V.foldl' (\ht (k, v) -> M.insertWith (+) k v ht) M.empty vec

ts2 :: V.Vector (Int,Int) -> M.HashMap Int [Int]
ts2 vec =
    V.foldl' (\ht (!k, !v) -> M.insertWith (++) k [v] ht) M.empty vec

main :: IO ()
main = ts2 kv `seq` putStrLn "done"

这是运行时吐出的内容:

   3,117,102,992 bytes allocated in the heap
   1,847,205,880 bytes copied during GC
     324,159,752 bytes maximum residency (12 sample(s))
       6,502,224 bytes maximum slop
             658 MB total memory in use (0 MB lost due to fragmentation)

                                    Tot time (elapsed)  Avg pause  Max pause
  Gen  0      5991 colls,     0 par    0.58s    0.58s     0.0001s    0.0003s
  Gen  1        12 colls,     0 par    0.69s    0.69s     0.0577s    0.3070s

  INIT    time    0.00s  (  0.00s elapsed)
  MUT     time    0.45s  (  0.45s elapsed)
  GC      time    1.27s  (  1.27s elapsed)
  EXIT    time    0.03s  (  0.03s elapsed)
  Total   time    1.75s  (  1.75s elapsed)

  %GC     time      72.7%  (72.8% elapsed)

  Alloc rate    6,933,912,935 bytes per MUT second

  Productivity  27.3% of total user, 27.3% of total elapsed

你可以看到它在 GC 中花费了很多时间，所以我决定使用刘海来使列表连接严格。我想 ++ 也很昂贵，但不知道解决这个问题的方法。

Answer 1

那些严格注释是没用的。他们只强制列表的第一个构造函数。

更糟糕的是，您似乎正试图向左折叠 (++)，这绝不是一个好主意。它会导致大量无用的中间列表复制，即使它是完全严格的。

您应该折叠到 [Int] -> [Int] 值。这将摆脱多个无用的分配。我在移动设备上，所以我无法真正提供完整的示例代码。主要思想是将循环更改为 M.insertWith (.) k (v:)，然后将 ($ [] ) 映射到 HashMap 中的值之后折叠。