performance - 优化一个产生过多垃圾的列表函数(不是堆栈溢出)

Question

我有那个 Haskell 函数，这导致了我的程序所有分配的 50% 以上，导致 GC 占用了我 60% 的运行时间。我用一个小堆栈(-K10K)运行，所以没有堆栈溢出，但我可以让这个函数更快，分配更少吗？

这里的目标是计算矩阵与向量的乘积。我不能使用 hmatrix 例如，因为这是使用 ad Automatic Differentiation 的更大功能的一部分。包，所以我需要使用 Num 的列表.在运行时我想使用 Numeric.AD模块意味着我的类型必须是 Scalar Double .

listMProd :: (Num a) => [a] -> [a] -> [a]
listMProd mdt vdt = go mdt vdt 0
  where
    go [] _  s = [s]
    go ls [] s = s : go ls vdt 0
    go (y:ys) (x:xs) ix = go ys xs (y*x+ix)

基本上，我们循环遍历矩阵，将累加器相乘和相加，直到到达向量的末尾，存储结果，然后再次继续重新启动向量。我有一个 quickcheck测试验证我得到的结果与 hmatrix 中的矩阵/向量积相同。

我试过 foldl , foldr等。我尝试过的任何方法都无法使该功能更快(有些东西像 foldr 会导致空间泄漏)。

使用分析运行告诉我，除了这个函数是花费大部分时间和分配的地方之外，还有 Cells 的负载。正在创建， Cells是来自 ad 的数据类型包裹。

运行一个简单的测试:

import Numeric.AD

main = do
    let m :: [Double] = replicate 400 0.2
        v :: [Double] = replicate 4 0.1
        mycost v m = sum $ listMProd m v 
        mygrads = gradientDescent (mycost (map auto v)) (map auto m)
    print $ mygrads !! 1000

这在我的机器上告诉我 GC 有 47% 的时间都在忙。

有任何想法吗？

Answer 1

一个非常简单的优化是使 go函数通过其累加器参数严格，因为它很小，如果 a 可以取消装箱是原始的并且总是需要被充分评估:

{-# LANGUAGE BangPatterns #-}
listMProd :: (Num a) => [a] -> [a] -> [a]
listMProd mdt vdt = go mdt vdt 0
  where
    go [] _  !s = [s]
    go ls [] !s = s : go ls vdt 0
    go (y:ys) (x:xs) !ix = go ys xs (y*x+ix)

在我的机器上，它提供了 3-4 倍的加速(使用 -O2 编译)。

另一方面，中间列表不应该是严格的，所以它们可以被融合。