GNU bug report logs - #69241
[PATCH] Jsonrpc: improve performance of process filter function

Previous Next

Full log

View this message in rfc822 format

From: Eli Zaretskii <eliz <at> gnu.org>
To: Daniel Pettersson <daniel <at> dpettersson.net>
Cc: 69241 <at> debbugs.gnu.org, joaotavora <at> gmail.com
Subject: bug#69241: Fixed patch issues
Date: Mon, 11 Mar 2024 14:24:00 +0200

> From: Daniel Pettersson <daniel <at> dpettersson.net>
> Cc: joaotavora <at> gmail.com,  69241 <at> debbugs.gnu.org
> Date: Sun, 10 Mar 2024 21:05:46 +0100
> 
> Eli Zaretskii <eliz <at> 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.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.