saner shootout programs

I don't know Haskell very well, but even I can tell, looking at, for
example, the N-body benchmark, that the Haskell code is probably not
type-safe, and the tricks used in it would not be usable in a larger
program (see below).

The task is essentially a pure computation: take a list of bodies
having mass, position and velocity; apply Newton laws at discrete
intervals for a large number of times; return new positions and
velocities.

I could write a C++ procedure that performs this task and have some
piece of mind regarding its type correctness, exception safety and
functional purity: side effects would be local to the procedure,
arguments passed as const or by value, the result returned by value,
no type casts or new/delete operators used.

On the other hand, the Haskell code makes assumptions about the size
of double-precision floats (obviously not type-safe). Further, the
simulation is not a pure function.

It is often argued that one only needs these dirty tricks in the most
time-consuming functions. However, if using imperative programming in
these "inner loop" procedures places them in IO monad, the "outer
loops" (the rest of the program - procedures that call it) will have
to go there as well. This makes me doubt the Haskell approach to
functional programming.

If anyone has a version of the N-body benchmark, where the simulation
is a type-safe pure function, I would very much like to see and time
it.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Don Stewart-2]

jhc0033:

> I don't know Haskell very well, but even I can tell, looking at, for
> example, the N-body benchmark, that the Haskell code is probably not
> type-safe, and the tricks used in it would not be usable in a larger
> program (see below).
>
> The task is essentially a pure computation: take a list of bodies
> having mass, position and velocity; apply Newton laws at discrete
> intervals for a large number of times; return new positions and
> velocities.
>
> I could write a C++ procedure that performs this task and have some
> piece of mind regarding its type correctness, exception safety and
> functional purity: side effects would be local to the procedure,
> arguments passed as const or by value, the result returned by value,
> no type casts or new/delete operators used.
>
> On the other hand, the Haskell code makes assumptions about the size
> of double-precision floats (obviously not type-safe). Further, the
> simulation is not a pure function.
>
> It is often argued that one only needs these dirty tricks in the most
> time-consuming functions. However, if using imperative programming in
> these "inner loop" procedures places them in IO monad, the "outer
> loops" (the rest of the program - procedures that call it) will have
> to go there as well. This makes me doubt the Haskell approach to
> functional programming.
>
> If anyone has a version of the N-body benchmark, where the simulation
> is a type-safe pure function, I would very much like to see and time
> it.

n-body requires updating a global array of double values to be
competitive performance-wise, though we haven't really nailed this
benchmark yet. The current entry should be considered an older approach
to raw performance -- typically we can get good (or better) results in
using the ST monad.

To improve safety, it should run in the ST monad. A version using ST is here,

    http://haskell.org/haskellwiki/Shootout/Nbody

However, the current fastest program should really be cross-ported to
run in ST, for best results. (Similar to the nsieve-bits program):

    http://shootout.alioth.debian.org/gp4/benchmark.php?test=nsievebits&lang=ghc&id=0

I suspect the optimisations that weren't happening, that
forced nbody to use Foreign.Ptr in the first place are likely obsolete
now -- GHC 6.8.2 should do a good job with STUArray Double, in careful
hands.

Also worth looking at is the other purely functional entry, in Clean,

    http://shootout.alioth.debian.org/gp4/benchmark.php?test=nbody&lang=clean&id=0

translation to Haskell should be fairly straightforward.

-- Don
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Don Stewart-2]

dons:

> jhc0033:
> > I don't know Haskell very well, but even I can tell, looking at, for
> > example, the N-body benchmark, that the Haskell code is probably not
> > type-safe, and the tricks used in it would not be usable in a larger
> > program (see below).
> >
> > The task is essentially a pure computation: take a list of bodies
> > having mass, position and velocity; apply Newton laws at discrete
> > intervals for a large number of times; return new positions and
> > velocities.
> >
> > I could write a C++ procedure that performs this task and have some
> > piece of mind regarding its type correctness, exception safety and
> > functional purity: side effects would be local to the procedure,
> > arguments passed as const or by value, the result returned by value,
> > no type casts or new/delete operators used.
> >
> > On the other hand, the Haskell code makes assumptions about the size
> > of double-precision floats (obviously not type-safe). Further, the
> > simulation is not a pure function.
> >
> > It is often argued that one only needs these dirty tricks in the most
> > time-consuming functions. However, if using imperative programming in
> > these "inner loop" procedures places them in IO monad, the "outer
> > loops" (the rest of the program - procedures that call it) will have
> > to go there as well. This makes me doubt the Haskell approach to
> > functional programming.
> >
> > If anyone has a version of the N-body benchmark, where the simulation
> > is a type-safe pure function, I would very much like to see and time
> > it.
>
> n-body requires updating a global array of double values to be
> competitive performance-wise, though we haven't really nailed this
> benchmark yet. The current entry should be considered an older approach
> to raw performance -- typically we can get good (or better) results in
> using the ST monad.

