Re: line buffer as Red Black Trees instead of linear

[Eli Zaretskii <eliz@gnu.org>]

> Date: Wed, 21 May 2014 19:00:49 +0300
> From: Alin Soare <as1789@gmail.com>
> Cc: Stefan Monnier <monnier@iro.umontreal.ca>, emacs-devel@gnu.org
> 
> > > Ideally, at each node all the text should have the same properties
> > (marks,
> > > fonts, etc), and chaging 1 such property can be implemented by splitting
> > > the node or removing a few nodes, and their text be preserved in 1 node
> > > (only the field owner must be changed when a few nodes are joined in only
> > > 1).
> >
> > That would mean we will need to rearrange the tree each time text
> > properties or overlays change, something we avoid today.
> >
> 
> Yes, each time ! But however, a simple mental computation is still much
> faster than now, because the computation is made only 1 for each change,
> and there will be lots of simple pre-computations that never repeat.

Not necessarily.  One scenario that comes to mind is when you visit a
large buffer, and have jit-stealth enabled, which fontifies the buffer
when Emacs is idle.  With your suggestion, each stealth fontification
will cause tree rearrangement; most of these will be in portions of
the buffer that are never displayed at all.

More generally, the savings from maintaining face information as part
of the buffer text are highly dependent on the usage patterns, and it
is not clear to me they will always be a win.

Once again, I urge you to measure and time the relevant code, and also
collect the various popular use cases relevant to the issue, because
otherwise you will be most probably optimizing in the wrong place.

> > Also please note that 'display' properties can specify that Emacs
> > displays something entirely different from buffer text, so the display
> > engine will still need to consult Lisp strings, in addition to the
> > text.  (Yes, it's lots of fun.)
> 
> What is displayed will be all the time pre-computed for each node, and this
> will never be re-computed for that node before modifications. The attribute
> NODE->what-to-display-data perhaps will be evaluated at the 1st display,
> not at the node creation.

So this means you will also have to rearrange the tree whenever
display properties change, which is more work, and non-trivial one at
that (access to overlay strings is not very efficient in Emacs, when
there are many of them).

And what happens with text that is covered with an invisible text
property?  Does it disappear from the tree?