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

Previous Next

Full log

View this message in rfc822 format

From: Daniel Pettersson <daniel <at> dpettersson.net>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: 69241 <at> debbugs.gnu.org, joaotavora <at> gmail.com
Subject: bug#69241: Fixed patch issues
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?

> 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'.

Hopefully my ramblings makes things clearer.

/Daniel

Previous Next

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