[Haskell-cafe] Progress on shootout entries

[Cale Gibbard]

On 03/01/06, Sebastian Sylvan <sebastian.sylvan at gmail.com> 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,
> > >
> > >   Where there were no entries to the
> > > http://shootout.alioth.debian.org/benchmark.php?test=chameneos&lang=all
> > > benchmark, there are now two.  The one by Josh Goldfoot is already
> > > posted, the one Einar Karttunen and I optimized has been submitted and
> > > will run faster/smaller.  Our code is at
> > > http://haskell.org/hawiki/ChameneosEntry
> > >
> > >   Now for improving the fasta benchmark,
> > > http://shootout.alioth.debian.org/benchmark.php?test=fasta&lang=all ,
> > > which currently has a space leak in the Haskell entry.
> > >
> > >   A non-leaking version which has been optimized to run 3.5 times faster
> > > is now up at http://haskell.org/hawiki/FastaEntra (ooops..my spelling
> > > mistake).
> > >
> > >   It could still be made to run about 3 times faster, if the other
> > > languages are any guide.  Anyone want to help polish this one?
> > >
> > >  Also, two other existing entries have space leaks, as can be seen at
> > > http://shootout.alioth.debian.org/benchmark.php?test=all&lang=ghc&lang2=ghc
> > >
> > >  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

You might not have been waiting for the final result. The first 30
perms print quickly, but it takes longer to get the solution to the
problem.

I managed to do better with the following program which gets the
following time report on my machine
real    0m8.175s
user    0m7.742s
sys     0m0.186s
as opposed to
real    0m23.232s
user    0m21.115s
sys     0m0.077s
for the shootout code.

I didn't try too hard to optimise it heavily, but it does use a
tree-based permutation generator I stole from some code which was in
an n-queens solution I had laying around (pretty sure it's not mine),
and an obvious memoisation hack when handling the flips.

 - Cale
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Fannkuch.hs
Type: text/x-haskell
Size: 1679 bytes
Desc: not available
Url : http://www.haskell.org//pipermail/haskell-cafe/attachments/20060103/cb8d8337/Fannkuch.bin