I've put up a half-serious benchmark page with comparisons of a simple
recursive algorithm implemented using 14 different programming languages.
All times were measured on a Pentium machine running Linux (except for
MSWLogo), using free compilers and interpreters. For some languages I
tried more than one implementation, which is why there are more than 14
entries listed.
Here is the list, arranged from fastest to slowest:
Gnu C++ (Template Metaprogram)
Gnu C
P2C Pascal Translator
Algol 60 to C Translator
CMU Common Lisp
Gnu Common Lisp
MIT Scheme
MIT Scheme without Numerics
Scheme 48
P4 Pascal P-code Interpreter
Ghostscript
Emacs Lisp
Gnu Awk
Orthogonal
TeX
Algol 60 Interpreter
INTERCAL
UCB Logo
MSW Logo
Pascal in Logo
Lisp in Awk
The speeds measured covered a full six orders of magnitude, and that's
without trying to count the template metaprogram (which solves the entire
problem at compile time).
http://www.webcom.com/nazgul/change.html
Louis Howell
······@netcom.com
Louis Howell <······@netcom.com>:
> I've put up a half-serious benchmark page with comparisons of a simple
> recursive algorithm implemented using 14 different programming languages.
>
> [...]
>
> http://www.webcom.com/nazgul/change.html
Take note, all: this page is very cuspy.
b
From: Fergus Henderson
Subject: Re: Recursive Benchmark in 14 Languages
Date:
Message-ID: <57oll6$3ti@mulga.cs.mu.OZ.AU>
Louis Howell <······@netcom.com>:
>
> I've put up a half-serious benchmark page with comparisons of a simple
> recursive algorithm implemented using 14 different programming languages.
> [...]
> http://www.webcom.com/nazgul/change.html
Never one to resist a benchmark, I tried this in Mercury.
On my Linux box compiling the Mercury program with `mc -O6'
resulted in code that was only a wee bit (2.7%) slower than
the C code compiled with `gcc -O3'.
However, the C code generated by `gcc -O3 -fomit-frame-pointer'
is 29% faster than that generated by `-O3'.
Anyway, I was happy that the Mercury code was only about 33% slower
than the C, given that the current Mercury compiler backend technology
isn't very well suited to architectures with a small number of registers.
I tried the same test on an Alpha box, and Mercury was in fact 17% faster
than `gcc -O3' with or without `-fomit-frame-pointer'. The DEC C compiler
didn't do any better than gcc.
One thing I did notice was that your C program was buggy (for example,
if you run it without any arguments, it gets a segmentation violation).
The equivalent error is very difficult to make in Mercury -- the
closest Mercury equivalent to the buggy C code would be illegal Mercury
code, and the Mercury compiler would catch the error at compile time.
(I've attached the C and Mercury versions of this benchmark below.)
--
Fergus Henderson <···@cs.mu.oz.au> | "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh> | of excellence is a lethal habit"
PGP: finger ···@128.250.37.3 | -- the last words of T. S. Garp.
-----------------------------------------------------------------------------
:- module change.
:- interface.
:- import_module io.
:- pred main(io__state::di, io__state::uo) is det.
:- implementation.
:- import_module int, string, float.
:- func first_denomination(int) = int.
first_denomination(Kinds_of_coins) =
(if (Kinds_of_coins = 1) then
1
else if (Kinds_of_coins = 2) then
5
else if (Kinds_of_coins = 3) then
10
else if (Kinds_of_coins = 4) then
25
else
50
).
:- func cc(int, int) = int.
cc(Amount, Kinds_of_coins) =
(if (Amount = 0) then
1
else if (Amount < 0 ; Kinds_of_coins = 0) then
0
else
cc(Amount - first_denomination(Kinds_of_coins), Kinds_of_coins) +
cc(Amount, Kinds_of_coins - 1)
).
:- func cc_tail(int, int, int) = int.
cc_tail(Amount, Kinds_of_coins, Count) =
(if (Amount = 0) then
Count + 1
else if (Amount < 0 ; Kinds_of_coins = 0) then
Count
else
cc_tail(Amount - first_denomination(Kinds_of_coins),
Kinds_of_coins,
cc_tail(Amount, Kinds_of_coins - 1, Count))
).
:- func count_change(int) = int.
count_change(Amount) =
/*
cc(Amount, 5).
*/
cc_tail(Amount, 5, 0).
main -->
io__command_line_arguments(Args),
(if { Args = [Num] } then
(if { string__to_int(Num, N), N >= 0 } then
{ get_clock(Time0) },
{ Answer = count_change(N) },
{ get_clock(Time) },
{ get_clocks_per_sec(ClocksPerSec) },
{ string__format("Answer = %d, Time = %f seconds\n",
[i(Answer),f((Time - Time0) / ClocksPerSec)], Message) },
io__write_string(Message)
else
io__write_string("invalid argument\n")
)
else
io__write_string("wrong number of arguments\n")
).
:- pragma c_header_code("
#include <stdio.h>
#include <time.h>
").
:- pred get_clock(float::out) is det.
:- pragma c_code(get_clock(Time::out), "
Time = clock();
").
:- pred get_clocks_per_sec(float::out) is det.
:- pragma c_code(get_clocks_per_sec(ClocksPerSec::out), "
ClocksPerSec = CLOCKS_PER_SEC;
").
-----------------------------------------------------------------------------
#include <stdio.h>
#include <time.h>
int first_denomination(int kinds_of_coins)
{
if (kinds_of_coins == 1) {
return 1;
}
else if (kinds_of_coins == 2) {
return 5;
}
else if (kinds_of_coins == 3) {
return 10;
}
else if (kinds_of_coins == 4) {
return 25;
}
else if (kinds_of_coins == 5) {
return 50;
}
}
int cc(int amount, int kinds_of_coins)
{
if (amount == 0) {
return 1;
}
else if (amount < 0 || kinds_of_coins == 0) {
return 0;
}
else {
return cc(amount - first_denomination(kinds_of_coins),
kinds_of_coins) +
cc(amount, kinds_of_coins - 1);
}
}
int cc_tail(int amount, int kinds_of_coins, int count)
{
if (amount == 0) {
return count + 1;
}
else if (amount < 0 || kinds_of_coins == 0) {
return count;
}
else {
return cc_tail(amount - first_denomination(kinds_of_coins),
kinds_of_coins,
cc_tail(amount, kinds_of_coins - 1, count));
}
}
int count_change(int amount)
{
/*
return cc(amount, 5);
*/
return cc_tail(amount, 5, 0);
}
main(int argc, char *argv[])
{
int answer, n;
clock_t t0, t1;
sscanf(argv[1], "%d", &n);
t0 = clock();
answer = count_change(n);
t1 = clock();
printf("%d %f\n", answer, (float)(t1 - t0) / CLOCKS_PER_SEC);
}
-----------------------------------------------------------------------------