Benchmarking Results

All experiments are run under Ubuntu Linux 14.04 and SBCL 1.2.8, with AMD Phenom II X6 2.8GHz and 4GB Memory.

Test Domains

Test Domains are partly picked from (Balland 2006). Source code of these domains is available @ bench/definisitons.lisp .

Fibonacci

Computes a large Fibonacci number. I didnt apply any memoization technique: it is a quite basic implementation.

Gomoku

Matches a set of randomly generated 5x5 fields of Gomoku table game against the winning patterns of the game, in order to determine if a Black player is winning, or a White player is winning. 100000 fields are generated and fixed, then supplied to each matcher.

Stringmatch

Collected all words in Lorem Ipsum @ wikipedia, then created a function that returns true if the corpus contains the given word. The input vector is a list of words of the original sentence in De finibus bonorum et malorum.

Results Summary

runtime [sec]	fibonacci	gomoku	string-match
optima	11.5	39.8	82.5
trivia	9.96	41.7	7.93
trivia + balland2006	9.68	37.4	1.57

Results varies across the test domains, but the overall performance of trivia+balland2006 outperforms Optima. Performance improvement in string-match is especially interesting, given that trivia (w/o optimization) is also fast.

The major reason for this difference is in the amount of consing: Optima conses 475,568 bytes in string-match, while Trivia (w/o optimization) is non-consing. Note that the amount of memory consumed during the test data generation is not accounted, and the same instances are used for all participants. Also, all results are verified by comparing the results to each other so that Trivia does not contain bugs.

Consing [bytes]	fibonacci	gomoku	string-match
optima	98,096	262,576	475,568
trivia	76,768	256,624	0
trivia + balland2006	36,464	196,720	0

Actual Log (+ Optimization Trace)

Below is an example of the trace log of balland2006’s optimization scheme. The runtime result does not necessarily match the numbers in the table above.

