From: Jon Freeman
Subject: The speed of various functional languages
Date:
Message-ID: <91544@netnews.upenn.edu>
This is not a question that I would normally ask, but unfortunately I
need to ask it and I need answers as soon as possible...
In the personal experience of people on the net, which widely
available implementation of a functional language is the fastest on
comparable programs? I'm thinking about language-implementation pairs
like MIT Scheme, Lucid Common Lisp, Franz Lisp, etc.
Here's why I'm asking: I have been writing search algorithms for the
CNF-satisfiability problem in Standard ML of New Jersey, version 0.75.
Although I like SML very much, and I think its static type-checking is
fantastic for program development, I'm afraid I have to admit that its
performance on my algorithms, at least, is simply terrible.
First, let me illustrate this claim with a specific example. There's
a local search algorithm for CNF-satisfiability called GSAT. The most
recent paper on GSAT is available via anonymous ftp from
research.att.com in the directory /dist/ai. Like all local search
algorithms, GSAT is very simple: it's essentially two nested FOR
loops. According to the above paper, the authors' implementation of
GSAT (written in C) can solve the 8, 20, and 30-queens problems in
0.1, 0.9, and 2.5 seconds, respectively. My SML implementation of
GSAT, on the other hand, requires an average of 3, 70, and 500 seconds
of CPU time, respectively. GSAT's simplicity makes these results
particularly troubling. My _backtracking_ search algorithms are also
much slower than their counterparts in the literature.
Second, let me emphasize that the speed of the language I use is not
_directly_ important to what I'm trying to accomplish. If it were, I
could get a Ph.D. by simply writing my programs in assembly language.
I need a sufficiently fast language only because I have to test my
algorithms on fairly large problems, and run lots and lots of trials,
in order to convice people that the complexity of my search algorithms
is what I say it is.
Third, I would prefer to continue using a functional language because
the thought of rewriting these tedious algorithms in C or C++ sends
chills up my spine. I would prefer to work in a Lisp-y language; I
used to program extensively in Scheme.
Thank you very much for your help in this matter. Again, I'm not
trying to criticize SML unnecessarily, but at this point I'm simply
dead in the water until I switch to a faster language.
Sincerely,
Jon
(·······@gradient.cis.upenn.edu)
P.S. Please email all replies; I don't want to be responsible for
starting any flame wars.