[Shootout-list] Directions of various benchmarks

[skaller]

On Thu, 2005-05-19 at 00:11, Einar Karttunen wrote:
> skaller <skaller@users.sourceforge.net> writes:
> > How the heck can you judge if a solution in C or Ocaml
> > or Haskell is 'the same way' as a Java program when one
> > language is imperative with variables and the other
> > is functional?
> 
> This should not be a hard problem if the description of the way is
> textual. Of course it will be prone to people finding new
> interpretations of the specification.

Yes, but sometimes we would approve the new way!
And sometimes, the new way shows we need to fix the
specification.

I agree, this may not be easy. For example, consider
Ackermann's function -- if you say 'calculate Ackermann(3,x)
for any x, the smart programm will KNOW that it is impossible
to calculate for x > 20 on any existing computer! So they
can calculate for x = 1 to 18 in advance and just write

	static int acka[20] = {0,1, ... };

	int ack(int x, int y) {
		return acka[y];
	}


where 'acka' contains all the known values of Ack(3,x).
Clearly this algorithm is (a) correct and (b) faster than
all others by a MASSIVE margin .. but it defeats the real
intent of the test.

The solution is: drop Ackermann as a test. The problem 
is that it does lots of function calls in naive version,
which we want BUT there are not enough possible inputs.

We must choose instead a function that is heavily recursive
but which has MANY inputs so the results can't be pre-calculated.
I do not know such a function off hand, but I'm confident
suitable ones exist.

> Wasn't the problem that Felix said "jump to handler X" and other
> languages were saying "jump to the topmost handler for this
> exception" (I don't remember so I can be wrong too).

Part of the problem was as you say, Felix says jump to a particular
handler. But C ALSO does that -- you have to name the particular
jumpbuf, and Scheme ALSO does that -- you have to supply the
particular continuation.

More precisely, you don't have to jump to a *known* handler,
you only have to know it indirectly -- you call a function
which knows, you can't see inside the function, so the
thrower does NOT know the handler: it is hidden behind
the abstraction provided by the function:

	proc f() {

		error_handler:> print "ERROR"; ...

		proc wrapper() { goto error_handler; }

		g(wrapper);
	}


	proc g(err: void -> void) { .. .. err(); .. }


So, this is not 'dynamic exception handling' of the same
kind as in C++ and Java, and that is quite deliberate:
I don't supply general dynamic EH because it is extremely
BAD to have, it is way too powerful. The connection between
the throw and catch points is not just 'open', it may
not even exist.

The Felix technique guarrantees the existence of the catcher,
and it is quite powerful enough to handle a wide class of errors,
IN PARTICULAR it easily solves the problem actually set
in the shootout.

I add a BTW: it has been PROVEN recently that call/cc
is equivalent to dynamic EH in power, in particular
languages with dynamic EH are as strong as those with
call/cc. However my technique is equivalent to call/cc
I think .. so it appears I have a semantic equivalent just
as powerful as dynammic EH but much easier to control
and reason about. But don't quote me on this, I havent
done the math or read the paper in detail.

The point is: it is no accident this is not the same
as in Java and C++. It isn't a mistake, it isn't a missing
feature, it is a superior method of error handling because
it is offers more guarrantees -- uncaught
exceptions are impossible.

Well I don't care if you agree with that claim or not,
and I don't care if it even a correct claim or not,
but I DO care if it clearly satisfies the test
requirements (the right answers are printed) and
it is banned 'because it isn't the same way as Java'
when I pointedly and specifically designed it to
handle errors a different way, yet several other languages
use exactly the same technique and were NOT banned,
including C and one of the Schemes (Bigloo actually has
dyanmic exceptions instead of call/cc I think).

So you can bet I'm plenty annoyed, when someone who
has no idea what it is all about bans the code which
clearly *justifies* the mechanism I chose, and the test
is so trivial the superior typing/guarrantees not only
make the code easier to reason about for humans,
it turns out the optimiser is able to reason about
the code better too .. and after inlining the 
the non-local goto turns into a local goto,
the stack unwinding is unnecessary, and the program
SCREAMS in way ahead of everyone else.

If that seems unfair I can easily devise a test where
having to pass the handler around is a measurable performance
penalty -- just make it pass down several levels .. but only
throw one time out of 1000 and Felix will be much slower than
C++ which pays no price unless an exception is thrown.

> > Similarly 'concurrency' tests are in question, because
> > a requirement to use Posix thread is absurd: should we
> > really measure OS thread handling limitations? 
> 
> The requirement is not posix threads but pre-emptive threads. 

There is no other way to get pre-emptive threading on linux
that I know of.

> There is a semantic difference between them and coroutines.

Actually not really. The only difference is that with
coroutines every point of the code except a yield
is a critical section, whereas with pre-emptive threading,
this behaviour is obtained by explicitly locking at the start
of the thread and yield is just a release and re-acquisition
of the lock -- so coroutines can be emulated by pre-emptive
threads. OTOH you can yield anywhere in a coroutine ..
so semantically they're actually equivalent, or more
precisely each can emulate the other.

However, threading is NOT concurrency, that requires
a multi-cpu computer, and you can often run two processes,
gain concurrency, and not have any threading.

Finally, the 'requirements' on at least one of the tests
allowed microthreding in a sloppy way: several systems
actually used it and were permitted despite not using 
Posix threads.

> All other languages could switch to using co-routines and have a similar
> performance boost 

Nope! Which other compiled language than Felix HAVE coroutines??

Um .. not C .. not Ocaml .. not C++ ..  Haskell might I think?

> - but we are trying to measure something
> different.

What? Everyone call Posix threads, the cost is the same
for everyone because it is so dang slow to create a Posix thread
and to switch them, it will dominate -- the tests don't actually
do any real work.

The proof is simple -- Felix does the work *without* calling
Posix threads and creams it in! It also isn't limited to 350 or
so threads (that's about when my old LInux box started to refuse
to create more threads) .. Felix easily runs 10,000 threads.
Again, it was designed to, the original design was for a
telephony environment (600 calls/second is the nominal
rating of a telephony switch .. average call length 3 minutes,
the load is shared between about 10 CPUs)

> You cannot get a sorting algorithm like that very easily in Haskell. It
> needs mutable arrays for the constant memory and thus the LOC will climb.

Then it will fail, if you can't write a sort in 5-6 loc.
Imperative programming does have some advantages?

> > And you can add that 'the intent is to use a bubble sort'. 
> > (Maybe its 6, but you can't implement a quicksort in such a small loc :)
> 
> Actually the classic (inefficient) Haskell quicksort is 5 lines:
> 
> qsort []= []
> qsort (x:xs) = qsort small ++ mid ++ qsort large
>    where small = [y | y<-xs, y<x]
>          mid   = [y | y<-xs, y=x] ++ [x]
>          large = [y | y<-xs, y>x]
> 

So, my test spec was in fact bad? Or alternatively, Haskell will
win easily. But you do get the idea I hope? It may be
harder to specify what you want operationally, in terms
only of tangible simple observables, but it is even
harder arguing about what 'same way' means :)

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