Re: Overlays as an AA-tree

[Andreas Politz]

>> From: Andreas Politz <address@hidden>
>> [...] the tree implementation is not completely free of quadratic
>> worst-case performance.[...]


Here is one such case were the tree is forced to search through all
overlays in order to find the next change:

|--------------------------|
   |-------------------|
      |-------------|
      B      ^      E
             P

We are looking for the next change after P, which is E.  But E is the
end of some overlay, and the tree knows nothing about the order of
these, so it needs to consider all overlays.  Here are some numbers;

+------------------------+-----+------+
|2500 overlays           |tree |list  |
+------------------------+-----+------+
|sequential/face/scroll  |1.28 |1.32  |
+------------------------+-----+------+
|hierarchical/face/scroll|76.59|174.64|
+------------------------+-----+------+

For comparison, I added the results for the same number of overlays, but
layed out in a non-overlapping, sequential fashion.  I think the list
performs even worse because the display engine calls overlay-recenter
approx. for every line, which does nothing but traversing the after list
once.

Earlier I wrote to the effect, this scenario being far fetched.  But
there is at least one very real application coming to my mind now: A
stateful folding mode using overlays to keep data about, possibly
closed, folds.

At the moment I can think of 4 ways out of this:

1. Use a variation of the interval tree

   a.) trees, the second being sorted by overlay-end.
       + would get rid of this altogether
       - more memory and code
   b.)  Have two node types and enter every overlay twice.
       - probably worse than 1. in every way.
   c.) ???

2. Use some heuristic cache

   E.g. when we are scrolling forward, a lot of re-computation of already
   computed end-values is performed.  These could be cached in some way.

   + my guess is that it had the potential of improving the performance
   by a constant factor
   - won't work for random access, e.g. isearch

3. Ignore the problem

   I think it is a very bad idea, to replace one data-structure with bad
   worst-case behavior with another one.  Unless we can convince
   ourselves that this really is no problem (*cough*).

4. Use some better data-structure

   We need the overlays-in function, indicating that some kind of
   efficient interval managing data-structure is the right approach.  It
   just also needs to be able to answer the next-overlay-change
   challenge in all cases efficiently.  I

-ap