Re: Overlays as an AA-tree

[Eli Zaretskii]

> From: Andreas Politz <address@hidden>
> Date: Mon, 13 Feb 2017 04:44:05 +0100
> 
>  I've been working on this thing and below are my preliminary
> findings, so to speak.  The code can be found here [1].  There is a
> file etc/noverlay.org in there, containing some notes and pointing to
> some other files.
> 
> I developed some performance tests, which for the most part are very
> bare-bones and test single functions only in a constrained environment.
> Following are some numbers, a description of the test-functions and an
> attempt to make sense of the results.

Thank you for working on this important issue.

>From my POV, a very important performance issue is that of redisplay.
So I'd like to see a performance comparison in at least three use
cases:

  . scrolling through a buffer with lots of overlays that affect faces
    of characters in the buffer text
  . scrolling through a buffer with lots of overlays that define
    'display' properties which are strings
  . scrolling through a buffer with lots of overlays that define
    'invisible' properties

Bonus points for having multiple overlays with different priorities at
the same buffer positions.

> The final test seems to indicate that redisplay has an effect on this,
> probably due to the fact that it in some cases recenters the lists.

The display engine always recenters overlays around the line of text
it is rendering.  See, e.g., display_line in xdisp.c.

Thanks.