算法的思想非常简单,在命令式术语中使其清晰:它接受一个“数组”,并向每个内部点添加一个值,该值是由点本身和其邻居点的值组合计算得出的。边界点是特殊情况。
所以,这是我的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
和bangs,在哪里以及为什么? - 最后,最重要的是,识别这样昂贵的结构的最佳策略是什么?
我阅读了Real World Haskell中关于分析和优化的章节,但仍不清楚我应该如何决定什么应该是严格的,什么不应该是严格的。
请原谅我发这么长的帖子。
编辑2:根据评论中A. Rex的建议,我尝试在valgrind中运行这两个程序。下面是我的观察结果。对于Haskell程序(
n
=200000),它发现:malloc/free: 33次分配,30次释放,已分配84,109字节。 ... 已检查55,712,980字节。
而对于C程序(经过小修复):
malloc/free: 2次分配,2次释放,已分配3,200,000字节。
因此,看起来虽然Haskell分配了更小的内存块,但它经常这样做,并且由于垃圾回收延迟,它们会累积并保留在内存中。所以,我有另一个问题:
- 是否可能在Haskell中避免大量小的分配?基本上,声明需要处理整个数据结构而不仅仅是按需处理其片段。
n
的值。time ./eulerhs 1000000
运行时间为2.236秒,而time ./eulerc 1000000
运行时间为0.293秒。我将编辑问题。谢谢你的评论! - sastanin