bug#26051: 25.1; overlays may make emacs very slow

bug#26051: 25.1; overlays may make emacs very slow

[ynyaaa]

Evaluating the form below in the *scratch* buffer,
it takes a few seconds to show the result.

(let ((n 65536))
  (save-excursion (dotimes (i n) (insert (format "%d\n" i))))
  (dotimes (i n) (make-overlay (point) (progn (forward-line) (point))))
  (message "Done."))

If I evaluate the form as below, it takes about 30 seconds.
  (1) switch to a newly created buffer
  (2) insert the code into the buffer
  (3) insert 2 line breaks after the last closing parenthesis
  (4) type C-x C-e

If I evaluate the form as below, it takes about 10 minutes.
  (1) switch to a newly created buffer
  (2) type M-: and input the code

In each case, the message "Done." is displayed in a few seconds.
But it takes a long time to display the buffer contents.



In GNU Emacs 25.1.1 (i686-w64-mingw32)
 of 2016-09-18 built on LAPHROAIG
Windowing system distributor 'Microsoft Corp.', version 6.0.6002
Configured using:
 'configure --host=i686-w64-mingw32 --without-dbus
 --without-compress-install CFLAGS=-static'

Configured features:
XPM JPEG TIFF GIF PNG RSVG SOUND NOTIFY ACL GNUTLS LIBXML2 ZLIB
TOOLKIT_SCROLL_BARS

Important settings:
  value of $LANG: JPN
  locale-coding-system: cp932

Major mode: Lisp Interaction

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

Recent messages:

Load-path shadows:
None found.

Features:
(shadow sort mail-extr emacsbug message dired format-spec rfc822 mml
mml-sec password-cache epg epg-config gnus-util mm-decode mm-bodies
mm-encode mail-parse rfc2231 mailabbrev gmm-utils mailheader sendmail
rfc2047 rfc2045 ietf-drums mm-util help-fns help-mode easymenu
cl-loaddefs pcase cl-lib mail-prsvr mail-utils time-date mule-util
japan-util tooltip eldoc electric uniquify ediff-hook vc-hooks
lisp-float-type mwheel dos-w32 ls-lisp disp-table w32-win w32-vars
term/common-win tool-bar dnd fontset image regexp-opt fringe
tabulated-list newcomment elisp-mode lisp-mode prog-mode register page
menu-bar rfn-eshadow timer select scroll-bar mouse jit-lock font-lock
syntax facemenu font-core 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 charscript case-table epa-hook jka-cmpr-hook help
simple abbrev 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
w32notify w32 multi-tty make-network-process emacs)

Memory information:
((conses 8 91638 4868)
 (symbols 32 19658 0)
 (miscs 32 50 119)
 (strings 16 15828 4143)
 (string-bytes 1 427112)
 (vectors 8 13127)
 (vector-slots 4 519096 5994)
 (floats 8 164 67)
 (intervals 28 213 16)
 (buffers 520 19))

bug#26051: 25.1; overlays may make emacs very slow

[Eli Zaretskii]

> From: ynyaaa@gmail.com
> Date: Sat, 11 Mar 2017 01:25:22 +0900
> 
> 
> Evaluating the form below in the *scratch* buffer,
> it takes a few seconds to show the result.
> 
> (let ((n 65536))
>   (save-excursion (dotimes (i n) (insert (format "%d\n" i))))
>   (dotimes (i n) (make-overlay (point) (progn (forward-line) (point))))
>   (message "Done."))
> 
> If I evaluate the form as below, it takes about 30 seconds.
>   (1) switch to a newly created buffer
>   (2) insert the code into the buffer
>   (3) insert 2 line breaks after the last closing parenthesis
>   (4) type C-x C-e
> 
> If I evaluate the form as below, it takes about 10 minutes.
>   (1) switch to a newly created buffer
>   (2) type M-: and input the code
> 
> In each case, the message "Done." is displayed in a few seconds.
> But it takes a long time to display the buffer contents.

