[Shootout-list] Missing programs and score calculation (Was:

[skaller]

On Fri, 2005-09-16 at 21:59 +0100, Jon Harrop wrote:

> I was clarifying: C is not literally "one of OCaml's intermediate 
> representations". But I guess I wasn't very clear...

I am not surprised Ocaml has a low level intermediate language
representation lacking lambdas: Felix does too. Perhaps one
difference is that many FPL's seem to do lambda-lifting late,
whereas Felix lifts them out immediately after parsing.

Perhaps one difference in the compilers: there's not a scrap
of lambda calculus in Felix code generation (the type calculator
uses some though). Lifting lambdas early allows the compiler
to concentrate on optimisations such as closure removal,
control flow, inlining, etc, more commonly associated
with procedural languages -- contrary to the impression
you may get from Marco's comment:

> In selected benchmarks of course. One benchmark 
> that is known to favour functional languages is a bit 
> simplistic isn't it ? :-)

Felix is billed as a *procedural* language, not a functional one.

However Felix often needs to 'reconstruct' the environments
lambdas represent, which is expensive and difficult: the system
could probably benefit from delaying lambda lifting a bit more:
flattened representation loses information about lifetime of variables
which is hard to reconstruct from SSA form.

It would actually be interesting to find which kinds of
programs are well optimised by different compilers: Haskell,
Ocaml, MLton, and Clean, as well as Felix, use entirely different
techniques, so you'd expect each to shine in certain situations
and perform very poorly in others: a function of the internal
compiler technology *and* the runtime system.

Unfortunately, discovering suitable tests is not easy, even
with the advice of the compiler writers, and the political
and technical structure of the shootout isn't really amenable
to the kind of cooperation required to develop such tests,
nor to provide relevant documentation which would aid
users in choosing a language.

For example: Felix follows the tradition of 
C/C++/Algol/Pascal/Modula in maintaining whole stack frames
in which variables are located, whereas Ocaml (and I think
MLton and Haskell and most FPLS) maintain variables
independently as boxed heap values. This has a significant
impact on the performance of different kinds of code:
boxing is expensive, and lots of low level boxes, including
closures, are very hard to manage efficiently.

On the other hand whole frames are cheap to manage,
but they cost more storage than individual variable management,
and failure to eliminiate dead pointers means the collector
has more work to do sweeping the heap.

Another example, ocaml can unbox structs and arrays of floats,
ints are unboxed, but other data types are generally boxed.
So tests which just use ints and floats will give Ocaml
a massive advantage: realistic data structures contain
a mix of data types and will drive the ocaml collector
much harder, and exercise the unboxing operations much
more frequently. Felix on the other hand will notice
no difference since types are not boxed, except
for closures, variants and explicit pointers.

However, the collector is naive, because the C/C++
object model prevents moving objects to which weak
pointers point, so a high performance collector
probably can't be used.

Contrary to which you might think, I have a vested
interest in finding low performance cases for Felix,
as well as high performance ones -- because it shows
where work needs to be done, or where instrinsic
limitations of the design lie.


-- 
John Skaller <skaller at users dot sourceforge dot net>

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part
Url : http://lists.alioth.debian.org/pipermail/shootout-list/attachments/20050917/c479f090/attachment-0001.pgp