Haskell空间泄漏

Question

Haskell空间泄漏

3

所有.

在尝试解决一些编程测验时： https://www.hackerrank.com/challenges/missing-numbers，我遇到了空间泄漏。

主函数是difference，它实现了多集合差异。通过-hT选项分析，我发现列表':'和三元组(,,)被保存在堆上。然而，只有大型列表是difference的两个参数，并且随着difference的尾递归不断缩小。但是列表消耗的内存随着程序运行而增加。

三元组是短暂的数组结构，用于记录多集合的每个元素的计数。但是三元组消耗的内存也在不断增加，我找不出原因。

虽然我在stackoverflow上浏览了类似的“空间泄漏”问题，但我无法理解这个想法。我肯定还有很多要学习的。

我感激任何评论。谢谢。

p.s) 可执行文件使用-O2开关编译。

$ ./difference -hT < input04.txt
Stack space overflow: current size 8388608 bytes.
$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 7.6.3

.

import Data.List
import Data.Array

-- array (non-zero-count, start-offset, array_data)
array_size=101

myindex :: Int -> Int -> Int
myindex key offset
    | key >= offset = key - offset
    | otherwise     = key - offset + array_size

mylookup x (_,offset,arr) = arr ! idx
    where idx = myindex x offset

addOrReplace :: Int -> Int -> (Int, Int, Array Int (Int,Int)) -> (Int, Int, Array Int (Int,Int))
addOrReplace key value (count,offset,arr) = (count', offset, arr // [(idx,(key,value))])
    where idx = myindex key offset
          (_,prev_value) = arr ! idx
          count' = case (prev_value, value) of
                      (0,0) -> count
                      (0,_) -> count + 1
                      (_,0) -> count - 1
                      otherwise -> count

difference :: (Int,Int,Array Int (Int,Int)) -> [Int] -> [Int] -> [Int]
difference (count,offset,arr) [] []
    | count == 0 = []
    | otherwise  = [ k | x <- [0..array_size-1], let (k,v) = (arr ! x), v /= 0]
difference m (x:xs) y = difference new_m xs y
    where (_,v) = mylookup x m
          new_m = addOrReplace x (v + 1) m
difference m [] (y:ys) = difference new_m [] ys
    where (_,v) = mylookup y m
          new_m = if v == 0
            then m
            else addOrReplace y (v - 1) m

main = do
    n <- readLn :: IO Int
    pp <- getLine
    m <- readLn :: IO Int
    qq <- getLine
    let p = map (read :: String->Int) . words $ pp
        q = map (read :: String->Int) . words $ qq
        startArray = (0,head q, array (0,100) [(i,(0,0)) | i <- [0..100]] )
    putStrLn . unwords . map show . sort $ difference startArray q p

[编辑] 在 Carl 的建议下，我对值和数组进行了序列化。我附上堆图。

[原始堆文件] [ original heap ]1

[对值 v 序列化后]

difference m (x:xs) y = difference new_m xs y
    where (_,v) = mylookup x m
          new_m = v `seq` addOrReplace x (v + 1) m

[在对值v和数组Array进行序列化后的堆]

difference m (x:xs) y = new_m `seq` difference new_m xs y
    where (_,v) = mylookup x m
          new_m = v `seq` addOrReplace x (v + 1) m

- Chul-Woong Yang

请查看Haskell标签信息页面，了解有关如何提问性能问题的方法。 - jberryman

谢谢，我在附言中添加了更多信息。 - Chul-Woong Yang

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Carl · Accepted Answer

我看到这段代码存在三个主要问题。

首先（虽然不是内存使用的原因，但绝对是普遍性能差的原因），对于这种用例，Array非常糟糕。O(1)的查找在更新为O(n)时将变得无用。

说到值存储在数组中，它们在difference循环其第一个输入时没有被强制执行。它们包含指向数组先前版本中未评估查找的指针。您可以通过多种方式确保在更新数组时同时评估该值。事实上，在difference循环其第二个输入时会意外地执行此操作，通过将该值与0进行比较。

第三，difference甚至不会强制计算在遍历其第一个参数时创建的新数组。在循环的那一部分没有要求评估旧数组。

解决这两个后续问题以修复空间泄漏。第一个问题不会导致空间泄漏，只会造成比所需更高的开销。