Re: line buffer as Red Black Trees instead of linear

[Alin Soare]

 

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.

There are many possibilities.

In the moment when we need to access them (lazy evaluation) or when we modify them, one can split a node in many nodes, such that all the block of text at a given node will have the same properties, so one can compute any property quickly.

In the worse case, when each character of a buffer has a distinct property than its neighbours, a buffer will have a rbt with 1 charater on each node, in which case the timing will be log(length(buffer->text)) for all operations.

 

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.

One can modify accordingly the rbt at the first transversal, or at modification, and at a 2nd nothing more to do, apart from reading the result in log(N).

 

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

I know the theory, but I wanted to report the bug, and provide the solution. I thought that those who have fresh in mind the place in emacs where it slows will say exactly why it slows, and indeed they answered.

 

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

This technique can help for sure, but I will not have time to implement it now. I did not know about bug reports, but this problem is annoying for me , as I am using emacs all the time.

I will solve it myself, if nobody solves it before.