11

我有那个 Haskell 函数，这导致了我的程序所有分配的 50% 以上，导致 GC 占用了我 60% 的运行时间。我用一个小堆栈 ( -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% 的时间都在忙。

有任何想法吗？

4

1 回答 1

7

一个非常简单的优化是通过它的累加器参数使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）。

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

于 2015-09-24T16:20:20.780 回答