On Sat, Nov 11, 2023 at 9:49 PM Dmitry Gutov <dmitry@gutov.dev> wrote:
>
> On 11/11/2023 20:07, Gerd Möllmann wrote:
> > Seq is 10 years in Emacs, its polymorphism is unused in the tree. Joao
> > showed that it's slow. Dmitry mentioned that it is not a full
> > replacement for what is in cl-lib.
>
> FWIW, it doesn't seem to me that seq's dynamic dispatch is the main part
> of what makes it "slow" in a number of cases.

Indeed I don't know if dynamic dispatch is the main culprit, but
my measurements show that calling cl-some lots of times on
small lists specifically yields much worse performance than cl-some.

In larger lists, the difference is attenuated.  So that's why
I conjectured that dynamic dispatch played a role, but I
didn't check.

Now that you mention set difference, I find this:

(when nil
  (let ((l2 '(4 5 6 7)))
    (benchmark-run 100000
      (let ((l (list 1 2 3 4 8 9 10 11 12 13 14)))
        (cl-set-difference l l2))))(0.5964884789999999 20 0.38926870999999996)


  (let ((l2 '(4 5 6 7)))
    (benchmark-run 100000
      (let ((l (list 1 2 3 4 8 9 10 11 12 13 14)))
        (cl-nset-difference l l2))))(0.594109028 20 0.37972229299999993)


  (let ((l2 '(4 5 6 7)))
    (benchmark-run 100000
      (let ((l (list 1 2 3 4 8 9 10 11 12 13 14)))
        (seq-difference l l2))))(3.087290361 102 2.020063915)

Eli thinks this doesn't really show seq.el is slower than cl-lib.el
and that may be half-true: it just shows how it is slower in this
micro-benchmark.

But you seem to have a real-world measurable case, which is
of course better, so I'm curious.

> cl-lib is not that well-optimized either.

That's certainly true.  I've been looking at the code and there
are some serious optimization opportunities in cl-lib.el.  The
one you found right away, destructive versions delegating to
overconsing non-destructive ones, but also other opportunities.

I attach a patch that I hope you can try with that bug report.
Very lightly tested here, but seems to show a measurable
improvement.

(when nil
  (let ((l2 '(4 5 6 7)))
    (benchmark-run 100000
      (let ((l (list 1 2 3 4 8 9 10 11 12 13 14)))
        (cl-set-difference l l2))));; (0.480944603 8 0.3380962310000015)

  (let ((l2 '(4 5 6 7)))
    (benchmark-run 100000
      (let ((l (list 1 2 3 4 8 9 10 11 12 13 14)))
        (cl-nset-difference l l2))));; (0.31953939800000003 5
0.21426147399999707)

  (let ((l2 '(4 5 6 7)))
    (benchmark-run 100000
      (let ((l (list 1 2 3 4 8 9 10 11 12 13 14)))
        (seq-difference l l2)))) ;; (2.3330953689999996 41 1.8175730390000027)
  )

João