[Shootout-list] Many tests cheat

[skaller]

On Tue, 2004-11-02 at 22:08, Einar Karttunen wrote:

> There is nothing in theory which should make things slower in 
> haskell, of course reality is different and that should show
> in the scores.

Hmm, well purely functional systems can't solve
certain problems efficiently. Arrays are a well 
known example, the best performance is 
around O(log n), most people believe it can be 
proven functional arrays can't exist although it
hasn't be done yet. Even if Haskell can escape purely
functional coding with monads (which is must to do
I/O I suppose) there are bound to be some difficulties
applying that technique with the ease it can be done
in a procedural language.

> > Ocaml also pays a price. Every write to
> > general storage is done via a subroutine call
> > which is necessary to manage the minor heap,
> > it's called a write barrier I believe.
> 
> Well that is just poor compiler..

It's a consequence of the way the run time works.
Hard to say the compiler is poor .. check out the Alioth
shootout rating .. :))

> If the array contains unboxed numbers, write barrier is not 
> needed and the code can be inlined resulting in more or less 
> the same code as in C (in theory).

This happens -- I said 'general storage' intending to mean
excepting the special cases.

> > However access to specialised arrays -- string, unboxed
> > floats arrays and int arrays and some of the new fatter
> > integer arrays -- avoids this overhead I think.
> 
> True. And it is precisely those arrays which matter in the array
> tests.

Indeed, and that's the problem I'm pointing out.
The test isn't measuring general array access fairly,
because it happens to pick on a case which Ocaml has special
handling for.

Add a test requiring a record (C struct) and then
the write barrier will be required .. and an extra
indirection as well.

The intent of my comment is not, however, to suggest
the test is inadequate, although that may be the case.
Rather to point out that defining what an array is,
and requiring some vague 'do it the same way' constraint
is not necessary nor sufficient to achieve fairness,
and is most likely to be an ill formed requirement,
unless it actually refers to an observable quantity
that can be checked.

AFAICS there are only 4 observables: time, memory,
lines of code, and the actual required output.

> But having the correct amount of laziness and optimization is 
> not very trivial..

Heh .. I asked the Ocaml team if they could explain
the inlining algorithm... the answer was just 'that's hard'.
I don't think they meant the algorithm was hard .. I suspect
it consists of heuristics that have been chosen with long
experience .. and not much theory.

Recent Ocaml performance measurements seem to indicate
inlining actually slows down execution .. modern CPUs
are so much faster than memory that cache misses are just
about the only thing that matters.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net