#:g1: なんとなくパタンマッチライブラリ比較

Posted 2014-03-25 16:00:00 GMT

 Common Lispには昔からパタンマッチのマクロはそれなりにある。
ふと、それぞれどんなものなのか比較してみたいと思ったので、harropifyの速度比較をしてみた。
もちろん限定的な比較なので、harropifyの速度がライブラリの良さに直結する訳ではない。念の為。
比較の為、パタンマッチは使わず手書きでリスト操作したものと、CL:TYPECASEで書いたものも一緒に計測した。

(cl:in-package :cl-user)

(defpackage :match-bench.non-pm (:use :cl) (:export :harropify))

(defpackage :match-bench.typecase (:use :cl) (:export :harropify))

(defpackage :match-bench.toadstool (:use :cl :toadstool) (:export :harropify))

(defpackage :match-bench.wright (:use :cl :snow-match) (:export :harropify))

(defpackage :match-bench.optima (:use :cl :optima) (:export :harropify))

(defpackage :match-bench.arnesi (:use :cl :arnesi) (:export :harropify))

(defpackage :match-bench.cl-match (:use :cl :cl-match) (:export :harropify))

(defpackage :match-bench.matchcomp (:use :cl :matchcomp) (:export :harropify))

(defpackage :match-bench.cl-unification (:use :cl :cl-unification) (:export :harropify))

(defpackage :match-bench.fare-matcher (:use :cl :fare-matcher) (:export :harropify))

(defpackage :match-bench.select-match (:use :cl :swank-match) (:import-from :swank-match :=>) (:export :harropify))

(cl:in-package :match-bench.non-pm)

(defun h (op a b) (case op (+ (cond ((and (numberp a) (numberp b)) (+ a b)) ((eql 0 a) b) ((eql 0 b) a) ((and (consp b) (eq '+ (nth 0 b))) (h '+ (h '+ a (nth 0 b)) (nth 1 b))) (T (list op a b)))) (* (cond ((and (numberp a) (numberp b)) (* a b)) ((eql 0 a) 0) ((eql 0 b) 0) ((eql 1 a) b) ((eql 1 b) a) ((and (consp b) (eq '* (nth 0 b))) (h '* (h '* a (nth 0 b)) (nth 1 b))) (T (list op a b)))) (otherwise (list op a b))))

(defun harropify (x) (typecase x (CONS (h (nth 0 x) (harropify (nth 1 x)) (harropify (nth 2 x)))) (T x)))

(cl:in-package :match-bench.typecase)

(defun h (op a b) (let ((arg (list op a b))) (declare (dynamic-extent arg)) (typecase arg ((CONS (EQL +) (CONS NUMBER (CONS NUMBER NULL))) (+ a b)) ((CONS (EQL +) (CONS (EQL 0) CONS)) b) ((CONS (EQL +) (CONS T (CONS (EQL 0) NULL))) b) ((CONS (EQL +) (CONS T (CONS (EQL +) NULL))) (h '+ (h '+ a (nth 0 b)) (nth 1 b))) ((CONS (EQL *) (CONS NUMBER (CONS NUMBER NULL))) (* a b)) ((CONS (EQL *) (CONS (EQL 0) CONS)) 0) ((CONS (EQL *) (CONS T (CONS (EQL 0) CONS))) 0) ((CONS (EQL *) (CONS (EQL 1) CONS)) b) ((CONS (EQL *) (CONS T (CONS (EQL 1) NULL))) a) ((CONS (EQL *) (CONS T (CONS (EQL *) CONS))) (h '* (h '* a (nth 0 b)) (nth 1 b))) (T (list op a b)))))

(defun harropify (x) (typecase x (CONS (h (nth 0 x) (harropify (nth 1 x)) (harropify (nth 2 x)))) (T x)))

(cl:in-package :match-bench.toadstool)

(defun h (op a b) (toad-case op a b '+ M N -> (when (and (numberp M) (numberp N))) (+ M N) '+ 0 F -> F '+ F 0 -> F '+ A (list '+ B C) -> (h '+ (h '+ A B) C) '* M N -> (when (and (numberp M) (numberp N))) (* M N) '* 0 F -> 0 '* F 0 -> 0 '* F 1 -> F '* 1 F -> F '* A (list '* B C) -> (h '* (h '* A B) C) Op A B -> (list Op A B)))

(defun harropify (x) (toad-case x (list Op A B) -> (h Op (harropify A) (harropify B)) A -> A))

(cl:in-package :match-bench.wright)

