[Haskell-cafe] Progress on shootout entries

[Chris Kuklewicz]

Discussing the fannkuch entry

Sebastian Sylvan wrote:
> On 1/3/06, Sebastian Sylvan <sebastian.sylvan at gmail.com> wrote:
> 
>>On 1/3/06, Chris Kuklewicz <haskell at list.mightyreason.com> wrote:
>>
>>>Hello,
>>>
>>> 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...
>>
>>While the implementation is far from "nice" it still finishes with N=9
>>(which, AFAICT, is what the benchmark is run with) in a fraction of a
>>second on my machine (and not anywhere near 51s as in the
>>benchmark)... I have a 2.6 Ghz P4...
>>
>>I was going to rewrite it using mutable STArrays for a pure version
>>that's still fast but i sorta feel like I lost the motivation now that
>>it turns out the existing implementation, though ugly, performs
>>somewhat okay...
> 
> 
> Hmm.. This may be due to laziness. Since it's only supposed to print
> out the first 30 lines it won't compute the full n! values...
> 
> 
> /S

If you look at the code, then you may see that

> findmax :: Int8 -> [[Int8]] -> Int8
> findmax soFar [] = soFar
> findmax soFar (x:xs) =
>    max (flop 0 x) (findmax soFar xs)

is broken. The soFar parameter (which is originally 0) does absolutely
nothing.  I think this would be more appropriate:

findmax' xs = foldl1' max $ map (flop 0) xs

They use (!!) on lists instead of, as you said, STArrays.

For truly optimal performance mallocArray of Word8 would actually model
the c code much better than the lists.

They have [a] types and fromIntegral when it is all Int8, as far as I
can see.

And for sanity's sake, I wish one of the entries would have documentated
a clear way to understand the permutation generator.   The PHP and Lua
versions are almost legible.

-- 
Chris