Re: State of the overlay tree branch?

[Eli Zaretskii <eliz@gnu.org>]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> 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_GPT (b), BUF_GPT_BYTE (b));
> >   CONSIDER (BUF_BEGV (b), BUF_BEGV_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.