Re: What's missing in ELisp that makes people want to use cl-lib?

[Dmitry Gutov <dmitry@gutov.dev>]

[-- Attachment #1: Type: text/plain, Size: 4516 bytes --]

On 13/11/2023 04:43, Dmitry Gutov wrote:
>>> The case with longer lists and other data structures should be
>>> possible to improve, though. As long as the type dispatch only happens
>>> once per sequence, and not for each element.
>>
>> Maybe it's possible.  But there are two things here: first, you need
>> non-destructive versions of things in seq.el, because consing is always
>> a killer.  Second, the generic function interface means the typical
>> shortcuts I applied in cl-lib.el are difficult.  Maybe even impossible
>> without breaking the current contract?  I don't know the contract well
>> enough to tell.  At any rate seems like non-trivial work, but I'm happy
>> if someone can give it a shot.
> 
> I hope someone will. And agree about destructive versions.

Here's an experimental patch that makes seq-difference about as fast as 
your new improved non-destructive cl-set-difference. And some notes.

First of all, the type dispatch _does_ happen more than once per 
sequence in the current master. That doesn't seem to hurt much while the 
method is not specialized (only has the default implementation), but has 
impact as soon as the function gets additional method definitions.

Second, the seq-reduce implementations for the set functions don't seem 
optimal. So, check out the attached with the below continued benchmark:

(defun joaot/handrolled-nset-difference (list1 list2)
   (if (or (null list1) (null list2)) list1
     (let ((res nil))
       (while (consp list1)
         (if (funcall #'member (car list1) list2)
             (setf list1 (cdr list1))
           (cl-shiftf list1 (cdr list1) res list1)))
       res)))

(defun dmitry/set-difference-nocons (list1 list2)
   (let (ref)
     (while (member (car list1) list2)
       (setq list1 (cdr list1)))
     (setq ref list1)
     (while ref
       (if (member (cadr ref) list2)
           (setcdr ref (cddr ref))
         (setq ref (cdr ref))))
     list1))

(setq cc (all-completions "" obarray))
(setq list2 (make-list 12 "shooveedoowaa"))

(when nil
   ;; (0.38175291299999997 0 0.0)
   (benchmark-run 100 (setq cc (joaot/handrolled-nset-difference cc list2)))

   ;; (0.345876673 0 0.0)
   (benchmark-run 100 (dmitry/set-difference-nocons cc list2))

   ;; (1.2209711170000002 38 0.7669010760000001)
   (benchmark-run 100 (cl-set-difference cc list2 :test #'equal))

   ;; (2.10207541 67 1.410268502) NOT THE FASTEST
   (benchmark-run 100 (seq-difference cc list2))

   ;; (1.3434452970000001 33 0.7025866390000006)
   (benchmark-run 100 (seq-difference-2 cc list2))

   ;; (1.243865238 34 0.7060731869999994)
   (benchmark-run 100 (seq-difference-3 cc list2))
   )

seq-difference is the original implementation based on seq-reduce. It's 
much faster here, though, because of the change to seq-contains-p which 
teaches it to use 'member' when it can.

seq-difference-2 is an implementation that just switched to using 
seq-filter.

And seq-difference-3 is the one that makes sure the type dispatch 
happens only once (or twice), and not for every element in SEQUENCE1. 
For that, I defined a new generic seq-contains-pred which returns a 
function.

seq-difference-3 is the fastest among the last three and is about the 
speed of the cl-lib's variant.

The plot twist is that when I tried to extract the sequence type check 
into a separate method (see the commented out "cl-defmethod 
seq-contains-p" line), the performance of seq-difference and 
seq-difference-2 fell by an order of a magnitude (2s -> 9s). So it seems 
like using the new seq-contains-pred is the one way that would keep 
decent performance while supporting generic extensions.

The latter also means all current uses of seq-contains-p inside seq.el 
should be rewritten using seq-contains-pred.

As for seq-some, 1.27x or 1.6x slower for the identity predicate doesn't 
look as bad in comparison. Especially for an implementation this short 
and generic. It incurs an extra funcall in Lisp through the use in 
'seq-doseq', so that might be the cost. It should be easy to add a 
specialization for lists while still keeping the code shorter than 
cl-some, if one were so inclined. Would be cooler to find a more generic 
bottleneck like in the case above, but so far, no luck.

And in other interesting functions, cl-remove-if-not is about 4x faster 
than seq-filter in the best case (e.g. the list is not modified), but 
about the same in the worst case (when the last link is removed). There 
must be some shortcut there too which could be reproduced.

[-- Attachment #2: seq-difference.diff --]
[-- Type: text/x-patch, Size: 2979 bytes --]

diff --git a/lisp/emacs-lisp/seq.el b/lisp/emacs-lisp/seq.el
index 346250c1d35..6869f498e43 100644
--- a/lisp/emacs-lisp/seq.el
+++ b/lisp/emacs-lisp/seq.el
@@ -440,12 +440,43 @@ seq-contains
 (cl-defgeneric seq-contains-p (sequence elt &optional testfn)
   "Return non-nil if SEQUENCE contains an element \"equal\" to ELT.
 \"Equality\" is defined by the function TESTFN, which defaults to `equal'."
+  (cond
+   ((and (listp sequence) (or (null testfn) (eq testfn 'equal)))
+    (member elt sequence))
+   ((and (listp sequence) (eq testfn 'eq))
+    (memq elt sequence))
+   (t
     (catch 'seq--break
-      (seq-doseq (e sequence)
-        (let ((r (funcall (or testfn #'equal) e elt)))
-          (when r
-            (throw 'seq--break r))))
-      nil))
+    (seq-doseq (e sequence)
+      (let ((r (funcall (or testfn #'equal) e elt)))
+        (when r
+          (throw 'seq--break r))))
+    nil)))
+  )
+
+;; (cl-defmethod seq-contains-p ((sequence list) elt &optional testfn)
+;;   (cond
+;;    ((or (null testfn) (eq testfn 'equal))
+;;     (member elt sequence))
+;;    ((eq testfn 'eq)
+;;     (memq elt sequence))
+;;    (t
+;;     (cl-call-next-method))))
+
+(cl-defgeneric seq-contains-pred (_sequence &optional testfn)
+  (cond
+   ((or (null testfn) (eq testfn 'equal))
+    #'member)
+   ((eq testfn 'eq)
+    #'memq)
+   (t
+    (lambda (elt sequence)
+      (catch 'seq--break
+        (seq-doseq (e sequence)
+          (let ((r (funcall testfn e elt)))
+            (when r
+              (throw 'seq--break r))))
+        nil)))))
 
 (cl-defgeneric seq-set-equal-p (sequence1 sequence2 &optional testfn)
   "Return non-nil if SEQUENCE1 and SEQUENCE2 contain the same elements.
@@ -488,9 +519,10 @@ seq-positions
 (cl-defgeneric seq-uniq (sequence &optional testfn)
   "Return a list of the elements of SEQUENCE with duplicates removed.
 TESTFN is used to compare elements, and defaults to `equal'."
-  (let ((result '()))
+  (let ((result '())
+        (pred (seq-contains-pred testfn)))
     (seq-doseq (elt sequence)
-      (unless (seq-contains-p result elt testfn)
+      (unless (funcall pred elt result)
         (setq result (cons elt result))))
     (nreverse result)))
 
@@ -574,6 +606,20 @@ seq-difference
               (seq-reverse sequence1)
               '()))
 
+(cl-defgeneric seq-difference-2 (sequence1 sequence2 &optional testfn)
+  "Return list of all the elements that appear in SEQUENCE1 but not in SEQUENCE2.
+\"Equality\" of elements is defined by the function TESTFN, which
+defaults to `equal'."
+  (seq-filter
+   (lambda (elt) (not (seq-contains-p sequence2 elt testfn)))
+   sequence1))
+
+(cl-defgeneric seq-difference-3 (sequence1 sequence2 &optional testfn)
+  (let ((pred (seq-contains-pred sequence2 testfn)))
+    (seq-filter
+     (lambda (elt) (not (funcall pred elt sequence2)))
+     sequence1)))
+
 ;;;###autoload
 (cl-defgeneric seq-group-by (function sequence)
   "Apply FUNCTION to each element of SEQUENCE.