Re: noverlay branch

[Matt Armstrong <matt@rfc20.org>]

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

> Matt Armstrong [2022-10-10 20:46:43] wrote:
>
>> Not yet...until...just now.
>
> ??
> In the code I have from feature/noverlay I see:
>
>     eassert (node->parent == ITREE_NULL || node->parent->otick >= node->otick);
>
> in `interval_tree_inherit_offset`.

Oh, yeah.  I was talking only about the `check_tree` function.


>>>>  3) All downward tree traversal propagates offsets and otick.
>>> I think we already do that, but if there are places we missed, then yes,
>>> of course.
>> Yes, I think we do.  The wrinkle is that we don't always start
>> inheriting at the root, but otick is not updated in that case.
>
> I don't think propagating `otick` is very important during
> tree traversals.

I agree.  I can't think of a strong argument to do it.


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


>>> This max_depth also sounds to me like over-engineering.
>> I'd like to keep max_depth.
>
> Sorry, not gonna happen.

[...]

> Yes, it's very helpful *while working on the code*.  But it's easy to
> sprinkle many more calls to `check_tree` as needed when you're debugging
> an error caught by the cheap checks.  And when you do that you can
> temporarily pay the price of full tree traversals.

[...]

> But some of them are currently at places where they're unacceptable
> because they cost a lot more than the surrounding code.

Great, thanks for those explanations.  I am now a little better
calibrated as far as the expected performance of ENABLE_CHECKING code.


> [ 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.  It is one of the first things I look at
when assessing a crash, since it is nice to know whether a tree is small
or enormous.  But, yeah, little else really needs it.

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?