Re: Mitigating the long-lines penalty in vundo

[JD Smith]

On Dec 16, 2023, at 2:13 PM, Eli Zaretskii <eliz@gnu.org> wrote:

I cannot view these images: my browser says there are errors, and if I
try downloading them with wget, I get 404...

GitHub shenanigans I guess.  Stephen’s link works: https://lists.gnu.org/archive/html/emacs-devel/2023-12/msg00448.html.  

Maybe the stuff you display uses some characters that make
redisplay slower for reasons other than line-length?  What kind of
characters are used for showing these "undo-trees"?

I just retried my test with the ascii-only symbols, and it resulted in a modest 17% speedup, but still >20s at 32K columns.

Very strange.  Profiling should point out the culprit, especially if
you load the .el file (not .elc!) and then profile.

I tried again from a clean session with eval-buffer’d vundo.el.  The profiler for 10,000 edits (no undos) reports a very odd result:

        1799  95% - command-execute

        1799  95%  - call-interactively

        1799  95%   - funcall-interactively

        1799  95%    - eval-_expression_

        1799  95%     - eval

        1799  95%      - save-current-buffer

        1797  95%       - vundo

        1797  95%        - let

        1756  93%         - vundo-1

        1756  93%          - save-current-buffer

        1756  93%           - let

        1756  93%            - save-current-buffer

        1756  93%             - vundo--refresh-buffer

        1756  93%              - save-current-buffer

        1756  93%               - let

        1651  87%                - if

        1649  87%                 - vundo--draw-tree

        1649  87%                  - let*

        1649  87%                   - while

        1649  87%                    - let*

        1640  86%                     - let

        1560  82%                      - max

        1560  82%                         1-

          71   3%                      - if

          71   3%                       - let

          71   3%                        - if

          65   3%                         + insert

           9   0%                      - rx-to-string

           7   0%                       + rx--translate

           1   0%                       + cons

           2   0%                     + if

           1   0%                     + progn

           1   0%                       vundo--put-node-at-point

           1   0%                       vundo--node-timestamp

           2   0%                 + eq

         105   5%                + let*

          41   2%         + let

          87   4% + ...

Looking closer, the only relevant thing in draw-tree is (1- (current-column)).  Adding that to my elp list and... we have found the principal culprit (here with 10K edits):

vundo--draw-tree  1           9.65838       9.65838

current-column    10001       9.124152      0.0009123239

`current-column’ is apparently pretty expensive here (~1ms).  The current-column docs do say:

In a buffer with very long lines, the value will be an approximation,

because calculating the exact number is very expensive.

I just tested it in a temp buffer with width 10K, and it’s much less expensive (60-100µs).  Perhaps the text properties on each node character (containing the defstruct node object) slows current-column down even further.  So it is a long-lines problem of a sort, just not display related. 

To confirm, it’s your understanding that functions like all those mentioned above (goto-char, looking at, delete-char, move-to-column, insert) should be agnostic w.r.t. the length of lines, for buffers of the same total character count?  

Yes.  Emacs editing commands are largely unaware of lines, unless Lisp
programs invoke functions that are sensitive to lines, like
end-of-line etc.  Buffer text is stored as a C string, it is not
subdivided into lines.  Only the display engine is sensitive to lines.

Bottom line: I don't think I understand what causes your problems.
The information presented is insufficient for even guessing the
possible reasons.  Please consider telling more.

I did include a link to the short draw function itself; not sure if you saw that.  And I demonstrated clearly (IMO of course) that the performance slowdown depends directly on the max column count of the displayed buffer.  As a small bit of constructive feedback, this take (“insufficient for even guessing the possible reasons”) strikes me as uncharitable given this context.

You must understand that I don't have time to study non-trivial code
when such questions are posted.  I spent 8 hours today reviewing and
installing patches, merging the release branch to master, fixing bugs
people reported over the last days, etc.  So by "insufficient
information" I meant what was presented explicitly, both here and in
the discussion of the issue.  My best suggestion so far is to profile
the code; if you are certain you know which function is problematic,
profile that after loading the code as .el file, and show the
completely expanded profile.  The profiles you've shown until now
indicate that vundo--draw-tree is the hot spot, so loading it as a .el
file and running "M-x profiler-start" followed by "M-x profiler-report"
when it finishes should show the expensive parts.

Thank for the suggestions.  I deeply appreciate all you do for Emacs and am honestly quite blown away by your responsiveness to bugs, queries, long bike-shed discussions, etc.  Please take my comment only as gentle feedback on communication & perceptions, which I always appreciate receiving.   Your advice was, as usual, good... now to workaround current-column slowness. 

Thanks again.