[Shootout-list] Stuff

[Jon Harrop]

I accidentally posted the last half of this e-mail off list - sorry for the 
duplication, Sebastien.

On Sunday 24 April 2005 23:08, Sebastien Loisel wrote:
> On 4/22/05, Jon Harrop <jon@ffconsultancy.com> wrote:
> > as well as floats. These kinds of things are so difficult to implement in
> > most other languages that programs are either at worst intractable
> > (Fortran) or at best error-prone (C++).
>
> I have begun working on such problems, attempting to stay within the
> limits of the shootout. Look at implicitode and
> http://www.math.mcgill.ca/loisel/numerical-integration.html.

I've never had to write code to solve that kind of task but it looks like a 
good test to me. I get 1.0s for C++, 1.6s for my OCaml version and 23s for 
Haskell (GHC 6.2.2 though).

I'll list my comments:

1. Get rid of the magic numbers (e.g. 0.8888... / 2.).
2. Put more spaces in the C++ to aid clarity.
3. Don't use macros in C++.
4. If "sin(x ln x)" is not an appropriate function then use an appropriate 
function.
5. Perhaps it would be better to provide the function externally, so as to 
avoid measuring the inlining performed by compilers.
6. What about integrating an interpolated function from a given data set?
7. Should "eps" be related to the machine precision?

I've just been playing with it. How about integrating this function instead:

f(x) = sin(x ln x) sin(100 ln 100 + (x - 100) (1 + ln 100))

with eps = 0.000001 and the same range.

Both programs and Mathematica, I get "8.787608...". The C++ took 4.366s and 
the OCaml took 5.942s.

> To borrow a word from a famous man, I think you misunderestimate C++.

Having written too much error-prone numerical code in C++ for my PhD, I've 
switched to OCaml. For example, if I compile your C++ implementation with -O3 
(on g++ 3.3.5 here) it segfaults. I have no idea why.

> > Regarding some other discussions I've read about in the archives. I think
> > it is vitally important to allow people to use common libraries (and to
> > not
>
> I'm specifically designing numerical code that prevents people from
> taking advantage of libraries like FFTW and LAPACK. I don't think they
> make for insteresting benchmarks.

The FFTW-based MEM program from my book is of practical interest and, I 
believe, is representative of many other tasks performed by scientists.

In this task, the majority of the time is spent doing FFTs (in FFTW) and, 
consequently, the performance of the host language is virtually irrelevant. 
However, run-time performance can be greatly improved by using more 
sophisticated local minimisation algorithms. Thus, the clarity and brevity of 
the host language are very important, more so than their performance.

> > 1. Sphere: Recursively subdivide an icosahedron to produce an arbitrarily
> > accurate approximation to a sphere (described in the OpenGL Red Book).
>
> I've implemented this many times and it's array+floats, and not even
> complicated float calculations, so I don't see why one would want to
> do this.

I think you're thinking of uniform subdivision. I'm thinking of adaptive 
subdivision. This algorithm underpins my planet demo, for example:

  http://www.chem.pwf.cam.ac.uk/~jdh30/programming/opengl/lod/index.html

The algorithm requires a lot more sophistication than just array+floats. The 
sophistication is to do with data structures (trees/graphs) rather than 
floating point arithmetic, so it won't satisfy your quest for float-intensive 
benchmarks.

As for practical application, this can be used to render a sphere and, 
consequently, should be useful for a lot of people.

> > 3. Discrete wavelet transform: This can be implemented really elegantly
> > using lists, or much more efficiently but less clearly using arrays (at
> > least in OCaml).
>
> You will certainly lose if you try lists against arrays.

Some languages may be able to represent the lists (and their tails) as arrays 
(and subarrays), in which case their implementations could be both fast and 
clear.

> It might be 
> an interesting test to have, but the main difficulties are the
> semi-random memory accesses when building the multiresolution thing,

I'm not sure what you mean by "building the multiresolution thing".

> because the base calculations aren't hard at all, so the test would
> have to show some interesting patterns in the languages because I
> can't see what's special about it.

I think the implementations will be quite varied and, therefore, interesting.

> > 5. Graphics algorithms: I like the idea of a ray tracer someone
> > suggested. How about some more algorithms from graphics?
>
> You'd have to be more specific. Raytracing is interesting if you have
> some hierarchical data structure to speed up the ray checks, because
> it gives an interesting algorithm, but many of the other graphics
> algorithms I know either take a fair bit of code to write or depend on
> some numerical algorithm which might as well be implemented on its
> own.

Yes. What about raytracing the old sphere-flake? Something like this:

  http://www.stud.fernuni-hagen.de/q5480035/kurs77074/04/IllumSphereFlake5.png

That was easy enough to implement and aesthetic enough to look at.

> > 6. Calculator or BASIC: a simple lexer, parser and interpreter.
>
> Yes, writing toy parsers, the great success of all functional
> languages. I'm not that keen on writing a yacc benchmark, but that's
> just me.

It would be interesting to have interpreters for one language written in 
several other languages and then compare their performance when executing the 
same code.

> > 7. Symbolic manipulation: write a program which can symbolically
> > differentiate x^x or multiply out polynomials with arbitrary-precision
> > integer coefficients or something.
>
> The arbitrary precision bit makes it difficult. I was going to use it
> in my implicitode test but it pushes everything off into large loc
> counts in several languages. I also know why you like this test, and
> it's true that it'll increase the loc count of C++ whether you do it
> with virtual functions or templates.

Yes, C++ won't be very good at this problem either. Efficient pattern matching 
is probably the main benefit of more modern languages here.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists