[Haskell-beginners] leaky folding

[Daniel Fischer]

On Sunday 15 August 2010 09:58:49, Travis Erdman wrote:
> in the code below, finalmap seems fast enough ... but it has a space
> leak. otoh, finalmap'rnf runs in constant space, but its performance is
> terrible, at least 4x slower than finalmap.

The performance isn't so bad, actually.
Consider that in each step it has to rnf the entire map. Even for small 
maps like this one, that's quite a bit of work (and mostly unnecessary, 
because almost everything is already in normal form).

>
> this is a common problem i'm having ... foldl' isn't strict enough, but
> foldl'rnf kills performance.

Firstly, foldl'rnf is a good idea *only* for small structures or if in each 
step large parts of the structure are changed. If you change only small 
parts of a large structure, you're wasting a lot of work.
Secondly, in this case your problem is a) the choice of a suboptimal data 
structure b) a bad choice of functions to manipulate the structure c) 
perhaps the lacking strictness of Data.IntMap.

a) STUArray would be better. But that makes itself really felt only for 
larger n.
b) that's the biggo
c) Data.IntMap doesn't offer any strict versions of insertWith, 
insertWithKey, adjust et al, which would often make it far easier to avoid 
space leaks. Data.Map at least offers strict(er) versions of 
insertWith[Key].

> And not only with IntMap as the cumulating
> data structure, but others as well.
>
> any ideas on this one?

Sure. See below.

> how can i get a fast fold in constant space?
>
> thanks again,
>
> travis
>
>
> {-# LANGUAGE BangPatterns #-}
>
> import System.Environment
> import Foreign (unsafePerformIO)
> import System.Random.Mersenne
> import Data.List
> import Control.DeepSeq
> import Control.Parallel.Strategies
> import qualified Data.IntMap as IntMap
>
> mersennegen = unsafePerformIO $ newMTGen Nothing
> infrandoms =  unfoldr ( Just . splitAt 3) $ map (\x -> abs (x `mod` n))
> (unsafePerformIO $ (randoms mersennegen)::[Int])

Arrrgh! Use of unsafePerformIO in that way makes my head hurt. Pass things 
as arguments, please.

>
> n = 200
>
> foldl'rnf :: NFData a => (a -> b -> a) -> a -> [b] -> a
> foldl'rnf f z xs = lgo z xs
>     where
>         lgo z []     = z
>         lgo !z (x:xs) = lgo (runEval (rdeepseq (f z x))) xs
>
> startmap = IntMap.fromDistinctAscList $ zip [0..] [1..n]

That is almost certainly a bad idea. If the map contains a contiguous range 
of keys, an array is practically guaranteed to be more appropriate (uses 
less memory and is faster to boot).

>
> finalmap x = foldl' g startmap (take x infrandoms)

Okay, that looks reasonable.

> finalmap'rnf x = foldl'rnf g startmap (take x infrandoms)

As stated above, rnf'ing the entire map at each step is a baad idea.
You can get reasonable performance while squashing the leak by splitting 
your list in chunks of size k and rnf'ing the map only after each chunk has 
been processed.

finalmap'rnf x = foldl'rnf h startmap
       (takeWhile (not . null) 
          (unfoldr (Just . splitAt 200) (take x infrandoms)))
    where
        h mp lst = foldl' g mp lst

The chunk size should be approximately the size of the map, so that after 
each chunk
- a large part of the map has been changed
- no value has been changed too often.
Then rnf'ing the entire map doesn't waste too much work (since only a small 
part of the map is already in NF) and no key maps to a too large thunk 
(which can cause a space leak with vanilla foldl', though here the problem 
is something else).

But, here at least, changing the folded function does better.

>
> g:: IntMap.IntMap Int -> [Int] -> IntMap.IntMap Int
> g !a [x,y,z] = IntMap.adjust (const $ y + (a IntMap.! z) `mod` n) x a

Oy gevalt!

The bang on the map parameter is superfluous since we foldl' anyway, but 
that's no big deal.

IntMap.adjust (const val) is not the best if the key at which the map is to 
be adjusted is guaranteed to be in the map. Then IntMap.insert is better.
But the difference is small, and if the key is not algorithmically 
guaranteed to be present, adjust is cleaner. So the use of adjust is no big 
deal either, even if insert is faster here.

What is bad is that you IntMap.adjust (const thunk).
Well, that alone isn't so bad.
What kills you is that the thunk refers to the map.
Thus each modified map contains a reference to the previous version, the 
old contents can't be garbage collected, hello space leak (and finally 
getting the values involves hopping through old cells).

If you modify a data structure, don't let the modified version contain any 
thunks referencing the old. That spells space leak.

With

g a [x,y,z] = let !w = y + (a IntMap.! z) `mod` n
              in IntMap.adjust (const w) x a

you're fine with foldl'.

Question by the way, did you really want

y + ((a ! z) `mod` n)

or rather

(y + (a ! z)) `mod` n
?

>
> main = do
>         args <- getArgs
>         print $ finalmap (read $ head args)