Benchmarking uLisp

#1

A classic benchmark for comparing implementations of Lisp is this variant of the Takeuchi function, originally used by Ikuo Takeuchi of Japan:

(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))))

With uLisp running on an Arduino Uno (16 MHz clock) with 2 Kbytes of RAM, calculating:

(tak 18 12 6)

takes 56 seconds to give the result, 7. How does your favourite Lisp compare?

#2

My somewhat minimal ulisp port on amd64:

[martin@localhost c-mera-ulisp]$ cat /proc/cpuinfo 
...
model name      : AMD FX(tm)-8350 Eight-Core Processor
stepping        : 0
microcode       : 0x600084f
cpu MHz         : 4013.460
cache size      : 2048 KB
...
[martin@localhost c-mera-ulisp]$ time ./b < tak.lisp
...
freespace: 242
> 

ÿ
real    0m0.134s
user    0m0.133s
sys     0m0.000s
#3

Thanks for posting that. Just to clarify; is that running tak on a port of my uLisp to the AMD FX-8350. If so, how much did you have to change to get it to run?

#4

Yes, it is based on your code. I touched pretty much everything.

#5

On a TMS320F28335 with 150MHz (tak 18 12 6) takes 3.91s. I send the instructions by SPI and receive the response on UART.

screen_tak_on_f28335_150MHz.png2560x1024 158 KB

#6

Almost instant on all the lisps I try on my laptop, but the difference in hardware speed is ridiculous. I’d be interested in seeing a benchmark of AmForth (amforth.sf.net) on Arduino (similar hardware to ulisp’s), running the same test. Here’s a Forth version of the same test (tested only in gforth, since again I don’t have an arduino):

: 3dup ( a b c -- a b c a b c ) >r 2dup r@ -rot r> ;
: tak ( x y z -- n )
    -rot 2dup <=
    if
        2drop ( z )
    else ( z x y )
        3dup rot 1- -rot recurse >r     \ tak (1- z) x y
        3dup 1- -rot recurse >r         \ tak (1- y) z x
        -rot 1- -rot recurse            \ tak (1- x) y z
        r> r> recurse
    then ;

\ correct output of the below is 7
: test 18 12 6 tak . ;

If someone uses amforth and wants to run it (make any changes necessary) that would be cool.

#7

I emailed Matthias Trute (author of amForth) about this benchmark and he kindly sent back timings he did on similar code a while back:

amforth 6.3 ATmega32 @ 16 MHz
time:  0.79562497139  seconds

amforth 6.3 ATmega1284P @ 8MHZ
time:  1.5945110321  seconds

amforth 6.3 MSP430G2553 @ 8MHz
time:  0.446244955063  seconds

His TAK implementation was similar to mine but not identical:

 : 3dup 2 pick 2 pick 2 pick ; 
 : -rot rot rot ;
 : tak ( x y z -- t )
   over 3 pick < negate if nip nip exit then
   3dup rot  1- -rot recurse >r
   3dup swap 1- -rot swap recurse >r
             1- -rot recurse
   r> swap r> -rot recurse ;

 : takbench ( -- )
   0 &10000 0 do drop &18 &12 6 tak loop ;

It makes me think uLisp would benefit from having a compiler of some sort. Do you know about Microscheme (microscheme.org)?

#8

If his version of Tak was slightly different the timings may not be strictly comparable. If you can give me the translation of his version into Lisp I’ll try it on uLisp.

#9

The Lisp version, Matthias’s Forth code, and my Forth code all compute exactly the same thing by the same algorithm. I just meant Matthias’s Forth implementation differs from mine slightly. Forth is very low level, like halfway between C and assembler, so it’s no big deal that a few details differ between Forth versions. For example, we each have a word 3DUP which copies the first 3 cells on the stack. Mine does it by using stack juggling commands and his uses PICK, which reaches into the stack interior. Both run in constant time but one might be a few cycles faster or slower than the other.