Stefan Monnier <monnier@iro.umontreal.ca> writes:

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

That and the basic tree operations (find, insert, remove, etc.).

You are right that there is enough essential updating going on in the
tree that perhaps the btree isn't a win.  I haven't thought about it
deeply.


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

Could most places use a fixed C array (maybe in a simple struct), with
fancy places still using the fancy thing?

Anyway, today 3 tiny patches.  Two improvements, one bug fix.  Also on
https://git.sr.ht/~matta/emacs/log/feature/noverlay.

And now patches...