Re: line buffer as Red Black Trees instead of linear

[Eli Zaretskii <eliz@gnu.org>]

> Date: Fri, 16 May 2014 10:44:44 +0300
> From: Alin Soare <as1789@gmail.com>
> Cc: Stefan Monnier <monnier@iro.umontreal.ca>, emacs-devel@gnu.org
> 
> > > logarithmic in the worse case.
> >
> > Not in redisplay.  It always moves to the next character, and
> > remembers the last place it was at, so it mostly only needs to advance
> > to the next character.
> 
> Whatever are the functions that scan the whole line of a buffer, slowing
> emacs, this can be improved if the values are precomputed and kept at the
> tree nodes, and when some change is made at a property, like the font, it
> will affect only some nodes, where it is precomputed.

The values that need to be precomputed are the metrics of each
"display element" (character glyph, stretch glyph, image glyph, etc.)
that will (or would) be displayed when/if the line is shown on the
screen.  Your suggestion calls for precomputing those in advance,
while the current implementation computes them only when they are
actually needed.  I very much doubt that your suggestion, if
implemented, will be a net win.

It might make sense to cache the values, once they are computed, so
that any subsequent routines that need to access the same portions of
buffer text won't need to recompute the same metrics.  But before this
kind of caching is attempted, Someone(TM) should demonstrate that the
same portions of the long lines are traversed by the display engine
more than once, because otherwise what you suggest will be pure
overhead with no hope of any gains.

> The solution of this problem is the red-black trees, by inserting at each
> node all the pre-computed characteristics of the block of text kept at the
> given node. Any modification will pre-compute a finite number of nodes, and
> when need to access them , only a logarithmic # of nodes will be taken in
> consideration for all possible operations.

"Premature optimization is the root of all evil."  (Donald Knuth)

I would suggest to study the relevant code and, more importantly, time
it to find the _real_ (as opposed to imaginary) hot spots.  Then
present that data, and we could thereafter discuss whether your
suggested solution might indeed speed up the code which takes up the
lion's share of the time when Emacs needs to display very long lines.

If indeed these techniques could help, patches will be very welcome,
as this is an annoying problem, and there's a bug report for it (see
http://debbugs.gnu.org/cgi/bugreport.cgi?bug=13675).