GNU bug report logs - #70077
An easier way to track buffer changes

Previous Next

Full log

View this message in rfc822 format

From: Ihor Radchenko <yantar92 <at> posteo.net>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: casouri <at> gmail.com, 70077 <at> debbugs.gnu.org, qhong <at> alum.mit.edu, frederic.bour <at> lakaban.net, joaotavora <at> gmail.com, mail <at> nicolasgoaziou.fr, acm <at> muc.de, Eli Zaretskii <eliz <at> gnu.org>, stephen_leake <at> stephe-leake.org, alan.zimm <at> gmail.com, phillip.lord <at> russet.org.uk
Subject: bug#70077: An easier way to track buffer changes
Date: Wed, 03 Apr 2024 12:34:47 +0000

Stefan Monnier <monnier <at> 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>

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.