Re: noverlay branch

[Stefan Monnier]

Matt Armstrong [2022-10-10 20:46:43] wrote:

> Stefan, I read only Eli's reply this morning.  Got to yours just now.
>
>
> Stefan Monnier <monnier@iro.umontreal.ca> writes:
>
>>> I had a different idea of tightening the otree invariant to this:
>>>  1) A node's otick must be greater than or equal to its children's.
>> That's already checked in the current code, right?
> 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`.

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

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

>> This max_depth also sounds to me like over-engineering.
> I'd like to keep max_depth.

Sorry, not gonna happen.

> My reason for adding it is informed by experience on similar projects.
> It is easier to understand an assertion that the tree is too deep than
> it is to debug, say, stack overflow when there is a cycle in the link
> structure of the tree.

The purpose of ENABLE_CHECKING assertions is:
- avoid errors remaining undetected.
- document the code.

If it crashes with a stack overflow, it still detects the problem, so
`max_depth` is not necessary for that.

Your checking code is nice and detailed, but it's becoming so large that
it increases the maintenance burden.  I want to make it shorter&simpler.

> It is easier to limit the height of checking if, indeed, on some night
> I am diagnosing an unrelated bug but the perf cost here is too much.

Many people run their Emacs always with ENABLE_CHECKING, so the
performance impact should be minimized.  It's OK to check a node's local
invariants in those places where you visit the node anyway.  It's OK to
check the overall state of the tree in those places where the code will
visit all the nodes anyway, but it's not OK to visit significantly more
nodes just for the check than what the normal code would do, especially
if an error there could be detected sooner or later by cheaper
checks elsewhere.

> With max_depth in place I can easily manually hack up
> a functon to verify checks only in a small subset of the tree
> (e.g. around a rotation operation, etc.).  I've done and benefited from
> this sort of thing in the past.

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.

> There is a small concrete benefit to it right now.  MAX_DEPTH is now
> initialized from interval_tree_max_height(), which currently could wildy
> under estimate the height and we wouldn't notice (because generator
> stacks auto-grow).  Since we call that fucntion to make "big enough to
> not need growing" stacks, it is nice to have test coverage for it.

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

>>> +  result.complete = left_result.complete && right_result.complete;
>>> +  if (result.complete)
>> I think all calls to `check_tree` should be complete traversals.
>> Most of the invariants checked in it are already checked incrementally
>> via sprinkled assertions elsewhere, so it's only really useful when
>> debugging a concrete known issue where the "local" checks aren't good
>> enough.
> All `check_tree` calls are complete traversals.

Great, so we can remove the `result.complete` field.

>> We could also include a few "cheap" calls to `check_tree` via `eassert`
>> (i.e. calls which we know shouldn't be algorithmically too expensive
>> because we're already traversing the whole tree for some other reason,
>> e.g. when killing a buffer (e.g. to verify that, at the end of the day,
>> we still preversed the RB invariants :-) or maybe during GC).
> ...I'm not understanding something here.  All `check_tree` calls are in
> `eassert` already.

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


        Stefan