Does the order in which I define defmethods play a role in performance?
Is it guaranteed that the first definition is tested for parameter type match first?
My mind-model of defmethod is, that it behaves like a cond where the first case is tested first and when the types of the parameters don't match, it jumps to the next.
(defstruct a)
(defstruct b)
(defun m (X)
(cond ((typep X 'a) ...)
((typep X 'b) ...)))
If I know that the first case occurs most frequently in my application, then I include this case as the first in cond. So, during runtime I expect to squeeze a little performace out of the order of the cond test cases.
Is it the same with defmethod.
Example: I define methods like this:
(defmethod m ((X a)) ...)
(defmethod m ((X b)) ...)
(defmethod m ((X other)) ...)
OR like that:
(defmethod m ((X b)) ...)
(defmethod m ((X other)) ...)
(defmethod m ((X a)) ...)
Because i expect my application to have lot more as than bs, this could change the performance because Common Lisp has to check the arguments and decide which method to use.
Is my mind model correct?
My concrete application example:
I have an AST that consists of various nested structs. A compile branch function goes along the path in this nested structure. And there could be hundreds of "let" structs, but fewer "for" structs. (maybe)
EDIT: Added more detail to the question and give an concrete application example.
I would hope that CLOS does not use a linear search to find a method. That would be slow.
Imagine if you want to speed up your code, which currently uses cond. Here follows a rough idea:
The structures:
(defstruct a)
(defstruct b)
(defstruct c)
(defstruct d)
(defstruct e)
(defstruct f)
(defstruct g)
(defstruct h)
(defstruct i)
(defstruct j)
(defstruct k)
now we need a table from structure name to function:
(defparameter *x-table*
(make-hash-table))
We memoize the function (which wraps the to be executed code) for each type-name. The FORMAT is only for demonstration, one would add there the code for each type specific clause. On first call it creates the memo entry, then calls itself again, where it then will find the memo entry and call it.
(defun faster-m (x &aux (f (gethash (type-of x) *x-table*)))
(if f
(progn
(print `(type-of ,x found in memo table - calling function ,f))
(funcall f))
(progn
(print `(type-of ,x not found in memo table - saving))
(setf (gethash (type-of x) *x-table*)
(typecase x
(a (lambda () (format nil "struct a")))
(b (lambda () (format nil "struct b")))
(c (lambda () (format nil "struct c")))
(d (lambda () (format nil "struct d")))
(e (lambda () (format nil "struct e")))
(f (lambda () (format nil "struct f")))
(g (lambda () (format nil "struct g")))
(h (lambda () (format nil "struct h")))
(i (lambda () (format nil "struct i")))
(j (lambda () (format nil "struct j")))
(k (lambda () (format nil "struct k")))))
(faster-m x))))
Let's see, first time it does not find the entry directly, it creates it and calls itself again. Then the code if found and called.
CL-USER 119 > (faster-m (make-e))
(TYPE-OF #S(E) NOT FOUND IN MEMO TABLE - SAVING)
(TYPE-OF #S(E) FOUND IN MEMO TABLE - CALLING FUNCTION
#<Function 5 subfunction of FASTER-M 8020001079>)
"struct e"
Next time it is only a hash table lookup and not a linear search:
CL-USER 120 > (faster-m (make-e))
(TYPE-OF #S(E) FOUND IN MEMO TABLE - CALLING FUNCTION
#<Function 5 subfunction of FASTER-M 8020001079>)
"struct e"
CL-USER 121 > (faster-m (make-e))
(TYPE-OF #S(E) FOUND IN MEMO TABLE - CALLING FUNCTION
#<Function 5 subfunction of FASTER-M 8020001079>)
"struct e"
CLOS implementations will do something similar for generic function dispatch. Possibly: Each generic function will memoize the classes for the arguments and the matching method.
Then the linear order of definitions will make no difference. Matching functions will be looked up in a hash table. Then there should not be a speed difference based on definition order.