(defun h (op a b) (match (list op a b) (('+ (:? numberp M) (:? numberp N)) (+ M N)) (('+ 0 F) F) (('+ F 0) F) (('+ A ('+ B C)) (h '+ (h '+ A B) C)) (('* (:? numberp M) (:? numberp N)) (* M N)) (('* 0 F) f 0) (('* F 0) f 0) (('* F 1) F) (('* 1 F) F) (('* A ('* B C)) (h '* (h '* A B) C)) ((Op A B) (list Op A B))))

(defun harropify (x) (match x ((Op A B) (h Op (harropify A) (harropify B))) (A A)))

(cl:in-package :match-bench.optima)

(defun h (op a b) (match (list op a b) ((list '+ M N) when (and (numberp M) (numberp N)) (+ M N)) ((list '+ 0 F) F) ((list '+ F 0) F) ((list '+ A (list '+ B C)) (h '+ (h '+ A B) C)) ((list '* M N) when (and (numberp M) (numberp N)) (* M N)) ((list '* 0 F) (declare (ignore F)) 0) ((list '* F 0) (declare (ignore F)) 0) ((list '* F 1) F) ((list '* 1 F) F) ((list '* A (list '* B C)) (h '* (h '* A B) C)) ((list Op A B) (list Op A B))))

(defun harropify (x) (match x ((list Op A B) (h Op (harropify A) (harropify B))) (A A)))

(cl:in-package :match-bench.arnesi)

(defun h (op a b) (match-case (list op a b) ((:list '+ (:and (:test numberp) M) (:and (:test numberp) N)) (+ M N)) ((:list '+ 0 F) F) ((:list '+ F 0) F) ((:list '+ A (:list '+ B C)) (h '+ (h '+ A B) C)) ((:list '* (:and (:test numberp) M) (:and (:test numberp) N)) (* M N)) ((:list '* 0 F) 0) ((:list '* F 0) 0) ((:list '* F 1) F) ((:list '* 1 F) F) ((:list '* A (:list '* B C)) (h '* (h '* A B) C)) ((:list Op A B) (list Op A B))))

(defun harropify (x) (match-case x ((:list Op A B) (h Op (harropify A) (harropify B))) (A A)))

(cl:in-package :match-bench.cl-match)

(defun h (op a b) (match (list op a b) ((:when (and (numberp M) (numberp N)) (:list '+ M N)) (+ M N)) ((:list '+ 0 F) F) ((:list '+ F 0) F) ((:list '+ A (:list '+ B C)) (h '+ (h '+ A B) C)) ((:when (and (numberp M) (numberp N)) (:list '* M N)) (* M N)) ((:list '* 0 F) 0) ((:list '* F 0) 0) ((:list '* F 1) F) ((:list '* 1 F) F) ((:list '* A (:list '* B C)) (h '* (h '* A B) C)) ((:list Op A B) (list Op A B))))

(defun harropify (x) (match x ((:list Op A B) (h Op (harropify A) (harropify B))) (A A)))

(cl:in-package :match-bench.fare-matcher)

(defun h (op a b) (match (list op a b) ((list '+ (and M (of-type integer)) (and N (of-type integer))) (+ M N)) ((list '+ 0 F) F) ((list '+ F 0) F) ((list '+ A (list '+ B C)) (h '+ (h '+ A B) C)) ((list '* (and M (of-type integer)) (and N (of-type integer))) (* M N)) ((list '* 0 F) 0) ((list '* F 0) 0) ((list '* F 1) F) ((list '* 1 F) F) ((list '* A (list '* B C)) (h '* (h '* A B) C)) ((list Op A B) (list Op A B))))

(defun harropify (x) (match x ((list Op A B) (h Op (harropify A) (harropify B))) (A A)))

(cl:in-package :match-bench.cl-unification)