The overlays is not the main problem here, the main problem is that
your buffer is made of digits, which are neutral characters for the
bidirectional display, so it needs to work much harder.  Compare with
this:

  (let ((n 65536))
    (save-excursion (dotimes (i n) (insert (format "a%d\n" i))))
    (dotimes (i n) (make-overlay (point) (progn (forward-line) (point))))
    (message "Done."))

I see no bugs here, just known issues/limitations of the current
display engine.

bug#26051: 25.1; overlays may make emacs very slow

[ynyaaa]

Eli Zaretskii <eliz@gnu.org> writes:
> The overlays is not the main problem here, the main problem is that
> your buffer is made of digits, which are neutral characters for the
> bidirectional display, so it needs to work much harder.  Compare with
> this:
>
>   (let ((n 65536))
>     (save-excursion (dotimes (i n) (insert (format "a%d\n" i))))
>     (dotimes (i n) (make-overlay (point) (progn (forward-line) (point))))
>     (message "Done."))
>
> I see no bugs here, just known issues/limitations of the current
> display engine.

I want the buffer to be unchanged.
And I don't know what characters are neutral.

The form above take a few seconds.
I tried some characters instead of 'a'. Each of them take long time.
  "@%d\n"
  "?%d\n"
  "\u00E1%d\n" ;; LATIN SMALL LETTER A WITH ACUTE
  "\u3042%d\n" ;; HIRAGANA LETTER A
  "\u4E00%d\n" ;; CJK IDEOGRAPH-4E00
  "\uFF41%d\n" ;; FULLWIDTH LATIN SMALL LETTER A

bug#26051: 25.1; overlays may make emacs very slow

[Eli Zaretskii]

> From: ynyaaa@gmail.com
> Cc: 26051@debbugs.gnu.org
> Date: Sat, 11 Mar 2017 13:22:48 +0900
> 
> I don't know what characters are neutral.

(I should have said "neutral or weak", sorry.)

You can find out this property of a character like this:

  M-: (get-char-code-property CHAR 'bidi-class) RET

where CHAR is the character in question, e.g. ?@ for your first
example below.  You can find more information about bidirectional
character types here:

  http://unicode.org/reports/tr9/#Bidirectional_Character_Types

Any value except L or R from the above expression means the character
doesn't have a strong directionality, which requires the display
engine to look for directional context needed for correct rendering of
the text.  And since your buffer also has no empty lines, looking for
the beginning of a paragraph is also very time consuming.  Lots of
overlays just make this preposterously slow rather than merely
sluggish, because the built-in fallbacks are tuned for the "normal"
use cases, where the number of overlays is much lower.

> The form above take a few seconds.
> I tried some characters instead of 'a'. Each of them take long time.
>   "@%d\n"
>   "?%d\n"
>   "\u00E1%d\n" ;; LATIN SMALL LETTER A WITH ACUTE
>   "\u3042%d\n" ;; HIRAGANA LETTER A
>   "\u4E00%d\n" ;; CJK IDEOGRAPH-4E00
>   "\uFF41%d\n" ;; FULLWIDTH LATIN SMALL LETTER A

What I see here, with all of the above except the first two, is that
what takes a long time is for the code to run; once I see "Done" in
the echo area, redisplay takes less than a second.

That is in contrast to the original example, and the first 2 above,
where "Done" is seen very quickly, and redisplay takes a very long
time.

bug#26051: 25.1; overlays may make emacs very slow

[ynyaaa]

Eli Zaretskii <eliz@gnu.org> writes:
>> The form above take a few seconds.
>> I tried some characters instead of 'a'. Each of them take long time.
>>   "@%d\n"
>>   "?%d\n"
>>   "\u00E1%d\n" ;; LATIN SMALL LETTER A WITH ACUTE
>>   "\u3042%d\n" ;; HIRAGANA LETTER A
>>   "\u4E00%d\n" ;; CJK IDEOGRAPH-4E00
>>   "\uFF41%d\n" ;; FULLWIDTH LATIN SMALL LETTER A
>
> What I see here, with all of the above except the first two, is that
> what takes a long time is for the code to run; once I see "Done" in
> the echo area, redisplay takes less than a second.

Why is it take long time to use multibyte characters?
2 seconds and 2 minutes are very different.

bug#26051: 25.1; overlays may make emacs very slow

[Eli Zaretskii]

> From: ynyaaa@gmail.com
> Cc: 26051@debbugs.gnu.org
> Date: Sun, 12 Mar 2017 10:44:21 +0900
> 
> >>   "@%d\n"
> >>   "?%d\n"
> >>   "\u00E1%d\n" ;; LATIN SMALL LETTER A WITH ACUTE
> >>   "\u3042%d\n" ;; HIRAGANA LETTER A
> >>   "\u4E00%d\n" ;; CJK IDEOGRAPH-4E00
> >>   "\uFF41%d\n" ;; FULLWIDTH LATIN SMALL LETTER A
> >
> > What I see here, with all of the above except the first two, is that
> > what takes a long time is for the code to run; once I see "Done" in
> > the echo area, redisplay takes less than a second.
> 
> Why is it take long time to use multibyte characters?
> 2 seconds and 2 minutes are very different.

My guess is because we need to compute the byte position of the
markers that store the overlay's beginning and end.  But that's just a
guess.

Btw, your original recipe will produce a much faster redisplay if you
set bidi-paragraph-direction of the buffer to left-to-right, instead
of leaving it at its default nil value.  Sorry I didn't mention this
earlier.

bug#26051: 25.1; overlays may make emacs very slow

[ynyaaa]

Eli Zaretskii <eliz@gnu.org> writes:
> My guess is because we need to compute the byte position of the
> markers that store the overlay's beginning and end.  But that's just a
> guess.

I tested with markers.
Markers make emacs slow too(a little bit faster than overlays).

M-x occur may make a buffer have thousands of markers,
and make point motion commands slow.

(benchmark
 1
 '(with-temp-buffer
    (let ((n 65536))
      (save-excursion (dotimes (i n) (insert (format "\u00E1%d\n" i))))
      (dotimes (i n) (make-overlay (point) (point)) (forward-line)))))