-------------------- BALLAND ----------------------------------------
; Swapping (EQL #:IT1 0), (EQL #:IT2 1) under T
; Fusing  T,  T
; Fusing  T,  T
Evaluation took:
  11.130 seconds of real time
  11.129130 seconds of total run time (11.125170 user, 0.003960 system)
  99.99% CPU
  33,390,657,846 processor cycles
  36,464 bytes consed
  
; Grounding
;  (((OR1 (GUARD1 (#:IT1 :IGNORABLE T ...) (TYPEP #:IT1 '(SIMPLE-VECTOR 25)) ...)
;     (GUARD1 (#:IT7 :IGNORABLE T ...) (TYPEP #:IT7 '(SIMPLE-VECTOR 25)) ...) ...))
;   1)
; Grounding
;  (((OR1 (GUARD1 (#:IT73 :IGNORABLE T ...) (TYPEP #:IT73 '(SIMPLE-VECTOR 25)) ...)
;     (GUARD1 (#:IT79 :IGNORABLE T ...) (TYPEP #:IT79 '(SIMPLE-VECTOR 25)) ...) ...))
;   0)
; Fusing
;   (TYPEP #:IT1 '(SIMPLE-VECTOR 25)),
;   (TYPEP #:IT7 '(SIMPLE-VECTOR 25)),
;   (TYPEP #:IT13 '(SIMPLE-VECTOR 25)),
;   (TYPEP #:IT19 '(SIMPLE-VECTOR 25)),
;   (TYPEP #:IT25 '(SIMPLE-VECTOR 25)),
;   (TYPEP #:IT31 '(SIMPLE-VECTOR 25)),
;   (TYPEP #:IT37 '(SIMPLE-VECTOR 25)),
;   (TYPEP #:IT43 '(SIMPLE-VECTOR 25)),
;   (TYPEP #:IT49 '(SIMPLE-VECTOR 25)),
;   (TYPEP #:IT55 '(SIMPLE-VECTOR 25)),
;   (TYPEP #:IT61 '(SIMPLE-VECTOR 25)),
;   (TYPEP #:IT67 '(SIMPLE-VECTOR 25)),
;   (TYPEP #:IT73 '(SIMPLE-VECTOR 25)),
;   (TYPEP #:IT79 '(SIMPLE-VECTOR 25)),
;   (TYPEP #:IT85 '(SIMPLE-VECTOR 25)),
;   (TYPEP #:IT91 '(SIMPLE-VECTOR 25)),
;   (TYPEP #:IT97 '(SIMPLE-VECTOR 25)),
;   (TYPEP #:IT103 '(SIMPLE-VECTOR 25)),
;   (TYPEP #:IT109 '(SIMPLE-VECTOR 25)),
;   (TYPEP #:IT115 '(SIMPLE-VECTOR 25)),
;   (TYPEP #:IT121 '(SIMPLE-VECTOR 25)),
;   (TYPEP #:IT127 '(SIMPLE-VECTOR 25)),
;   (TYPEP #:IT133 '(SIMPLE-VECTOR 25)),
;   (TYPEP #:IT139 '(SIMPLE-VECTOR 25))
; Fusing  T,  T
; Fusing  T,  T
; Fusing  T,  T,  T,  T,  T,  T
; Fusing  T,  T,  T
; Fusing  T,  T,  T,  T,  T,  T,  T
; Fusing  T,  T,  T
; Fusing  T,  T
 Black : White : Notany = 29034000 : 30429540 : 536460 
Evaluation took:
  36.966 seconds of real time
  36.965855 seconds of total run time (36.949955 user, 0.015900 system)
  100.00% CPU
  110,904,550,048 processor cycles
  196,720 bytes consed
  
; Grounding
;  (((OR1 (GUARD1 (#:IT1 :IGNORABLE T ...) (TYPEP #:IT1 '(SIMPLE-STRING 5)) ...)
;     (GUARD1 (#:IT7 :IGNORABLE T ...) (TYPEP #:IT7 '(SIMPLE-STRING 5)) ...) ...))
;   T)
; Swapping (TYPEP #:IT13 '(SIMPLE-STRING 5)), (TYPEP #:IT19 '(SIMPLE-STRING 3)) under T
; Swapping (TYPEP #:IT7 '(SIMPLE-STRING 5)), (TYPEP #:IT19 '(SIMPLE-STRING 3)) under T
;;; ...
; Swapping (TYPEP #:IT346 '(SIMPLE-STRING 8)), (TYPEP #:IT432 '(SIMPLE-STRING 7)) under T
; Swapping (TYPEP #:IT322 '(SIMPLE-STRING 8)), (TYPEP #:IT432 '(SIMPLE-STRING 7)) under T
; Fusing
;   (TYPEP #:IT19 '(SIMPLE-STRING 3)),
;   (TYPEP #:IT57 '(SIMPLE-STRING 3)),
;   (TYPEP #:IT365 '(SIMPLE-STRING 3)),
;   (TYPEP #:IT392 '(SIMPLE-STRING 3)),
;   (TYPEP #:IT428 '(SIMPLE-STRING 3))
; Fusing
;   (TYPEP #:IT72 '(SIMPLE-STRING 6)),
;   (TYPEP #:IT93 '(SIMPLE-STRING 6)),
;   (TYPEP #:IT103 '(SIMPLE-STRING 6)),
;   (TYPEP #:IT116 '(SIMPLE-STRING 6)),
;   (TYPEP #:IT140 '(SIMPLE-STRING 6)),
;   (TYPEP #:IT292 '(SIMPLE-STRING 6)),
;   (TYPEP #:IT299 '(SIMPLE-STRING 6)),
;   (TYPEP #:IT309 '(SIMPLE-STRING 6)),
;   (TYPEP #:IT413 '(SIMPLE-STRING 6))
;;; ...
;;; ...
; Fusing  (TYPEP #:IT28 '(SIMPLE-STRING 11)),  (TYPEP #:IT40 '(SIMPLE-STRING 11))
; Swapping (EQL #:IT58 #\s), (EQL #:IT366 #\n) under T
; Swapping (EQL #:IT20 #\s), (EQL #:IT366 #\n) under T
; Swapping (EQL #:IT58 #\s), (EQL #:IT393 #\q) under T
; Swapping (EQL #:IT20 #\s), (EQL #:IT393 #\q) under T
; Swapping (EQL #:IT366 #\n), (EQL #:IT393 #\q) under T
; Swapping (EQL #:IT58 #\s), (EQL #:IT429 #\e) under T
; Swapping (EQL #:IT20 #\s), (EQL #:IT429 #\e) under T
; Fusing  (EQL #:IT20 #\s),  (EQL #:IT58 #\s)
; Swapping (EQL #:IT21 #\i), (EQL #:IT59 #\e) under T
;;; ...
; Fusing  (EQL #:IT220 #\c),  (EQL #:IT356 #\c)
; Swapping (EQL #:IT221 #\o), (EQL #:IT357 #\u) under T
; Swapping (EQL #:IT29 #\c), (EQL #:IT41 #\a) under T
 Matched 7100000 times
Evaluation took:
  1.550 seconds of real time
  1.548633 seconds of total run time (1.548624 user, 0.000009 system)
  99.94% CPU
  4,647,723,704 processor cycles
  0 bytes consed
  
-------------------- OPTIMA ----------------------------------------
Evaluation took:
  10.052 seconds of real time
  10.052829 seconds of total run time (10.052810 user, 0.000019 system)
  100.01% CPU
  30,159,591,174 processor cycles
  98,096 bytes consed
  
 Black : White : Notany = 29034000 : 30429540 : 536460 
Evaluation took:
  39.315 seconds of real time
  39.298361 seconds of total run time (39.286375 user, 0.011986 system)
  99.96% CPU
  117,951,743,059 processor cycles
  262,576 bytes consed
  
 Matched 7100000 times
Evaluation took:
  82.826 seconds of real time
  82.788210 seconds of total run time (82.684360 user, 0.103850 system)
  99.95% CPU
  248,490,424,774 processor cycles
  475,568 bytes consed
  
-------------------- TRIVIA -----------------------------------------
Evaluation took:
  10.279 seconds of real time
  10.278082 seconds of total run time (10.226178 user, 0.051904 system)
  99.99% CPU
  30,839,143,995 processor cycles
  76,768 bytes consed
  
 Black : White : Notany = 29034000 : 30429540 : 536460 
Evaluation took:
  42.913 seconds of real time
  42.895526 seconds of total run time (42.707732 user, 0.187794 system)
  99.96% CPU
  128,745,325,086 processor cycles
  256,624 bytes consed
  
 Matched 7100000 times
Evaluation took:
  8.186 seconds of real time
  8.185925 seconds of total run time (8.169921 user, 0.016004 system)
  100.00% CPU
  24,559,567,889 processor cycles
  0 bytes consed