Re: State of the overlay tree branch?

[Stefan Monnier <monnier@iro.umontreal.ca>]

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

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

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.


        Stefan