GNU bug report logs - #35453
26.1; Poor performance of vertical-motion in large org buffer

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 35453 in the body.
You can then email your comments to 35453 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: 'Ihor Radchenko' <yantar92 <at> gmail.com>
To: bug-gnu-emacs <at> gnu.org
Subject: 26.1; Poor performance of vertical-motion in large org buffer
Date: Thu, 25 Apr 2019 14:23:06 +0800

[Message part 1 (text/plain, inline)]

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. 

In GNU Emacs 26.1 (build 1, x86_64-pc-linux-gnu, X toolkit)
 of 2019-01-13 built on yantar92-laptop
Windowing system distributor 'The X.Org Foundation', version 11.0.12003000
Recent messages:
Making completion list...
You can run the command ‘profiler-reset’ with M-x pr-res RET
Quit
-1 (#o377777777777777777777, #x3fffffffffffffff)
Making completion list...
Quit
Making completion list...
user-error: No further undo information
Quit
1 (#o1, #x1, ?\C-a)
Quit
Configured using:
 'configure --prefix=/usr --build=x86_64-pc-linux-gnu
 --host=x86_64-pc-linux-gnu --mandir=/usr/share/man
 --infodir=/usr/share/info --datadir=/usr/share --sysconfdir=/etc
 --localstatedir=/var/lib --disable-silent-rules
 --docdir=/usr/share/doc/emacs-26.1-r3
 --htmldir=/usr/share/doc/emacs-26.1-r3/html --libdir=/usr/lib64
 --program-suffix=-emacs-26 --infodir=/usr/share/info/emacs-26
 --localstatedir=/var
 --enable-locallisppath=/etc/emacs:/usr/share/emacs/site-lisp
 --without-compress-install --without-hesiod --without-pop
 --with-file-notification=inotify --enable-acl --with-dbus
 --with-modules --without-gameuser --with-gpm --without-kerberos
 --without-kerberos5 --with-lcms2 --with-xml2 --without-mailutils
 --without-selinux --with-gnutls --without-libsystemd --with-threads
 --without-wide-int --with-zlib --with-sound=alsa --with-x --without-ns
 --without-gconf --without-gsettings --without-toolkit-scroll-bars
 --with-gif --with-jpeg --with-png --with-rsvg --with-tiff --with-xpm
 --with-imagemagick --with-xft --without-cairo --without-libotf
 --without-m17n-flt --with-x-toolkit=lucid --with-xaw3d
 'CFLAGS=-march=broadwell -pipe -O2' CPPFLAGS= 'LDFLAGS=-Wl,-O1
 -Wl,--as-needed''

Configured features:
XAW3D XPM JPEG TIFF GIF PNG RSVG IMAGEMAGICK SOUND GPM DBUS NOTIFY ACL
GNUTLS LIBXML2 FREETYPE XFT ZLIB LUCID X11 MODULES THREADS LCMS2

Important settings:
  value of $LANG: en_US.utf8
  value of $XMODIFIERS: @im=imsettings
  locale-coding-system: utf-8-unix

Major mode: Org

Minor modes in effect:
  tooltip-mode: t
  global-eldoc-mode: t
  electric-indent-mode: t
  mouse-wheel-mode: t
  tool-bar-mode: t
  menu-bar-mode: t
  file-name-shadow-mode: t
  global-font-lock-mode: t
  font-lock-mode: t
  blink-cursor-mode: t
  auto-composition-mode: t
  auto-encryption-mode: t
  auto-compression-mode: t
  line-number-mode: t
  transient-mark-mode: t

Load-path shadows:
None found.

Features:
(shadow sort mail-extr time-stamp profiler emacsbug sendmail
org-duration org-rmail org-mhe org-irc org-info org-gnus nnir gnus-sum
gnus-group gnus-undo gnus-start gnus-cloud nnimap nnmail mail-source tls
gnutls utf7 netrc nnoo parse-time gnus-spec gnus-int gnus-range message
rmc puny seq byte-opt gv bytecomp byte-compile cconv rfc822 mml mml-sec
password-cache epa derived epg epg-config mm-decode mm-bodies mm-encode
mail-parse rfc2231 mailabbrev gmm-utils mailheader gnus-win gnus
nnheader gnus-util rmail rmail-loaddefs rfc2047 rfc2045 ietf-drums
mail-utils mm-util mail-prsvr wid-edit org-docview doc-view jka-compr
image-mode dired dired-loaddefs org-bibtex bibtex org-bbdb org-w3m
org-element cl-seq avl-tree generator org advice org-macro org-footnote
org-pcomplete pcomplete org-list org-faces org-entities noutline outline
easy-mmode org-version ob-emacs-lisp ob ob-tangle org-src ob-ref ob-lob
ob-table ob-keys ob-exp ob-comint comint ansi-color ring ob-core ob-eval
org-compat org-macs org-loaddefs format-spec find-func cal-menu easymenu
calendar cal-loaddefs cl-loaddefs cl-lib elec-pair time-date mule-util
tooltip eldoc electric uniquify ediff-hook vc-hooks lisp-float-type
mwheel term/x-win x-win term/common-win x-dnd tool-bar dnd fontset image
regexp-opt fringe tabulated-list replace newcomment text-mode elisp-mode
lisp-mode prog-mode register page menu-bar rfn-eshadow isearch timer
select scroll-bar mouse jit-lock font-lock syntax facemenu font-core
term/tty-colors frame cl-generic cham georgian utf-8-lang misc-lang
vietnamese tibetan thai tai-viet lao korean japanese eucjp-ms cp51932
hebrew greek romanian slovak czech european ethiopic indian cyrillic
chinese composite charscript charprop case-table epa-hook jka-cmpr-hook
help simple abbrev obarray minibuffer cl-preloaded nadvice loaddefs
button faces cus-face macroexp files text-properties overlay sha1 md5
base64 format env code-pages mule custom widget hashtable-print-readable
backquote dbusbind inotify lcms2 dynamic-setting font-render-setting
x-toolkit x multi-tty make-network-process emacs)

Memory information:
((conses 16 299128 44290)
 (symbols 48 30479 3)
 (miscs 40 55308 6589)
 (strings 32 63232 2240)
 (string-bytes 1 1952225)
 (vectors 16 46945)
 (vector-slots 8 1085988 21536)
 (floats 8 207 207)
 (intervals 56 736 59)
 (buffers 992 15))

-- 
Ihor Radchenko

[todo-3.org (text/plain, attachment)]

[signature.asc (application/pgp-signature, inline)]

Message #8 received at 35453 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: 'Ihor Radchenko' <yantar92 <at> gmail.com>
Cc: 35453 <at> debbugs.gnu.org
Subject: Re: bug#35453: 26.1;
 Poor performance of vertical-motion in large org buffer
Date: Sun, 28 Apr 2019 18:20:09 +0300

> From: 'Ihor Radchenko' <yantar92 <at> 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.

Message #15 received at 35453 <at> debbugs.gnu.org (full text, mbox):

From: Ihor Radchenko <yantar92 <at> gmail.com>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: 35453 <at> debbugs.gnu.org
Subject: Re: bug#35453: 26.1;
 Poor performance of vertical-motion in large org buffer
Date: Sun, 05 May 2019 09:05:46 +0800

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 <at> gnu.org> writes:

>> From: 'Ihor Radchenko' <yantar92 <at> 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

Message #18 received at 35453 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Ihor Radchenko <yantar92 <at> gmail.com>
Cc: 35453 <at> debbugs.gnu.org
Subject: Re: bug#35453: 26.1;
 Poor performance of vertical-motion in large org buffer
Date: Sun, 05 May 2019 18:58:52 +0300

> From: Ihor Radchenko <yantar92 <at> gmail.com>
> Cc: 35453 <at> 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.

Message #21 received at 35453 <at> debbugs.gnu.org (full text, mbox):

From: Ihor Radchenko <yantar92 <at> gmail.com>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: 35453 <at> debbugs.gnu.org
Subject: Re: bug#35453: 26.1;
 Poor performance of vertical-motion in large org buffer
Date: Sat, 18 May 2019 18:36:37 +0800

> 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 <at> gnu.org> writes:

>> From: Ihor Radchenko <yantar92 <at> gmail.com>
>> Cc: 35453 <at> 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.

Message #24 received at 35453 <at> debbugs.gnu.org (full text, mbox):

From: Ihor Radchenko <yantar92 <at> posteo.net>
To: Ihor Radchenko <yantar92 <at> gmail.com>
Cc: Eli Zaretskii <eliz <at> gnu.org>, 35453 <at> debbugs.gnu.org
Subject: Re: bug#35453: 26.1; Poor performance of vertical-motion in large
 org buffer
Date: Sat, 29 Oct 2022 09:02:31 +0000

Ihor Radchenko <yantar92 <at> 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>

Message #29 received at 35453-done <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Ihor Radchenko <yantar92 <at> posteo.net>
Cc: yantar92 <at> gmail.com, 35453-done <at> debbugs.gnu.org
Subject: Re: bug#35453: 26.1; Poor performance of vertical-motion in large
 org buffer
Date: Sat, 29 Oct 2022 13:42:36 +0300

> From: Ihor Radchenko <yantar92 <at> posteo.net>
> Cc: Eli Zaretskii <eliz <at> gnu.org>,  35453 <at> debbugs.gnu.org
> Date: Sat, 29 Oct 2022 09:02:31 +0000
> 
> Ihor Radchenko <yantar92 <at> 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.

Message #32 received at 35453 <at> debbugs.gnu.org (full text, mbox):

From: Stefan Kangas <stefankangas <at> gmail.com>
To: 35453 <at> debbugs.gnu.org, eliz <at> gnu.org, yantar92 <at> gmail.com
Cc: Ihor Radchenko <yantar92 <at> posteo.net>
Subject: Re: bug#35453: 26.1;
 Poor performance of vertical-motion in large org buffer
Date: Sat, 29 Oct 2022 15:31:47 +0200

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

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.