[Haskell-cafe] forLoop + strict State monad is much faster than foldl'

[John Lato]

On Tue, Apr 29, 2014 at 9:31 AM, Niklas Hambüchen <mail at nh2.me> wrote:

> This is just a short notice that using
>
>    foldl' (+) 0 [0..100000::Int]
>
> is over 10 times slower than using
>
>   flip execState 0 $
>     forLoop (0 :: Int) (< n) (+1) $ \i -> do
>       x <- get
>       put $! x + i
>
> with `loopFor` as on https://github.com/nh2/loop.
>

So this is interesting.  The forLoop code gets compiled into a nice loop in
core over unboxed Ints.  The foldl' function OTOH still goes via a list.  I
expect it's not foldl' itself that's slow, rather that it doesn't fuse with
the list producers in current GHCs.  This may be improved in the future.
 Especially as the vectorized foldl' does fuse.


>
> Even using an IORef is twice as fast as the pure foldl' (but still 5
> times slower than strict State).
>
> The benchmark is at
>
> http://htmlpreview.github.io/?https://github.com/nh2/loop/blob/master/results/bench-foldl-and-iorefs-are-slow.html
> .
>
> (All benchmarks are linked from https://github.com/nh2/loop.)
>
> You can see there that the problem is gone when using Vector.foldl', but
> only for Int - for Word32 it persists.
>
> It seems that manual looping is beneficial even when dealing with prime
> examples of pure code that GHC ought to optimize well.
>

That's why I suggested using vector in the first place.  But it seems that
Vector.enumFromTo could use some optimizations to help with some common
cases.

John
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20140429/facd1dd7/attachment.html>