Fwd: Re: [Shootout-list] Science-related benchmarks

[Jon Harrop]

On Tuesday 26 April 2005 16:27, Sebastien Loisel wrote:
> Aside from the integrator you've tweaked, I've proposed the new
> spectral norm test and the implicitode tests; my next bench is to be
> something multi-dimensional involving either LU, sparse LU or GMRES
> and other algorithms.

Excellent. Where can I find more details on these?

> My goal was to add some numerical benchmarks that used nontrivial sets
> of numerical algorithms in an interrelated way, with interesting data
> structures and hopefully some polymorphism. The test implicitode is a
> (possibly flawed) example of what I was thinking of. It solves several
> odes using the trapezoidal method, with a newton solver which uses
> automatic differentation(*) to compute f' with a variety of scalar
> fields to force polymorphism.

Interesting.

> I think the polymorphism in particular has been poorly received
> because it makes the implementation longer in most languages and more
> importantly more difficult to understand. I will take that into
> account in future tests.

In addition to polymorphism, I'd like to see implementations of solutions
which naturally use higher-order functions (e.g. Newton-Raphson). This is
easy in functional languages, C can use pointers to functions, Java can use
inheritance, C++ can use templates or either of those, and so on.

> > IIRC, Newton's method is actually better here because it is more
> > numerically
>
> Newton is almost always better but it has a matrix inverse, so people
> don't use it for large scale problems, that's why I suggested CG.

Yes, CG doesn't work in this case as it is too numerically unstable. The
simplex method might be interesting but probably won't be any better for the
shootout than gradient descent. I'm not sure how subspace Newton methods
(BFGS is it?) compare against CG. Most people I know just use some form of CG
or gradient descent.

For the shootout, I'd be happy to stick with gradient descent. My "relax"
proposal is good in this respect as more sophisticated minimisation
algorithms don't really buy you anything in that case (and many others).

> > The Mathematica JIT compiler I wrote for Wolfram Research included this
> > functionality. Coupled with the unusually powerful pattern matching
>
> Interesting. Did that particular bit end up in the consumer product?

Not yet. In the mean time, they are considering releasing a free
implementation of the core Mathematica language, which would be a welcome
addition to the shootout, I think.

> > We could try FP intensive tests (e.g. bounding box) instead and see if
> > they were faster. I'd be surprised if they were though, unless we're also
> > doing
>
> I don't think they'd be faster, but the algorithm would be more
> representative of a real algorithm.

We'll have to disagree here. In my work, my optimisations are almost always
either algorithm or data structure. I know that lots of other people have
float-intensive work though, although I think that is often memory bound and
optimisations are then to do with cache coherency. Given the increasing
memory gap in modern hardware, floating point performance is becoming less
important.

> > The C++ was virtually identical - just cosmetic improvements. I shaved
> > 10% or so off the OCaml (mainly by type specialising the heap, IIRC).
>
> In that case, for apples to apples, it would be good to write a
> specialized heap for C++ as well, although I suspect there won't be a
> gain.

Oh no, I'd rather leave it as it is. I don't like the idea of counting
standard library code (assuming you'd just cut and paste that) towards the
total LOC of the program as that no longer reflects the effort and risk
involved in writing the program. I know LOC isn't a great measure, but I
think it's the best we can do.

> Also, I saw you preallocate the heap in the ocaml, I think we
> should either disallow that or make everyone preallocate it.

Yes, I don't think it improved the performance much so you might as well get
rid of it (or opt for some "standard" value like 1024).

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