fast-eval for Allegro CL 5.1
Steven Furlong
5.1?
My LISP skills aren't high enough to let me even diagnose the run-time
problem, but I can email or post the error messages if anyone would like
them.
FWIW, run-genetic-programming-system works fine so long as I stick with
eval. Slow, though...
Thanks,
Steven Furlong
Stephen Waits
Steven Furlong wrote:
>
> FWIW, run-genetic-programming-system works fine so long as I stick with
> eval. Slow, though...
Consider reimplementing in C if possible, as even Koza has done.
--Steve
Markus Mottl
Or even better, use a highly efficient, safe and powerful language like OCaml:
Regards,
Markus Mottl
--
Markus Mottl, mo...@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl
Stephen Waits
Markus Mottl wrote:
>
> > Consider reimplementing in C if possible, as even Koza has done.
>
> Or even better, use a highly efficient, safe and powerful language like OCaml:
>
> http://caml.inria.fr
>
If you are into functional programming, sure, or even Haskell
(haskell.org). However, I'm (personally - no religion wars please)
placing my bets on C for performance.
--Steve
Markus Mottl
> If you are into functional programming, sure, or even Haskell
> (haskell.org). However, I'm (personally - no religion wars please)
> placing my bets on C for performance.
I hope you do not mind my somewhat long elaboration on this topic,
but I think that it is important to show hard facts than to talk on
"language religions"...
There are easy answers to this: try to beat (e.g.) this OCaml program
(uses recursion only! - was compiled with flag -unsafe (turns off bounds
checking on arrays)) with C:
file: sieve.ml (implements the Sieve of Eratosthenes for computing primes)
---------------------------------------------------------------------------
let count = 200000
let primes =
let primes = Array.create (max count 3) 0 in
primes.(0) <- 2; primes.(1) <- 3; primes.(2) <- 5; primes
let rec is_prime i pr bd =
if primes.(i) > bd then true
else if pr mod primes.(i) = 0 then false else is_prime (succ i) pr bd
let rec prime_n psize nr tog =
if psize < count then
let psize' =
if is_prime 2 nr (truncate (sqrt (float nr))) then begin
primes.(psize) <- nr; succ psize end
else psize in
prime_n psize' (nr + tog) (6 - tog)
let _ = prime_n 3 7 4; Printf.printf "prime %d: %d\n" count primes.(pred count)
---------------------------------------------------------------------------
Here a highly optimized C-program I tried with gcc (flags: -O2
-fomit-frame-pointer) on both an Alpha and an Intel platform (watch the
nifty gotos - can you find a faster version than I?):
---------------------------------------------------------------------------
#include <stdio.h>
#include <math.h>
#define how_many 200000
int main()
{
unsigned int nr = 5, toggle = 2, max, primes_size = 3, i;
unsigned int primes[how_many];
primes[0] = 2; primes[1] = 3; primes[2] = 5;
loop:
nr += toggle; toggle = 6 - toggle;
max = sqrt(nr);
for (i = 2; primes[i] <= max; ++i)
if (!(nr % primes[i])) goto loop;
primes[primes_size++] = nr;
if (primes_size < how_many) goto loop;
printf("%i\n", primes[how_many - 1]);
return 0;
}
---------------------------------------------------------------------------
Result on the platforms I tested: OCaml handily wins by a margin of 7-8%!
Not convinced by this special case? I have other tests to show...
To be honest: given a specific algorithm and hand-tailoring it an
eternity you will in most cases be able to beat OCaml and other
functional languages using C. However, to come even *close* to the
average OCaml-program requires an effort you definitely do not want
to pay. Some aspects of C++, for example, (e.g. STL-I/O-libraries)
are indeed slow compared to OCaml.
I have programmed C++ for quite a while and I know that I can write
faster and more correct programs in less time using OCaml. And even
today I have still two times more experience (in terms of years) in C/C++
than in OCaml.
Considering the time it takes me to write a correct program *and*
(there is a slight contradiction here in C/C++) making it fairly fast,
I would be rather irrational to continue fighting these beasts.
There are some problems I could not even imagine to implement in C/C++
(e.g. persistent datastructures) without getting mad before - whereas
the same only require a few lines of OCaml-code.
If you still think that OCaml or other functional languages are "slow"
(whatever this means for a language - it's the compiler which counts),
then take a look at the results of the last ICFP-contest, where not a
single of the imperative entries (mostly C - overall) made it into the
finals (i.e. top 6 candidates):
http://www.eecs.harvard.edu/~nr/icfp/results.html
Reality can be tough! ;-)
I hope that my information helps you to get the right impression of the
state-of-the-art in FP. Don't forget: we are not in the 70s anymore!
FP-compilers have had time to advance...
Best regards,
Sean Luke
> Has anyone rewritten Koza's fast-eval to work with Allegro Common Lisp
> 5.1?
Ignoring everyone else's postings about their Favorite Language, no, I was
not aware that fast-eval didn't work with ACL 5.1, and I am not
aware of anyone who is maintaining the Koza Little-Lisp code at this
point.
I know you're going to hate me saying this, but I recommend going with
lil-gp instead. It is well-supported, popular, and written in C. It's not
the fastest GP system out there (it's far faster than Little-Lisp), but it
does have a host of features, and extremely good documentation. A number
of people have modified it considerably, including myself
(http://www.cs.umd.edu/users/seanl/gp/patched-gp/). You can download a
current version at
http://garage.cps.msu.edu/software/lil-gp/lilgp-index.html
Sean
Russell Wallace
> To be honest: given a specific algorithm and hand-tailoring it an
> eternity you will in most cases be able to beat OCaml and other
> functional languages using C. However, to come even *close* to the
> average OCaml-program requires an effort you definitely do not want
> to pay.
Depends on what you're comfortable with. Personally, I'd rather work
with your C version of the sieve program - it's a few percent slower,
but to me, it seems a bit simpler. De gustibus non disputandum, and all
that.
--
"To summarize the summary of the summary: people are a problem."
Russell Wallace
mailto:mano...@iol.ie
Markus Mottl
> Depends on what you're comfortable with. Personally, I'd rather work
> with your C version of the sieve program - it's a few percent slower,
> but to me, it seems a bit simpler. De gustibus non disputandum, and all
> that.
There are always examples where some program/algorithm has a property in
language A so that A is a better choice for implementing it than, say, a
language B. In the upper case, performance is indeed reversed and (at least in
your eyes) simplicity reduced. However, nobody would seriously argue that C is
a more expressive or readable language than modern functional languages. You
should not forget: habits preshape minds. This alone lets you read things in
another way.
The difference is the following: in C you can get very fast code. Can. But in
general you get very complex programs which are hard to implement and
maintain. In functional languages you normally get code that is much easier to
reason about and (as shown) performance can be surprisingly much higher than
most people think.
Implementing a system which has to be fast *and* which is large in C is nearly
a contradiction. There is heavy empirical evidence for this which should make
people think:
Consider the Horus project (written in C - ca. half a million LOCs), conducted
at Cornell University. Then consider its successor project "Ensemble" in which
they switched to OCaml and rewrote the whole system in about fifty thousand
LOCs. Result (read their page below): a *speedup* by an order of magnitude! So
the system was not only considerably less complex but also much faster...
http://www.cs.cornell.edu/Info/Projects/Ensemble/index.html
Well, you could argue now that they are lousy C-programmers but excellent
OCaml-hackers. However, implementing a 500 kLOC program in C is not peanuts...
This is common experience with most people who switch to FP (I also used C/C++
for about 5-6 years before I turned to FP). Because it is so much easier to
implement sophisticated and difficult algorithms (correctly!), performance is
often improved by switching to FP (or modern logic programming languages -
generally: high-level languages).
There are cases in which people really need to squeeze out every drop of
performance of their programs - well, then write this part in C or even
assembler and import the functions via a foreign language interface. This is
very easy (there are code generators for this) and common practice. In OCaml,
for example, the bignum-library for handling arbitrary precision arithmetics
is about 1/4 Assembler, 1/4 C and 1/2 OCaml and it is probably one of the
fastest freely available library packages for this purpose.
So before tormenting my too small brain with too complex a language (C), I use
FP-languages and solve my problems faster and more correctly. I honestly never
felt the need for implementing parts of my code in C, Fortran or else due to
speed considerations (though, this could be necessary in a *few* other
projects - but how many people really do numerical computations that run
months on supercomputers?).
Regards,
lste...@my-deja.com
Markus Mottl <mo...@miss.wu-wien.ac.at> wrote:
> If you still think that OCaml or other functional languages are "slow"
> (whatever this means for a language - it's the compiler which counts),
> then take a look at the results of the last ICFP-contest, where not a
> single of the imperative entries (mostly C - overall) made it into the
> finals (i.e. top 6 candidates):
Isn't this most likely due to the fact that C programmers on the
average are not involved with optimizations of FSA's while that seems
to be the area of expertise of the best functional programmers around?
--
WildHeart'2k
Homepage: http://come.to/wildheart/
Sent via Deja.com http://www.deja.com/
Before you buy.
Markus Mottl
> Isn't this most likely due to the fact that C programmers on the
> average are not involved with optimizations of FSA's while that seems
> to be the area of expertise of the best functional programmers around?
Maybe - maybe not. I'd say this would be speculation. I do not see any
apparent reason why the people who competed with C/C++-entries (or generally:
imperative languages) should have less background in this field than
FP-people, even more so since they all attended this conference.
We only know details about the winners and they are provably all excellent
programmers both in the FP- and in the imperative paradigm (C). At least their
choice of language seems to indicate that they were more convinced of winning
with it (they could have chosen C as e.g. Lennart Augusstson, this year's
Jury-prize winner (he used Haskell), did the year before).