Re: [Haskell-cafe] Progress on shootout entries

Discussing the fannkuch entry Sebastian Sylvan wrote:

On 1/3/06, Sebastian Sylvan wrote:

...

On 1/3/06, Chris Kuklewicz 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