bug#35453: 26.1; Poor performance of vertical-motion in large org buffer

[Ihor Radchenko <yantar92@gmail.com>]

Not sure why, but my reply did not show up in the mailing list. Resending.

  > I'm not sure I understand: is your problem with vertical-motion, or in
  > general with moving by lines in that file's buffer?

  The problem is actually more general. I had a poor performance on line
  motion, re-search-forward, and outline-based motion. However,
  performance of the latter commands seems to depend on the visibility
  state of the buffer. I was only able to reproduce the issue for
  vertical-motion.

  >  So instead of skipping
  > all that hidden text in one go, vertical-motion loops over those 17.5K
  > overlays examining the properties of each one of them.  And that takes
  > time.

  Make sense. Though it was very weird for me that I did not have a
  gradual performance degradation on that file. The motion suddenly became
  much slower in a single day (the file size did not change
  significantly). I do not remember for sure, but I suspect that it might
  have something to deal with org-lint, which somehow introduced extra
  property drawers in the file. 

  > Of course, if someone comes up with ideas how to speed up
  > vertical-motion without changing what Org does with overlays and/or
  > how overlays are implemented, such ideas will be most welcome.

  Rather dumb idea.
  Currently, vertical-motion just loops over all the intervals in the
  buffer. What if we optimise next-single-char-property-change and use it
  in vertical-motion? Say, the interval data structure can extended. In
  addition to the currently available pointers to next and previous
  intervals, each (or just 'invisible') property of the interval might
  also contain a pointer to next/previous interval with different property
  value. Then, by increasing the structure size a bit, we can
  significantly speed up the buffer motion commands.

  Best,
  Ihor

Eli Zaretskii <eliz@gnu.org> writes:

>> From: 'Ihor Radchenko' <yantar92@gmail.com>
>> Date: Thu, 25 Apr 2019 14:23:06 +0800
>> 
>> C-n and C-p are extremely slow (>10 sec to move one visual line) when
>> moving around a large org buffer in overview state, especially right
>> after opening the file.
>> The issue seems to be with low-level vertical-motion command - M-:
>> (vertical-motion 1) also takes >10sec on some lines.
>> 
>> Steps to reproduce (emacs -Q):
>> 1. Open the attached org file
>> 2. C-n, C-n, C-n, C-n
>> 3. Observe emacs hanging for >10sec. 
>
> I'm not sure I understand: is your problem with vertical-motion, or in
> general with moving by lines in that file's buffer?
>
> If the problem is the latter, then my advice to Org users is to use
> "C-c C-n/C-p" and "C-c C-f/C-b", not the normal cursor motion
> commands, because Org makes the latter very slow when a large portion
> of a large buffer is hidden.  I will now try to explain why.
>
> This buffer's size is around 1MB and 42K lines, and the part between
> the 3rd and the 4th heading holds its lion's share: almost 40K lines
> of text.  When C-n calls vertical-motion, the latter needs to find the
> buffer position displayed directly below the place where you typed
> C-n.  Since much of the text between these places, vertical-motion
> needs to skip the invisible text as quickly as possible, because from
> the user's POV that text "doesn't exist": it isn't on the screen.
> However, Org makes this skipping exceedingly hard, because (1) it uses
> overlays (as opposed to text properties) to hide text, and (2) it puts
> an awful lot of overlays on the hidden text: there are 18400 overlays
> in this file's buffer, 17500 of them between the 3rd and the 4th
> heading.  Because of this, vertical-motion must examine each and every
> overlay as it moves through the text, because each overlay can
> potentially change the 'invisible' property of text, or it might have
> a display string that needs to be displayed.  So instead of skipping
> all that hidden text in one go, vertical-motion loops over those 17.5K
> overlays examining the properties of each one of them.  And that takes
> time.
>
> Profiling shows that 80%(!) of the CPU time is spent in the function
> overlays_at which looks for overlays at a given buffer position, and
> 10% more in marker_position (because overlay endpoints are markers).
> So 90% of the time you wait for the cursor to move is spent processing
> overlays.
>
> Compare this with Outline mode, which places a single overlay on the
> entire hidden text between headings.  If you visit the same file in
> Outline mode, C-n will be much, much faster.
>
> So with the current implementation of Org and overlays, Org users are
> well advised not to make such large bodies in their Org files, and if
> they do, definitely not to use C-n and C-p for vertical motion.
>
> Of course, if someone comes up with ideas how to speed up
> vertical-motion without changing what Org does with overlays and/or
> how overlays are implemented, such ideas will be most welcome.

-- 
Ihor Radchenko