Topic: LISP: 10 Basic Benchmarks

[enderprime]

Happy Sunday Swampers =)

This little project was born out of my need to verify comments like "its faster if you do it this way".
For someone new to LISP like myself, it helps to have some numbers so I know exactly how much weight every
algorithm is contributing to the overall speed in a given project. So I have compiled here a collection of
(10) basic unit tests that compare similar functions and report their speeds relative to one another.

First, let me describe the unit test itself. Using the (apply 'fx 'list) function at its core, a list of functions
is passed to the unit test for processing, along with a max variance constant (bear with me). For each function
in the input list, (1) second is designated for a function to repeat itself and record of the number of iterations
it achieves along the way. Within this time limit, each function is actually tested a number of times (for these
tests, 8 times to be exact) and the iteration count from each run is compiled in a list. From this list, the ratio
between the highest and lowest values is recorded as test run "variance". If the test run variance is above the max
variance constant supplied to the unit test, the function is retested. Once a function has passed the variance
requirement, the test results for that function are considered reliable. The highest and lowest values are then
dropped from the list, and the remaining values are used to calculate an iteration average for the function,
expressed in "kips", which is my notation for kilo-iterations per second. In case it is not obvious, this number is
equivalent to iterations per millisecond. Once all function tests are complete, the results are sorted by kips
in descending order and echoed to the command line. The slowest function in a unit test (the lowest kips rating) is
used as a baseline and assigned a value of 1.0. All other functions are assigned a speed relative to this baseline.

Any questions about this method let me know. I'll be posting the actual code for the unit test after some formatting.

One more thing, dont let small differences fool you. A 5% difference can be wildly compounded in a complex routine.
For example, upon finishing these basic benchmarks, I rewrote a major algorithm I was working on before getting
sidetracked by this quest, and I was able to take it from 0.55 kips to 4.2 kips.. same functionality; faster code.

[EDIT: AutoCAD 2012 results follow]

[LINK to source code: Another benchmark function]


Test 1: Cond vs If-then-else

Functions:

Code - Auto/Visual Lisp: [Select]

1. (defun tCond () (cond (nil T)   (nil T)   (T T) )))
2. (defun tIfIf ()    (if nil T (if nil T (if T T)))))

Results:

Code: [Select]

   Unit test   2.00 s    kips   rel   var
 ------------------------------------------
   TCOND                  121  1.00  1.02
   TIFIF                  121  1.00  1.05
 ------------------------------------------
   Completed   241,702 =  121

Test 2: = vs Equal, Int / Real / Str

Functions:

Code - Auto/Visual Lisp: [Select]

1. (defun tCmpreInt () (=      0   0 )))
2. (defun tCmpreRel () (=     0.0 0.0)))
3. (defun tCmpreStr () (=     "A" "A")))
4. (defun tEqualInt () (equal  0   0 )))
5. (defun tEqualRel () (equal 0.0 0.0)))
6. (defun tEqualStr () (equal "A" "A")))

Results:

Code: [Select]

   Unit test   6.00 s    kips   rel   var
 ------------------------------------------
   TCMPREREL              116  1.04  1.05
   TEQUALINT              115  1.04  1.04
   TCMPREINT              114  1.03  1.05
   TEQUALREL              113  1.01  1.05
   TEQUALSTR              112  1.01  1.05
   TCMPRESTR              111  1.00  1.05
 ------------------------------------------
   Completed   680,148 =  113

Test 3: < vs <=

Functions:

Code - Auto/Visual Lisp: [Select]

1. (defun tLessOrEq (/ i) (setq i 1) (while (<= i 8) (setq i (1+ i)))))
2. (defun tLessThan (/ i) (setq i 0) (while (<  i 8) (setq i (1+ i)))))

Results:

Code: [Select]

   Unit test   2.00 s    kips   rel   var
 ------------------------------------------
   TLESSTHAN               66  1.00  1.03
   TLESSOREQ               66  1.00  1.01
 ------------------------------------------
   Completed   131,565 =   66

Test 4: Append vs Cons

Functions:

Code - Auto/Visual Lisp: [Select]

1. (defun tApnd (/ l n) (foreach n (list 0 1 2) (append l (list n)))   ))
2. (defun tConr (/ l n) (foreach n (list 0 1 2) (cons n l)) (reverse l)))
3. (defun tCons (/ l n) (foreach n (list 0 1 2) (cons n l))            ))

Results:

Code: [Select]

   Unit test   3.00 s    kips   rel   var
 ------------------------------------------
   TCONS                   83  1.28  1.02
   TCONR                   83  1.27  1.03
   TAPND                   65  1.00  1.03
 ------------------------------------------
   Completed   231,098 =   77

Test 5: Repeat vs While

Functions:

Code - Auto/Visual Lisp: [Select]

