[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Lisp is faster than Prolog?
- To: prolog%ernie@Berkeley, franz-friends%ucbkim@Berkeley
- Subject: Lisp is faster than Prolog?
- From: Rick McGeer (on an aaa-60-s) <mcgeer%ucbkim@Berkeley>
- Date: Wed, 27 Mar 85 00:06:57 GMT
- Original-date: Tue, 26 Mar 85 16:06:57 pst
A number of articles in recent IEEE Spectra have discussed Silicon
Compilation in Prolog, and concluded with a statement to the effect: for
performance reasons, we will go to Lisp for a production version.
Is Lisp really faster than Prolog? I used to think so. Some time
ago, I wrote a Prolog interpreter in Lisp: after several versions, I gave
up, because I couldn't make my Prolog fast. Its best speed was 100 LIPS
through the append loop on a 780, or about 7% of the speed of C-Prolog (1500
LIPS, according to the literature.
Then it occured to me that I could not expect my Prolog to run
faster than an equivalent function coded in Lisp. I coded the function, and
the result was the following:
(def my-append
(lambda (x y)
(cond (x (cons (car x) (my-append (cdr x) y)))
(t y))))
it can be seen that the time of the computation is invariant with respect to
the second argument. Hence, for all the tests to be mentioned, the second
argument is '(1 2 3 4 5).
I ran the program on the lists consisting of the first 100, 250, and
300 integers. The results were the following:
list length ticks (60/sec) LIPS equivalent
100 14 429
250 29 517
300 34 529
Or about one-third the published speed of of the same function in CProlog on
a 780. I then wondered how the native Franz append would do. This function
is compiled, and is optimized for tail recursion, so the experiment is not
really fair to CProlog. In any case:
list length ticks LIPS equivalent
100 3 2000
250 8 1875
300 10 1800
I don't know what this proves, but I know what it doesn't prove. The Lisp
used, by the way, was Franz version 38.96 on a Vax 11/780 at the University
of California at Berkeley. Despite numerous queries to Edinburgh, we still
don't have a version of C-Prolog for comparative measurement here, so I
can't personally vouch for the 1500 LIPS claim.
Rick.