[Haskell-cafe] Progress on shootout entries

[Krasimir Angelov]

2006/1/3, Chris Kuklewicz <haskell at list.mightyreason.com>:
>  And finially, the haskel entry for
> http://shootout.alioth.debian.org/benchmark.php?test=fannkuch&lang=all
>  is currently the *slowest* entry out of 28 languages.  It is 813x
> slower than the c-code, 500x slower than OCaml.  Should be easy to make
> it faster...

In this particular case the flop function is very slow.

flop :: Int8 -> [Int8] -> Int8
flop acc (1:xs) = acc
flop acc list@(x:xs) = flop (acc+1) mangle
    where   mangle = (reverse front) ++ back
            (front,back) = splitAt (fromIntegral x) list


It can be optimized using a new mangle function:

mangle :: Int -> [a] -> [a]
mangle m xs = xs'
  where
    (rs,xs') = splitAt m xs rs

    splitAt :: Int -> [a] -> [a] -> ([a], [a])
    splitAt 0    xs  ys = (xs,ys)
    splitAt _    []  ys = ([],ys)
    splitAt m (x:xs) ys = splitAt (m - 1) xs (x:ys)

The mangle function transforms the list in one step while the original
implementation is using reverse, (++) and splitAt. With this function
the new flop is:

flop :: Int8 -> [Int8] -> Int8
flop acc (1:xs) = acc
flop acc list@(x:xs) = flop (acc+1) (mangle (fromIntegral x) list)