One of the reasons LISP did not become more popular for scientific computing was the perception that it was slower than FORTRAN. In this post I will compare the performance of the LISP and FORTRAN implementations on MTS using a simple problem.
The problem and some caveats
We'll use the finding emirp primes problem introduced in the FORTRAN posts on this blog as the subject. To make it simpler we will just look at the third test, finding the 10,000th emirp.
So some caveats before we start. Benchmarks are notoriously difficult to get right and this is only a single sample. I'm not an expert at optimising LISP or FORTRAN so there may well be better ways of implementing this. Finally, the UTILISP implementation is from the 1980s, MTS LISP is from the 1970s and the FORTRAN G and H compilers date from at least the 1960s so this is not a historically accurate recreation.
Having said that, it'll be interesting to see how they stack up, so let's start.
We'll use the source code for the FORTRAN emirp implementation discussed before, taking out the first and second test.
We compile without optimisations first (ie using FORTRAN G) and then try again with FORTRAN H. The results look like this:
# run *ftn scards=emirp3.f # Execution begins 11:39:08 No errors in PRIME No errors in REVRSE No errors in EMIRP No errors in SHOW No errors in TEST3 No errors in MAIN # Execution terminated 11:39:08 T=0.045 # run -load # Execution begins 11:39:10 948349 # Execution terminated 11:39:19 T=9.05 # # $run *ftn scards=emirp3.f par=opt=h # Execution begins 11:39:49 **** No errors for PRIME **** SAT MAY 09/15 11:39:49 **** No errors for REVRSE **** SAT MAY 09/15 11:39:49 **** No errors for EMIRP **** SAT MAY 09/15 11:39:49 **** No errors for SHOW **** SAT MAY 09/15 11:39:49 **** No errors for TEST3 **** SAT MAY 09/15 11:39:49 **** No errors for MAIN **** SAT MAY 09/15 11:39:49 # Execution terminated 11:39:49 T=0.074 # run -load # Execution begins 11:39:54 948349 # Execution terminated 11:39:59 T=4.281
So 9.05s for FORTRAN G and 4.28s for FORTRAN H.
Let's try the original MTS LISP first. It's fairly easy to translate using the (GO) form to do looping.
;; Checks if n is prime using a simple division test (DEFUN PRIME-P (N) (COND ;; Deal with numbers <= 3 ((LESS N 2) NIL) ((LESS N 4) T) ;; Check if divisible by 2 or 3 ((EQUAL (REMAIN N 2) 0) NIL) ((EQUAL (REMAIN N 3) 0) NIL) ;; See if divisible by 5, 7, ..., up to approx sqrt(n) (T (PROG (I RESULT) (SETQ I 5) A (SETQ RESULT (COND ((GREATER (TIMES I I) N) 'PRIME) ((EQUAL (REMAIN N I) 0) 'NOT-PRIME) (T (SETQ I (ADD I 2)) NIL))) (COND ((NOT RESULT) (GO A))) (EQ RESULT 'PRIME))))) ;; Return a number that has the reversed digits in n (DEFUN REVERSE-DIGITS (N) (PROG (REVERSED) (SETQ REVERSED 0) ;; Take last digit from n and append to reversed (PROG () B (SETQ REVERSED (TIMES REVERSED 10)) (SETQ REVERSED (ADD REVERSED (REMAIN N 10))) (SETQ N (IDIVIDE N 10)) (COND ((GREATER N 0) (GO B)))) ;; CAR needed to evaluate REVERSED otherwise PROG will return ;; the symbol REVERSED (CAR REVERSED))) ;; Check if a number is an emirp, ie both it and its reversed digits ;; are prime. (DEFUN EMIRP-P (N) (PROG (REVERSED) (SETQ REVERSED (REVERSE-DIGITS N)) (AND (NOT (EQUAL N REVERSED)) (PRIME-P N) (PRIME-P REVERSED)))) (DEFUN EMIRP-10K () (PROG (N COUNT LAST) (SETQ N 0) (SETQ COUNT 0) (SETQ LAST 0) C (COND ((EMIRP-P N) (SETQ COUNT (ADD COUNT 1)) (SETQ LAST N))) (SETQ N (ADD N 1)) (COND ((LESS COUNT 10000) (GO C))) (CAR LAST))) (EMIRP-10K) (STOP)
We'll first execute it through the interpreter:
# $run *lisp scards=emirp.l # Execution begins 12:41:27 WELCOME TO LISP/MTS > PRIME-P > REVERSE-DIGITS > EMIRP-P > EMIRP-10K * GC: COLLECTED 23370 CELLS ... * GC: COLLECTED 23370 CELLS > 948349 # Execution terminated 12:47:15 T=347.517
Next we'll compile the functions. Add
(COMPILE PRIME-P) and so on for all the functions and rerun
# $run *lisp scards=emirp.l WELCOME TO LISP/MTS > PRIME-P > REVERSE-DIGITS > EMIRP-P > EMIRP-10K * COMPILE 04-17-79 RESTORED > (PRIME-P) > (REVERSE-DIGITS) > (EMIRP-P) > (EMIRP-10K) * GC: COLLECTED 23370 CELLS ... * GC: COLLECTED 23370 CELLS > 948349 # Execution terminated 12:56:39 T=72.347
OK, so we are down from 348s to 72s (the compilation itself takes less than 0.5s). Not bad, but still 17 times slower than FORTRAN H.
Let's see how UTILISP compares. We do need to change the program in quite a few places to match the different built in functions (eg
+ instead of
ADD) but at least we can now use the
do macro to create more expressive loops.
;; Checks if n is prime using a simple division test (defun prime-p (n) (cond ;; Deal with numbers <= 3 ((<= n 1) nil) ((<= n 3) t) ;; Check if divisible by 2 or 3 ((= (remainder n 2) 0) nil) ((= (remainder n 3) 0) nil) ;; See if divisible by 5, 7, ..., up to approx sqrt(n) (t (do ((i 5 (+ i 2)) (result nil)) (result (eq result 'prime)) (setq result (cond ((> (* i i) n) 'prime) ((= (remainder n i) 0) 'not-prime) (t nil))))))) ;; Return a number that has the reversed digits in n (defun reverse-digits (n) (do ((reversed 0) (m n (// m 10))) ((< m 1) reversed) ;; Take last digit from n and append to reversed (setq reversed (* reversed 10)) (setq reversed (+ reversed (remainder m 10))))) ;; Check if a number is an emirp, ie both it and its reversed digits ;; are prime. (defun emirp-p (n) (let ((reversed (reverse-digits n))) (and (neq n reversed) (prime-p n) (prime-p reversed)))) ;; Return the 10,000th emirp (defun emirp-10k () (do ((n 0 (+ n 1)) (count 0) (last 0)) ((eq count 10000) last) (cond ((emirp-p n) (setq count (+ count 1)) (setq last n))))) ;; Run the test (print (emirp-10k)) (quit)
And let's run it through the interpreter.
# $run *utilisp 0=emirp.ul # Execution begins 18:18:02 948349 # Execution terminated 18:21:30 T=208.35
So that's 40% quicker than the MTS LISP interpreted version. Let's try compiling the forms, which we can just do by putting
(compile prime-p reverse-digits emirp-p emirp-10k)
after the definitions and then adding the
fix parameter to the command line to reserve memory for the compiler (again compilation takes less than 0.5s of the total):
$ run *utilisp 0=emirp.ul par=fix=100 # Execution begins 18:32:27 ; Loading Utilisp Compiler System Version(82-11-09) 948349 # Execution terminated 18:32:54 T=27.788
Much better - 3 times faster than the MTS LISP compiled version but 7 times slower still than FORTRAN H.
Summary of results and final thoughts
|MTS LISP interpreted||347.52|
|MTS LISP compiled||72.35|
Compiled UTILISP puts up a good showing and it's definitely usable for light numerical tasks but in the end FORTRAN wins on pure performance. The UTILISP implementation is much faster than MTS LISP for both interpreted and compiled code, which you'd expect given the amount of knowledge creating fast LISP implementations that was built up between the release of the two programs.
Another factor evident from this test was the lack of LISP standardisation (pre-Common Lisp) makes porting programs between implementations a chore, whereas FORTRAN was relatively standardised.
Any suggestions for optimising the code? Please let me know in the comments.
In the next post, in a couple of weeks, we'll look at PL/1.
Full source code for the programs shown here is on github.