ccl
ccl copied to clipboard
Clozure
(member x '(a b c)) uses eql test instead of eq
As a simple performance optimization, calling member with a list of symbols should always use eq as the test (better performance), but CCL uses eql. The following example shows how the functions f (using just member) and g (using :test #'eq) are compiled differently.
? (defun f (x) (member x '(a b c)))
F
? (defun g (x) (member x '(a b c) :test #'eq))
G
? (disassemble 'f)
;;; (defun f (x) (member x '(a b c)))
(recover-fn-from-rip) ; [0]
(cmpl ($ 8) (% nargs)) ; [7]
(jne L53) ; [10]
(pushq (% rbp)) ; [12]
(movq (% rsp) (% rbp)) ; [13]
(pushq (% arg_z)) ; [16]
;;; (member x '(a b c))
(movq (@ -8 (% rbp)) (% arg_y)) ; [17]
;;; '(a b c)
(movq (@ '(A B C) (% fn)) (% arg_z)) ; [21]
;;; (member x '(a b c))
(movl ($ 16) (% nargs)) ; [28]
(movq (@ 'CCL::MEMEQL (% fn)) (% temp0)) ; [33]
(movq (% rbp) (% rsp)) ; [40]
(popq (% rbp)) ; [43]
(jmpq (@ 10 (% temp0))) ; [44]
;;; #<no source text>
(:align 2)
L53 ; [@68]
(uuo-error-wrong-number-of-args) ; [53]
NIL
? (disassemble 'g)
;;; (defun g (x) (member x '(a b c) :test #'eq))
(recover-fn-from-rip) ; [0]
(cmpl ($ 8) (% nargs)) ; [7]
(jne L97) ; [10]
(pushq (% rbp)) ; [12]
(movq (% rsp) (% rbp)) ; [13]
(pushq (% arg_z)) ; [16]
;;; '(a b c)
(pushq (@ '(A B C) (% fn))) ; [17]
;;; (member x '(a b c) :test #'eq)
(jmp L74) ; [24]
L26 ; [@41]
(movq (@ -16 (% rbp)) (% arg_z)) ; [26]
(movl (% arg_z.l) (% imm0.l)) ; [30]
(andl ($ 7) (% imm0.l)) ; [32]
(cmpl ($ 3) (% imm0.l)) ; [35]
(jne L105) ; [38]
(movq (@ 5 (% arg_z)) (% arg_y)) ; [40]
(movq (@ -8 (% rbp)) (% arg_x)) ; [44]
(cmpq (% arg_x) (% arg_y)) ; [48]
(jne L62) ; [51]
(movq (@ -16 (% rbp)) (% arg_z)) ; [53]
(movq (% rbp) (% rsp)) ; [57]
(popq (% rbp)) ; [60]
(retq) ; [61]
L62 ; [@77]
(movq (@ -16 (% rbp)) (% arg_z)) ; [62]
(movq (@ -3 (% arg_z)) (% arg_z)) ; [66]
(movq (% arg_z) (@ -16 (% rbp))) ; [70]
L74 ; [@89]
(cmpb ($ 11) (@ -16 (% rbp))) ; [74]
(jne L26) ; [78]
(movl ($ #x1300B) (% arg_z.l)) ; [80]
(movq (% rbp) (% rsp)) ; [85]
(popq (% rbp)) ; [88]
(retq) ; [89]
;;; #<no source text>
(:align 4)
L97 ; [@112]
(uuo-error-wrong-number-of-args) ; [97]
(:align 3)
L105 ; [@120]
(uuo-error-reg-not-list (% arg_z)) ; [105]
NIL
CCL defaults to #'eql because ANSI requires it.
https://www.lispworks.com/documentation/HyperSpec/Body/17_ba.htm
"If neither a :test nor a :test-not argument is supplied, it is as if a :test argument of #'eql was supplied."
Although it might be theoretically possible to optimize this when a list of symbols is involved, in that case #'member would have to check the entire list at runtime to ensure that #'eq would work, and that would be much more expensive than simply defaulting to #'eql. If the programmer knows the list will always contain symbols, they can always specify :test #'eq as you did above.
In the example above where the list of symbols is literally specified, it's probably possible for the compiler to do the optimization automatically--that sounds like what you're suggesting. But probably in the vast majority of cases, #'member won't be used on a literal list of symbols anyway, so I don't think such an optimization adds any real value over the programmer simply specifying :test #'eq.
Yes, my suggestion was related to literal lists of symbols (or a literal symbol as the first argument).
This actually occurs a lot in the Maxima Computer Algebra System, which supports CCL. It is used basically as a shorter way to write (or (eq ... ...) (eq ... ...) (eq ... ...) ...). Some time ago, :test #'eq has been mostly removed from the source because the developers argued that any modern Lisp compiler would see that either the first argument is a literal symbol or the second argument is a literal list of symbols and automatically use eq instead of eql. SBCL and others indeed do this.
This optimization should be relatively easy to implement, right? I'm quite sure that it would result in a noticeable speed-up for Maxima.
I dug into this a bit more.
If you look at the sourse for #'memeql, you'll see that it does check the first argument. If the first arg is a symbol, #'eq is used as the equality predicate.
(#'memeql uses #'need-use-eql-macro, which returns nil for symbols. You cannot meta-dot this macro since it's only present when CCL is being compiled, but the source is in the same file as #'memeql, which itself can be meta-dotted.)
The above is a runtime check. Note that in your function f, x is not a literal, so any check of the first arg has to happen at runtime. CCL appears not to be checking the second arg for literal-ness, however, except when both args are literals.
If you write the somewhat ridiculous function
(defun f-literal (x)
(member 'x '(a b c)))
it will throw a valid warning about x being unused, but if you disassemble it you'll see that it's doing no work at all because in this case both args are literals. This optimization appears not to be happening in the compiler-macro for #'member but somewhere earlier in the compiler chain where constant-folding happens.
Thus it appears that CCL is almost doing what the maxima authors expect. What's not happening is the compiler noticing that the second argument -- the list -- is a literal at compile-time and deciding to use the #'eq test then. That could probably be handled by modifying the compiler-macro for #'member in a similar manner to the compiler-macro for #'memeql, which does check the list for being a literal.
Before anybody spends time on this it would be nice to know if the runtime check of the first arg is fast enough in Maxima, and if the literal check of the second arg would really speed things up very much. In other words, do we really know this is a long pole in the tent for Maxima speed? Is it possible to re-insert :test #'eq into the appropriate places in Maxima and benchmark it, or are such places too numerous?