Load benchmarking code
(load-file "multi-benchmarks.el")Load multi-patterns
(load-file "multi-patterns.el")How does pattern-matching compare to the existing semantically similar solutions. E.g. manual destructuring, seq-* functions, dash, etc. Idea is to have baseline perf we should strive for and to give users some idea about perf so they can decide if its good enough for them.
(mu-bench*
:compare t
(mu-bench "multi-case"
(let* ((test-cases '(() (1) (1 2) (1 2 3) (1 2 3 4)))
(len (length test-cases))
(test-case (lambda () (nth (random len) test-cases))))
(mu-case (funcall test-case)
((lst) 0)
((lst _) 1)
((lst _ _) 2)
((lst _ _ _) 3)
(otherwise 'many))))
(mu-bench "pcase"
(let* ((test-cases '(() (1) (1 2) (1 2 3) (1 2 3 4)))
(len (length test-cases))
(test-case (lambda () (nth (random len) test-cases))))
(pcase (funcall test-case)
(`nil 0)
(`(,_) 1)
(`(,_ ,_) 2)
(`(,_ ,_ ,_) 3)
(otherwise 'many)))))| Form | x slower | Total time | GCs | GC time | Timestamp |
|---|---|---|---|---|---|
| multi-case | 1.00 | 0.002010 | 0 | 0.000000 | Sun Dec 30 11:34:41 2018 |
| pcase | 1.06 | 0.002134 | 0 | 0.000000 | Sun Dec 30 11:34:41 2018 |
| Form | x slower | Total time | GCs | GC time | Timestamp |
| pcase | 1.00 | 0.001325 | 0 | 0.0 | Thu Dec 27 08:41:01 2018 |
| multi-case | 1.56 | 0.002069 | 0 | 0.0 | Thu Dec 27 08:41:01 2018 |
mu-let is terribly slow and triggers GC
(mu-bench*
:compare t
(mu-bench "seq-let"
(mapcar
(lambda (arg)
(seq-let (s1 &rest d) arg
(seq-let (a &rest t2) s1
(seq-let (b c) (seq-elt t2 0)
(list a b c d)))))
(list '((1 (2 3)) 4) [[1 [2 3]] 4])))
(mu-bench "mu-let"
(mapcar
(lambda (arg)
(mu-let (([[a &rest [[b c]]] &rest d] arg))
(list a b c d)))
(list '((1 (2 3)) 4) [[1 [2 3]] 4])))
(mu-bench "mu-case"
(mapcar
(lambda (arg)
(mu-case arg
([[a &rest [[b c]]] &rest d] (list a b c d))))
(list '((1 (2 3)) 4) [[1 [2 3]] 4]))))| Form | x slower | Total time | GCs | GC time | Timestamp |
|---|---|---|---|---|---|
| seq-let | 1.00 | 0.032032 | 0 | 0.000000 | Sun Dec 30 11:45:50 2018 |
| mu-case | 6.94 | 0.222181 | 0 | 0.000000 | Sun Dec 30 11:45:50 2018 |
| mu-let | 15.79 | 0.505918 | 1 | 0.046986 | Sun Dec 30 11:45:50 2018 |
| Form | x slower | Total time | GCs | GC time | Timestamp |
| seq-let | 1.00 | 0.031043 | 0 | 0.000000 | Thu Dec 27 08:44:16 2018 |
| mu-case | 8.04 | 0.249537 | 0 | 0.000000 | Thu Dec 27 08:44:16 2018 |
| mu-let | 20.46 | 0.635143 | 1 | 0.099905 | Thu Dec 27 08:44:16 2018 |
(mu-bench*
:compare t
("seq-let" (let* ((a 1))
(seq-let (b) '(2 3)
(seq-let (c d e) '(3 4)
(list a b c d e)))))
("mu-let" (mu-let ((a 1)
([b] '(2 3))
([c d e] '(3 4)))
(list a b c d e))))| Form | x slower | Total time | GCs | GC time | Timestamp |
|---|---|---|---|---|---|
| seq-let | 1.00 | 0.005221 | 0 | 0.000000 | Thu Dec 27 08:45:38 2018 |
| mu-let | 44.47 | 0.232198 | 0 | 0.000000 | Thu Dec 27 08:45:38 2018 |
(mu-bench*
:compare t
(mu-bench "ht-get"
(let* ((table (ht (:a 1) ('b 2) (:c 3) ('d 4)))
(a (ht-get table :a))
(b (ht-get table 'b))
(c (ht-get table :c))
(D (ht-get table 'd)))
(list a b c D)))
(mu-bench "ht-pattern"
(mu-case (ht (:a 1) ('b 2) (:c 3) ('d 4))
;; NOTE this one is richer than the ht-get version cause
;; it tries different keys :a 'a "a" in order
((ht :a b 'c ('d D)) (list a b c D)))))| Form | x slower | Total time | GCs | GC time | Timestamp |
|---|---|---|---|---|---|
| ht-pattern | 1.00 | 0.079156 | 1 | 0.049057 | Sun Dec 30 11:47:27 2018 |
| ht-get | 1.05 | 0.082799 | 1 | 0.046360 | Sun Dec 30 11:47:27 2018 |
| Form | x slower | Total time | GCs | GC time | Timestamp |
| ht-pattern | 1.00 | 0.130536 | 1 | 0.095632 | Thu Dec 27 08:46:47 2018 |
| ht-get | 1.05 | 0.137433 | 1 | 0.101954 | Thu Dec 27 08:46:47 2018 |
(mu-bench*
:compare t
(mu-bench "ht-get"
(let* ((l (list (ht (:a 1)) '((:b . 2))))
(a (ht-get (car l) :a))
(b (alist-get :b (cadr l))))
(list a b)))
(mu-bench "ht-pattern"
(mu-case (list (ht (:a 1)) '((:b . 2)))
((l (ht :a) (ht b)) (list a b)))))| Form | x slower | Total time | GCs | GC time | Timestamp |
|---|---|---|---|---|---|
| ht-pattern | 1.00 | 0.064096 | 1 | 0.046210 | Sun Dec 30 11:47:52 2018 |
| ht-get | 1.12 | 0.071720 | 1 | 0.047829 | Sun Dec 30 11:47:52 2018 |
| Form | x slower | Total time | GCs | GC time | Timestamp |
| ht-get | 1.00 | 0.118207 | 1 | 0.096840 | Thu Dec 27 08:47:22 2018 |
| ht-pattern | 1.07 | 0.126853 | 1 | 0.102074 | Thu Dec 27 08:47:22 2018 |
(mu-bench*
:compare t
(mu-bench "lambda"
(let ((fun (lambda () t)))
(funcall fun)))
(mu-bench "mu-lambda"
(let ((fun (mu [] t)))
(funcall fun))))| Form | x slower | Total time | GCs | GC time | Timestamp |
|---|---|---|---|---|---|
| mu-lambda | 1.00 | 0.000613 | 0 | 0.000000 | Sun Dec 30 11:48:29 2018 |
| lambda | 1.49 | 0.000915 | 0 | 0.000000 | Sun Dec 30 11:48:29 2018 |
| Form | x slower | Total time | GCs | GC time | Timestamp |
| lambda | 1.00 | 0.000499 | 0 | 0.000000 | Thu Dec 27 08:48:50 2018 |
| mu-lambda | 1.22 | 0.000609 | 0 | 0.000000 | Thu Dec 27 08:48:50 2018 |
I don’t think this is apples to apples comparison, need a better bench.
(mu-bench*
:compare t
(mu-bench "lambda" (funcall (lambda (a b &rest args) (list* a b args)) 1 2 3 4))
(mu-bench "mu-lambda" (funcall (mu [a b | args] (list* a b args)) 1 2 3 4)))| Form | x slower | Total time | GCs | GC time | Timestamp |
|---|---|---|---|---|---|
| lambda | 1.00 | 0.000627 | 0 | 0.000000 | Sun Dec 30 11:49:01 2018 |
| mu-lambda | 151.09 | 0.094734 | 0 | 0.000000 | Sun Dec 30 11:49:01 2018 |
| Form | x slower | Total time | GCs | GC time | Timestamp |
| lambda | 1.00 | 0.000718 | 0 | 0.000000 | Thu Dec 27 08:49:00 2018 |
| mu-lambda | 161.32 | 0.115828 | 0 | 0.000000 | Thu Dec 27 08:49:00 2018 |
(mu-bench*
:compare t
(mu-bench "lambda"
(let ((fun (lambda (&rest args)
(pcase args
((or `(,a ,b) `[,a ,b]) (list a b))
((or `(,a ,b ,c) `[,a ,b ,c]) (list a b c))))))
(list (funcall fun 1 2)
(funcall fun 1 2 3))))
(mu-bench "mu-lambda"
(let ((fun (mu _
([a b] (list a b))
([a b c] (list a b c)))))
(list (funcall fun 1 2)
(funcall fun 1 2 3)))))| Form | x slower | Total time | GCs | GC time | Timestamp |
|---|---|---|---|---|---|
| mu-lambda | 1.00 | 0.003206 | 0 | 0.000000 | Sun Dec 30 11:49:27 2018 |
| lambda | 1.19 | 0.003807 | 0 | 0.000000 | Sun Dec 30 11:49:27 2018 |
| Form | x slower | Total time | GCs | GC time | Timestamp |
| mu-lambda | 1.00 | 0.003443 | 0 | 0.000000 | Thu Dec 27 08:50:05 2018 |
| lambda | 1.01 | 0.003485 | 0 | 0.000000 | Thu Dec 27 08:50:05 2018 |
Benchmarks to track perf improvements and spot regressions. Ideally we should cover a wide variaty of patterns in every API bell-n-whistle we expose.
(mu-bench
(mapcar
(lambda (arg)
(mu-case arg
((lst) 0)
((lst _) 1)
((lst _ _) 2)
((lst _ _ _) 3)
(otherwise 'many)))
'(() (1) (1 2) (1 2 3) (1 2 3 4))))| Total time | GCs | GC time | Timestamp |
|---|---|---|---|
| 0.007033 | 0 | 0.0 | Thu Dec 27 08:50:55 2018 |
(mu-bench
(mapcar
(lambda (arg)
(mu-case arg
([[a &rest [[b c]]] &rest d] (list a b c d))))
(list '((1 (2 3)) 4) [[1 [2 3]] 4])))| Total time | GCs | GC time | Timestamp |
|---|---|---|---|
| 0.255855 | 0 | 0.0 | Thu Dec 27 08:51:25 2018 |
Load multi-methods
(load-file "multi-methods.el")As a running example we’ll be using the following global hierachy:
:dot -> :square -> :rect *-> :shape
| ^
| |
*-> :parallelogram *-> :multiangle
captured in the following function:
(defsubst mu--bench-reset-hierachy ()
;; reset global hierarchy
(setq mu-global-hierarchy (make-mu-hierarchy))
;; install new relations
(mu-rel :dot isa :square)
(mu-rel :rect isa :shape)
(mu-rel :square isa :rect)
(mu-rel :square isa :parallelogram)
(mu-rel :parallelogram isa :multiangle)
(mu-rel :parallelogram isa :shape))TODO I think I’m testing the interpreted code here. I need the “dispatch” be byte-compiled and running byte-code. Both the user-install foo-dispatcher and my mu-method lookup. I guess this means I want to (byte-compile #’foo-test)?
multimethods vs generic dispatch
(mu-bench/context
;; benchmark
(mu-bench*/let ((s0 (make-foo-struct-0))
(s1 (make-foo-struct-1))
(s2 (make-foo-struct-2))
(s3 (make-foo-struct-3))
(s4 (make-foo-struct-4))
(s5 (make-foo-struct-5))
(s6 (make-foo-struct-6)))
:times 1000
:compare t
(mu-bench "generic"
(foo-struct-test s0)
(foo-struct-test s1)
(foo-struct-test s2)
(foo-struct-test s3)
(foo-struct-test s4)
(foo-struct-test s5)
(foo-struct-test s6))
(mu-bench "multi"
(foo-test s0)
(foo-test s1)
(foo-test s2)
(foo-test s3)
(foo-test s4)
(foo-test s5)
(foo-test s6)))
;; context
(cl-defstruct foo-struct-0)
(cl-defstruct foo-struct-1)
(cl-defstruct foo-struct-2)
(cl-defstruct foo-struct-3)
(cl-defstruct foo-struct-4)
(cl-defstruct foo-struct-5)
(cl-defstruct foo-struct-6)
;; multi
(mu-defmulti foo-test #'type-of)
(mu-defmethod foo-test (x) :when 'foo-struct-1 1)
(mu-defmethod foo-test (x) :when 'foo-struct-2 2)
(mu-defmethod foo-test (x) :when 'foo-struct-3 3)
(mu-defmethod foo-test (x) :when 'foo-struct-4 4)
(mu-defmethod foo-test (x) :when 'foo-struct-5 5)
(mu-defmethod foo-test (x) :when 'foo-struct-6 6)
(mu-defmethod foo-test (x) :when :default 0)
;; generic
(cl-defgeneric foo-struct-test (s) 0)
(cl-defmethod foo-struct-test ((s foo-struct-1)) 1)
(cl-defmethod foo-struct-test ((s foo-struct-2)) 2)
(cl-defmethod foo-struct-test ((s foo-struct-3)) 3)
(cl-defmethod foo-struct-test ((s foo-struct-4)) 4)
(cl-defmethod foo-struct-test ((s foo-struct-5)) 5)
(cl-defmethod foo-struct-test ((s foo-struct-6)) 6))| Form | x slower | Total time | GCs | GC time | Timestamp |
|---|---|---|---|---|---|
| generic | 1.00 | 0.001680 | 0 | 0.000000 | Sun Dec 30 11:12:15 2018 |
| multi | 244.41 | 0.410613 | 2 | 0.210106 | Sun Dec 30 11:12:15 2018 |
| Form | x slower | Total time | GCs | GC time | Timestamp |
| :generic | 1.00 | 0.001652 | 0 | 0.000000 | Thu Dec 27 16:36:18 2018 |
| :mu-method | 237.57 | 0.392460 | 2 | 0.194683 | Thu Dec 27 16:36:18 2018 |
basic isa lookup
(mu--bench-reset-hierachy)
(mu-bench*
:times 1000
:compare t
(mu-bench "equal" (mu-isa? 42 42))
(mu-bench "direct" (mu-isa? :rect :shape))
(mu-bench "indirect" (mu-isa? :square :shape))
(mu-bench "seq1" (mu-isa? [:square :rect] [:rect :shape]))
(mu-bench "seq2" (mu-isa? [:square :shape] [:rect :shape]))
(mu-bench "nested" (mu-isa? [[:dot :parallelogram] :square] [[:shape :multiangle] :rect])))| Form | x slower | Total time | GCs | GC time | Timestamp |
|---|---|---|---|---|---|
| equal | 1.00 | 0.000603 | 0 | 0.000000 | Sun Dec 30 11:13:09 2018 |
| indirect | 6.82 | 0.004114 | 0 | 0.000000 | Sun Dec 30 11:13:09 2018 |
| direct | 6.89 | 0.004154 | 0 | 0.000000 | Sun Dec 30 11:13:09 2018 |
| seq2 | 12.86 | 0.007752 | 0 | 0.000000 | Sun Dec 30 11:13:09 2018 |
| seq1 | 18.04 | 0.010876 | 0 | 0.000000 | Sun Dec 30 11:13:09 2018 |
| nested | 28.42 | 0.017139 | 0 | 0.000000 | Sun Dec 30 11:13:09 2018 |
| Form | x slower | Total time | GCs | GC time | Timestamp |
| :equal | 1.00 | 0.000477 | 0 | 0.000000 | Thu Dec 27 11:45:38 2018 |
| :direct | 7.61 | 0.003632 | 0 | 0.000000 | Thu Dec 27 11:45:38 2018 |
| :indirect | 8.75 | 0.004175 | 0 | 0.000000 | Thu Dec 27 11:45:38 2018 |
| :seq2 | 15.37 | 0.007332 | 0 | 0.000000 | Thu Dec 27 11:45:38 2018 |
| :seq1 | 22.34 | 0.010657 | 0 | 0.000000 | Thu Dec 27 11:45:38 2018 |
| :nested | 42.18 | 0.020122 | 0 | 0.000000 | Thu Dec 27 11:45:38 2018 |
dispatch on equality - no deep isa hierarchy traversal
(mu-bench/context
;; benchmark
(mu-bench*
:times 1000
:compare t
(mu-bench "a" (foo :a))
(mu-bench "b" (foo :b))
(mu-bench "a-a" (foo :a :a))
(mu-bench "b-b" (foo :a :b)))
;; context
(mu-defmulti foo (lambda (&rest args) (apply #'vector args)))
(mu-defmethod foo (&rest x) :when [:a] :a)
(mu-defmethod foo (&rest x) :when [:b] :b)
(mu-defmethod foo (&rest x) :when [:a :a] :a)
(mu-defmethod foo (&rest x) :when [:a :b] :b))| Form | x slower | Total time | GCs | GC time | Timestamp |
|---|---|---|---|---|---|
| a | 1.00 | 0.017098 | 0 | 0.000000 | Sun Dec 30 11:14:02 2018 |
| b | 1.10 | 0.018743 | 0 | 0.000000 | Sun Dec 30 11:14:02 2018 |
| b-b | 1.10 | 0.018848 | 0 | 0.000000 | Sun Dec 30 11:14:02 2018 |
| a-a | 1.12 | 0.019098 | 0 | 0.000000 | Sun Dec 30 11:14:02 2018 |
| Form | x slower | Total time | GCs | GC time | Timestamp |
| :b | 1.00 | 0.017638 | 0 | 0.000000 | Thu Dec 27 16:38:10 2018 |
| :a | 1.02 | 0.017966 | 0 | 0.000000 | Thu Dec 27 16:38:10 2018 |
| :b-b | 1.04 | 0.018348 | 0 | 0.000000 | Thu Dec 27 16:38:10 2018 |
| :a-a | 1.05 | 0.018576 | 0 | 0.000000 | Thu Dec 27 16:38:10 2018 |
Hierarchies are rarely used, so most cache benefit comes from avoiding to isa with every registered method (0-20 in this example). The more methods we register the more overhead choosing the one becomes. Keep in mind: cache may overflow if most of the time you go to the :default method, so need to think of cache excision eventually.
(mu-defmulti foo #'identity)
(mu-defmethod foo (&rest args) :when 0 0)
(mu-defmethod foo (&rest args) :when 1 1)
(mu-defmethod foo (&rest args) :when 2 2)
(mu-defmethod foo (&rest args) :when 3 3)
(mu-defmethod foo (&rest args) :when 4 4)
(mu-defmethod foo (&rest args) :when 5 5)
(mu-defmethod foo (&rest args) :when 6 6)
(mu-defmethod foo (&rest args) :when 7 7)
(mu-defmethod foo (&rest args) :when 8 8)
(mu-defmethod foo (&rest args) :when 9 9)
(mu-defmethod foo (&rest args) :when 10 10)
(mu-defmethod foo (&rest args) :when 11 11)
(mu-defmethod foo (&rest args) :when 12 12)
(mu-defmethod foo (&rest args) :when 13 13)
(mu-defmethod foo (&rest args) :when 14 14)
(mu-defmethod foo (&rest args) :when 15 15)
(mu-defmethod foo (&rest args) :when 16 16)
(mu-defmethod foo (&rest args) :when 17 17)
(mu-defmethod foo (&rest args) :when 18 18)
(mu-defmethod foo (&rest args) :when 19 19)
(mu-defmethod foo (&rest args) :when 20 20)
(mu-bench/let ((random20 (byte-compile (lambda () (random 21)))))
(foo (funcall random20)))| Form | Total time | GCs | GC time | Timestamp |
|---|---|---|---|---|
| _ | 1.442045 | 7 | 0.7474569999999403 | Sun Dec 30 11:30:35 2018 |