优化创建过多垃圾的列表函数(不是堆栈溢出)

Question

我有Haskell功能,这导致了我的程序的所有分配的50%以上,导致60%的运行时间被GC占用.我运行一个小堆栈(-K10K)所以没有堆栈溢出,但是我可以更快地使用更少的分配来实现此功能吗？

这里的目标是通过向量计算矩阵的乘积.我不能使用hmatrix例如因为这是使用ad自动微分包的更大功能的一部分,所以我需要使用列表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).

另一方面,中间列表不应该严格,因此它们可以融合.