[Top][All Lists]

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

Re: State of the overlay tree branch?

From: Noam Postavsky
Subject: Re: State of the overlay tree branch?
Date: Fri, 23 Mar 2018 09:37:55 -0400

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


reply via email to

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