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

[Eli Zaretskii <eliz@gnu.org>]

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