[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"?
https://debbugs.gnu.org/cgi/bugreport.cgi?bug=24548
https://debbugs.gnu.org/cgi/bugreport.cgi?bug=29439
- Re: State of the overlay tree branch?, (continued)
- Re: State of the overlay tree branch?, Stefan Monnier, 2018/03/22
- Re: State of the overlay tree branch?, Sebastian Sturm, 2018/03/22
- Re: State of the overlay tree branch?, Stefan Monnier, 2018/03/23
- Re: State of the overlay tree branch?, Sebastian Sturm, 2018/03/23
- Re: State of the overlay tree branch?, Eli Zaretskii, 2018/03/23
- Re: State of the overlay tree branch?, Stefan Monnier, 2018/03/23
- Re: State of the overlay tree branch?,
Noam Postavsky <=
- Re: State of the overlay tree branch?, Stefan Monnier, 2018/03/23
- Re: State of the overlay tree branch?, Eli Zaretskii, 2018/03/23
- Re: State of the overlay tree branch?, Stefan Monnier, 2018/03/23
- Re: State of the overlay tree branch?, Stefan Monnier, 2018/03/23
- Re: State of the overlay tree branch?, Stefan Monnier, 2018/03/25
- Re: State of the overlay tree branch?, Eli Zaretskii, 2018/03/25
- Re: State of the overlay tree branch?, Stefan Monnier, 2018/03/25
- Re: State of the overlay tree branch?, Eli Zaretskii, 2018/03/23
- Re: State of the overlay tree branch?, Eli Zaretskii, 2018/03/23
- Re: State of the overlay tree branch?, Sebastian Sturm, 2018/03/23