[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Lisp is faster than Prolog?

	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.