Oh, for those following, the program we're talking about is this one:

    http://shootout.alioth.debian.org/gp4/benchmark.php?test=nbody&lang=ghc&id=0

Which I have to argue doesn't /look/ to bad, though the use of Ptr
Double to represent mutable arrays of vectors -- following C -- is a bit
lower level than we'd like.

-- Don
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[PR Stanley]

>I don't know Haskell very well, but


         Paul: "I'm not racist but . . ." :-)

>even I can tell, looking at, for
>example, the N-body benchmark, that the Haskell code is probably not
>type-safe, and the tricks used in it would not be usable in a larger
>program (see below).
>
>The task is essentially a pure computation: take a list of bodies
>having mass, position and velocity; apply Newton laws at discrete
>intervals for a large number of times; return new positions and
>velocities.
>
>I could write a C++ procedure that performs this task and have some
>piece of mind regarding its type correctness, exception safety and
>functional purity: side effects would be local to the procedure,
>arguments passed as const or by value, the result returned by value,
>no type casts or new/delete operators used.
>
>On the other hand, the Haskell code makes assumptions about the size
>of double-precision floats (obviously not type-safe). Further, the
>simulation is not a pure function.
>
>It is often argued that one only needs these dirty tricks in the most
>time-consuming functions. However, if using imperative programming in
>these "inner loop" procedures places them in IO monad, the "outer
>loops" (the rest of the program - procedures that call it) will have
>to go there as well. This makes me doubt the Haskell approach to
>functional programming.
>
>If anyone has a version of the N-body benchmark, where the simulation
>is a type-safe pure function, I would very much like to see and time
>it.
>_______________________________________________
>Haskell-Cafe mailing list
>Haskell-Cafe@...
>http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

On Sun, May 11, 2008 at 1:40 PM, Don Stewart <dons@...> wrote:

> n-body requires updating a global array of double values to be

I think the array and any side-effects on it can and should be local
to the simulation procedure.

> competitive performance-wise, though we haven't really nailed this
> benchmark yet. The current entry should be considered an older approach
> to raw performance -- typically we can get good (or better) results in
> using the ST monad.

As I understand, a function can use ST, but still be pure. If so,
that's the version I'd like to time (assuming it's also type-safe).
The only pure functional solution on that page that I found claims to
have a huge leak.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Don Stewart-2]

jhc0033:

> On Sun, May 11, 2008 at 1:40 PM, Don Stewart <dons@...> wrote:
>
> > n-body requires updating a global array of double values to be
>
> I think the array and any side-effects on it can and should be local
> to the simulation procedure.
>
> > competitive performance-wise, though we haven't really nailed this
> > benchmark yet. The current entry should be considered an older approach
> > to raw performance -- typically we can get good (or better) results in
> > using the ST monad.
>
> As I understand, a function can use ST, but still be pure. If so,

Right, its identical to the current solution, but the mutability is
guaranteed not to escape the simulation scope.

-- Don
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Benjamin L.Russell]

--- On Mon, 5/12/08, PR Stanley <prstanley@...> wrote:

> >I don't know Haskell very well, but
>
>
>          Paul: "I'm not racist but . . ." :-)

Relevant Haskell humor:

Humor/Homework - HaskellWiki: see line 3:
http://www.haskell.org/haskellwiki/Humor/Homework

Benjamin L. Russell
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Richard Kelsall]

J C wrote:
...
> If anyone has a version of the N-body benchmark, where the simulation
> is a type-safe pure function, I would very much like to see and time
> it.

Hello JC, I think you've set yourself a challenge there :) Welcome to
Haskell programming. Taking a Shootout entry and playing with it is
a great way to learn Haskell. The Shootout provides an example in your
favourite previous language for comparison and a small well defined
program with exact test results you can pit your wits against. Fame
awaits you for a fast and beautiful entry. I'm still learning useful
things from the Fasta benchmark. It's surprising how many interesting
things you can discover in a small piece of code.


Richard.

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

On Mon, May 12, 2008 at 4:38 AM, Richard Kelsall
<r.kelsall@...> wrote:

>  Hello JC, I think you've set yourself a challenge there :) Welcome to
>  Haskell programming. Taking a Shootout entry and playing with it is
>  a great way to learn Haskell. The Shootout provides an example in your
>  favourite previous language for comparison and a small well defined
>  program with exact test results you can pit your wits against. Fame
>  awaits you for a fast and beautiful entry. I'm still learning useful
>  things from the Fasta benchmark. It's surprising how many interesting
>  things you can discover in a small piece of code.

