[Shootout-list] Many tests cheat

[skaller]

On Tue, 2004-11-02 at 02:24, Isaac Gouy wrote:
> > Many of the tests I've seen cheat, one way of the other.
> 
> Do you mean that many of the programs cheat?

yes.

> So compile a list of offending programs, indicating why you believe
> they should not be accepted. 

I plan to, but I'm still trying to actually get the list
to work. I have the shootout CVS, but I can't build it,
and without list access it's tricky to get help :)

Strangely I get two copies of this mail... which seems to indicate
one by private email and one from the list.

However as indicated below, part of the problem
is that some of the tests don't really measure what they
intend to, and that's partly because the intent isn't
representable -- eg 'array access speed' is semantic
nonsense. It assumes far too much about the language
implementation and semantics.

Python? Arrays? But Python arrays are actually
dictionaries, and Python lists are actually arrays.
Tcl -- doesn't have any arrays at all AFICR.

My argument isn't that we shouldn't test array access speed,
but that it must be done by requiring a calculation that
is best done using contiguous random access storage.

> > I'm generally in favour of functional testing,
> > and doubt that 'do it the same way' tests prove
> > anything at all. They tend to bias the tests in favour
> > of language with 'same way' facilities and against
> > others that don't -- for example Haskell can't do arrays
> > so well.
> 
> Isn't that a useful thing to know?

Not really. If Haskell can solve a problem which seems
to require arrays just as fast as C, then something
much more important is learned -- arrays aren't necessary
for many problems.

Let's look at the C solution for array access:

for (k=0; k<1000; k++) {
	for (i = n-1; i >= 0; i--) {
	    y[i] += x[i];	
}

I can solve this problem like so much faster:

for (i = n-1; i >= 0; i--) 
  y[i] += x[i] * k;	

Given a sophisticated enough compiler, it may well
generate this code -- defeating the test. Therefore
the test *itself* is bugged, IMHO, because it isn't
necessary to actually access the array k times.

In requiring the code be 'executed n times' you're
specifying something that only makes sense in a
dumb imperative language. In a declarative language,
perhaps like Mercury, and possibly even Haskell,
most of the work is on finding a solution, and I wouldn't
be surprised if the result was less memory accesses
than expected.

Real compilers can do loop reordering, loop unrolling,
invariant code motion, and even decide that repeated
addition is the same as multiplication.

On the other hand my original Felix solution to this
problem performed really badly. Why? It had absolutely
nothing to do with array access in Felix, which I 
can promise you is just as fast as C because the generated
code is exactly the same as C array accesses. My solution:

	for {i = n-1;}  {i >= 0} { i--;} {
	    y.[i] = y.[i] + x.[i];
	};

looks very much like the C code. But it is utterly different:
that 'for' isn't a builtin control structure, it's a curried
function with four arguments, which means that without
optimisation, every loop iteration is calling a function
just to compare i, and another to increment i .. and this
totally dominates the time, the array accesses aren't even
marginally relevant.

So for Felix, with that solution, the test is actually
meauring function call overhead. Note also that I didn't
use += because it didn't work properly. In other words,
the test is really good for me as the compiler writer,
because it identifies several performance problems --
but it isn't measuring array access at all.

In fact, if I can't get the *same* performance as C,
exactly, for array accesses, there is probably a bug
in the way shootout is doing the measurements, because
the generated code is *literally* the same as C. 

In fact the test is measuring a heap of things other
than array access -- for example the C solution
can access the index variable 'i' faster than Felix
because the Felix code becomes

	ptf -> i

for a pointer 'ptf' to the global frame object.

I guess my point is that the test is really useful
because it measures poor performance in Felix
for everything *except* array access :)

-- 
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