Re: Language Efficiency

[fjh@munta.cs.mu.OZ.AU (Fergus Henderson)]

dewar@cs.nyu.edu (Robert Dewar) writes:

>Please substantiate the "heresy" that different languages make a big
>difference in generated code efficiency.

Sure.  There's a language called Prolog, which has been around
for a decade or two now.  Lots of effort has been put into optimizing it.
Hundreds of papers have been written.  Dozens of implementations have
been developed.

I and a couple of others have developed a new language called Mercury
over the last year or two.  Mercury is similar to a subset of
Prolog with additional declarations.

We've done quite a bit of benchmarking, and the Mercury compiler
produces code that is on average about 70% faster than the code
produced by the best optimizing Prolog compiler, Aquarius Prolog, for a
set of small benchmarks.  (For real-world code the difference is almost
certainly _larger_ than 70%, since the techniques used in the Mercury
compiler scale better to large programs than those used in Aquarius Prolog.)

This difference in efficiency is precisely because Mercury was deliberately
designed to make it much easier to generate efficient code.

Note that in it's most optimizing mode, Aquarius Prolog does not
support certain features of Prolog, because they prevent some optimizations.
If you invoke Aquarius Prolog in a mode which supports those features,
the generated code is about a factor of two slower.  So if you compare
Mercury to that, we're about 3.4 times faster.
(The feature in question is the ability to write `read(X), call(X)',
which can call any predicate with any arguments depending on the input.)

For more details, including detailed performance tables, see

	The execution algorithm of Mercury: an efficient purely
	declarative logic programming language.  Zoltan Somogyi, Fergus
	James Henderson and Thomas Charles Conway.

available from http://www.cs.mu.oz.au/~zs/mercury.html.

-- 
Fergus Henderson            | As practiced by computer science, the study of
fjh@cs.mu.oz.au             | programming is an unholy mixture of mathematics,
http://www.cs.mu.oz.au/~fjh | literary criticism, and folklore. - B. A. Sheil