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

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

[Brennan Vincent]

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

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

[Eli Zaretskii]

> From: Brennan Vincent <brennan@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.

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

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

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

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

[Brennan Vincent]

Stefan Monnier <monnier@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

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

[Stefan Kangas]

Stefan Monnier via "Bug reports for GNU Emacs, the Swiss army knife of
text editors" <bug-gnu-emacs@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`.

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

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

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

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

[João Távora]

On Fri, Jan 5, 2024 at 3:50 AM Stefan Monnier <monnier@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

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

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

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