GNU bug report logs - #68072
pp functions have O(n^2) runtime with lisp-indent-function set to common-lisp-indent-function

Previous Next

To reply to this bug, email your comments to 68072 AT debbugs.gnu.org.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Brennan Vincent <brennan <at> umanwizard.com>
To: bug-gnu-emacs <at> gnu.org
Subject: pp functions have O(n^2) runtime with lisp-indent-function set to
 common-lisp-indent-function
Date: Wed, 27 Dec 2023 19:10:28 -0500

This also causes eglot (in its default configuration) to hang when
opening large Rust files, since rust-analyzer tends to send large amounts of
inlay hints, and eglot logs the messages it receives as pretty-printed
lisp objects.

Note the times in the comments here, showing clearly quadratic behavior:

(setq lisp-indent-function  'common-lisp-indent-function)

(defun bm1 (sz)
  (car
   (benchmark-run (progn (setq p (pp-to-string (make-list sz 'foo))) nil))))

(bm1 1000) ;; 0.057078079
(bm1 2000) ;; 0.22562238599999998
(bm1 10000) ;; 5.312058368
(bm1 20000) ;; 21.00088354

Message #8 received at 68072 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Brennan Vincent <brennan <at> umanwizard.com>,
 Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 68072 <at> debbugs.gnu.org
Subject: Re: bug#68072: pp functions have O(n^2) runtime with
 lisp-indent-function set to common-lisp-indent-function
Date: Thu, 28 Dec 2023 08:23:19 +0200

> From: Brennan Vincent <brennan <at> umanwizard.com>
> Date: Wed, 27 Dec 2023 19:10:28 -0500
> 
> This also causes eglot (in its default configuration) to hang when
> opening large Rust files, since rust-analyzer tends to send large amounts of
> inlay hints, and eglot logs the messages it receives as pretty-printed
> lisp objects.
> 
> Note the times in the comments here, showing clearly quadratic behavior:
> 
> (setq lisp-indent-function  'common-lisp-indent-function)
> 
> (defun bm1 (sz)
>   (car
>    (benchmark-run (progn (setq p (pp-to-string (make-list sz 'foo))) nil))))
> 
> (bm1 1000) ;; 0.057078079
> (bm1 2000) ;; 0.22562238599999998
> (bm1 10000) ;; 5.312058368
> (bm1 20000) ;; 21.00088354

Adding Stefan to the discussion.

Message #11 received at 68072 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Brennan Vincent <brennan <at> umanwizard.com>
Cc: 68072 <at> debbugs.gnu.org
Subject: Re: bug#68072: pp functions have O(n^2) runtime with
 lisp-indent-function set to common-lisp-indent-function
Date: Thu, 28 Dec 2023 02:20:16 -0500

I can definitely agree: `pp` using the default `pp-default-function`
(i.e. `pp-fill`) is *not* a good idea if you have changed
`lisp-indent-function` (unless you changed it to a faster function, of
course).  We may be able to fix this O(N²) behavior, but the underlying
principle stands: it's much too easy to fall into another O(N²) behavior.

> This also causes eglot (in its default configuration) to hang when
> opening large Rust files, since rust-analyzer tends to send large amounts of
> inlay hints, and eglot logs the messages it receives as pretty-printed
> Lisp objects.

And Eglot should probably use a faster pretty printer than the default
`pp` for that.  Maybe we should make `lisp-data-mode` set
`pp-default-function` or `lisp-indent-function` to avoid such problems?


        Stefan

Message #14 received at 68072 <at> debbugs.gnu.org (full text, mbox):

From: Brennan Vincent <brennan <at> umanwizard.com>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>, 68072 <at> debbugs.gnu.org
Subject: Re: bug#68072: pp functions have O(n^2) runtime with
 lisp-indent-function set to common-lisp-indent-function
Date: Thu, 28 Dec 2023 10:37:09 -0500

Stefan Monnier <monnier <at> iro.umontreal.ca> writes:

> I can definitely agree: `pp` using the default `pp-default-function`
> (i.e. `pp-fill`) is *not* a good idea if you have changed
> `lisp-indent-function` (unless you changed it to a faster function, of
> course).  We may be able to fix this O(N²) behavior, but the underlying
> principle stands: it's much too easy to fall into another O(N²) behavior.
>

Thanks for the tip and I can definitely remove the customization of
lisp-indent-function to common-lisp-indent-function. I actually don't
remember why I originally set it since I don't write common lisp... but
anyway, if we don't expect changing lisp-indent-function globally to
behave nicely with other features (like pp), perhaps
lisp-indent-function shouldn't be Customize-able , or we should at least
mention this in the documentation?

>> This also causes eglot (in its default configuration) to hang when
>> opening large Rust files, since rust-analyzer tends to send large amounts of
>> inlay hints, and eglot logs the messages it receives as pretty-printed
>> Lisp objects.
>
> And Eglot should probably use a faster pretty printer than the default
> `pp` for that.  Maybe we should make `lisp-data-mode` set
> `pp-default-function` or `lisp-indent-function` to avoid such problems?
>
>
>         Stefan

Message #17 received at 68072 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Kangas <stefankangas <at> gmail.com>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>,
 Brennan Vincent <brennan <at> umanwizard.com>
Cc: 68072 <at> debbugs.gnu.org
Subject: Re: bug#68072: pp functions have O(n^2) runtime with
 lisp-indent-function set to common-lisp-indent-function
Date: Thu, 28 Dec 2023 09:10:27 -0800

Stefan Monnier via "Bug reports for GNU Emacs, the Swiss army knife of
text editors" <bug-gnu-emacs <at> gnu.org> writes:

> Maybe we should make `lisp-data-mode` set `pp-default-function` or
> `lisp-indent-function` to avoid such problems?

It sounds like a good idea.  This problem is presumably not at all
limited to eglot, and this should fix it for any case using
`lisp-data-mode`.

Message #20 received at 68072 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: João Távora <joaotavora <at> gmail.com>
Cc: Brennan Vincent <brennan <at> umanwizard.com>, 68072 <at> debbugs.gnu.org
Subject: Re: bug#68072: pp functions have O(n^2) runtime with
 lisp-indent-function set to common-lisp-indent-function
Date: Thu, 04 Jan 2024 22:50:51 -0500

> And Eglot should probably use a faster pretty printer than the default
> `pp` for that.  Maybe we should make `lisp-data-mode` set
> `pp-default-function` or `lisp-indent-function` to avoid such problems?

Jsonrpc uses the pretty printer via `pp-to-string` so there's no major
mode to change (and `pp-to-string` isn't told whether it's printing code
or data 🙁), and in order to run on older Emacsen it can't really use
the `pp-function` argument either.

So in the mean time, maybe the patch below is in order?
João, any comment?


        Stefan


diff --git a/lisp/jsonrpc.el b/lisp/jsonrpc.el
index 3f33443f321..f0f5842a0ee 100644
--- a/lisp/jsonrpc.el
+++ b/lisp/jsonrpc.el
@@ -1011,7 +1010,9 @@
                        (format "%s%s" preamble
                                (or (and foreign-message
+                                    (let ((lisp-indent-function ;bug#68072
+                                           #'lisp-indent-function))
                                         (concat "\n" (pp-to-string
-                                                      foreign-message)))
+                                                    foreign-message))))
                                    (concat log-text "\n")))))))
           (goto-char (point-max))

Message #23 received at 68072 <at> debbugs.gnu.org (full text, mbox):

From: João Távora <joaotavora <at> gmail.com>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: Brennan Vincent <brennan <at> umanwizard.com>, 68072 <at> debbugs.gnu.org
Subject: Re: bug#68072: pp functions have O(n^2) runtime with
 lisp-indent-function set to common-lisp-indent-function
Date: Fri, 5 Jan 2024 13:06:30 +0000

On Fri, Jan 5, 2024 at 3:50 AM Stefan Monnier <monnier <at> iro.umontreal.ca> wrote:
>
> > And Eglot should probably use a faster pretty printer than the default
> > `pp` for that.  Maybe we should make `lisp-data-mode` set
> > `pp-default-function` or `lisp-indent-function` to avoid such problems?
>
> Jsonrpc uses the pretty printer via `pp-to-string` so there's no major
> mode to change (and `pp-to-string` isn't told whether it's printing code
> or data 🙁), and in order to run on older Emacsen it can't really use
> the `pp-function` argument either.
>
> So in the mean time, maybe the patch below is in order?
> João, any comment?

Maybe, I think so.

Though the starting premise of this bug:

> This also causes eglot (in its default configuration) to hang when
> opening large Rust files, since rust-analyzer tends to send large amounts of
> inlay hints, and eglot logs the messages it receives as pretty-printed
> lisp objects.

Is not true anymore, starting around the time Brennan opened it.
Eglot now uses JSON by default, which should solve most of the
performance  issues related to logging.

But Lisp pp is still opt-in, and making it faster (and relatively
pretty) is a good thing.

João

Message #26 received at 68072 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: João Távora <joaotavora <at> gmail.com>
Cc: Brennan Vincent <brennan <at> umanwizard.com>, 68072 <at> debbugs.gnu.org
Subject: Re: bug#68072: pp functions have O(n^2) runtime with
 lisp-indent-function set to common-lisp-indent-function
Date: Sun, 07 Jan 2024 00:07:24 -0500

>> So in the mean time, maybe the patch below is in order?
>> João, any comment?
>
> Maybe, I think so.

OK, pushed, thanks.

> Though the starting premise of this bug:
>> This also causes eglot (in its default configuration) to hang when
>> opening large Rust files, since rust-analyzer tends to send large amounts of
>> inlay hints, and eglot logs the messages it receives as pretty-printed
>> lisp objects.
> Is not true anymore, starting around the time Brennan opened it.
> Eglot now uses JSON by default, which should solve most of the
> performance  issues related to logging.

I assumed that Brennan had changed the format to `lisp`.

> But Lisp pp is still opt-in, and making it faster (and relatively
> pretty) is a good thing.

The `pp` code would really benefit from extra info about what kind of
"pp" is desired (are we prettifying ELisp code or just some arbitrary
data?  Do we really want to be pretty for a human reader or do we just
want something printed quickly but a bit more manageable than a single
super-long line?).


        Stefan

Previous Next

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