Re: Mitigating the long-lines penalty in vundo

[JD Smith <jdtsmith@gmail.com>]

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



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

[-- Attachment #2: Type: text/html, Size: 10143 bytes --]