bug#69241: Fixed patch issues

[Eli Zaretskii]

> From: Daniel Pettersson <daniel@dpettersson.net>
> Cc: joaotavora@gmail.com,  69241@debbugs.gnu.org
> Date: Sun, 10 Mar 2024 21:05:46 +0100
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > Thank you.  Should we reflect that in admin/MAINTAINERS?
> 
> That is fine by me.  I am not sure what the impact of that would be?

Just that you express interest in this package and don't mind to be
CC'ed when some issue about it comes up.

> > I don't see where the list is sorted with the above behavior.  Can you
> > point out which code you allude to?
> 
> Let's continue use the implementation on `master' and my example to
> give it some.
> 
> In my example process property 'jsonrpc-mqueue is an list of ~50,000
> messages. 
> 
> In `jsonrpc--process-filter' we evaluate `run-at-time' macro, which in
> turn invokes `timer--activate'.
> 
> (cl-defun jsonrpc--process-filter (proc string)
> ...
>           (cl-loop
>            for msg = (pop (process-get proc 'jsonrpc-mqueue)) while msg
>            do (run-at-time 0 nil
>                            (lambda (m) (with-temp-buffer
>                                          (jsonrpc-connection-receive conn m)))
>                            msg)))))))
> 
> `timer--active' makes sure that the `timer-list' is sorted by time to
> trigger in ascending order:
> 
> (defun timer--activate (timer &optional triggered-p reuse-cell idle)
> ...
>       ;; Skip all timers to trigger before the new one.
>       (while (and timers (timer--time-less-p (car timers) timer))
>       (setq last timers
>             timers (cdr timers)))
>       ;; Insert new timer after last which possibly means in front of queue.
>       (setf (cond (last (cdr last))
>                   (idle timer-idle-list)
>                   (t    timer-list))
>             reuse-cell)
> 
> This is especially bad when the time of the timer is created inside a
> loop as in `jsonrpc--process-filter'.
> 
> Let's take the last loop iteration in the `cl-loop'; timer_{N} from
> N messages.
> 
> timer_{N} will always be compared with timer_{1}, timer_{2},
> ... timer_{N-2}, timer_{N-1}.
> 
> This ends up with doing N^2/2 timer comparisons in
> `jsonrpc--process-filter'.

So the problem is not with timer--activate, the problem is with
jsonrpc--process-filter which calls timer--activate, and the net
effect of those two is the N^2 complexity, is that right?  Your
original statement was that the list of timers is sorted with N^2
complexity, and that is the part to which I responded.