It may be fun, but I don't think it would be meaningful. My code will
be, most likely, slow, leaving some doubt as to whether it's slow
because of the limitations of the compiler or my inexperience.

On the other hand, if the experts can't help using malloc, unsafe*,
global mutables and IO, I'll be able to conclude that this is probably
what it takes to make Haskell run fast :-(
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Brandon S. Allbery KF8NH]

On 2008 May 13, at 0:26, J C wrote:

> On the other hand, if the experts can't help using malloc, unsafe*,
> global mutables and IO, I'll be able to conclude that this is probably
> what it takes to make Haskell run fast :-(

Very few of the shootout entries have been revisited since most of the  
improvements to list and stream fusion, etc. in GHC, if I can trust  
the amount of discussion of shootout entries I've seen on IRC.  Some  
of them are still vintage 6.4.2, which had very little in the way of  
compiler smarts so hand optimization was crucial.  6.8.2, on the other  
hand, does much better all by itself as long as you don't e.g. use  
lists in stupid ways.

--
brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery@...
system administrator [openafs,heimdal,too many hats] allbery@...
electrical and computer engineering, carnegie mellon university    KF8NH


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Richard Kelsall]

J C wrote:

> <r.kelsall@...> wrote:
>
>>  Hello JC, I think you've set yourself a challenge there :) Welcome to
>>  Haskell programming. Taking a Shootout entry and playing with it is
>>  a great way to learn Haskell. The Shootout provides an example in your
>>  favourite previous language for comparison and a small well defined
>>  program with exact test results you can pit your wits against. Fame
>>  awaits you for a fast and beautiful entry. I'm still learning useful
>>  things from the Fasta benchmark. It's surprising how many interesting
>>  things you can discover in a small piece of code.
>
> It may be fun, but I don't think it would be meaningful. My code will
> be, most likely, slow, leaving some doubt as to whether it's slow
> because of the limitations of the compiler or my inexperience.
>
> On the other hand, if the experts can't help using malloc, unsafe*,
> global mutables and IO, I'll be able to conclude that this is probably
> what it takes to make Haskell run fast :-(

Don't tell the experts who wrote the current shootout entries, but the
playing field is tilted radically in favour of us beginners being able
to improve on their entries because of new versions of GHC and new
tools that have been developed since they wrote their entries.

GHC will now automatically perform many of the optimisations that used
to have to be done by hand. For example I was surprised to discover
the other day when working on Fasta that putting this plain and simple
version of splitAt

splitAt n (x : xs) = (x : xs', xs'')
                 where (xs', xs'') = splitAt (n-1) xs

in my program made it run more quickly than using the built-in version
of splitAt which I now know looks like (ug!) this

splitAt (I# n#) ls
   | n# <# 0#    = ([], ls)
   | otherwise   = splitAt# n# ls
     where
         splitAt# :: Int# -> [a] -> ([a], [a])
         splitAt# 0# xs     = ([], xs)
         splitAt# _  xs@[]  = (xs, xs)
         splitAt# m# (x:xs) = (x:xs', xs'')
           where
             (xs', xs'') = splitAt# (m# -# 1#) xs

because I was compiling my splitAt with -O2 optimisation as opposed
to the built-in version being compiled with -O. The extra optimisations
in -O2 are a new feature of GHC (and -O2 is slower to compile which is
why the built-in version doesn't use it, but that doesn't matter for the
shootout). You may similarly find various elaborations in the shootout
entries that were historically necessary for speed or memory reasons,
but which can now be removed because GHC or new libraries do the work
for us.

Have a go and see what happens to the speed when you change things
to make N-body more readable. I would bet money on there being simple
tweaks which will make it simultaneously faster and more readable.


Richard.


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Sterling Clover]

Well, it would be meaningful for your own experience in learning Haskell. Some time ago somebody took a shot at nbodies using pure immutable structures, and as I recall, got within about 4x the performance of mutable structures. In 6.6, an STArray based approach was maybe 2x slower, but by now it may well be comparable, as Dons pointed out. In fact, lots of the shootout entries could use an overhaul now that 6.8 is running on their machines, as plenty of older, uglier, optimizations are probably preformed as efficiently if not more so by the newer GHC, whose strictness analysis, for example, is consistently and pleasantly surprising.

If you take a stab at some of these benchmarks, with some helpful guidance from #haskell, you'll no doubt get a much better sense of how memory and performance works in haskell, and which tweaks are just there for the last 2%. So even if you can't beat the current winners (and given the compiler changes, you may well be able to) you'll still come out ahead in the process.

As for the clean entry though, it no doubt relies heavily on uniqueness typing and so is secretly mutating like crazy under the hood.

Cheers,
S.

On Tue, May 13, 2008 at 12:26 AM, J C <jhc0033@...> wrote:

On Mon, May 12, 2008 at 4:38 AM, Richard Kelsall
<r.kelsall@...> wrote:

>  Hello JC, I think you've set yourself a challenge there :) Welcome to
>  Haskell programming. Taking a Shootout entry and playing with it is
>  a great way to learn Haskell. The Shootout provides an example in your
>  favourite previous language for comparison and a small well defined
>  program with exact test results you can pit your wits against. Fame
>  awaits you for a fast and beautiful entry. I'm still learning useful
>  things from the Fasta benchmark. It's surprising how many interesting
>  things you can discover in a small piece of code.

It may be fun, but I don't think it would be meaningful. My code will
be, most likely, slow, leaving some doubt as to whether it's slow
because of the limitations of the compiler or my inexperience.

On the other hand, if the experts can't help using malloc, unsafe*,
global mutables and IO, I'll be able to conclude that this is probably
what it takes to make Haskell run fast :-(

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Bulat Ziganshin-2]

Hello Richard,

Tuesday, May 13, 2008, 6:10:54 PM, you wrote:

> because I was compiling my splitAt with -O2 optimisation as opposed
> to the built-in version being compiled with -O. The extra optimisations
> in -O2 are a new feature of GHC (and -O2 is slower to compile which is
> why the built-in version doesn't use it, but that doesn't matter for the
> shootout).

-O2 is very old ghc feature and i think that ghc base library is
compiled with -O2 - it's too obvious idea

--
Best regards,
 Bulat                            mailto:Bulat.Ziganshin@...

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Richard Kelsall]

Bulat Ziganshin wrote:

> Hello Richard,
>
> Tuesday, May 13, 2008, 6:10:54 PM, you wrote:
>
>> because I was compiling my splitAt with -O2 optimisation as opposed
>> to the built-in version being compiled with -O. The extra optimisations
>> in -O2 are a new feature of GHC (and -O2 is slower to compile which is
>> why the built-in version doesn't use it, but that doesn't matter for the
>> shootout).
>
> -O2 is very old ghc feature and i think that ghc base library is
> compiled with -O2 - it's too obvious idea
>

In July 2007 -O2 was documented in GHC as making no difference to
the speed of programs :

http://www.haskell.org/pipermail/haskell-cafe/2007-July/029118.html

and from this thread

http://www.haskell.org/pipermail/haskell-cafe/2008-April/042155.html

it appears to be currently unused for splitAt.

I guess -O2 has however been around for a long time.


Richard.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Bulat Ziganshin-2]

Hello Richard,

Tuesday, May 13, 2008, 7:56:36 PM, you wrote:

> In July 2007 -O2 was documented in GHC as making no difference to
> the speed of programs :

> http://www.haskell.org/pipermail/haskell-cafe/2007-July/029118.html

it's because ghc is 15 years old and its documentation may be not
updated as things changes :)

> and from this thread

> http://www.haskell.org/pipermail/haskell-cafe/2008-April/042155.html

> it appears to be currently unused for splitAt.

i've read this thread. it was just assumption - don't believe it
before you have checked it


--
Best regards,
 Bulat                            mailto:Bulat.Ziganshin@...

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Richard Kelsall]