(defun h (op a b) (match-case ((list op a b)) ('(+ #.(make-instance 'unify:number-template :spec '(number ?M)) #.(make-instance 'unify:number-template :spec '(number ?N))) (+ M N)) ('(+ 0 ?F) F) ('(+ ?F 0) F) ('(+ ?A (+ ?B ?C)) (h '+ (h '+ A B) C)) ((list '* #.(make-instance 'unify:number-template :spec '(number ?M)) #.(make-instance 'unify:number-template :spec '(number ?N))) (* M N)) ('(* 0 ?F) 0) ('(* ?F 0) 0) ('(* ?F 1) F) ('(* 1 ?F) F) ('(* ?A (* ?B ?C)) (h '* (h '* A B) C)) ('(?Op ?A ?B) (list Op A B))))

(defun harropify (x) (match-case (x) ('(?Op ?A ?B) (h Op (harropify A) (harropify B))) (?A A)))

(cl:in-package :match-bench.matchcomp)

(defun h (&rest op-a-b) (match-case op-a-b ((+ ?A ?B) (if (and (numberp A) (numberp B)) (+ A B) (match-case op-a-b ((+ 0 ?F) F) ((+ ?F 0) F) ((+ ?A (+ ?B ?C)) (h '+ (h '+ A B) C)) (?- op-a-b)))) ((* ?M ?N) (if (and (numberp M) (numberp N)) (* M N) (match-case op-a-b ((* 0 ?F) F 0) ((* ?F 0) F 0) ((* 1 ?F) F) ((* ?F 1) F) ((* ?A (* ?B ?C)) (h '* (h '* A B)) C) (?- op-a-b)))) (?- op-a-b)))

(defun harropify (x) (match-case x ((?Op ?A ?B) (h Op (harropify A) (harropify B))) (?A A)))

(cl:in-package :match-bench.select-match)

#|(defun h (op a b) (match (list op a b) (('+ (#'numberp M) (#'numberp N)) (+ M N)) (('+ 0 F) F) (('+ F 0) F) (('+ A ('+ B C)) (h '+ (h '+ A B) C)) (('* (#'numberp M) (#'numberp N)) (* M N)) (('* 0 F) f 0) (('* F 0) f 0) (('* F 1) F) (('* 1 F) F) (('* A ('* B C)) (h '* (h '* A B) C)) ((Op A B) (list Op A B))))|#

(defun h (op a b) (match (list op a b) ('+ (#'numberp M) (#'numberp N)) => (+ M N) ('+ 0 F) => F ('+ F 0) => F ('+ A ('+ B C)) => (h '+ (h '+ A B) C) ('* (#'numberp M) (#'numberp N)) => (* M N) ('* 0 F) => 0 ('* F 0) => 0 ('* F 1) => F ('* 1 F) => F ('* A ('* B C)) => (h '* (h '* A B) C) (Op A B) => (list Op A B)))

(defun harropify (x) (match x ((Op A B) (h Op (harropify A) (harropify B))) (A A)))

;;; *END*

harropify 100,000回

================================================================================
MATCH-BENCH.NON-PM
100,000 times
Evaluation took:
  0.024 seconds of real time
  0.024002 seconds of total run time (0.024002 user, 0.000000 system)
  100.00% CPU
  57,848,832 processor cycles
  9,591,680 bytes consed

================================================================================ MATCH-BENCH.TYPECASE 100,000 times Evaluation took: 0.056 seconds of real time 0.056004 seconds of total run time (0.056004 user, 0.000000 system) 100.00% CPU 134,556,993 processor cycles 9,591,664 bytes consed

================================================================================ MATCH-BENCH.TOADSTOOL 100,000 times Evaluation took: 0.029 seconds of real time 0.032002 seconds of total run time (0.032002 user, 0.000000 system) 110.34% CPU 71,145,513 processor cycles 9,624,400 bytes consed

================================================================================ MATCH-BENCH.WRIGHT 100,000 times Evaluation took: 0.089 seconds of real time 0.076005 seconds of total run time (0.076005 user, 0.000000 system) 85.39% CPU 210,852,306 processor cycles 33,651,632 bytes consed

================================================================================ MATCH-BENCH.OPTIMA 100,000 times Evaluation took: 0.052 seconds of real time 0.048003 seconds of total run time (0.048003 user, 0.000000 system) 92.31% CPU 122,556,141 processor cycles 33,587,168 bytes consed

================================================================================ MATCH-BENCH.ARNESI 100,000 times Evaluation took: 16.032 seconds of real time 15.960997 seconds of total run time (15.916995 user, 0.044002 system) [ Run times consist of 1.585 seconds GC time, and 14.376 seconds non-GC time. ] 99.56% CPU 38,380,723,029 processor cycles 7,241,620,560 bytes consed

================================================================================ MATCH-BENCH.CL-MATCH 100,000 times Evaluation took: 0.108 seconds of real time 0.108007 seconds of total run time (0.108007 user, 0.000000 system) [ Run times consist of 0.036 seconds GC time, and 0.073 seconds non-GC time. ] 100.00% CPU 259,417,548 processor cycles 33,619,920 bytes consed

================================================================================ MATCH-BENCH.FARE-MATCHER 100,000 times Evaluation took: 0.487 seconds of real time 0.484030 seconds of total run time (0.484030 user, 0.000000 system) [ Run times consist of 0.072 seconds GC time, and 0.413 seconds non-GC time. ] 99.38% CPU 1,166,408,235 processor cycles 326,382,928 bytes consed

================================================================================ MATCH-BENCH.CL-UNIFICATION 100,000 times Evaluation took: 12.488 seconds of real time 12.380774 seconds of total run time (12.368773 user, 0.012001 system) [ Run times consist of 0.304 seconds GC time, and 12.077 seconds non-GC time. ] 99.14% CPU 29,896,123,851 processor cycles 1,371,211,456 bytes consed

================================================================================ MATCH-BENCH.MATCHCOMP 100,000 times Evaluation took: 0.045 seconds of real time 0.044003 seconds of total run time (0.044003 user, 0.000000 system) 97.78% CPU 106,829,712 processor cycles 23,995,488 bytes consed

================================================================================ MATCH-BENCH.SELECT-MATCH 100,000 times Evaluation took: 0.043 seconds of real time 0.044003 seconds of total run time (0.044003 user, 0.000000 system) 102.33% CPU 101,878,632 processor cycles 33,587,136 bytes consed

harropify 1,000,000回

 arnesi:match-caseとcl-unification:match-caseは他と比較して100倍位遅いので計測から外してある。
cl-unificationはその名の通りユニフィケーションの為のライブラリで双方向マッチ可能なので、harropifyのようなもので比較されるのは不利なのではないかと思う。

================================================================================
MATCH-BENCH.NON-PM
1,000,000 times
Evaluation took:
  0.228 seconds of real time
  0.228015 seconds of total run time (0.228015 user, 0.000000 system)
  100.00% CPU
  547,773,129 processor cycles
  96,014,720 bytes consed

================================================================================ MATCH-BENCH.TYPECASE 1,000,000 times Evaluation took: 0.604 seconds of real time 0.600037 seconds of total run time (0.600037 user, 0.000000 system) [ Run times consist of 0.040 seconds GC time, and 0.561 seconds non-GC time. ] 99.34% CPU 1,446,669,081 processor cycles 96,005,920 bytes consed

================================================================================ MATCH-BENCH.TOADSTOOL 1,000,000 times Evaluation took: 0.309 seconds of real time 0.304019 seconds of total run time (0.304019 user, 0.000000 system) 98.38% CPU 740,617,974 processor cycles 95,981,984 bytes consed

================================================================================ MATCH-BENCH.WRIGHT 1,000,000 times Evaluation took: 0.870 seconds of real time 0.856053 seconds of total run time (0.852053 user, 0.004000 system) [ Run times consist of 0.080 seconds GC time, and 0.777 seconds non-GC time. ] 98.39% CPU 2,082,572,298 processor cycles 335,990,736 bytes consed

================================================================================ MATCH-BENCH.OPTIMA 1,000,000 times Evaluation took: 0.563 seconds of real time 0.556035 seconds of total run time (0.552034 user, 0.004001 system) [ Run times consist of 0.076 seconds GC time, and 0.481 seconds non-GC time. ] 98.76% CPU 1,348,189,524 processor cycles 336,002,592 bytes consed

================================================================================ MATCH-BENCH.CL-MATCH 1,000,000 times Evaluation took: 0.810 seconds of real time 0.792049 seconds of total run time (0.788049 user, 0.004000 system) [ Run times consist of 0.080 seconds GC time, and 0.713 seconds non-GC time. ] 97.78% CPU 1,940,743,188 processor cycles 335,989,232 bytes consed

================================================================================ MATCH-BENCH.FARE-MATCHER 1,000,000 times Evaluation took: 4.624 seconds of real time 4.560284 seconds of total run time (4.424276 user, 0.136008 system) [ Run times consist of 0.464 seconds GC time, and 4.097 seconds non-GC time. ] 98.62% CPU 11,070,526,455 processor cycles 3,263,990,384 bytes consed

================================================================================ MATCH-BENCH.MATCHCOMP 1,000,000 times Evaluation took: 0.467 seconds of real time 0.460028 seconds of total run time (0.460028 user, 0.000000 system) [ Run times consist of 0.020 seconds GC time, and 0.441 seconds non-GC time. ] 98.50% CPU 1,117,957,527 processor cycles 239,987,984 bytes consed

================================================================================ MATCH-BENCH.SELECT-MATCH 1,000,000 times Evaluation took: 0.480 seconds of real time 0.472029 seconds of total run time (0.472029 user, 0.000000 system) [ Run times consist of 0.040 seconds GC time, and 0.433 seconds non-GC time. ] 98.33% CPU 1,147,606,731 processor cycles 336,014,880 bytes consed

comments powered by Disqus