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

[João Távora]

On Sun, Nov 12, 2023 at 11:22 AM Eli Zaretskii <eliz@gnu.org> wrote:

> > 1. I posted some micro-benchmarks about cl-some and seq-some.
> > 2. Gerd wrote "Joao showed that it's slow.".
> > 3. You replied, directly below  "No, he didn't.".
> >
> > Now you say I misquoted you.  Hope to have rectified that.
> >
> > So you _do_ think this shows seq.el is slower than cl-lib.el?
>
> I believe I explained the issue in another message.  It has to do with
> the (significant in this case) difference between "slower" and "slow".
> I responded to "slow", whereas you said I disagreed with "slower".

That's clear now, thanks.  I read that email as well.

I agree things can never be taken in absolute terms, and one
has to consider specific jobs.

However, I think it is even more important to note that to
have any useful statement regarding the efficiency  -- relative
or absolute -- of any library, that statement should be falsifiable.
For statements like "micro-benchmark X doesn't matter in the common
case" to be useful we need to characterize the "common case"
well, because if we don't they're not falsifiable.

So I hope that in this discussion we can eventually come up with
some characterization of this "common case". so that we can
design experiments around it. I think performance, despite not being
the sole one, is an important consideration in this discussion.

IME sequence-processing ability and efficiency does play a very
significant role in determining the performance of certain
Lisp programs (including Common Lisp, of course).  This is so
especially when garbage generation is involved.

In certain Common Lisp implementations with more advanced
multi-generational garbage collectors, the results are sometimes
counter-intuitive: generating lots of fast-to-scavenge garbage
ends up being better than long-lived slow-to-scavenge
garbage).  But in Elisp at least, it seems garbage is always bad.

Destructive versions of sequence-processing functions are
in that respect very useful.  cl-lib.el has them but it seems
many of them are missing low-hanging optimization opportunities.
However I worked on that in another patch and it seems to have
provided a good speedup (in micro-benchmarks).  Let's see what
Dmitry comes up with when he takes them to a real-world case.

> Sometimes much slower, sometimes slightly slower (and in at least
> one case faster).

Anyway, I took the "cl-some vs seq-some" measurements again, after
applying this simple patch that I attach after my sig.  The summary:

Small lists:
  cl-some fastest
  seq-some 5.7 times slower, garbage collects

Big lists
  cl-some fastest
  seq-some 1.6 times slower

Small vectors:
  cl-some fastest
  seq-some 5.13 times slower, garbage collects

Big vectors
  cl-some fastest
  seq-some 1.27 times slower

The "in one case faster" is gone.  Also interesting is the
garbage generation footprint of seq.el functions in their current
form.

I'm not sure we can easily dismiss the "small seqs/tight loop" 5x
slowdown that seq.el exhibits in this microbenchmark, because as you
can see in the benchmark detail there's a lot of garbage generation
involved.  So even if the tight loop were to go away, that garbage
would pile up.  I also think that tight sequence-processing loops
are not all that uncommon in Elisp programs.  Finally, a program
may not use these tight loops but do lots of different sequence
processing functions: if it selects slow abstractions for all of
them, it ends up being just as if there was a tight loop.

But as I wrote above  it is best if we find real-world applications
to benchmark the two approaches.  Maybe someone else reading this
can help find one or two.

João


First the benchmarks in full:

