bug#70077: An easier way to track buffer changes

[Ihor Radchenko <yantar92@posteo.net>]

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

>> My reading of `track-changes--before' is that `concat' is called on
>> every change except when a new change is already inside the previously
>> recorded one.
>
> The "previously recorded one" (i.e. the info stored in
> `track-changes--before-beg/end/string`) is a conservative
> over-approximation of the changed area.  We (at least) double its size
> every time we have to grow it, specifically to reduce the number of
> times we need to grow it (otherwise we quickly fall into the O(N²)
> trap).

I am not 100% where the O(N^2) is coming from. I'd rather see the
"doubling" explained better in the comment before the code.

In any case, while I do see where the idea of over-expanding the region
comes from, it is not ideal for my use-case in Org mode - it is often
critical to know precise region where the change happened.

Larger region spanning over more lines than needed can easily trigger
re-parsing too much, especially when changes are being made near Org
heading lines. In worst-case scenario, Org mode has to drop parser cache
for the whole edited subtree repeatedly, slowing things down by orders
of magnitude.

And this is not a theoretical consideration - I had to tweak things
considerably in the past for certain Org mass-editing commands in order
to not slow them down because of repeated cache drops.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>