bug#57079: 29.0.50; Performance of seq-uniq is not very good

bug#57079: 29.0.50; Performance of seq-uniq is not very good

[Stefan Kangas]

Severity: minor

`seq-uniq' is not very performant compared to `-uniq' (from dash.el) and
even slower compared to the recently removed `gnus-delete-duplicates':

    (benchmark-run 10000 (seq-uniq '(a c b c c a d)))
    => (0.355001481 1 0.2518970439999748)

    (benchmark-run 10000 (-uniq '(a c b c c a d)))
    => (0.006599549 0 0.0)

    (benchmark-run 10000 (gnus-delete-duplicates '(a c b c c a d)))
    => (0.0034537929999999997 0 0.0)

Could we improve the performance of `seq-uniq' for lists?


PS. `gnus-delete-duplicates' was recently removed but looks like this:

    (defun gnus-delete-duplicates (list)
      "Remove duplicate entries from LIST."
      (let ((result nil))
        (while list
          (unless (member (car list) result)
    	(push (car list) result))
          (pop list))
        (nreverse result)))

bug#57079: 29.0.50; Performance of seq-uniq is not very good

[Eli Zaretskii]

> From: Stefan Kangas <stefan@marxist.se>
> Date: Tue, 9 Aug 2022 09:11:07 -0700
> 
> Severity: minor
> 
> `seq-uniq' is not very performant compared to `-uniq' (from dash.el) and
> even slower compared to the recently removed `gnus-delete-duplicates':
> 
>     (benchmark-run 10000 (seq-uniq '(a c b c c a d)))
>     => (0.355001481 1 0.2518970439999748)
> 
>     (benchmark-run 10000 (-uniq '(a c b c c a d)))
>     => (0.006599549 0 0.0)
> 
>     (benchmark-run 10000 (gnus-delete-duplicates '(a c b c c a d)))
>     => (0.0034537929999999997 0 0.0)
> 
> Could we improve the performance of `seq-uniq' for lists?

What's wrong with using delete-dups for your cases above?

bug#57079: 29.0.50; Performance of seq-uniq is not very good

[Lars Ingebrigtsen]

Eli Zaretskii <eliz@gnu.org> writes:

> What's wrong with using delete-dups for your cases above?

delete-dups is destructive.  You can copy the list first, of course, but
seq-uniq should be much faster than it is.

bug#57079: 29.0.50; Performance of seq-uniq is not very good

[Eli Zaretskii]

> From: Lars Ingebrigtsen <larsi@gnus.org>
> Cc: Stefan Kangas <stefan@marxist.se>,  57079@debbugs.gnu.org
> Date: Tue, 09 Aug 2022 18:57:33 +0200
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > What's wrong with using delete-dups for your cases above?
> 
> delete-dups is destructive.

No one said that was a problem in these cases.

bug#57079: 29.0.50; Performance of seq-uniq is not very good

[Lars Ingebrigtsen]

Eli Zaretskii <eliz@gnu.org> writes:

> No one said that was a problem in these cases.

I haven't audited the callers, but changing code that used to be
non-destructive to be destructive isn't to be taken lightly.

Anyway, I've now made seq-uniq faster.  This used to take 27 seconds,
and now takes 1.4s.

(let ((list (seq-map-indexed (lambda (_ i)
			       i)
			     (make-list 10000 nil))))
  (setq list (append list list))
  ;;(benchmark-run 10 (gnus-delete-duplicates list))
  (benchmark-run 10 (seq-uniq list))
  )

bug#57079: 29.0.50; Performance of seq-uniq is not very good

[Stefan Kangas]

Lars Ingebrigtsen <larsi@gnus.org> writes:

> Anyway, I've now made seq-uniq faster.  This used to take 27 seconds,
> and now takes 1.4s.

Thanks!

bug#57079: 29.0.50; Performance of seq-uniq is not very good

[Eli Zaretskii]

> From: Lars Ingebrigtsen <larsi@gnus.org>
> Cc: Stefan Kangas <stefan@marxist.se>,  57079@debbugs.gnu.org
> Date: Tue, 09 Aug 2022 18:57:33 +0200
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > What's wrong with using delete-dups for your cases above?
> 
> delete-dups is destructive.  You can copy the list first, of course, but
> seq-uniq should be much faster than it is.

How much faster?  Using copy-sequence and delete-dups is 7 times
faster here than seq-uniq and twice faster than
gnus-delete-duplicates.

bug#57079: 29.0.50; Performance of seq-uniq is not very good

[Lars Ingebrigtsen]

Eli Zaretskii <eliz@gnu.org> writes:

>> delete-dups is destructive.  You can copy the list first, of course, but
>> seq-uniq should be much faster than it is.
>
> How much faster?  Using copy-sequence and delete-dups is 7 times
> faster here than seq-uniq and twice faster than
> gnus-delete-duplicates.

I didn't claim that seq-uniq will be faster than copy + delete-dups; I
just said that it's unnecessarily slow.

bug#57079: 29.0.50; Performance of seq-uniq is not very good

[Eli Zaretskii]

> From: Lars Ingebrigtsen <larsi@gnus.org>
> Cc: stefan@marxist.se,  57079@debbugs.gnu.org
> Date: Tue, 09 Aug 2022 19:23:10 +0200
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> >> delete-dups is destructive.  You can copy the list first, of course, but
> >> seq-uniq should be much faster than it is.
> >
> > How much faster?  Using copy-sequence and delete-dups is 7 times
> > faster here than seq-uniq and twice faster than
> > gnus-delete-duplicates.
> 
> I didn't claim that seq-uniq will be faster than copy + delete-dups; I
> just said that it's unnecessarily slow.

But the above means that using seq-uniq with TESTFN nil is going to be
unnecessarily slow from the get-go.  People shouldn't use seq-uniq if
they don't need a non-default TESTFN, because much faster
implementations exist.

IOW, since this bug is about speed, not anything else, I think making
seq-uniq faster when TESTFN is nil isn't the right solution, the right
solution is to point out that seq-uniq's purpose in this case is not
to be a Speedy Gonzales.

bug#57079: 29.0.50; Performance of seq-uniq is not very good

[Eli Zaretskii]

> Cc: 57079@debbugs.gnu.org, stefan@marxist.se
> Date: Tue, 09 Aug 2022 20:36:34 +0300
> From: Eli Zaretskii <eliz@gnu.org>
> 
> But the above means that using seq-uniq with TESTFN nil is going to be
> unnecessarily slow from the get-go.  People shouldn't use seq-uniq if
> they don't need a non-default TESTFN, because much faster
> implementations exist.
> 
> IOW, since this bug is about speed, not anything else, I think making
> seq-uniq faster when TESTFN is nil isn't the right solution, the right
> solution is to point out that seq-uniq's purpose in this case is not
> to be a Speedy Gonzales.

In particular, it means that this:

 commit 171b9314bf2b2ed1719f2451b527960e0a363a40
 Author:     Stefan Kangas <stefan@marxist.se>
 AuthorDate: Tue Aug 9 14:29:12 2022 +0200
 Commit:     Stefan Kangas <stefan@marxist.se>
 CommitDate: Tue Aug 9 17:58:15 2022 +0200

     Replace utility functions with seq-uniq

     * lisp/gnus/gnus-util.el (gnus-delete-duplicates):
     * lisp/ibuf-ext.el (ibuffer-remove-duplicates): Redefine as
     obsolete function alias for 'seq-uniq'.  Update callers.

is incorrect: those callers should have been replaced with a faster
implementation than seq-uniq could ever become.

bug#57079: 29.0.50; Performance of seq-uniq is not very good

[Lars Ingebrigtsen]

Eli Zaretskii <eliz@gnu.org> writes:

> But the above means that using seq-uniq with TESTFN nil is going to be
> unnecessarily slow from the get-go.  People shouldn't use seq-uniq if
> they don't need a non-default TESTFN, because much faster
> implementations exist.
>
> IOW, since this bug is about speed, not anything else, I think making
> seq-uniq faster when TESTFN is nil isn't the right solution, the right
> solution is to point out that seq-uniq's purpose in this case is not
> to be a Speedy Gonzales.

I didn't make seq-uniq faster just when TESTFN is nil -- I made it
faster for all lists, so I don't follow you at all here.

bug#57079: 29.0.50; Performance of seq-uniq is not very good

[Eli Zaretskii]

> From: Lars Ingebrigtsen <larsi@gnus.org>
> Cc: stefan@marxist.se,  57079@debbugs.gnu.org
> Date: Tue, 09 Aug 2022 19:52:51 +0200
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > But the above means that using seq-uniq with TESTFN nil is going to be
> > unnecessarily slow from the get-go.  People shouldn't use seq-uniq if
> > they don't need a non-default TESTFN, because much faster
> > implementations exist.
> >
> > IOW, since this bug is about speed, not anything else, I think making
> > seq-uniq faster when TESTFN is nil isn't the right solution, the right
> > solution is to point out that seq-uniq's purpose in this case is not
> > to be a Speedy Gonzales.
> 
> I didn't make seq-uniq faster just when TESTFN is nil -- I made it
> faster for all lists, so I don't follow you at all here.

My point is that it will never be as fast as the implementations
Stefan deleted, replacing them with seq-uniq.  My point is that those
changes just made several places in Emacs slower, even after your
speedup, for no good reason.  Those deleted functions, if they needed
to be deleted, should have been replaced by a different
implementation, which doesn't support TESTFN and is therefore faster,
as the original implementations, now deleted, were.

bug#57079: 29.0.50; Performance of seq-uniq is not very good

[Lars Ingebrigtsen]

Eli Zaretskii <eliz@gnu.org> writes:

> My point is that it will never be as fast as the implementations
> Stefan deleted, replacing them with seq-uniq.  My point is that those
> changes just made several places in Emacs slower, even after your
> speedup, for no good reason.  Those deleted functions, if they needed
> to be deleted, should have been replaced by a different
> implementation, which doesn't support TESTFN and is therefore faster,
> as the original implementations, now deleted, were.

The performance of the new seq-uniq (called with no TESTFN) is identical
to the old gnus-delete-duplicates -- it's the same code.

bug#57079: 29.0.50; Performance of seq-uniq is not very good

[Eli Zaretskii]

> From: Lars Ingebrigtsen <larsi@gnus.org>
> Cc: stefan@marxist.se,  57079@debbugs.gnu.org
> Date: Tue, 09 Aug 2022 20:03:46 +0200
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > My point is that it will never be as fast as the implementations
> > Stefan deleted, replacing them with seq-uniq.  My point is that those
> > changes just made several places in Emacs slower, even after your
> > speedup, for no good reason.  Those deleted functions, if they needed
> > to be deleted, should have been replaced by a different
> > implementation, which doesn't support TESTFN and is therefore faster,
> > as the original implementations, now deleted, were.
> 
> The performance of the new seq-uniq (called with no TESTFN) is identical
> to the old gnus-delete-duplicates -- it's the same code.

Yes, and delete-dups on a copy is faster.

bug#57079: 29.0.50; Performance of seq-uniq is not very good

[Juri Linkov]

>> > My point is that it will never be as fast as the implementations
>> > Stefan deleted, replacing them with seq-uniq.  My point is that those
>> > changes just made several places in Emacs slower, even after your
>> > speedup, for no good reason.  Those deleted functions, if they needed
>> > to be deleted, should have been replaced by a different
>> > implementation, which doesn't support TESTFN and is therefore faster,
>> > as the original implementations, now deleted, were.
>>
>> The performance of the new seq-uniq (called with no TESTFN) is identical
>> to the old gnus-delete-duplicates -- it's the same code.
>
> Yes, and delete-dups on a copy is faster.

delete-dups is faster because its implementation uses the hash table.

bug#57079: 29.0.50; Performance of seq-uniq is not very good

[Lars Ingebrigtsen]

Juri Linkov <juri@linkov.net> writes:

> delete-dups is faster because its implementation uses the hash table.

Good point.  I've now made seq-uniq do the same, and this makes the test
case go from 1.7s to 0.07s.

bug#57079: 29.0.50; Performance of seq-uniq is not very good

[Michael Heerdegen]

Lars Ingebrigtsen <larsi@gnus.org> writes:

> > delete-dups is faster because its implementation uses the hash table.
>
> Good point.  I've now made seq-uniq do the same, and this makes the test
> case go from 1.7s to 0.07s.

Good.

I think a large amount of non-standard test functions is of the form

  (lambda (x y) (TEST (F x) (F y)))

where TEST is a standard test function (equal or eq) and F some function
that CL calls key function.

This case can still be supported using hash tables.  So I think it could
make sense to add support for an additional optional KEY argument.

Michael.

bug#57079: 29.0.50; Performance of seq-uniq is not very good

[Lars Ingebrigtsen]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> I think a large amount of non-standard test functions is of the form
>
>   (lambda (x y) (TEST (F x) (F y)))
>
> where TEST is a standard test function (equal or eq) and F some function
> that CL calls key function.

More importantly, we can use a hash table directly if TESTFN is
`eq'/`equal'/`eql' (or other pre-defined hash table tests), but it
didn't seem important enough.

> This case can still be supported using hash tables.  So I think it could
> make sense to add support for an additional optional KEY argument.

I think we're into cl-lib.el territory then -- seq doesn't do KEY.

bug#57079: 29.0.50; Performance of seq-uniq is not very good

[Michael Heerdegen]

Lars Ingebrigtsen <larsi@gnus.org> writes:

> I think we're into cl-lib.el territory then -- seq doesn't do KEY.

It would make lots of uses much faster, call it as you like, don't think
about how it's used in CL, it makes sense to add it as functionality to
this function - that's the important part.  We can find a different
interface if you prefer that, e.g. allow the test function to be
(TEST F) or something like that.

I have search for occurrences of `seq-uniq' in all elisp files on my
computer, and nearly all non-standard tests fell into this class.
That's why I think we should provide a way to use `seq-uniq' for such
cases.  I had not at all been inspired by CL.

Michael.

bug#57079: 29.0.50; Performance of seq-uniq is not very good

[Lars Ingebrigtsen]

Michael Heerdegen <michael_heerdegen@web.de> writes:

>> I think we're into cl-lib.el territory then -- seq doesn't do KEY.
>
> It would make lots of uses much faster, call it as you like, don't think
> about how it's used in CL, it makes sense to add it as functionality to
> this function - that's the important part.  We can find a different
> interface if you prefer that, e.g. allow the test function to be
> (TEST F) or something like that.

My point is that the seq library doesn't do KEY, it only does TESTFN,
presumably because the person who wrote it was inspired by functional
languages.

We have virtually all the same functions in cl-lib.el, and the
inspiration there is from Common Lisp, so all those functions take KEY
(and a dozen other keyword parameters).

Myself, I'd prefer that virtually all the functions in seq.el take a
KEY, too, but that's not what that library is.  Adding KEY to just
`seq-uniq' doesn't make sense from a library design standpoint.

bug#57079: 29.0.50; Performance of seq-uniq is not very good

[Michael Heerdegen]

Lars Ingebrigtsen <larsi@gnus.org> writes:

> Myself, I'd prefer that virtually all the functions in seq.el take a
> KEY, too, but that's not what that library is.  Adding KEY to just
> `seq-uniq' doesn't make sense from a library design standpoint.

But it makes sense from the viewpoint of practical requirements.  Half
of all use cases will run much slower if we don't support this case.
Practical requirements and efficiency are more important than a slippery
as an eel design.

I come from mathematics, I looked at the code usages and saw equivalence
classes and projection functions hiding behind.  I regret that I ever
used the work "key function".

It would be a bad design choice not to address all the situations where
abstraction wrt equivalence classes makes sense and improves a library
just because CL also does that.

Or do you have an idea for a different design that addresses such cases?
Simply ignoring them makes no sense.

And I see a bigger (design) problem here: as you said, there is a large
overlap between seq.el and cl-lib.el.  Once we said we don't want to
extend CL too much because it should be compatible with Common Lisp.
That was one reason why seq.el had been started.  When we now say that
we can't implement something in seq.el, something that is a practical
need, because it already exists in cl-lib, we have a problem: we will end
with two incomplete and half baked solutions for sequence handling.

People will then have to use both libraries to get efficient code and
support for their use cases, merging functions from libraries in their
code.  This should not be our long-term objective.  It would also be a
very bad design, in the end, for Emacs.

Michael.

bug#57079: 29.0.50; Performance of seq-uniq is not very good

[Lars Ingebrigtsen]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> But it makes sense from the viewpoint of practical requirements.  Half
> of all use cases will run much slower if we don't support this case.
> Practical requirements and efficiency are more important than a slippery
> as an eel design.

Well, history tells a different tale.

> And I see a bigger (design) problem here: as you said, there is a large
> overlap between seq.el and cl-lib.el.  Once we said we don't want to
> extend CL too much because it should be compatible with Common Lisp.

We've dropped that argument a long time ago -- it's free-for-all-time in
cl-lib.el. 

> That was one reason why seq.el had been started.  When we now say that
> we can't implement something in seq.el, something that is a practical
> need, because it already exists in cl-lib, we have a problem: we will end
> with two incomplete and half baked solutions for sequence handling.

They're both fully baked, but use different design philosophies,
catering to different audiences.  Of course I think that all seq.el
functions should have :key...  and :test-not and :start and :from-end,
but I come from a CL background.

bug#57079: 29.0.50; Performance of seq-uniq is not very good

[Michael Heerdegen]

Lars Ingebrigtsen <larsi@gnus.org> writes:

> > [...]  Once we said we don't want to extend CL too much because it
> > should be compatible with Common Lisp.
>
> We've dropped that argument a long time ago -- it's free-for-all-time in
> cl-lib.el.

Are we going to merge (or cherry pick) stuff from seq.el to cl-lib?
Probably not, so let's disregard the idea that cl-lib will ever be a
complete replacement for seq.el stuff.

> They're both fully baked, but use different design philosophies,
> catering to different audiences.  Of course I think that all seq.el
> functions should have :key...  and :test-not and :start and :from-end,
> but I come from a CL background.

I don't think I get it/buy it.  Could you explain (in theory, a yes/no
question) why we should not support that use case in `seq-uniq' without
saying the word "CL", and if you say "design", without comparing with
the design of CL?

If you can't: seq.el has lots of overlaps with other parts of Emacs.
What is so special about CL that an overlap is not acceptable?  Or what
is special about this task that it is not possible to handle it in
several places?

Please remember: I don't think in the term of "key functions", and I
don't want to introduce something like that to other seq.el functions,
so here is no argument.

I'll stop asking after this Email because we are going in circles - but
so far I just don't find your argumentation conclusive.

Actually, this `seq-uniq' function is a logical part of the yet-to-write
set.el library.  The task/semantics is: Find a subset containing exactly
one representative from each class of the elements of a given set.  But
I guess this library would also not be allowed to solve this task?  Why
do we add and develop them then at all?  Wouldn't it be better to
improve and develop cl-lib further instead then?  Serious question.

TIA,

Michael.

bug#57079: 29.0.50; Performance of seq-uniq is not very good

[Lars Ingebrigtsen]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> Are we going to merge (or cherry pick) stuff from seq.el to cl-lib?
> Probably not, so let's disregard the idea that cl-lib will ever be a
> complete replacement for seq.el stuff.

Why probably not?  We used to limit ourselves to what was in Common Lisp
when the library was called cl.el, but now that it's cl-lib.el, we've
opened up the possibility of adding whatever we think is useful in
Emacs.

> If you can't: seq.el has lots of overlaps with other parts of Emacs.
> What is so special about CL that an overlap is not acceptable?  Or what
> is special about this task that it is not possible to handle it in
> several places?

I'm just explaining why the design of seq.el is the way that it is: It's
the way it is because the person who wrote it wanted a sequence library
with a simple, extremely regular interface.

bug#57079: 29.0.50; Performance of seq-uniq is not very good

[Drew Adams]

> We used to limit ourselves to what was in Common Lisp
> when the library was called cl.el, but now that it's cl-lib.el, we've
> opened up the possibility of adding whatever we think is useful in
> Emacs.

Why would/did you do that?  Why isn't cl-lib.el
reserved for Common Lisp compatibility code?

An answer of, essentially, "because we've already
made that mistake" isn't, IMHO, a reasonable reason
to continue making it.

"whatever we think is useful in Emacs" - seriously?

Not intending/expecting flames.  Just one opinion.

Emacs Lisp could & should have a Common Lisp
compatibility library.  That was the original
intention of cl.el, I believe, and that should
still be an intention, regardless of where that
lives.  If cl-lib.el is now too far polluted to
serve as that, then maybe consider moving stuff
that does have that intention somewhere else.