bug#59787: 29.0.60; Very slow pos-visible-in-window-p with long truncated lines

bug#59787: 29.0.60; Very slow pos-visible-in-window-p with long truncated lines

[Eli Zaretskii]

As reported in https://debbugs.gnu.org/cgi/bugreport.cgi?bug=56682#1977:

  2. after starting Isearch at a large column number,
     Emacs hangs up indefinitely, e.g. with
     'M-g TAB 10000000 RET C-s' then even C-g doesn't get out.
     Debugging shows that the problem is in 'isearch-update'
     where the call to 'pos-visible-in-window-group-p' doesn't return.
     When this call is removed, the search is instantaneous.
     (Optimizing lazy-highlight is a separate problem in bug#56815.)

The problem is that pos-visible-in-window-p starts from window-start point
and goes to the POSITION passed as argument using move_it_to, which in this
case is very slow, because it has all the 10000000 columns to traverse.

The solution is to introduce shortcuts into pos_visible_p in this case.


In GNU Emacs 29.0.60 (build 17, i686-pc-mingw32) of 2022-12-02 built on
 HOME-C4E4A596F7
Repository revision: 4b3eb928fed4b236d1ae06ae7d9d51a4466554d2
Repository branch: emacs-29
Windowing system distributor 'Microsoft Corp.', version 5.1.2600
System Description: Microsoft Windows XP Service Pack 3 (v5.1.0.2600)

Configured using:
 'configure -C --prefix=/d/usr --with-wide-int
 --enable-checking=yes,glyphs 'CFLAGS=-O0 -gdwarf-4 -g3''

Configured features:
ACL GIF GMP GNUTLS HARFBUZZ JPEG JSON LCMS2 LIBXML2 MODULES NOTIFY
W32NOTIFY PDUMPER PNG RSVG SOUND SQLITE3 THREADS TIFF
TOOLKIT_SCROLL_BARS TREE_SITTER WEBP XPM ZLIB

Important settings:
  value of $LANG: ENU
  locale-coding-system: cp1255

Major mode: Lisp Interaction

Minor modes in effect:
  tooltip-mode: t
  global-eldoc-mode: t
  eldoc-mode: t
  show-paren-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
  line-number-mode: t
  indent-tabs-mode: t
  transient-mark-mode: t
  auto-composition-mode: t
  auto-encryption-mode: t
  auto-compression-mode: t

Load-path shadows:
None found.

Features:
(shadow sort mail-extr dabbrev emacsbug message mailcap yank-media puny
dired dired-loaddefs rfc822 mml mml-sec password-cache epa derived epg
rfc6068 epg-config gnus-util text-property-search time-date subr-x
mm-decode mm-bodies mm-encode mail-parse rfc2231 mailabbrev gmm-utils
mailheader cl-loaddefs cl-lib sendmail rfc2047 rfc2045 ietf-drums
mm-util mail-prsvr mail-utils rmc iso-transl tooltip cconv eldoc paren
electric uniquify ediff-hook vc-hooks lisp-float-type elisp-mode mwheel
dos-w32 ls-lisp disp-table term/w32-win w32-win w32-vars term/common-win
tool-bar dnd fontset image regexp-opt fringe tabulated-list replace
newcomment text-mode lisp-mode prog-mode register page tab-bar menu-bar
rfn-eshadow isearch easymenu timer select scroll-bar mouse jit-lock
font-lock syntax font-core term/tty-colors frame minibuffer nadvice seq
simple cl-generic indonesian philippine 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 emoji-zwj charscript charprop case-table
epa-hook jka-cmpr-hook help abbrev obarray oclosure cl-preloaded button
loaddefs theme-loaddefs faces cus-face macroexp files window
text-properties overlay sha1 md5 base64 format env code-pages mule
custom widget keymap hashtable-print-readable backquote threads
w32notify w32 lcms2 multi-tty make-network-process emacs)

Memory information:
((conses 16 43232 13224)
 (symbols 48 6330 6)
 (strings 16 16709 3199)
 (string-bytes 1 406733)
 (vectors 16 9402)
 (vector-slots 8 147021 11501)
 (floats 8 25 28)
 (intervals 40 273 112)
 (buffers 896 10))

bug#59787: 29.0.60; Very slow pos-visible-in-window-p with long truncated lines

[Juri Linkov]

> As reported in https://debbugs.gnu.org/cgi/bugreport.cgi?bug=56682#1977:
>
>   2. after starting Isearch at a large column number,
>      Emacs hangs up indefinitely, e.g. with
>      'M-g TAB 10000000 RET C-s' then even C-g doesn't get out.
>      Debugging shows that the problem is in 'isearch-update'
>      where the call to 'pos-visible-in-window-group-p' doesn't return.
>      When this call is removed, the search is instantaneous.
>      (Optimizing lazy-highlight is a separate problem in bug#56815.)
>
> The problem is that pos-visible-in-window-p starts from window-start point
> and goes to the POSITION passed as argument using move_it_to, which in this
> case is very slow, because it has all the 10000000 columns to traverse.
>
> The solution is to introduce shortcuts into pos_visible_p in this case.

Could you explain why pos-visible-in-window-p is instantaneous at any
position when long lines are not truncated.  Why it doesn't need to
traverse 10000000 columns in this case?

bug#59787: 29.0.60; Very slow pos-visible-in-window-p with long truncated lines

[Eli Zaretskii]

> From: Juri Linkov <juri@linkov.net>
> Cc: 59787@debbugs.gnu.org
> Date: Wed, 07 Dec 2022 09:58:40 +0200
> 
> > As reported in https://debbugs.gnu.org/cgi/bugreport.cgi?bug=56682#1977:
> >
> >   2. after starting Isearch at a large column number,
> >      Emacs hangs up indefinitely, e.g. with
> >      'M-g TAB 10000000 RET C-s' then even C-g doesn't get out.
> >      Debugging shows that the problem is in 'isearch-update'
> >      where the call to 'pos-visible-in-window-group-p' doesn't return.
> >      When this call is removed, the search is instantaneous.
> >      (Optimizing lazy-highlight is a separate problem in bug#56815.)
> >
> > The problem is that pos-visible-in-window-p starts from window-start point
> > and goes to the POSITION passed as argument using move_it_to, which in this
> > case is very slow, because it has all the 10000000 columns to traverse.
> >
> > The solution is to introduce shortcuts into pos_visible_p in this case.
> 
> Could you explain why pos-visible-in-window-p is instantaneous at any
> position when long lines are not truncated.  Why it doesn't need to
> traverse 10000000 columns in this case?

Because when lines are wrapped, window-start is at the first visible
character in the window, which is much closer to point than 10000000
characters, even with today's huge screens.  And
pos-visible-in-window-p starts from window-start position, because
that's where it _knows_ the exact X coordinate.  (It needs the X
coordinate to start from so that it could report the X coordinate of
point when the 3rd argument is non-nil.)

By contrast, when lines are truncated and the window is hscrolled,
window-start is at the first character of the first line, which in the
above case is 10000000 characters before the first visible character.
So starting from window-start will need to traverse 10000000 invisible
characters before it gets to point.  (Which if you think about it,
almost suggests the shortcut for when the lines are very long...)