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

[Dmitry Gutov <dmitry@gutov.dev>]

On 13/11/2023 03:03, João Távora wrote:
> 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?

Probably not. Not sure which big users of cl-lib we can find in the 
core: comp.el uses it, but mostly for the 'loop' macro.

Anyway, my point was these benchmarks are very good for improving each 
of the libs, but not necessarily for making the ultimate choice between 
them (if we really had to).

>> 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))
>      
>       )

All right, time to roll out the big guns. For your attention, ladies and 
gentlemen, a version in pure, unadulterated Elisp, extracted from my 
unused patch of two weeks ago (https://debbugs.gnu.org/66806#17):

(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))

And the benchmarks (we're so fast, 100 iterations for stable numbers):

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

   ;; (0.9393577359999999 16 0.5063504589999965) NO COMMENTS
   (benchmark-run 100 (dmitry/set-difference cc list2))

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

Anyway, it's pretty cool to have cl-nset-difference so "down to the metal".

Although I'm not sure if we should be worried that the funcall overhead 
makes basically no difference (e.g. if I inline the funcall in 
joaot/handrolled-nset-difference). I think it's been said that our 
funcalls are relatively slow.

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

Nice.

>>> 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.

I hope someone will. And agree about destructive versions.

> 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.

Stefan moved a bunch of code there in 2019 (0e4dd67aae8b1003).

Good example to try and see if this actually made anything slower.