Re: Overlays as an AA-tree

[Andreas Politz]

Eli Zaretskii <address@hidden> writes:

>> +------------------------+-----+------+
>> |2500 overlays           |tree |list  |
>> +------------------------+-----+------+
>> |sequential/face/scroll  |1.28 |1.32  |
>> +------------------------+-----+------+
>> |hierarchical/face/scroll|76.59|174.64|
>> +------------------------+-----+------+
>
> The new implementation is still faster than the old one, so perhaps
> you shouldn't bother too much?  Or am I missing something?

Well, if my implementation were to be, for example, twice as fast as the
current one for every operation, that would still be to slow.

There is absolute run-time and then there is growth rate.  What you
should comparing is the first with the second line, any column will
do. It's a factor of >50 and the difference between m*log(n) and m*n
(with m being the number of "scrolled lines" and n the number of
overlays.)  The only difference here is the way these overlays were
layed out.

Ideally, I think, this last detail should be of no consequence and the
implementation should only be limited by the number of overlays and not
by where in the buffer they occur.

But, yes, I shouldn't worry so much.  I also missed an important detail:
After we determined the next overlay change, we most likely are going to
examine the overlays properties at that position.  And this would
require examining all n overlays (in the "hierarchical" scenario)
anyway, thus the complexity of the operation as a whole would not
change, if next-overlay-change were to be faster.

I think I'm going to relax now.

-ap