Re: noverlay branch

[Matt Armstrong]

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

>> to allow C++.  With std::multimap/std::multiset, we would have a
>> ready-made complete solution for the tree, tested by a gazillion of
>> users.  Just dreaming :-))
>
> I'm not familiar with C++ libs: does this `multiset` lib offer something
> similar to the lazy update of buffer positions that Andreas's code uses
> (via the `offset` field together with the `interval_tree_inherit_offset`
> function)?

The ordered collections in the C++ standard library do not support
augmentation.  User code isn't allowed to see the left, right, parent
pointers, for example, nor are there "hooks" that allow running user
code as the tree is traversed or modified.  The "treeness" of the
collection is abstracted away entirely.

The kind of augmentation used by noverly is quite bespoke, and I think
it justifies a bespoke implementation.  It is "augmented" both bottom up
(the LIMIT field) and top down (the OFFSET field), and requires specific
handling of each.

There are enticing features in C++, but I don't think an off-the-shelf
solution to the overlay problem, suitable for use in Emacs
(e.g. licensing), is one of them.

I like C++ quite a lot, and have decades of using it professionally, but
I'd still be very cautious using it in Emacs.  For one, Emacs aims to
support all sorts of relatively obscure compilers on little used
platforms.  C++ tends to reduce what a program is portable to, though
admitedly it is much more portable in practice than most "modern"
programming languages.


>>> I think in the context of this overlay work the performance difference
>>> is not very significant, since the code is doing a lot of other stuff
>>> while traversing the tree.
>> I agree.  I think NULL could be better in multi-threaded cases, as
>> Stefan alluded to.
>
> The current code should be multi-thread safe (except for the global
> iterator, of course), despite its use of a global sentinel node: there's
> no need to synchronize anything when reading a read-only field or when
> writing a write-only field.

Pedantically, read-only fields do need synchronization with respect to
previous writers.  As for writing, you do need synchronization of writes
to avoid undefined behavior.  The memory model doesn't allow for
unsynchronized writes.

Anyway, neither is happening here.

If this global sentinel node is never modified then it isn't ever used,
so there can't be a synchronization problem!  It is just there to
generate a unique constant address that the tree code uses as a "null"
value without actually using NULL.  I think it is unusual and
unecessary, but it is thread safe.