(require 'cl-lib)

(defun bench-seq-some (seq)
  (seq-some #'identity seq))

(defun bench-cl-some (seq)
  (cl-some #'identity seq))

(defun bench-cl-loop-list (l)
  ;; checks for some types of improper lists
  (cl-loop for e in l thereis (identity e)))

(defun bench-cl-loop-vec (v)
  (cl-loop for e across v thereis (identity e)))


(when nil
  ;; Small lists
  (let ((l (list nil nil nil nil t)))
    ;; FASTEST (0.23516409500000002 0 0.0)
    (benchmark-run 1000000 (bench-cl-some l)))


  (let ((l (list nil nil nil nil t)))
     ;; 5.7x SLOWER (1.338184149 16 0.8307866220000051)
    (benchmark-run 1000000 (bench-seq-some l)))


  (let ((l (list nil nil nil nil t)))
     ;; 1.14x SLOWER (0.26885113699999996 0 0.0)
    (benchmark-run 1000000 (bench-cl-loop-list l)))


  ;; Big lists
  (let ((l (make-list 10000000 nil)))
    ;; FASTEST (0.266716895 0 0.0)
    (benchmark-run 1 (bench-cl-some l)))


  (let ((l (make-list 10000000 nil)))
    ;; 1.6x SLOWER (0.428996694 0 0.0)
    (benchmark-run 1 (bench-seq-some l)))


  (let ((l (make-list 10000000 nil)))
    ;; 1.05x SLOWER (0.279309231 0 0.0)
    (benchmark-run 1 (bench-cl-loop-list l)))


  ;; Small vectors
  (let ((v (vector nil nil nil nil t)))
    ;; FASTEST (0.257238335 0 0.0)
    (benchmark-run 1000000 (bench-cl-some v)))


  (let ((v (vector nil nil nil nil t)))
    ;; 5.13x SLOWER (1.317641304 16 0.8448574659999935)
    (benchmark-run 1000000 (bench-seq-some v)))


  (let ((v (vector nil nil nil nil t)))
    ;; 1.14x SLOWER (0.29413928100000003 0 0.0)
    (benchmark-run 1000000 (bench-cl-loop-vec v)))


  ;; Big vectors
  (let ((v (make-vector 10000000 nil)))
    ;; FASTEST (0.316211001 0 0.0)
    (benchmark-run 1 (bench-cl-some v)))


  (let ((v (make-vector 10000000 nil)))
    ;; 1.27x SLOWER (0.40362057500000004 0 0.0)
    (benchmark-run 1 (bench-seq-some v)))


  (let ((v (make-vector 10000000 nil)))
    ;; 1.11x SLOWER
    (benchmark-run 1 (bench-cl-loop-vec v)))

  )

And here's the patch I used to make cl-some faster for
the common case of only one non-list sequence passed.

diff --git a/lisp/emacs-lisp/cl-extra.el b/lisp/emacs-lisp/cl-extra.el
index 2ca2d03170a..7c09328eda5 100644
--- a/lisp/emacs-lisp/cl-extra.el
+++ b/lisp/emacs-lisp/cl-extra.el
@@ -206,16 +206,26 @@ cl-some
 non-nil value.

 \n(fn PREDICATE SEQ...)"
-  (if (or cl-rest (nlistp cl-seq))
-      (catch 'cl-some
-        (apply #'cl-map nil
-               (lambda (&rest cl-x)
-                 (let ((cl-res (apply cl-pred cl-x)))
-                   (if cl-res (throw 'cl-some cl-res))))
-       cl-seq cl-rest) nil)
-    (let ((cl-x nil))
-      (while (and cl-seq (not (setq cl-x (funcall cl-pred (pop cl-seq))))))
-      cl-x)))
+  (cond
+   (cl-rest
+    (catch 'cl-some
+      (apply #'cl-map nil
+             (lambda (&rest cl-x)
+               (let ((cl-res (apply cl-pred cl-x)))
+                 (if cl-res (throw 'cl-some cl-res))))
+             cl-seq cl-rest) nil))
+   ((nlistp cl-seq)
+    (let ((cl-x nil)
+          (l (length cl-seq))
+          (i 0))
+      (while (and (< i l)
+                  (prog1 (not (setq cl-x (funcall cl-pred
+                                                  (aref cl-seq i))))
+                    (cl-incf i))))
+      cl-x))
+   (t (let ((cl-x nil))
+        (while (and cl-seq (not (setq cl-x (funcall cl-pred (pop cl-seq))))))
+        cl-x))))

 ;;;###autoload
 (defun cl-every (cl-pred cl-seq &rest cl-rest)