Re: Future of display engine and lines

[Eli Zaretskii <eliz@gnu.org>]

> From: Richard Stallman <rms@gnu.org>
> Cc: larsi@gnus.org, galex-713@galex-713.eu, emacs-devel@gnu.org
> Date: Thu, 28 Oct 2021 08:19:41 -0400
> 
> Imagine that one region of the buffer is displayed in two side-by-side
> columns.  The top of the window is in that region.  To redisplay it,
> display needs to know where in the buffer each column starts.
> For the second column, it also needs to know how many screen lines (or
> how much screen height) is off the top of the window.
> 
> It can fill up the first column's rectangle by processing text linearly
> from the window start, line by line, and putting the result into the
> correct part of each screen line.
> 
> It can fill up the second column's rectangle by processing text
> linearly from the proper place in the buffer (where the right column
> text should start), line by line, and putting the result into the
> correct part of each screen line.
> 
> I am thinking about non-graphics terminals.  For graphics terminals,
> the data structure will have to be different.  (They already use a
> different data structure.)
> 
> The point is, there is no need to change the representation of buffers.

You are describing the initial thorough display of a window, whereby
the display engine produces the display of the entire window from
scratch.  That is indeed a relatively easy job, but it is quite an
infrequent use case in practice.  Most of the jobs that the display
engine needs to do have to do with redrawing only small parts of the
window, or scrolling the window by a small number of lines, or even
with just moving point via cursor-motion commands.  For these
situations, it is very important to be able to find the buffer
position that corresponds to some screen coordinates, or vice versa.
We currently do that by simulating redisplay, i.e. by performing all
the layout decisions without actually storing the produced glyphs.

The problem is that all those jobs need to start from some well-known
point in the buffer, where we can know the corresponding screen
coordinates.  And having the buffer text as an unstructured stream of
bytes makes it hard to find such places.  More often than not, we use
the beginnings of some physical line, where at least the X coordinate
is known to be zero.  We then go through the buffer, one character at
a time, performing layout calculations to track the X and Y
coordinates, until we come to the place we need -- either where some
condition about the buffer position becomes true, or some condition
regarding the screen coordinates becomes true.  This painstaking
iteration from a well-known point is what makes redisplay slow in some
situations, for example if the lines are very long (which means the
beginning of the previous line could be very far away, and we need to
examine a large fraction of the buffer).  It also makes movement back
in the buffer much slower (and here the variable-length internal
encoding of characters joins the previous problem to make it harder).

For example, imagine that the user moves the cursor to the right of
the rightmost character of the first column, with the intent to move
to the second column.  We'd now need to find the buffer position that
corresponds to that screen position, and the only way we have now is
to start from the window-start of the second column and go all the way
down until we reach the same Y coordinate.  Imagine how much faster we
could do that job if we kept record of the beginning of each screen
line.

So for those other jobs that redisplay must do, which in practice are
much more important and frequent than redrawing the entire window, the
current implementation of buffer text puts a limit on the speed, and
IME we have all but exhausted all the potential for speeding that up
without changing the buffer representation.  Which is why I think we
should change the buffer text representation if we want a faster
redisplay, especially if we want to introduce complications like
multiple columns etc, and still have reasonably performant redisplay.