Re: Overlays as an AA-tree

[Eli Zaretskii]

> From: Andreas Politz <address@hidden>
> Cc: address@hidden, Stefan Monnier <address@hidden>, Joakim Jalap 
> <address@hidden>
> Date: Sun, 19 Feb 2017 23:39:41 +0100
> 
> 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|
> +------------------------+-----+------+

The new implementation is still faster than the old one, so perhaps
you shouldn't bother too much?  Or am I missing something?