=>"Elapsed time: 129.815000s (0.277000s in 17 GCs)"

(benchmark
 1
 '(with-temp-buffer
    (let ((n 65536) tmp)
      (save-excursion (dotimes (i n) (insert (format "\u00E1%d\n" i))))
      (dotimes (i n)
        ;; protect against garbage collection
        (setq tmp (cons (list (point-marker) (point-marker)) tmp))
        (forward-line)))))
=>"Elapsed time: 90.038000s (0.272000s in 16 GCs)"

> Btw, your original recipe will produce a much faster redisplay if you
> set bidi-paragraph-direction of the buffer to left-to-right, instead
> of leaving it at its default nil value.  Sorry I didn't mention this
> earlier.

It is a good solution for me, thanks. 

bug#26051: 25.1; overlays may make emacs very slow

[Andreas Politz]

ynyaaa@gmail.com writes:

> (benchmark
>  1
>  '(with-temp-buffer
>     (let ((n 65536))
>       (save-excursion (dotimes (i n) (insert (format "\u00E1%d\n" i))))
>       (dotimes (i n) (make-overlay (point) (point)) (forward-line)))))
> =>"Elapsed time: 129.815000s (0.277000s in 17 GCs)"

I feel like I should advertise my noverlay branch

    https://github.com/politza/emacs-noverlay

where this takes 0.15s on my laptop.

-ap

bug#26051: 25.1; overlays may make emacs very slow

[Eli Zaretskii]

> From: Andreas Politz <politza@hochschule-trier.de>
> Cc: Eli Zaretskii <eliz@gnu.org>,  26051@debbugs.gnu.org
> Date: Mon, 13 Mar 2017 12:29:37 +0100
> 
> > (benchmark
> >  1
> >  '(with-temp-buffer
> >     (let ((n 65536))
> >       (save-excursion (dotimes (i n) (insert (format "\u00E1%d\n" i))))
> >       (dotimes (i n) (make-overlay (point) (point)) (forward-line)))))
> > =>"Elapsed time: 129.815000s (0.277000s in 17 GCs)"
> 
> I feel like I should advertise my noverlay branch
> 
>     https://github.com/politza/emacs-noverlay
> 
> where this takes 0.15s on my laptop.

That's wonderful news, thanks!