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

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

[Ihor Radchenko]

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

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

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@gmail.com>
> Cc: 35453@debbugs.gnu.org
> Date: Sun, 05 May 2019 09:05:46 +0800
> 
>   > 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.

There are no intervals in this story.  The way overlays are
implemented, they don't use intervals (if by that you mean the
facilities in intervals.c).  Someone was working on making overlays
more efficient by changing the low-level implementation details, but
that work is yet unfinished.

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

[Ihor Radchenko]

> There are no intervals in this story.  The way overlays are
> implemented, they don't use intervals (if by that you mean the
> facilities in intervals.c).  Someone was working on making overlays
> more efficient by changing the low-level implementation details, but
> that work is yet unfinished.

I see. Hope that overlays will be optimised eventually...

Eli Zaretskii <eliz@gnu.org> writes:

>> From: Ihor Radchenko <yantar92@gmail.com>
>> Cc: 35453@debbugs.gnu.org
>> Date: Sun, 05 May 2019 09:05:46 +0800
>> 
>>   > 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.
>
> There are no intervals in this story.  The way overlays are
> implemented, they don't use intervals (if by that you mean the
> facilities in intervals.c).  Someone was working on making overlays
> more efficient by changing the low-level implementation details, but
> that work is yet unfinished.

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

[Ihor Radchenko]

Ihor Radchenko <yantar92@gmail.com> writes:

>> There are no intervals in this story.  The way overlays are
>> implemented, they don't use intervals (if by that you mean the
>> facilities in intervals.c).  Someone was working on making overlays
>> more efficient by changing the low-level implementation details, but
>> that work is yet unfinished.
>
> I see. Hope that overlays will be optimised eventually...

And "eventually" finally came :)
I am pretty sure that this can be closed now.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

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

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Cc: Eli Zaretskii <eliz@gnu.org>,  35453@debbugs.gnu.org
> Date: Sat, 29 Oct 2022 09:02:31 +0000
> 
> Ihor Radchenko <yantar92@gmail.com> writes:
> 
> >> There are no intervals in this story.  The way overlays are
> >> implemented, they don't use intervals (if by that you mean the
> >> facilities in intervals.c).  Someone was working on making overlays
> >> more efficient by changing the low-level implementation details, but
> >> that work is yet unfinished.
> >
> > I see. Hope that overlays will be optimised eventually...
> 
> And "eventually" finally came :)
> I am pretty sure that this can be closed now.

Thanks, done.

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

[Stefan Kangas]

For posterity, this was closed by feature/noverlay being merged:
https://lists.gnu.org/archive/html/emacs-devel/2022-10/msg02166.html