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

我是函数式编程的新手,现在学习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

为了比较,我还写了一个纯C实现.

现在,如果我尝试为足够大的数组运行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

编辑:这种比较并不公平,因为Haskell版本使用分析标志进行编译,而C则不是.如果我用两个程序编译两个程序-O2而没有分析标志,我可以增加n.在这种情况下time ./eulerhs 1000000需要0m2.236s,而time ./eulerc 1000000只需要0m0.293s.因此,问题仍然存在于所有优化和没有分析,它只是抵消.

我还要注意,Haskell程序的内存分配似乎与之相关n.这可能还可以.

但最糟糕的是内存要求.我的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.所以,我的问题是:

在Haskell中有一种方法可以严格地构建列表/列表推导吗？在这种情况下,保持懒惰是没有好处的.

在这种情况下,如何减少总体内存使用量？我想,我必须做一些严格的事情,但却没有看到什么.换句话说,如果我必须放一些seq和刘海,在哪里以及为什么？

最后,最重要的是,识别这种昂贵结构的最佳策略是什么？

我确实阅读了关于Real World Haskell中的分析和优化的章节,但我仍然不清楚我究竟能够确定什么应该是严格的,什么不是.

请原谅我这么长的帖子.

EDIT2:正如A. Rex在评论中所建议的那样,我尝试在valgrind中运行这两个程序.这就是我观察到的.对于Haskell程序(n= 200000),它发现:

malloc/free:33个allocs,30个frees,84,109个字节....检查了55,712,980字节.

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

malloc/free:分配2个allocs,2个frees,3,200,000个字节.

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

是否有可能避免Haskell中的大量小分配？基本上,要声明,我需要处理整个数据结构而不是仅按需处理它的片段.

ADEpt.. 20

列表不是这类代码的最佳数据结构(有很多(++)和(最后)).你失去了大量的时间来构建和解构列表.我在C版本中使用Data.Sequence或数组.

makeu0的thunks没有机会被垃圾收集,因为你需要保留所有这些(好吧,所有"漫反射"的结果,确切地说)直到计算结束才能成为能够在applyBC中做"逆转".这是非常昂贵的事情,考虑到您只需要列表尾部的两个项目为您的"zeroflux".

以下是快速入侵您的代码,试图实现更好的列表融合并减少列表(de)构建:

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秒

列表不是这类代码的最佳数据结构(有很多(++)和(最后)).你失去了大量的时间来构建和解构列表.我在C版本中使用Data.Sequence或数组.

makeu0的thunks没有机会被垃圾收集,因为你需要保留所有这些(好吧,所有"漫反射"的结果,确切地说)直到计算结束才能成为能够在applyBC中做"逆转".这是非常昂贵的事情,考虑到您只需要列表尾部的两个项目为您的"zeroflux".

以下是快速入侵您的代码,试图实现更好的列表融合并减少列表(de)构建:

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秒

在我的32位x86系统上,您的程序仅使用大约40 MB的内存.

您是否可能会混淆分析输出中的"total alloc = 116,835,180 bytes"行,以及程序在任何时候实际使用了多少内存？总alloc是在整个程序运行中分配的内存量; 随着你的进展,垃圾收集器释放了大部分内容.你可以期望这个数字在Haskell程序中变得非常大; 我有程序在整个运行过程中分配了许多TB的内存,尽管它们的最大虚拟内存大小实际上是一百兆字节左右.

在程序运行过程中,我不会过分担心大量的总分配; 这是纯语言的本质,GHC的运行时有一个非常好的垃圾收集器来帮助弥补这一点.