[Haskell-cafe] Memory leak or wrong use of Array ?

[Stuart Cook]

On 9/14/07, L.Guo <leaveye.guo at gmail.com> wrote:
> Hi MailList Haskell-Cafe:
>
> I am tring to solve Project Euler problem 70.
> And write some code. (will at the end of this mail)
> And, I run the code in GHCi.
>
> The problem is that, when the input is 1,000,000, it works
> fine, when the input is up to 10,000,000, the memory GHCi
> used increase very fast and did not stop.
>
> Is this a memory leak ? or, is there some mis-understand
> about array ?

Haskell's boxed arrays are non-strict, which can cause space leaks
when you don't actually need the laziness. The usual quick-&-dirty
solution is to switch to unboxed arrays (e.g. IOUArray), which are
inherently strict, but they're only available for certain primitive
element types.

The solution, then, is to make sure you adequately force your thunks
before storing them in an array.

>         update arr p i = do
>             (_,o) <- readArray arr i
>             writeArray arr i (True,o*(p-1)/p)

Here's a possible fix, though it's untested, and I'm sure there are
more elegant ways to write it:

  update arr p i = do
      (_, o) <- readArray arr i
      let val = o * (p-1) / p
      val `seq` return () -- force the thunk
      writeArray arr i (True, val)

This ensures that the second component of the pair is a value, rather
than a thunk.

Strictifying data such as numbers and booleans is relatively easy, but
things get tricky when you try to force more complicated structures
(deepSeq, anyone?).


Stuart