Subject: Re: bug#78665: 31.0.50; Very slow saves

From: Stefan Monnier <[email-masked]>
Date: Mon, 02 Jun 2025 14:49:38 -0400

> 10 sec to save that is awfully slow, I agree.
> But I cannot find any change during the recent two months that could
> explain that, maybe I missed something?

I sent the bug-report because I had finally the backtrace to point the
finger at something but couldn't investigate further at that point.
But now that you mention it, maybe the culprit is:

    commit 746a3cb3143194436c4a1a63d26aac890c1a705f
    Author: Juri Linkov <[email-masked]>
    Date:   Tue Apr 29 19:55:48 2025 +0300

        Ignore parens in strings for outline headings in emacs-lisp-mode.

[ Poor Juri: while it's his change, I was the one who asked him to install
  it into `master` since it seemed like an obvious improvement (I mean,
  it is, but I didn't forsee such impacts on performance).   ]

FWIW, I have now a direct way to reproduce the problem:

    src/emacs -Q --batch lisp/transient.el -f outline-minor-mode \
              --eval "(let (f)                                   \
                        (hide-sublevels 1000)                    \
                        (message \"%S\" (benchmark-call (lambda () \
                          (setq f (outline-revert-buffer-restore-visibility))))) \
                        (message \"%S\" (benchmark-call (lambda () \
                          (syntax-ppss-flush-cache (point-min))  \
                          (funcall f)))))"

and I see that it takes ~10s in my usual build (with lots of
assertions and largely unoptimized) but ~1.7s in a more normal build,
so it seems part of the problem is in the specific build options I use
which magnify the performance issue.

In the mean time, I got a more detailed profile:

        7873  83% - normal-top-level
        7873  83%  - command-line
        7873  83%   - command-line-1
        7873  83%    - eval
        7873  83%     - funcall
        7669  81%      - #<byte-code-function F5C>
        7669  81%       - outline--hidden-headings-restore-paths
        7669  81%        - outline-map-region
        7008  74%         - #<byte-code-function F79>
        7008  74%          - outline-hide-subtree
        7008  74%           - outline-flag-subtree
        3710  39%            - outline-back-to-heading
        3686  38%             + elisp-outline-search
          16   0%             + outline-on-heading-p
           4   0%               get-char-property
        3234  34%            - outline-end-of-subtree
        3190  33%             - outline-next-heading
        3182  33%              + elisp-outline-search
          28   0%             + outline-back-to-heading
          12   0%             + lisp-outline-level
          56   0%            + outline-flag-region
           8   0%            + outline-end-of-heading
         661   6%         + outline-next-heading
         204   2%      + outline-revert-buffer-restore-visibility

and I'm surprised by the fact that we spend 39% of the time in
`outline-back-to-heading` but only 0% in `outline-on-heading-p` even
tho, by construction `outline-back-to-heading` is always called from
a BOL looking at the heading of the subtree we want to hide, so it
should just call `outline-on-heading-p` and exit.

AFAICT the problem is that sometimes this heading is already hidden
(because of a preceding subtree covering the current one), so we end up
going back to the preceding/larger subtree and re-hiding it.  So for
a subtree like that of `;;; Code:` covering N smaller subtrees that were
previously hidden, we end hiding the `;;; Code:` subtree N times (and
each time, this requires looping through all the covered headings),
which introduces an O(N^2) complexity.

And indeed a search&replace of `^;;; ` with `;;;; ` in `transient.el`
after `;;; Code:` (so that `;;; Code:` covers the whole file and the
quadratic performance is in full display) brings the time to run the
above test to more than 40s, in the normal build!

        Stefan