Re: noverlay branch

[Stefan Monnier]

>>>> Regarding `otick`, I can see 2 more options:
>>>> - Get rid of it completely: its sole purpose is to try and keep
>>>>   `overlay-start/end` O(1) in the usual case instead of O(log N), but
>>>>   I'm not convinced it's worth the cost of propagating `otick` everywhere
>>>>   all the time.
>>>> - A halfway point is to keep `otick` but update it more lazily,
>>>>   i.e. only update it when we do `overlay-start/end` (e.g. in
>>>>   `interval_tree_validate`).
>>> These ideas are simpler but similar in direction to my idea to use a
>>> btree instead.
>> Sorry, I fail to see the connection to btrees.
> Just a performance conjecture.  A b-tree is shallower, so your first
> idea above is more attractive.

I still fail to see the connection: changes in `otick` need to be
propagated everywhere anyway, so the shape of the tree probably doesn't
make much difference.

[...time passe...]

Oh, I think you're talking specifically about the complete removal of
`otick` where a shallower tree would make that less costly.
Sorry.  I understand quickly, but only after a long explanation.

>> [ FWIW, I'd like to get rid of the `tree->size` field, and thus rely on
>>   auto-growing more heavily.  ]
> I rather like the size field.

I agree it has its benefit, which is why I haven't removed it yet:
I'm not sure.

> I have a different idea about the stacks, though.  Idea: use fixed size
> stacks, no auto-growing.  120 elements is all that is needed (the max
> possible depth of a 3-pointer red-black tree on 64 bit architectures).
> That is 1K memory overhead per traversal, which I think isn't an issue?
> At least, this is a reasonable choice in other systems I've worked in.
> Is it reasonable for Emacs?

Maybe you're right.  I think this decision is muddled by the (ab)use of
stacks as collections of nodes at a few places (where we use
`interval_stack_push`), where it's not limited to O(log N).


        Stefan