[Haskell-beginners] Re: Space leak in a fold even after the usual fixes

[Heinrich Apfelmus]

Travis Erdman wrote:
> The driver of my algorithm looks like this:
> 
> foldl' processfn nullarray (take arg infinitelist)
> 
> where processfn takes an array and the next set of inputs,
> processes, and delivers a new updated array (using the
> Data.Vector library).
>  
> Apparently, I have a space leak ... the "maximum residency"
> varies linearly with the size of "arg" supplied, garbage
> collection consumes ~75% of CPU time, and, if the arg is too
> big, the whole thing crashes with an out of memory
> error.  The algorithm should operate in constant
> space.
> 
> As you can see, I'm using a strict left-fold and also have
> made the accumulating array strict in the processfn
> definition with a bang pattern.  So, I'm sort of at a
> loss as to how to resolve this.

I take it that size of the array does not depend on  arg ?

Apparently, despite your attempts to force evaluation, the array still
contains many unevaluated expressions. Documentation for the  vector
pacakge reveals that  Data.Vector  is a *boxed* array, i.e. the entries
are only evaluated on demand, so that's where the unevaluated
expressions linger around.

Unless you need the extra laziness - which you probably don't, given how
you've structured your algorithm - you might want to switch to
Data.Vector.Unboxed  or  Data.Vector.Storable .


Regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com