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

Fibonacci

Computes a large Fibonacci number. I didnt apply the 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 + emilie2006	9.68	37.4	1.57

Results varies across the test domains, but the performance of trivia+emilie2006 is interesting especially in string-match. Interestingly, trivia (w/o optimization) is also fast in string-match.

Actual Log (+ Optimization Trace)

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

-------------------- EMILIE ----------------------------------------
; 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
  
-------------------- TRIVIAL ----------------------------------------
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