[Haskell-cafe] Reasoning about performance

[Scott Pakin]

On 09/03/2013 05:43 PM, Bob Ippolito wrote:
> Haskell's non-strict evaluation can often lead to unexpected results when doing tail recursion if you're used to strict functional programming languages. In order to get the desired behavior you will need to force the accumulator (with something like Data.List's foldl', $!, seq, BangPatterns, etc.).

I had previously tried BangPatterns and recall it not making any
difference.  However, this result now makes sense given what you
described in terms of tail recursion thwarting some of the benefits of
non-strict evaluation.

> I think what's happening with allPairs2 is that GHC is throwing away the the list during the traversal since the result of the computation isn't used at all. I get very different timings (still fast, but no longer orders of magnitude difference) for allPairs2 if the result is still around. You could probably figure this out with the heap profiler.
>
> h> deepseq (allPairs2 [1..10000]) True
> True
> (2.47 secs, 4403724176 bytes)
> h> let x = allPairs2 [1..10000]
> (0.00 secs, 510488 bytes)
> h> deepseq x True
> True
> (10.47 secs, 4401625192 bytes)
> h> deepseq x True
> True
> (2.21 secs, 1031864 bytes)

Ah, I hadn't thought about that.  Even though deepseq is forcing the
complete evaluation, it can discard evaluated results (and maybe even
deforest) in the lazy allPairs1 and allPairs2 implementations but not
in the tail-recursive-but-not-lazy allPairs3.  Using your let trick to
prevent the result from being discarded cases caused my memory
subsystem to scream in pain in all three cases.  I had to reduce the
problem size quite a bit and still ended up spending hours of real
time in GC.  With this approach, allPairs1 and allPairs2 take an equal
amount of time and roughly equal amounts of memory.  allPairs3 takes
twice as long and uses a bit more than half the memory:

     Prelude Control.DeepSeq System.Mem AllPairs> let x = allPairs1 [1..4000]
     (0.00 secs, 512968 bytes)
     Prelude Control.DeepSeq System.Mem AllPairs> performGC
     (1.31 secs, 1113528 bytes)
     Prelude Control.DeepSeq System.Mem AllPairs> deepseq x True
     True
     (0.74 secs, 641687568 bytes)

     Prelude Control.DeepSeq System.Mem AllPairs> let x = allPairs2 [1..4000]
     (0.00 secs, 510144 bytes)
     Prelude Control.DeepSeq System.Mem AllPairs> performGC
     (3.53 secs, 848312 bytes)
     Prelude Control.DeepSeq System.Mem AllPairs> deepseq x True
     True
     (0.74 secs, 705185688 bytes)

     Prelude Control.DeepSeq System.Mem AllPairs> let x = allPairs3 [1..4000]
     (0.01 secs, 510072 bytes)
     Prelude Control.DeepSeq System.Mem AllPairs> performGC
     (27.00 secs, 956096 bytes)
     Prelude Control.DeepSeq System.Mem AllPairs> deepseq x True
     True
     (1.54 secs, 385915160 bytes)

Thanks for the explanation,
-- Scott