[Top][All Lists]

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

Re: State of the overlay tree branch?

From: Eli Zaretskii
Subject: Re: State of the overlay tree branch?
Date: Fri, 23 Mar 2018 17:22:10 +0300

> From: Stefan Monnier <address@hidden>
> Date: Fri, 23 Mar 2018 09:19:11 -0400
> > I'd be interested to see a comparison with a code that ignores the
> > markers entirely, and uses just these 4:
> >
> >   CONSIDER (BUF_PT (b), BUF_PT_BYTE (b));
> >   CONSIDER (BUF_ZV (b), BUF_ZV_BYTE (b));
> I tried that, and in the synthetic benchmark which tries to reproduce
> Sebastian's lsp-mode situation the result was indeed much better, but
> then in other benchmarks it caused very significant slowdowns.

In what benchmarks did it cause significant slowdowns?

> > That's because BYTECHAR_DISTANCE_INCREMENT is probably a function of
> > the number of markers.
> I haven't investigated closely enough to be sure, but in my tests with
> INCREMENT=50 I reached points where adding more overlays did not make
> things worse any more, so I suspect that the ideal INCREMENT depends on
> the buffer size more than on the number of markers.

Could be.  My point was that it isn't a constant.

> 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.

Yes, agreed.

reply via email to

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