Re: Overlays as an AA-tree

[Eli Zaretskii]

> From: Stefan Monnier <address@hidden>
> Cc: address@hidden
> Date: Wed, 21 Sep 2016 12:24:30 -0400
> 
> >> > Speaking of which, is the byte position stored in a marker of any
> >> > significance in an overlay?  Otherwise I could at least get rid of
> >> > those.
> >> AFAIK, the byte-position of markers is used, but the byte-position of
> >> overlays isn't, so you should be able to get rid of them.
> > Why bother?
> 
> AFAIK there'd be no benefit at all until/unless you add extra code to
> try and use those byte-positions somewhere.
> I know of two cases where we use such byte-positions, currently:
> - in goto-char, but that never receives an overlay as argument.
> - when converting charpos <-> bytepos (where we use the table of
>   markers as a kind of cache of existing translations)

That's a larger issue about markers, AFAU, it has nothing in
particular to do with overlays.

My point was that if overlay edges are implemented as markers, their
movement with buffer changes is for free, and doesn't need to be
reimplemented.

I also envision other subtleties that rely on them being markers
(e.g., the buffer-modification hooks).  I see no reason why Joakim
should add to his immediate job, which is large already, also the job
of replacing start/end markers and dealing with the fallout.  That
should IMO be a separate job.

> - This hack of (ab)using markers can occasionally lead to bad
>   performance because it makes the charpos<->bytepos conversion O(N)
>   in the worst case where N is the number of markers which can get very
>   large).
> - It can also lead to bad performance in the other case: lack of
>   markers around the "destination" makes the conversion O(N) in the
>   worst case where N is the size of the displacement.

Do you have numbers to back that up?  IME, this is a non-issue.

in any case, I was only talking about the overlay start/end
implementation, not about the byte position of markers in general.