[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Overlays as an AA-tree

From: Andreas Politz
Subject: Re: Overlays as an AA-tree
Date: Sun, 19 Feb 2017 23:39:41 +0100
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/25.1 (gnu/linux)

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

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  |

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

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


reply via email to

[Prev in Thread] Current Thread [Next in Thread]