haskell - 如何减少 Haskell 应用程序中的内存使用量？

Question

我是函数式编程新手，现在正在学习 Haskell。作为练习，我决定对一维线性扩散方程实现显式欧拉方法。虽然下面的代码可以正常工作，但我对其性能并不满意。事实上，我关心的是内存消耗。我相信它与惰性求值有关，但无法弄清楚如何减少其内存使用量。

该算法的思想非常简单，用命令式的术语来说清楚:它需要一个“数组”，并为每个内部点添加一个值，该值是作为该点本身的值的组合来计算的以及它的邻居。边界点是特殊情况。

所以，这是我的 Euler1D.hs 模块:

module Euler1D
( stepEuler
, makeu0
) where

-- impose zero flux condition
zeroflux :: (Floating a) => a -> [a] -> [a]
zeroflux mu (boundary:inner:xs) = [boundary+mu*2*(inner-boundary)]

-- one step of integration
stepEuler :: (Floating a) => a -> [a] -> [a]
stepEuler mu u@(x:xs) = (applyBC . (diffused mu)) u
    where
          diffused mu (left:x:[]) = []    -- ignore outer points
          diffused mu (left:x:right:xs) = -- integrate inner points
                   (x+mu*(left+right-2*x)) : diffused mu (x:right:xs)
          applyBC inner = (lbc u') ++ inner ++ (rbc u') -- boundary conditions
               where u' = [head u] ++ inner ++ [last u]
                     lbc = zeroflux mu             -- left boundary
                     rbc = (zeroflux mu) . reverse -- right boundary

-- initial condition
makeu0 :: Int -> [Double]
makeu0 n = [ ((^2) . sin . (pi*) . xi) x | x <- [0..n]]
    where xi x = fromIntegral x / fromIntegral n

还有一个简单的 Main.hs:

module Main where

import System ( getArgs )
import Euler1D

main = do
      args <- getArgs
      let n = read $ head args :: Int
      let u0 = makeu0 n
      let un = stepEuler 0.5 u0
      putStrLn $ show $ sum un

为了比较，我还写了a pure C implementation .

现在，如果我尝试为足够大的数组运行 Haskell 实现 n ，我有:

$ time ./eulerhs 200000
100000.00000000112

real    0m3.552s
user    0m3.304s
sys     0m0.128s

相比之下，C 版本快了几乎两个数量级:

$ time ./eulerc 200000
100000

real    0m0.088s
user    0m0.048s
sys     0m0.008s

EDIT: This comparison is not really fair, because Haskell version is compiled with profiling flags, and C is not. If I compile both programs with -O2 and both without profiling flags, I can increase n. In this case time ./eulerhs 1000000 takes 0m2.236s, while time ./eulerc
1000000 takes only 0m0.293s. So the problem still remains with all optimizations and without profiling, it is only offset.

I would like also to note, that memory allocation of the Haskell program seems to grow lineary with n. This is probably OK.

但最糟糕的是内存要求。我的 Haskell 版本需要超过 100MB(我估计 C 语言的最低要求是4MB)。我想这可能就是问题的根源。根据分析报告，该程序 85% 的时间都花在 GC 上，并且

        total time  =        0.36 secs   (18 ticks @ 20 ms)
        total alloc = 116,835,180 bytes  (excludes profiling overheads)

COST CENTRE                    MODULE               %time %alloc

makeu0                         Euler1D               61.1   34.9
stepEuler                      Euler1D               33.3   59.6
CAF:sum                        Main                   5.6    5.5

我很惊讶地看到 makeu0太贵了。我认为这是由于它的惰性评估(如果它的 thunk 保留在内存中直到 stepEuler 结束)。

我在 Main.hs 中尝试了此更改:

   let un = u0 `seq` stepEuler 0.5 u0

但没有注意到任何差异。我不知道如何减少 stepEuler 中的内存使用量。所以，我的问题是:

1. Haskell 有没有办法严格构建列表/执行列表推导？在这种情况下，保持懒惰没有任何好处。
2. 在这种情况下如何减少总体内存使用量？我想，我必须做一些严格的事情，但看不到什么。换句话说，如果我必须输入一些 seq s和刘海，在哪里以及为什么？
3. 最后，最重要的是，识别此类昂贵结构的最佳策略是什么？

我确实在 Real World Haskell 中阅读了有关分析和优化的章节。 ，但目前还不清楚我如何准确地决定什么应该严格，什么不应该严格。

请原谅我这么长的帖子。

EDIT2: As suggested by A. Rex in comments, I tried running both programs in valgrind. And this is what I observed. For Haskell program (n=200000) it found:

malloc/free: 33 allocs, 30 frees, 84,109 bytes allocated. ... checked 55,712,980 bytes.

对于 C 程序(经过小修改):

malloc/free: 2 allocs, 2 frees, 3,200,000 bytes allocated.

所以，看起来虽然 Haskell 分配更小的内存块， 它经常这样做，并且由于延迟 垃圾收集，它们积累 并留在内存中。所以我有 另一个问题:

• 是否可以避免很多 Haskell 中的小分配？ 基本上，要声明，我需要 处理整个数据结构 而不仅仅是它的碎片 需求。

Answer 1

1. 列表并不是此类代码的最佳数据结构(有很多 (++) 和 (last))。您会花费大量时间来构建和解构列表。我会使用 Data.Sequence 或数组，就像在 C 版本中一样。

2. makeu0 的 thunk 不可能被垃圾收集，因为你需要保留所有它们(准确地说，是“diffuse”的所有结果)一直到最后的计算以便能够在 applyBC 中进行“反向”操作。这是非常昂贵的事情，考虑到您只需要列表末尾的两项作为“zeroflux”。

这是对代码的快速破解，尝试实现更好的列表融合并减少列表(解)构造:

module Euler1D
( stepEuler
) where

-- impose zero flux condition
zeroflux mu (boundary:inner:xs) = boundary+mu*2*(inner-boundary)

-- one step of integration
stepEuler mu n = (applyBC . (diffused mu)) $ makeu0 n
    where
          diffused mu (left:x:[]) = []    -- ignore outer points
          diffused mu (left:x:right:xs) = -- integrate inner points
                   let y = (x+mu*(left+right-2*x))
                       in y `seq` y : diffused mu (x:right:xs)
          applyBC inner = lbc + sum inner + rbc -- boundary conditions
               where
                     lbc = zeroflux mu ((f 0 n):inner)             -- left boundary
                     rbc = zeroflux mu ((f n n):(take 2 $ reverse inner)) -- right boundary

-- initial condition
makeu0 n = [ f x n | x <- [0..n]]

f x n = ((^2) . sin . (pi*) . xi) x
    where xi x = fromIntegral x / fromIntegral n

对于 200000 点，它在 0.8 秒内完成，而初始版本为 3.8 秒