uLisp

Benchmarks

This page gives a collection of simple Lisp programs that have traditionally been used for benchmarking Lisp systems. Most of them are recursive, and some of them have no other obvious practical use beyond acting as a benchmark.

4th July 2024: Have added a sieve benchmark to test the performance of arrays.

Takeuchi function

A classic benchmark for comparing implementations of Lisp is this variant of the Takeuchi function, originally used by Ikuo Takeuchi of Japan, and described in the book Performance and Evaluation of Lisp Systems ^[1]:

(defun tak (x y z)
  (if (not (< y x))
      z
    (tak
     (tak (1- x) y z)
     (tak (1- y) z x)
     (tak (1- z) x y))))

A good set of parameters, giving execution times in the range 1 to 60 secs for typical uLisp platforms, is:

(tak 18 12 6)

On an Arduino Mega 2560 (tak 18 12 6) takes 55.6 seconds to return the answer 7.

You can display the time taken to run the function using:

> (time (tak 18 12 6))
7
Time: 55.6 s

For a comparison of the time to run tak on different platforms see Performance.

Fibonacci sequence

The Fibonacci sequence is:

1, 1, 2, 3, 5, 8, 13, 21 ...

where the first two terms are 1, and each subsequent term is the sum of the two previous terms. The following recursive function finds the nth term, counting from 0:

(defun fib (n)
  (if (< n 3) 1
    (+ (fib (- n 1)) (fib (- n 2)))))

On an Arduino Mega 2560 (fib 23) takes 30.5 seconds to return the answer 28657.

Hofstadter Q sequence

This is one of several recursive sequences described in Douglas Hofstadter's book "Gödel, Escher, Bach: an Eternal Golden Braid". It is defined as follows:

(defun q (n)
  (if (<= n 2) 1
    (+
     (q (- n (q (- n 1))))
     (q (- n (q (- n 2)))))))

It is related to the Fibonacci sequence, except that in this case the two preceding terms specify how far to go back in the sequence to find the two terms to be summed.

On an Arduino Mega 2560 (q 21) takes 58.2 seconds to return the answer 12.

Two-dimensional recursive function Q2

This function Q2 is my two-dimensional extension of the Hofstadter Q sequence ^[2]:

(defun q2 (x y)
  (if (or (< x 1) (< y 1)) 1
    (+ (q2 (- x (q2 (1- x) y)) y)
       (q2 x (- y (q2 x (1- y)))))))

It's a time-consuming function to calculate. For example, it takes about 113 seconds to calculate (q2 7 8) on an Arduino 2560:

> (time (q2 7 8))
31
Time: 113.0 s

Factor

This function takes a simple approach to finding the least prime factor of a number:

(defun factor (n)
  (let ((d 2) (i 1))
    (loop
     (when (> (* d d) n) (return n))
     (when (zerop (mod n d)) (return d))
     (incf d i) (setq i 2))))

If the number is prime, factor will print the number itself.

For example, on a 32-bit platform to find the least prime factor of 2142142141 (it's a prime), and time how long it takes:

> (time (factor 2142142141))
2142142141
Time: 5.8 s

> (time (factor 2146654199))
46327
Time: 5.8 s

Factorize

You can use the above factor function as the basis for a simple recursive routine to factorize a number into a list of its prime factors:

(defun factorize (n)
  (let ((f (factor n)))
    (if (= n f) (list n) (cons f (factorize (/ n f))))))

For example:

> (factorize 731731731)
(3 17 43 333667)

CRC-32

Calculates a CRC-32 Cyclic Redundancy Check. This requires 32-bit integer arithmetic:

(defun crc32 (str)
  (let ((crc #xFFFFFFFF))
    (dotimes (k (length str))
      (let* ((c (char str k))
             (n (char-code c)))
        (dotimes (i 8)
          (setq crc 
                (if (oddp (logxor n crc))
                    (logxor (logand (ash crc -1) #x7FFFFFFF) #xEDB88320)
                  (logand (ash crc -1) #x7FFFFFFF)))
          (setq n (ash n -1)))))
    (logxor crc #xFFFFFFFF)))

For example, on an Adafruit Feather M0:

> (time (crc32 "The quick brown fox jumps over the lazy dog"))
1095738169
Time: 97 ms

Sieve

This uses a technique called the Sieve of Eratosthenes ^[3] to find all the prime numbers up to a certain number, and it returns the largest one found. It uses a bit array to identify which numbers are prime. Initially all the elements are '0', but at each stage all the multiples of the next prime are set to '1'. The resulting bit array contains a '0' for each prime number:

(defun sieve (size)
  (let ((a (make-array size :element-type 'bit))
        max)
    (setf (aref a 0) 1 (aref a 1) 1)
    (dotimes (i size max)
      (when (zerop (aref a i))
        (setq max i)
        (do ((j (* 2 i) (+ j i))) ((>= j size)) (setf (aref a j) 1))))))

For example, on a Raspberry Pi Pico, to find the largest 5-digit prime:

> (time (sieve 100000))
99991
Time: 20.8 s

For a graphical example that uses the Sieve of Eratosthenes see Prime number spiral.

1. ^ Performance and Evaluation of Lisp Systems, Richard P. Gabriel, MIT Press, PDF on rpgpoet.com.
2. ^ An erratic two-dimensional recursive function Q2 on Lispology.
3. ^ Sieve of Eratosthenes on Wikipedia.