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

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)

基本上是循环遍历矩阵，乘以并添加累加器，直到到达vector的末端，存储结果，然后再次继续重新启动vector。我有一个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编译)。

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