Bulat Ziganshin wrote:

> Hello Richard,
>
>> In July 2007 -O2 was documented in GHC as making no difference to
>> the speed of programs :
>
>> http://www.haskell.org/pipermail/haskell-cafe/2007-July/029118.html
>
> it's because ghc is 15 years old and its documentation may be not
> updated as things changes :)
>
>> and from this thread
>
>> http://www.haskell.org/pipermail/haskell-cafe/2008-April/042155.html
>
>> it appears to be currently unused for splitAt.
>
> i've read this thread. it was just assumption - don't believe it
> before you have checked it
>

Hello Bulat,

Yes it was just a plausible guess, but not contradicted by the experts.
And that was using the Windows version of GHC so other versions may
have better optimisation. I don't know how to check, maybe the experts
can illuminate the subject?


Richard.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Bulat Ziganshin-2]

Hello Richard,

Tuesday, May 13, 2008, 8:23:59 PM, you wrote:

> Yes it was just a plausible guess, but not contradicted by the experts.
> And that was using the Windows version of GHC so other versions may
> have better optimisation. I don't know how to check, maybe the experts
> can illuminate the subject?

note that my letter was not contradicted too LOL

1. many experts just don't read this list due to its high traffic,
write into ghc-users instead

2. ghc is too large system and no one know all its details. this
particular option may be set up 10 years ago and never
touched/studied by anyone since then. for example, i'm ghc performance
expert [to some degree], but i don't know anything about its build
system. all that i can tell is that ghc base library build times don't
prohibit use of -O2


--
Best regards,
 Bulat                            mailto:Bulat.Ziganshin@...

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Richard Kelsall]

Bulat Ziganshin wrote: