Re: master 3e5298f: Improve performance of seq-union

Re: master 3e5298f: Improve performance of seq-union

[Robert Pluim]

>>>>> On Fri, 17 Sep 2021 08:01:59 -0400 (EDT), stefankangas@gmail.com (Stefan Kangas) said:

    Stefan> branch: master
    Stefan> commit 3e5298fc96c98d2296432d31ee1d3de86a4c466c
    Stefan> Author: Stefan Kangas <stefan@marxist.se>
    Stefan> Commit: Stefan Kangas <stefan@marxist.se>

    Stefan>     Improve performance of seq-union
    
    Stefan>     * lisp/emacs-lisp/seq.el (seq-union): Improve performance by using
    Stefan>     nreverse instead of seq-reverse.

Utterly idle thought: would packages that tend to generate long lists
and reverse them, such as Gnus, benefit from a builtin-in queue data
type that supported efficient appending?

Robert
-- 

Re: master 3e5298f: Improve performance of seq-union

[Lars Ingebrigtsen]

Robert Pluim <rpluim@gmail.com> writes:

> Utterly idle thought: would packages that tend to generate long lists
> and reverse them, such as Gnus, benefit from a builtin-in queue data
> type that supported efficient appending?

A new data structure that has both head and a tail pointer?  I think
you'd be hard pressed to get that to be faster than push+nreverse unless
you implement it in C -- nreverse is very fast.

But I could be wrong.

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

Re: master 3e5298f: Improve performance of seq-union

[Lars Ingebrigtsen]

Lars Ingebrigtsen <larsi@gnus.org> writes:

> A new data structure that has both head and a tail pointer?  I think
> you'd be hard pressed to get that to be faster than push+nreverse unless
> you implement it in C -- nreverse is very fast.

(I mean -- for lists of lengths you'd be likely to see in something like
Gnus.  If you operate on lists that are billions of elements long, then
sure.)

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

Re: master 3e5298f: Improve performance of seq-union

[Robert Pluim]

>>>>> On Mon, 27 Sep 2021 17:07:39 +0200, Lars Ingebrigtsen <larsi@gnus.org> said:

    Lars> Robert Pluim <rpluim@gmail.com> writes:
    >> Utterly idle thought: would packages that tend to generate long lists
    >> and reverse them, such as Gnus, benefit from a builtin-in queue data
    >> type that supported efficient appending?

    Lars> A new data structure that has both head and a tail pointer?  I think
    Lars> you'd be hard pressed to get that to be faster than push+nreverse unless
    Lars> you implement it in C -- nreverse is very fast.

Intuitively, such a data structure needs to do less work than
nreverse, but it has to maintain the tail pointer, which should be a
net win.

    Lars> But I could be wrong.

Iʼve not implemented and measured it :-)

Robert
--