bug#69241: [PATCH] Jsonrpc: improve performance of process filter function

bug#69241: [PATCH] Jsonrpc: improve performance of process filter function

[Daniel Pettersson]

[-- Attachment #1: Type: text/plain, Size: 868 bytes --]

Tags: patch


This was issue was discovered during elpa package dape's development,
where an adapter was sending 72000 notifications on startup which leads
to emacs looping over timer--time-less-p for > 50 seconds and after the
fix for less then 1 second.  The "integrity" of timer order are messed
with but as timer_check runs all of the ripe timers in the same while
loop it only becomes an question of execution order.  This change uses
timer.el internal api `timer--triggered', but this might be fine as it's
tightly coupled with keyboard.

In GNU Emacs 30.0.50 (build 1, aarch64-apple-darwin23.1.0, NS
 appkit-2487.20 Version 14.1.1 (Build 23B81)) of 2023-12-20 built on
 Daniels-Air
Repository revision: 281be72422f42fcc84d43f50723a3e91b7d03cbc
Repository branch: master
Windowing system distributor 'Apple', version 10.3.2487
System Description:  macOS 14.1.1


[-- Attachment #2: 0001-Jsonrpc-improve-performance-of-process-filter-functi.patch --]
[-- Type: text/patch, Size: 2710 bytes --]

From 92eef1a5221dd69dc95a9484eafeacad571246f8 Mon Sep 17 00:00:00 2001
From: Daniel Pettersson <daniel@dpettersson.net>
Date: Sun, 18 Feb 2024 02:05:46 +0100
Subject: [PATCH] Jsonrpc: improve performance of process filter function

`run-at-time' keeps `timer-list' list sorted by inserting each timer
based on the timer value.  This means that `timer--time-less-p' needs is
executed ~ N*N/2 times for each N pending messages.  This means that
jsonrpc becomes unusable for connections that generate a lot messages at
the same time.

* lisp/jsonrpc.el (Version): Bump to 1.0.25
(jsonrpc--process-filter): Improve performance
---
 lisp/jsonrpc.el | 21 ++++++++++++++++-----
 1 file changed, 16 insertions(+), 5 deletions(-)

diff --git a/lisp/jsonrpc.el b/lisp/jsonrpc.el
index 14fe0447008..9a52b5a76cf 100644
--- a/lisp/jsonrpc.el
+++ b/lisp/jsonrpc.el
@@ -4,7 +4,7 @@
 
 ;; Author: João Távora <joaotavora@gmail.com>
 ;; Keywords: processes, languages, extensions
-;; Version: 1.0.24
+;; Version: 1.0.25
 ;; Package-Requires: ((emacs "25.2"))
 
 ;; This is a GNU ELPA :core package.  Avoid functionality that is not
@@ -782,11 +782,22 @@ jsonrpc--process-filter
           ;; non-locally (typically the reply to a request), so do
           ;; this all this processing in top-level loops timer.
           (cl-loop
+           with time = (timer-relative-time nil 0)
            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)))))))
+           do (let ((timer (timer-create)))
+                (timer-set-time timer time)
+                (timer-set-function timer
+                                    (lambda (conn msg)
+                                      (with-temp-buffer
+                                        (jsonrpc-connection-receive conn msg)))
+                                    (list conn msg))
+                (setf (timer--triggered timer) nil)
+                ;; We're bypassing `timer-activate' due to performance
+                ;; concerns.  `timer-activate' iterates through all
+                ;; timers scheduled to execute before inserting our
+                ;; callback.  While it doesn't maintain the precise
+                ;; order of timers, we should be fine.
+                (setf timer-list (cons timer timer-list)))))))))
 
 (defun jsonrpc--remove (conn id &optional deferred-spec)
   "Cancel CONN's continuations for ID, including its timer, if it exists.
-- 
2.39.3 (Apple Git-145)

bug#69241: Fixed patch issues

[Daniel Pettersson]

[-- Attachment #1: Type: text/plain, Size: 308 bytes --]


The previous patch included an large regression, where "batch" of
messages where handled as an LIFO.  This patch should fix the issue and
also removes the dependency on timer.el internal apis.  Which makes it
instead dependent on undocumented behavior that timers of equal time are
executed in LIFO order.


[-- Attachment #2: patch --]
[-- Type: text/x-patch, Size: 3597 bytes --]

From c4d5ddb9ce5cdb8c283928daf6b166e4ce5a430d Mon Sep 17 00:00:00 2001
From: Daniel Pettersson <daniel@dpettersson.net>
Date: Wed, 28 Feb 2024 13:03:56 +0100
Subject: [PATCH] Jsonrpc: improve performance of process filter function

`run-at-time' keeps `timer-list' list sorted by inserting each timer
based on the timer value.  This means that `timer--time-less-p' needs is
executed ~ N*N/2 times for each N pending messages.  This means that
jsonrpc becomes unusable for connections that generate a lot messages at
the same time.

* lisp/jsonrpc.el (Version): Bump to 1.0.25
(jsonrpc--process-filter): Improve performance
---
 lisp/jsonrpc.el | 28 +++++++++++++++++++---------
 1 file changed, 19 insertions(+), 9 deletions(-)

diff --git a/lisp/jsonrpc.el b/lisp/jsonrpc.el
index 14fe0447008..5037d8c5b2b 100644
--- a/lisp/jsonrpc.el
+++ b/lisp/jsonrpc.el
@@ -4,7 +4,7 @@
 
 ;; Author: João Távora <joaotavora@gmail.com>
 ;; Keywords: processes, languages, extensions
-;; Version: 1.0.24
+;; Version: 1.0.25
 ;; Package-Requires: ((emacs "25.2"))
 
 ;; This is a GNU ELPA :core package.  Avoid functionality that is not
@@ -760,10 +760,11 @@ jsonrpc--process-filter
                                 (setq message
                                       (plist-put message :jsonrpc-json
                                                  (buffer-string)))
-                                (process-put proc 'jsonrpc-mqueue
-                                             (nconc (process-get proc
-                                                                 'jsonrpc-mqueue)
-                                                    (list message)))))
+                                ;; Put new messages at the front of the queue,
+                                ;; this is correct as the order is reversed
+                                ;; before putting the timers on `timer-list'.
+                                (push message
+                                      (process-get proc 'jsonrpc-mqueue))))
                           (goto-char message-end)
                           (let ((inhibit-read-only t))
                             (delete-region (point-min) (point)))
@@ -782,11 +783,20 @@ jsonrpc--process-filter
           ;; non-locally (typically the reply to a request), so do
           ;; this all this processing in top-level loops timer.
           (cl-loop
+           ;; `timer-activate' orders timers by time, which is an
+           ;; very expensive operation when jsonrpc-mqueue is large,
+           ;; therefore the time object is reused for each timer
+           ;; created.
+           with time = (current-time)
            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)))))))
+           do (let ((timer (timer-create)))
+                (timer-set-time timer time)
+                (timer-set-function timer
+                                    (lambda (conn msg)
+                                      (with-temp-buffer
+                                        (jsonrpc-connection-receive conn msg)))
+                                    (list conn msg))
+                (timer-activate timer))))))))
 
 (defun jsonrpc--remove (conn id &optional deferred-spec)
   "Cancel CONN's continuations for ID, including its timer, if it exists.
-- 
2.39.3 (Apple Git-145)

bug#69241: Fixed patch issues

[Eli Zaretskii]

bug#69241: Fixed patch issues

[Eli Zaretskii]

> From: Daniel Pettersson <daniel@dpettersson.net>
> Date: Wed, 28 Feb 2024 13:22:50 +0100
> 
> The previous patch included an large regression, where "batch" of
> messages where handled as an LIFO.  This patch should fix the issue and
> also removes the dependency on timer.el internal apis.  Which makes it
> instead dependent on undocumented behavior that timers of equal time are
> executed in LIFO order.

João, any comments or suggestions?  Should I install this?

> >From c4d5ddb9ce5cdb8c283928daf6b166e4ce5a430d Mon Sep 17 00:00:00 2001
> From: Daniel Pettersson <daniel@dpettersson.net>
> Date: Wed, 28 Feb 2024 13:03:56 +0100
> Subject: [PATCH] Jsonrpc: improve performance of process filter function
> 
> `run-at-time' keeps `timer-list' list sorted by inserting each timer
> based on the timer value.  This means that `timer--time-less-p' needs is
> executed ~ N*N/2 times for each N pending messages.  This means that
> jsonrpc becomes unusable for connections that generate a lot messages at
> the same time.
> 
> * lisp/jsonrpc.el (Version): Bump to 1.0.25
> (jsonrpc--process-filter): Improve performance
> ---
>  lisp/jsonrpc.el | 28 +++++++++++++++++++---------
>  1 file changed, 19 insertions(+), 9 deletions(-)
> 
> diff --git a/lisp/jsonrpc.el b/lisp/jsonrpc.el
> index 14fe0447008..5037d8c5b2b 100644
> --- a/lisp/jsonrpc.el
> +++ b/lisp/jsonrpc.el
> @@ -4,7 +4,7 @@
>  
>  ;; Author: João Távora <joaotavora@gmail.com>
>  ;; Keywords: processes, languages, extensions
> -;; Version: 1.0.24
> +;; Version: 1.0.25
>  ;; Package-Requires: ((emacs "25.2"))
>  
>  ;; This is a GNU ELPA :core package.  Avoid functionality that is not
> @@ -760,10 +760,11 @@ jsonrpc--process-filter
>                                  (setq message
>                                        (plist-put message :jsonrpc-json
>                                                   (buffer-string)))
> -                                (process-put proc 'jsonrpc-mqueue
> -                                             (nconc (process-get proc
> -                                                                 'jsonrpc-mqueue)
> -                                                    (list message)))))
> +                                ;; Put new messages at the front of the queue,
> +                                ;; this is correct as the order is reversed
> +                                ;; before putting the timers on `timer-list'.
> +                                (push message
> +                                      (process-get proc 'jsonrpc-mqueue))))
>                            (goto-char message-end)
>                            (let ((inhibit-read-only t))
>                              (delete-region (point-min) (point)))
> @@ -782,11 +783,20 @@ jsonrpc--process-filter
>            ;; non-locally (typically the reply to a request), so do
>            ;; this all this processing in top-level loops timer.
>            (cl-loop
> +           ;; `timer-activate' orders timers by time, which is an
> +           ;; very expensive operation when jsonrpc-mqueue is large,
> +           ;; therefore the time object is reused for each timer
> +           ;; created.
> +           with time = (current-time)
>             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)))))))
> +           do (let ((timer (timer-create)))
> +                (timer-set-time timer time)
> +                (timer-set-function timer
> +                                    (lambda (conn msg)
> +                                      (with-temp-buffer
> +                                        (jsonrpc-connection-receive conn msg)))
> +                                    (list conn msg))
> +                (timer-activate timer))))))))
>  
>  (defun jsonrpc--remove (conn id &optional deferred-spec)
>    "Cancel CONN's continuations for ID, including its timer, if it exists.
> -- 
> 2.39.3 (Apple Git-145)
> 

bug#69241: Fixed patch issues

[João Távora]

On Sat, Mar 9, 2024 at 8:56 AM Eli Zaretskii <eliz@gnu.org> wrote:
>
> > From: Daniel Pettersson <daniel@dpettersson.net>
> > Date: Wed, 28 Feb 2024 13:22:50 +0100
> >
> > The previous patch included an large regression, where "batch" of
> > messages where handled as an LIFO.  This patch should fix the issue and
> > also removes the dependency on timer.el internal apis.  Which makes it
> > instead dependent on undocumented behavior that timers of equal time are
> > executed in LIFO order.
>
> João, any comments or suggestions?  Should I install this?

From where I stand, Daniel Pettersson is the new Jsonrpc maintainer.  I'd give
him push rights so he can install this and push any follow-up fixes easily.

bug#69241: Fixed patch issues

[Daniel Pettersson]

João Távora <joaotavora@gmail.com> writes:

> From where I stand, Daniel Pettersson is the new Jsonrpc maintainer.  I'd give
> him push rights so he can install this and push any follow-up fixes easily.

As I have previously stated I am willing to take on the maintainer role
for Jsonrpc.  

> +           ;; `timer-activate' orders timers by time, which is an
> +           ;; very expensive operation when jsonrpc-mqueue is large,
> +           ;; therefore the time object is reused for each timer
> +           ;; created.

I am interested in what both of you think about relying on undocumented
behavior.

To grasp the scope of this issue, an adapter server sent 50 000
messages. With `read-process-output-max' set to the platforms max, each
of those messages where placed on `timer-list' in the same call to
jsonrpc's filter function, which then had to be sorted as O(N^2)
(calls to timer--time-less-p). 

Which makes Jsonrpc unusable for that particular server.

bug#69241: Fixed patch issues

[João Távora]

On Sun, Mar 10, 2024 at 2:28 PM Daniel Pettersson
<daniel@dpettersson.net> wrote:

> As I have previously stated I am willing to take on the maintainer role
> for Jsonrpc.

Thank you Daniel.  It'll be in very good hands.

> > +           ;; `timer-activate' orders timers by time, which is an
> > +           ;; very expensive operation when jsonrpc-mqueue is large,
> > +           ;; therefore the time object is reused for each timer
> > +           ;; created.
>
> I am interested in what both of you think about relying on undocumented
> behavior.
>
> To grasp the scope of this issue, an adapter server sent 50 000
> messages. With `read-process-output-max' set to the platforms max, each
> of those messages where placed on `timer-list' in the same call to
> jsonrpc's filter function, which then had to be sorted as O(N^2)
> (calls to timer--time-less-p).
>
> Which makes Jsonrpc unusable for that particular server.

I think your analysis is sound, Daniel. As you have noticed the run-at-time 0
is not to actually  use a timer, but just to get a call that is independent
from the current  call stack which may be nested because of the use case
of bug#67945.

The calls must be processed in the order of the queue though, but in
theory that shouldn't lead to O(N^2) if a suitable technique is found (perhaps
different from (run-at-time 0)).

Finally 50.000 is a gigantic amount -- are all of these essential?  Can't the
server coalesce this data into fewer messages within the DAP protocol?

João

bug#69241: Fixed patch issues

[Daniel Pettersson]

João Távora <joaotavora@gmail.com> writes:

> The calls must be processed in the order of the queue though, but in
> theory that shouldn't lead to O(N^2) if a suitable technique is found (perhaps
> different from (run-at-time 0)).

The first patch I sent had this issue of them being process out of
order.  But the second patch ensures that they are handled correctly.
It may look like they don't but they do :)

1. We push each message on 'jsonrpc-mqueue (Order is reversed)
2. We pop each item of 'jsonrpc-mqueue and push (Guaranteed by sharing
the same `time' for each timer) the item on `timer-list'.
3. Timers are evaluated in the order of `timer-list'.

Simplified:
(setf timer-list (append (reverse (reverse messages)) timer-list))

:)

This is not that straight forward and loops back to my point of relying
on timer.el internals, but as I see it there is no other way, if one
would like to get around the internal sorting of timers in timer.el
which I would very much like to do.

> Finally 50.000 is a gigantic amount -- are all of these essential?  Can't the
> server coalesce this data into fewer messages within the DAP protocol?

Sorry I made an error it's 5000, this is js-debug sending an list of
javascript sources for "medium" sized js React project and no that cant
be configured.  Which as I stated in my other reply leads to 12,500,000
(N^2/2) calls to `timer--time-less-p' (timer sorting in timer.el) but
with my patch only requires 5000.

(why does an "medium" sized modern js web project require 5000 sources
is the real question we need to ask ourselves)

/Daniel

bug#69241: Fixed patch issues

[Eli Zaretskii]

> From: Daniel Pettersson <daniel@dpettersson.net>
> Cc: Eli Zaretskii <eliz@gnu.org>,  69241@debbugs.gnu.org
> Date: Mon, 11 Mar 2024 10:44:38 +0100
> 
> João Távora <joaotavora@gmail.com> writes:
> 
> > The calls must be processed in the order of the queue though, but in
> > theory that shouldn't lead to O(N^2) if a suitable technique is found (perhaps
> > different from (run-at-time 0)).
> 
> The first patch I sent had this issue of them being process out of
> order.  But the second patch ensures that they are handled correctly.
> It may look like they don't but they do :)
> 
> 1. We push each message on 'jsonrpc-mqueue (Order is reversed)
> 2. We pop each item of 'jsonrpc-mqueue and push (Guaranteed by sharing
> the same `time' for each timer) the item on `timer-list'.
> 3. Timers are evaluated in the order of `timer-list'.

Can't the code activate the timers in reverse order?  Then each
timer--activate will likely compare with just one timer, the first
one.

> This is not that straight forward and loops back to my point of relying
> on timer.el internals, but as I see it there is no other way, if one
> would like to get around the internal sorting of timers in timer.el
> which I would very much like to do.

Timers must fire in the order of their time, so they must be kept
sorted, or else running the timer functions and removing the timer
from the list will be much more complex.

Assuming that timers are sorted is not relying on the internals, if
you ask me.

> (why does an "medium" sized modern js web project require 5000 sources
> is the real question we need to ask ourselves)

Indeed.  Any idea of what the answer could be?

bug#69241: Fixed patch issues

[Daniel Pettersson]

Eli Zaretskii <eliz@gnu.org> writes:

> Can't the code activate the timers in reverse order?  Then each
> timer--activate will likely compare with just one timer, the first
> one.

In my patch they do.  As all timers are using the same time list and
pushed on timer-list in the correct order.  Feels like *I* have pushed
this thread into bikeshedding territory :)

> Timers must fire in the order of their time, so they must be kept
> sorted, or else running the timer functions and removing the timer
> from the list will be much more complex.
>
> Assuming that timers are sorted is not relying on the internals, if
> you ask me.

Great,  what actions do I need to take to move forward with this
maintainership thing?

/Daniel

bug#69241: Fixed patch issues

[Eli Zaretskii]

> From: Daniel Pettersson <daniel@dpettersson.net>
> Cc: joaotavora@gmail.com,  69241@debbugs.gnu.org
> Date: Mon, 11 Mar 2024 15:48:02 +0100
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > Can't the code activate the timers in reverse order?  Then each
> > timer--activate will likely compare with just one timer, the first
> > one.
> 
> In my patch they do.  As all timers are using the same time list and
> pushed on timer-list in the correct order.  Feels like *I* have pushed
> this thread into bikeshedding territory :)

Maybe.  But then why we are talking about N^2 order, if you already
have a way to fix that?

> > Timers must fire in the order of their time, so they must be kept
> > sorted, or else running the timer functions and removing the timer
> > from the list will be much more complex.
> >
> > Assuming that timers are sorted is not relying on the internals, if
> > you ask me.
> 
> Great,  what actions do I need to take to move forward with this
> maintainership thing?

It's basically up to you, but maybe I don't understand what you are
asking.

bug#69241: Fixed patch issues

[Daniel Pettersson]

Eli Zaretskii <eliz@gnu.org> writes:

> Maybe.  But then why we are talking about N^2 order, if you already
> have a way to fix that?

It's in the first reply to this bug.  I believe we got sidetracked.

> It's basically up to you, but maybe I don't understand what you are
> asking.

I am up for it, I thought that maybe some actions need to be taken on my
end to get that process rolling (getting push permission etc.).

/Daniel

bug#69241: Fixed patch issues

[Eli Zaretskii]

> From: Daniel Pettersson <daniel@dpettersson.net>
> Cc: joaotavora@gmail.com,  69241@debbugs.gnu.org
> Date: Mon, 11 Mar 2024 20:03:22 +0100
> 
> > It's basically up to you, but maybe I don't understand what you are
> > asking.
> 
> I am up for it, I thought that maybe some actions need to be taken on my
> end to get that process rolling (getting push permission etc.).

Write access to the repository is a separate decision.  We usually
make it after observing your patches and review comments to them over
some period, to make sure you are on top of our conventions and
procedures.  So no need to wait for that or see it as a prerequisite
for your development and maintenance work.

Thanks.

bug#69241: Fixed patch issues

[Daniel Pettersson]

[-- Attachment #1: Type: text/plain, Size: 813 bytes --]

Eli Zaretskii <eliz@gnu.org> writes:

> Write access to the repository is a separate decision.  We usually
> make it after observing your patches and review comments to them over
> some period, to make sure you are on top of our conventions and
> procedures.  So no need to wait for that or see it as a prerequisite
> for your development and maintenance work.

That makes sense, actually I appreciate the hand holding :) Is there any
thing more that you need from me regarding the original issue?  I feel
like I have a decent enough understanding of Jsonrpc so I am happy to be
noted as an maintainer contact in admin/MAINTAINERS.

Also I am a bit bad at reading tones in email form.  I am sorry if I
made any faux pas in this thread.

Re attaching the patch as to not get it confused with the first patch sent.

[-- Attachment #2: PATCH --]
[-- Type: text/x-patch, Size: 3597 bytes --]

From c4d5ddb9ce5cdb8c283928daf6b166e4ce5a430d Mon Sep 17 00:00:00 2001
From: Daniel Pettersson <daniel@dpettersson.net>
Date: Wed, 28 Feb 2024 13:03:56 +0100
Subject: [PATCH] Jsonrpc: improve performance of process filter function

`run-at-time' keeps `timer-list' list sorted by inserting each timer
based on the timer value.  This means that `timer--time-less-p' needs is
executed ~ N*N/2 times for each N pending messages.  This means that
jsonrpc becomes unusable for connections that generate a lot messages at
the same time.

* lisp/jsonrpc.el (Version): Bump to 1.0.25
(jsonrpc--process-filter): Improve performance
---
 lisp/jsonrpc.el | 28 +++++++++++++++++++---------
 1 file changed, 19 insertions(+), 9 deletions(-)

diff --git a/lisp/jsonrpc.el b/lisp/jsonrpc.el
index 14fe0447008..5037d8c5b2b 100644
--- a/lisp/jsonrpc.el
+++ b/lisp/jsonrpc.el
@@ -4,7 +4,7 @@
 
 ;; Author: João Távora <joaotavora@gmail.com>
 ;; Keywords: processes, languages, extensions
-;; Version: 1.0.24
+;; Version: 1.0.25
 ;; Package-Requires: ((emacs "25.2"))
 
 ;; This is a GNU ELPA :core package.  Avoid functionality that is not
@@ -760,10 +760,11 @@ jsonrpc--process-filter
                                 (setq message
                                       (plist-put message :jsonrpc-json
                                                  (buffer-string)))
-                                (process-put proc 'jsonrpc-mqueue
-                                             (nconc (process-get proc
-                                                                 'jsonrpc-mqueue)
-                                                    (list message)))))
+                                ;; Put new messages at the front of the queue,
+                                ;; this is correct as the order is reversed
+                                ;; before putting the timers on `timer-list'.
+                                (push message
+                                      (process-get proc 'jsonrpc-mqueue))))
                           (goto-char message-end)
                           (let ((inhibit-read-only t))
                             (delete-region (point-min) (point)))
@@ -782,11 +783,20 @@ jsonrpc--process-filter
           ;; non-locally (typically the reply to a request), so do
           ;; this all this processing in top-level loops timer.
           (cl-loop
+           ;; `timer-activate' orders timers by time, which is an
+           ;; very expensive operation when jsonrpc-mqueue is large,
+           ;; therefore the time object is reused for each timer
+           ;; created.
+           with time = (current-time)
            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)))))))
+           do (let ((timer (timer-create)))
+                (timer-set-time timer time)
+                (timer-set-function timer
+                                    (lambda (conn msg)
+                                      (with-temp-buffer
+                                        (jsonrpc-connection-receive conn msg)))
+                                    (list conn msg))
+                (timer-activate timer))))))))
 
 (defun jsonrpc--remove (conn id &optional deferred-spec)
   "Cancel CONN's continuations for ID, including its timer, if it exists.
-- 
2.39.3 (Apple Git-145)

bug#69241: Fixed patch issues

[Eli Zaretskii]

> From: Daniel Pettersson <daniel@dpettersson.net>
> Cc: joaotavora@gmail.com,  69241@debbugs.gnu.org
> Date: Mon, 11 Mar 2024 20:39:18 +0100
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > Write access to the repository is a separate decision.  We usually
> > make it after observing your patches and review comments to them over
> > some period, to make sure you are on top of our conventions and
> > procedures.  So no need to wait for that or see it as a prerequisite
> > for your development and maintenance work.
> 
> That makes sense, actually I appreciate the hand holding :) Is there any
> thing more that you need from me regarding the original issue?  I feel
> like I have a decent enough understanding of Jsonrpc so I am happy to be
> noted as an maintainer contact in admin/MAINTAINERS.

I have all the information I need, and will make the change soon.

> Also I am a bit bad at reading tones in email form.  I am sorry if I
> made any faux pas in this thread.

You didn't, no worries.

> Re attaching the patch as to not get it confused with the first patch sent.

Thanks, will install soon.

bug#69241: Fixed patch issues

[Eli Zaretskii]

> Cc: 69241@debbugs.gnu.org, joaotavora@gmail.com
> Date: Tue, 12 Mar 2024 05:27:48 +0200
> From: Eli Zaretskii <eliz@gnu.org>
> 
> > From: Daniel Pettersson <daniel@dpettersson.net>
> > Cc: joaotavora@gmail.com,  69241@debbugs.gnu.org
> > Date: Mon, 11 Mar 2024 20:39:18 +0100
> > 
> > Eli Zaretskii <eliz@gnu.org> writes:
> > 
> > > Write access to the repository is a separate decision.  We usually
> > > make it after observing your patches and review comments to them over
> > > some period, to make sure you are on top of our conventions and
> > > procedures.  So no need to wait for that or see it as a prerequisite
> > > for your development and maintenance work.
> > 
> > That makes sense, actually I appreciate the hand holding :) Is there any
> > thing more that you need from me regarding the original issue?  I feel
> > like I have a decent enough understanding of Jsonrpc so I am happy to be
> > noted as an maintainer contact in admin/MAINTAINERS.
> 
> I have all the information I need, and will make the change soon.

Done.

> > Re attaching the patch as to not get it confused with the first patch sent.
> 
> Thanks, will install soon.

And done.

Should we close this bug now?

bug#69241: Fixed patch issues

[Daniel Pettersson]

Eli Zaretskii <eliz@gnu.org> writes:

> Should we close this bug now?

Yes

/Daniel

bug#69241: Fixed patch issues

[Eli Zaretskii]

> From: Daniel Pettersson <daniel@dpettersson.net>
> Cc: 69241@debbugs.gnu.org,  joaotavora@gmail.com
> Date: Tue, 12 Mar 2024 15:34:20 +0100
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > Should we close this bug now?
> 
> Yes

Thanks, done.

bug#69241: Fixed patch issues

[Eli Zaretskii]

> From: Daniel Pettersson <daniel@dpettersson.net>
> Cc: joaotavora@gmail.com,  69241@debbugs.gnu.org
> Date: Mon, 11 Mar 2024 20:39:18 +0100
> 
> Re attaching the patch as to not get it confused with the first patch sent.

Thanks, installed on the master branch.

A few nits for the future:

 . Please make sure the lines in the commit log message are wrapped at
   column 65 at most, so that the generated ChangeLog file, which
   indents the entries by a TAB, has lines wrapped at 74 columns.
 . Each log entry should end in a period, i.e. be a complete sentence.
 . Please always mention the bug number, if known, as part of the
   commit log messages.

bug#69241: Fixed patch issues

[Daniel Pettersson]

Eli Zaretskii <eliz@gnu.org> writes:

> Thanks, installed on the master branch.

Great, thanks!

> A few nits for the future:
>
>  . Please make sure the lines in the commit log message are wrapped at
>    column 65 at most, so that the generated ChangeLog file, which
>    indents the entries by a TAB, has lines wrapped at 74 columns.
>  . Each log entry should end in a period, i.e. be a complete sentence.
>  . Please always mention the bug number, if known, as part of the
>    commit log messages.

Will do better in next patch, thanks again.

/Daniel

bug#69241: Fixed patch issues

[Eli Zaretskii]

> From: Daniel Pettersson <daniel@dpettersson.net>
> Cc: Eli Zaretskii <eliz@gnu.org>,  69241@debbugs.gnu.org
> Date: Sun, 10 Mar 2024 15:28:21 +0100
> 
> As I have previously stated I am willing to take on the maintainer role
> for Jsonrpc.  

Thank you.  Should we reflect that in admin/MAINTAINERS?

> To grasp the scope of this issue, an adapter server sent 50 000
> messages. With `read-process-output-max' set to the platforms max, each
> of those messages where placed on `timer-list' in the same call to
> jsonrpc's filter function, which then had to be sorted as O(N^2)
> (calls to timer--time-less-p). 

I don't see where the list is sorted with the above behavior.  Can you
point out which code you allude to?

bug#69241: Fixed patch issues

[Daniel Pettersson]

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?

> 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

bug#69241: Fixed patch issues

[Daniel Pettersson]

Daniel Pettersson <daniel@dpettersson.net> writes:

> In my example process property 'jsonrpc-mqueue is an list of ~50,000
> messages. 

I have to make an correction here, even if it does not really matter but
an extra zero seams to have made it's way into these conversation.  The
benchmark I have been benchmarking against is ~5,000 messages.

12,500,000 (N^2/2) calls to `timer--time-less-p' is enough to make any
machine crawl to a halt.

> /Daniel

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.

bug#69241: Fixed patch issues

[Daniel Pettersson]

Eli Zaretskii <eliz@gnu.org> writes:

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

Oh that's fine.

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

Correct, sorry if I was being unclear.

/Daniel