Re: State of the overlay tree branch?

[Noam Postavsky]

On 23 March 2018 at 09:19, Stefan Monnier <address@hidden> wrote:

> In any case, my patch is just a "quick hack" to try and reduce the pain,
> but it doesn't really solve the problem: the slow down with many markers
> and a large buffer still grows pretty significantly with the size of
> the buffer.  I think it's worse than O(sqrt N).
>
> If we want to really solve this problem, we should use an algorithm with
> at most an O(log N) complexity, e.g. keeping the markers in
> a red-black tree, or inside a sorted array (probably with a gap like we
> have for the buffer text) so we can do a binary search.

Is this related to Bug#24548 "Long GC delays with many non-detached
markers (PATCH)"
aka Bug#29439 "Quadratic complexity in sweep_markers"?

https://debbugs.gnu.org/cgi/bugreport.cgi?bug=24548
https://debbugs.gnu.org/cgi/bugreport.cgi?bug=29439