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

jhc0033:

On Sun, May 11, 2008 at 1:40 PM, Don Stewart 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

On Mon, May 12, 2008 at 4:38 AM, Richard 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 :-(

J C wrote:

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.

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.

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.

Bulat Ziganshin wrote:

Hello Richard,

...

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

Good point. I have started a thread here http://www.haskell.org/pipermail/glasgow-haskell-users/2008-May/014742.html

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