1. (defun tIpeat (/ i) (setq i 0) (repeat 8      (setq i (1+ i)))))
2. (defun tRpeat (/ i) (setq i 0) (repeat 8             T       )))
3. (defun tWhile (/ i) (setq i 0) (while (< i 8) (setq i (1+ i)))))

Results:

Code: [Select]

   Unit test   3.00 s    kips   rel   var
 ------------------------------------------
   TRPEAT                  70  1.13  1.05
   TWHILE                  67  1.07  1.01
   TIPEAT                  62  1.00  1.02
 ------------------------------------------
   Completed   198,586 =   66

Test 6: Member vs Vl-position, First / Middle / Last

Functions:

Code - Auto/Visual Lisp: [Select]

1. (if (null tMem0) (defun tMember () (member      0 (list 0 1 2 3 4 5 6 7 8))))
2. (if (null tMem1) (defun tMember () (member      4 (list 0 1 2 3 4 5 6 7 8))))
3. (if (null tMem2) (defun tMember () (member      8 (list 0 1 2 3 4 5 6 7 8))))
4. (if (null tVlp0) (defun tPstion () (vl-position 0 (list 0 1 2 3 4 5 6 7 8))))
5. (if (null tVlp1) (defun tPstion () (vl-position 4 (list 0 1 2 3 4 5 6 7 8))))
6. (if (null tVlp2) (defun tPstion () (vl-position 8 (list 0 1 2 3 4 5 6 7 8))))

Results:

Code: [Select]

   Unit test   6.00 s    kips   rel   var
 ------------------------------------------
   TVLP0                   81  1.10  1.01
   TVLP1                   80  1.09  1.01
   TMEM0                   79  1.08  1.02
   TVLP2                   78  1.07  1.02
   TMEM1                   75  1.03  1.02
   TMEM2                   73  1.00  1.02
 ------------------------------------------
   Completed   466,067 =   78

Test 7: Short vs Long function names, Alpha / Numeric

Functions:

Code - Auto/Visual Lisp: [Select]

1. (defun t0123       () T))
2. (defun tABCD       () T))
3. (defun t_B_D       () T))
4. (defun t0123456789 () T))
5. (defun tABCDEFGHIJ () T))
6. (defun t-B-D-F-H-J () T))

Results:

Code: [Select]

   Unit test   6.00 s    kips   rel   var
 ------------------------------------------
   T_B_D                   96  1.03  1.05
   T0123                   95  1.02  1.01
   TABCD                   95  1.02  1.04
   T0123456789             94  1.01  1.01
   TABCDEFGHIJ             94  1.01  1.01
   T-B-D-F-H-J             93  1.00  1.04
 ------------------------------------------
   Completed   567,202 =   95

Test 8: CAR / CADR vs Nth

Functions:

Code - Auto/Visual Lisp: [Select]

1. (defun tCAR0 () (car    (list 0 1 2 3 4 5 6 7 8))))
2. (defun tCAR1 () (cadr   (list 0 1 2 3 4 5 6 7 8))))
3. (defun tCAR2 () (caddr  (list 0 1 2 3 4 5 6 7 8))))
4. (defun tCAR3 () (cadddr (list 0 1 2 3 4 5 6 7 8))))
5. (defun tNth0 () (nth 0  (list 0 1 2 3 4 5 6 7 8))))
6. (defun tNth1 () (nth 1  (list 0 1 2 3 4 5 6 7 8))))
7. (defun tNth2 () (nth 2  (list 0 1 2 3 4 5 6 7 8))))
8. (defun tNth3 () (nth 3  (list 0 1 2 3 4 5 6 7 8))))

Results:

Code: [Select]

   Unit test   8.00 s    kips   rel   var
 ------------------------------------------
   TCAR0                   82  1.05  1.03
   TCAR1                   81  1.04  1.01
   TCAR2                   81  1.04  1.01
   TCAR3                   80  1.04  1.01
   TNTH0                   79  1.01  1.02
   TNTH1                   78  1.01  1.02
   TNTH2                   78  1.00  1.02
   TNTH3                   78  1.00  1.02
 ------------------------------------------
   Completed   636,115 =   80

Test 9: (+ i 1) vs (1+ i)

Functions:

Code - Auto/Visual Lisp: [Select]

1. (defun tPlus1 (/ i) (setq i 0) (setq i (+ i 1))))
2. (defun t1Plus (/ i) (setq i 0) (setq i (1+ i ))))

Results:

Code: [Select]

   Unit test   2.00 s    kips   rel   var
 ------------------------------------------
   TPLUS1                  93  1.00  1.01
   T1PLUS                  93  1.00  1.01
 ------------------------------------------
   Completed   185,470 =   93

Test 10: Predicates vs Type Checking

Functions:

Code - Auto/Visual Lisp: [Select]

