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