[Shootout-list] Many tests cheat

Einar Karttunen ekarttun@cs.helsinki.fi
Tue, 2 Nov 2004 13:08:14 +0200


On 02.11 20:06, skaller wrote:
> > Actually Haskell has many kinds of mutable arrays:
> > boxed and unboxed arrays in both the IO and the ST monad and
> > even the parallel array extension. The last one is the fastests 
> > in many cases, but the compiler support is quite buggy.
> 
> Sure, because it's a hard problem. So it is likely
> Haskell will pay some price one way or another.

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

> 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..
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). Of course ocaml has some
issues with the float array thing, which do not occur in 
haskell. 

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

> So an array access test that only examines 'int' is giving
> Ocaml an unfair advantage -- it will be almost as fast as C.
> For general values, however, it will be slower because of the
> write barrier .. and if the array is big enough,
> the collector will also have to scan it.

Well in the general case you have to do lots of other things in C 
too. The write barrier is just a part of GC, and C will need manual 
memory management or a GC without write barrier which might be
slower...

> So measuring 'array access' in a naive way is failing,
> because of the assumption that arrays of everything are
> the same as they are in C. In Ocaml this isn't the case.
> There is a small price to pay for running the Ocaml 
> collector in the presence of mutable data structures.

Well array of pointers needs care in C too... Actually it is 
usually quite painfull with "who should free this pointer".

> I'd be very interested to see how Haskell copes, mainly
> because, from working on Felix, I'm beginning to believe
> that in the end purely functional language will outperform
> others in many circumstances, mainly because of the 
> optimisation opportunities. I originally specified eager
> evaluation .. but I'm moving now to 'sloppy' evaluation,
> meaning the compiler can evaluate anytime it wants.
> (eagerly if usage is high, lazily if low).

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

- Einar Karttunen