[Shootout-list] Ackermann

[Jon Harrop]

On Saturday 18 June 2005 17:45, Eric Lavigne wrote:
> I agree with this completely.

Wahey! I'm convincing people. Now for Brent and Isaac... ;-)

> With only minor changes, as Jon recommends, we can go all-out to get the 
> best possible performance from our codes without leading to the benchmark 
> becoming totally meaningless.  

Exactly. Formally, this discussion is related to irreducible computational 
complexity. We want to design benchmark tasks which cannot be reduced beyond 
a certain point, e.g. to just printing out the answer.

As Eric is saying, this is much more representative of real programs and still 
leaves plenty of interesting opportunities for optimisation and, 
consequently, will make the shootout much more useful.

As a consequence of the irreducible complexity, it will be necessary to have a 
reference implementation of each test which the shootout will run first, 
feeding in the chosen input, in order to get the "correct answer" for that 
input. The test implementations will then be run with the same input and 
their answer compared to the reference implementation's answer to check that 
they ran ok.

Note that this is what we're already doing with my ray tracer, the original 
57-line OCaml implementation is the reference. The only difference is that 
the inputs are always the same and the correct answers were generated by 
executing the reference implementation manually.

> > Consider this: if "random" seeded the random number generator with the
> > given integer then the test would not be any more "complex" but could no
> > longer be precomputed.
>
> I basically like this idea. There might be issues where the rankings
> shift a bit depending on which random number was chosen, but that
> shouldn't be a big issue. Maybe average the results of several
> different numbers?

Does the shootout already choose the fastest of three runs?

For tests with a computational complexity dependent upon the size of one of 
their inputs, we can also satisfy Bengt's request for multiple "N" at the 
same time. We just log all of the results for all the different "N" as they 
are generated. Then the shootout picks a random "N" each day.

This also answers Isaac's concern that it won't be obvious when different 
implementations use different algorithms - the performance as a function of 
"N" will make this clear in most cases.

> The webpage for that benchmark should indicate what 
> range of random numbers are being used because some languages will
> need to allocate arrays and other containers at compile time.

I don't quite follow this. Can you give an example?

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