如何减少存储器的使用在Haskell的程序？

StackOverflow https://stackoverflow.com/questions/459725

题

我是新来编程功能，现在了解Haskell.作为一个练习，我决定实施明确的欧拉法1D线性扩散等式。虽然代码下面正常工作，我不高兴约其性能。事实上，我感到关切的是与存储的消耗。我认为，这是有关懒惰的评估，但是无法弄清楚我怎么可以减少其存储器的使用。

这个想法的算法是非常简单，以使其在必要的条款：它需要一个`阵列'，每一个内心点它增加了一个价值，其计算方法作为一个组合的价值观点本身，并在其邻国。边界点的特殊情况。

所以，这是我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

和一个简单的。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 似乎增长与lineary n.这可能是确定。

但最糟糕的是存储器的要求。我Haskell版本需要 超过100MB (我估计最低限度在C 4M).我认为这可能来源的问题。根据分析报告的程序，花费了85%的时间，在气相色谱法，

        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 是 所以 昂贵的。我决定，这是由于它的懒惰的评估(如果它形式转换仍然在存储器，直到结束 stepEuler).

我想这改变 Main.hs:

   let un = u0 `seq` stepEuler 0.5 u0

但没有注意到任何差别。我不知道如何减少内存使用情况 stepEuler.因此，我的问题是：

  1. 有没有办法在Haskell建立列出/活动列表的严格地推导?在这种情况下，没有利益，以保持它的懒惰。
  2. 我如何可以减少整体存储器的使用在这种情况下？我假设，我已经做出一些严格的，但未见到什么。换句话说，如果我必须把一些 seqs和刘海，在哪里和为什么?
  3. 最后，最重要的是，什么是最好的战略，以确定这样的代价高昂的结构?

我读一章分析和优化 现实世界Haskell, 但它仍然不清楚究竟如何，我可以决定什么应该是严格的和什么不可以。

请原谅我这样的一个长期职位。

EDIT2:建议A雷克斯在意见，我试图运行 计划在才.这是什么 我观察到的。对哈斯克程序 (n=200000)它的发现：

malloc/免费的：33分配的30释放，84,109字节的分配。...检查55,712,980字节。

和C程序(后一个小的修复):

malloc/免费的：2分配，2时释放，为数3 200 000字节的分配。

因此，它的出现，同时Haskell 分配更小的记忆区块， 它经常，由于延迟 垃圾收集，他们积累的 和留在记忆。因此，我已 另一个问题：

  • 是否有可能避免很多 小部分拨款在Haskell?基本上，要宣布，我需要 进程的整个数据结构 而不是只有它的碎片 需求。
有帮助吗？

解决方案

  1. 清单不是最好的datastructure对于这种类型的代码(与很多(++)，(最后一)).你失去了很多时间constucting和解构名单。我会使用的数据。序列或阵列，作为在C版本。

  2. 有没有机会为形式转换的makeu0是垃圾回收，因为你需要保留所有的人(很好，所有的结果的"扩散"，是准确的)的所有方式，直到结束的计算，以便能够做到"反向"在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秒vs3.8秒钟为初始版本

其他提示

在我的32位x86系统、程序只使用约40MB的存储器。

你是混乱的"总分配=116,835,180字节"行自己的分析产出有多少存储器实际被使用过该程序在任何一个时间？总的分配是多少内存被分配在整个程序的运行；这是释放了垃圾回收。你可以期待这一数字为获得非常大的一Haskell程序；我有计划拨出很多terrabytes的存在过程中他们的整个运行，虽然他们实际上有一个最大的虚拟存储器大小的一个百兆字节。

我不会太担心大的总拨款过程的程序的运行；这是自然界的一个纯粹的语言，并GHC的运行时具有非常良好的垃圾收集器，以帮助弥补这一点。

更一般地说，你可以找出你的记忆会使用 GHC的堆分析工具。 以我的经验，他们并不一定会告诉你为什么你的数据被泄露，但可以至少缩小潜在原因。

你也可以找到照射这个 优秀的博客后由唐*斯图尔特 关于了解严格，它是如何相互作用与垃圾收集，以及如何诊断和解决问题。

并迫使"联合国-懒惰"使用$!有帮助吗？为每 这个答案.

每Harleqin的以下请求：你有没有尝试过设置优化的标志吗？例如，与全康，可以使用添加"-O2"就像你会与海湾合作委员会.(虽然我不确定是什么化水平存在ghc;人页面没有确切地说。。。)

在我过去的经验，设定这种标志了 巨大的 差异。我可以告诉， runhugs 并未优化 ghc 使用的最基本的，显而易见的执行情况的Haskell;不幸的是，这有时并不非常有效的。

但那只是猜测。正如我所说的在我的评论，我希望有人能回答您的问题。我经常有问题的分析和固定Haskell的存储器的使用。

使用开关 -fvia-C 还。

一件事，跳到我的眼睛现在是，Haskell的输出是一个浮动，而C输出似乎是整数。我还没有掌握Haskell的代码，但是也许有些地方，你有漂浮点运算在Haskell的同时，C采用整数？

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top