1. (defun tEqZeroI () (zerop      0         )))
2. (defun tEqZeroR () (zerop     0.0        )))
3. (defun tEqZeroS () (=        "" ""       )))
4. (defun tHasAVal () (boundp     T         )))
5. (defun tLstPred () (listp   '(nil)       )))
6. (defun tNoCheck ()             T          ))
7. (defun tNumberI () (numberp    0         )))
8. (defun tNumberR () (numberp   0.0        )))
9. (defun tNullVal () (null      nil        )))
10. (defun tSymPred () (vl-symbolp T         )))
11. (defun tTypeInt () (= (type    0  ) 'INT )))
12. (defun tTypeLst () (= (type '(nil)) 'LIST)))
13. (defun tTypeRel () (= (type   0.0 ) 'REAL)))
14. (defun tTypeStr () (= (type   ""  ) 'STR )))
15. (defun tTypeSym () (= (type   'T  ) 'SYM )))

Results:

Code: [Select]

   Unit test  15.00 s    kips   rel   var
 ------------------------------------------
   TNOCHECK               121  1.20  1.06
   TNULLVAL               119  1.18  1.09
   TEQZEROR               119  1.18  1.05
   TSYMPRED               119  1.17  1.07
   TNUMBERI               119  1.17  1.06
   TEQZEROI               119  1.17  1.09
   TLSTPRED               118  1.17  1.05
   TNUMBERR               117  1.15  1.10
   THASAVAL               116  1.15  1.06
   TTYPELST               115  1.14  1.05
   TEQZEROS               114  1.13  1.08
   TTYPESTR               105  1.04  1.07
   TTYPESYM               104  1.03  1.06
   TTYPEREL               103  1.02  1.10
   TTYPEINT               101  1.00  1.05
 ------------------------------------------
   Completed 1,703,654 =  114


[enderprime]

AutoCAD 2005 results:

Code: [Select]

   Unit test   2.00 s    kips   rel   var
 ------------------------------------------
   TIFIF                  115  1.01  1.05
   TCOND                  113  1.00  1.04
 ------------------------------------------
   Completed   227,188 =  114

   Unit test   6.00 s    kips   rel   var
 ------------------------------------------
   TEQUALINT              113  1.03  1.04
   TCMPRESTR              113  1.03  1.04
   TCMPREINT              113  1.03  1.05
   TCMPREREL              111  1.01  1.03
   TEQUALSTR              111  1.00  1.04
   TEQUALREL              110  1.00  1.05
 ------------------------------------------
   Completed   669,892 =  112

   Unit test   2.00 s    kips   rel   var
 ------------------------------------------
   TLESSOREQ               79  1.01  1.02
   TLESSTHAN               79  1.00  1.04
 ------------------------------------------
   Completed   158,388 =   79

   Unit test   3.00 s    kips   rel   var
 ------------------------------------------
   TCONS                   83  1.28  1.04
   TCONR                   83  1.27  1.04
   TAPND                   65  1.00  1.05
 ------------------------------------------
   Completed   231,006 =   77

   Unit test   3.00 s    kips   rel   var
 ------------------------------------------
   TRPEAT                  85  1.16  1.05
   TWHILE                  79  1.09  1.03
   TIPEAT                  73  1.00  1.05
 ------------------------------------------
   Completed   237,068 =   79

   Unit test   6.00 s    kips   rel   var
 ------------------------------------------
   TVLP0                   98  1.13  1.02
   TVLP1                   97  1.13  1.03
   TVLP2                   97  1.12  1.03
   TMEM0                   96  1.11  1.05
   TMEM1                   91  1.05  1.03
   TMEM2                   87  1.00  1.03
 ------------------------------------------
   Completed   565,444 =   94

   Unit test   6.00 s    kips   rel   var
 ------------------------------------------
   T0123                  117  1.03  1.05
   TABCD                  117  1.03  1.05
   T0123456789            117  1.03  1.05
   T-B-D-F-H-J            117  1.02  1.05
   TABCDEFGHIJ            116  1.02  1.04
   T_B_D                  114  1.00  1.05
 ------------------------------------------
   Completed   696,223 =  116

   Unit test   8.00 s    kips   rel   var
 ------------------------------------------
   TCAR0                   98  1.04  1.03
   TCAR2                   97  1.03  1.04
   TCAR1                   97  1.02  1.03
   TCAR3                   97  1.02  1.04
   TNTH1                   95  1.01  1.03
   TNTH3                   95  1.01  1.02
   TNTH0                   95  1.00  1.03
   TNTH2                   94  1.00  1.03
 ------------------------------------------
   Completed   768,241 =   96

   Unit test   2.00 s    kips   rel   var
 ------------------------------------------
   T1PLUS                 114  1.01  1.05
   TPLUS1                 112  1.00  1.05
 ------------------------------------------
   Completed   224,928 =  112

   Unit test  15.00 s    kips   rel   var
 ------------------------------------------
   TNOCHECK               115  1.14  1.07
   TNUMBERI               115  1.14  1.06
   TNULLVAL               115  1.14  1.06
   TEQZEROR               115  1.13  1.06
   TLSTPRED               115  1.13  1.07
   TEQZEROI               115  1.13  1.05
   TEQZEROS               114  1.12  1.05
   TSYMPRED               113  1.11  1.02
   TNUMBERR               113  1.11  1.05
   THASAVAL               112  1.11  1.09
   TTYPELST               110  1.09  1.05
   TTYPESTR               104  1.03  1.05
   TTYPEINT               102  1.01  1.04
   TTYPESYM               101  1.00  1.05
   TTYPEREL               101  1.00  1.09
 ------------------------------------------
   Completed 1,653,428 =  110


[togores]

This reminds me of good old Tony Tanzillo, who revealed (in the times of comp.cad.autocad) the undocumented variable MILLISECS 

[enderprime]

I'll take that as a good thing? 

[togores]

Of course, he pioneered this kind of research, it's great that you keep on the good work.
I used his approach in showing the difference between list and array access in my books on AutoLISP/Visual LISP. The first one published in 2003 (in Spanish).

[irneb]

Just be careful of simply taking such benchmarks as gospel. There's more to it than just what type of loop / comparison method you use, it's usually a lot more important about your working algorithm - and in some cases your algorithm governs which methods you can actually use. Mainly this is what's referred to a premature-optimization.

E.g. http://alisp-ext.wikidot.com/auotolisp-nthcdr

Notice that even though a while loop is a bit faster than a repeat loop (at least if uncompiled), it would mean there's an extra index needed, with an accompanying setq and <. This might make the loop slower.

[irneb]

As a further example. Say your intention is to join 10 lists together. Even though you "know" that cons performs faster than append (from your previous tests) ... would you consider using cons to do so on these 10 lists?

Code - Auto/Visual Lisp: [Select]

1. (setq L0 '(0 1 2 3 4 5 6 7 8 9) n 10)
2. (while (> (setq n (1- n)) 0)
3.   (set (read (strcat "L" (itoa n))) (mapcar '(lambda (x) (+ x (* 10 n))) L0)))

Would you do it this way?

Code - Auto/Visual Lisp: [Select]

1. (defun JoinLists-Cons (n / result)
2.   (repeat n
3.     (foreach item (reverse (eval (read (strcat "L" (itoa (setq n (1- n)))))))
4.       (setq result (cons item result)))))

Well, if you only take into account that "cons is faster than append" then you should be doing this shouldn't you?

How about using the more "natual" way:

Code - Auto/Visual Lisp: [Select]

1. (defun JoinLists-Append (n / result)
2.   (repeat n
3.     (setq result (append (eval (read (strcat "L" (itoa (setq n (1- n)))))) result))))

From your previous tests, this should be slower right?

OK, so let's try to "optimize" it a bit by changing the 10 appends into one append:

Code - Auto/Visual Lisp: [Select]

1. (defun JoinLists-Append2 (n / result)
2.   (repeat n
3.     (setq result (cons (eval (read (strcat "L" (itoa (setq n (1- n)))))) result)))
4.   (apply 'append result))

Now consider these "strange" results:

Code: [Select]

Benchmarking ... done for 16384 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(JOINLISTS-APPEND2 10)                       16384      1918      1918      1.94
(JOINLISTS-APPEND 10)                         8192      1140      2280      1.63
(JOINLISTS-CONS 10)                           8192      1856      3712      1.00
--------------------------------------------------------------------------------It seems that in this case append is at least 60% faster than cons, and nearly 100% if optimized a bit. So you see what i mean? Looking at these "unit tests" don't necessarily give you a "one-size-fits-all" answer.

[enderprime]

It seems that in this case append is at least 60% faster than cons, and nearly 100% if optimized a bit. So you see what i mean? Looking at these "unit tests" don't necessarily give you a "one-size-fits-all" answer.

Excellent point.

[VovKa]

cons and append shouldn't be benchmarked against each other
cons is a 'base' lisp function while append is a sequence of conses

[irneb]

cons and append shouldn't be benchmarked against each other
cons is a 'base' lisp function while append is a sequence of conses

Good point! Though I was only using that as an example - trying to indicate that just because something works faster in once scenario doesn't mean it's faster in all.

Usually I would try to use the most "appropriate" method. E.g. if there's a minimal difference in speed between mapcar and foreach, I'd go with the one which makes more sense in the scenario which prevails. I.e. I'd not "force" the use of mapcar where foreach is clearly more natural, and similarly I'd use the mapcar instead of creating an imperative foreach with a reverse where that is more natural.