Re: Overlays as an AA-tree

[Stefan Monnier <monnier@IRO.UMontreal.CA>]

> I stopped working on this, since it wasn't clear where this will be
> going (among other things).  But I'm willing to pick it up again.
> Following is a fairly concise status-report.

What's missing for it to be "good enough for master" (which AFAIK means
mostly that the code is clean, there are no known bugs, and the
performance is varies between "no worse" and "much better" than what we
currently have)?

> I think it would be advantageous to represent overlays with identical
> start values as a single node by utilizing a linked list.  This would
> improve performance in some degenerate cases (from a tree's
> perspective), by combining the best aspects of the (current) list and
> tree approaches.

I don't think we should care too much about those degenerate cases.

> We also talked about using the same data-structure for marker, but
> there is no work done in this direction currently.

Good.  Maybe it's a good idea, but maybe not.  There's no hurry to
investigate (let alone make a decision on) this.


        Stefan