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

[João Távora]

Dmitry Gutov <dmitry@gutov.dev> writes:

>> More importantly, there's an important takeaway here.  Your
>> results seem to show that regardless of the alternative (cl-lib
>> or hand-rolled) the solution with Emacs's current recommended
>> sequence processing library is nearly 6 times slower in a
>> real-world use-case.
>
> Note that it's still the difference for the case where the "business
> logic" (the filtering predicate or whatever) doesn't do
> anything.

OK.  So can you provide an even more realistic case?

> Although certain order-of-magnitude differences are worrying.

You can say that again...  I optimized cl-nset-difference considerably
more.  In the process also found your handrolled version can be sped
up considerably.  Have a look at this:

   (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 (list1 list2)
      (delq 'wrong
            (mapcar
             (lambda (c) (if (member c list2)
                        'wrong
                      c))
             list1)))
    
   (setq cc (all-completions "" obarray))
   (setq list2 (make-list 12 "shooveedoowaa"))
    
   (when nil
     ;; FASTEST (0.074594068 0 0.0)
     (benchmark-run 10 (setq cc (joaot/handrolled-nset-difference cc list2)))
    
     ;; FASTEST (0.070370948 0 0.0)
     (benchmark-run 10 (setq cc (cl-nset-difference cc list2 :test #'equal)))
    
     ;; 1.8x SLOWER (0.138797637 1 0.06212087500000507)
     (benchmark-run 10 (cl-set-difference cc list2 :test #'equal))
    
     ;; 3.2x SLOWER (0.22628817199999998 2 0.13694317399999534)
     (benchmark-run 10 (dmitry/set-difference cc list2))
    
     ;; 18x SLOWER  (1.29373404 12 0.7763814810000014) 
     (benchmark-run 10 (seq-difference cc list2 #'equal))
    
     )

Yes, that's _eighteen_.

All my work, including the docstring overhauls Alan requested and some
new tests, now in branch feature/cl-lib-improvements.

>> Maybe seq.el can be made faster too?  Who knows, but it seems
>> difficult without breaking at least some of its defgeneric-based
>> contract.
>
> I was wondering whether you tried looking into seq.el's performance
> problems. It being slower on shorter lists is quite expected: if the
> type dispatch has non-negligible overhead, that should be most
> noticeable when the rest of the work is small.
>
> 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.

Another thing I noticed is that recently cl-lib.el started depending on
seql.el, in its implementation.  Given what I've been seeing, this tells
me there's more low-hanging fruit to optimize in cl-lib.el.

João