Re: Exposing buffer text modifications to Lisp

[Ihor Radchenko <yantar92@gmail.com>]

Eli Zaretskii <eliz@gnu.org> writes:

>> > We already have a TODO item for making markers more efficient; any
>> > takers?
>> 
>> This is trickier than it may appear.
>> Each element in Org AST has 3-7 markers.
>> My real-life large org buffer contains ~200k Org syntax elements
>> (actually more, but not all the elements are ever queried).
>> So, we are talking about 600k-1.4M markers in buffer if Org AST were to
>> use markers.
>> 
>> Now, imagine an edit somewhere near the beginning of Org buffer. Such
>> edit means that Emacs will have to shift positions of nearly all the
>> markers in the buffer. All the >1M markers. On every
>> self-insert-command.
>
> The inner loop of adjust_markers_for_insert is just 40 machine
> instructions.  (This is in unoptimized code; it could be fewer
> instruction in an optimized build.)  Assuming a 3GHz CPU clock, 40
> instructions should take just 13 nsec, and 1 million of these should
> take 13 milliseconds -- a very short time indeed.  I expect that to be
> between 5 and 7 msec in an optimized build.
>
> (Compare that with inserting the characters itself: the first
> insertion could potentially mean moving the gap, which in a large
> buffer means moving megabytes of bytes -- not a negligible feat.)

Noted.
Does Emacs C code provide any generic tree structure implementation?

> So I don't think the performance degradation due to markers is because
> the insert/delete operations on buffer text need to update many
> markers.  I think the real slowdown comes from the functions which
> convert character positions to byte positions and vice versa: these
> use markers.  There are a lot of such calls all over our code, and
> that's where the current linear-linked-list implementation of markers
> slows us down.
>
> Of course, the right method to show the bottleneck(s) is to profile
> the code with a tool like 'prof', and take it from there.  So here's
> one more interesting job for someone to volunteer.

That's what I did in https://orgmode.org/list/87y21wkdwu.fsf@localhost:

>>> The bottleneck appears to be buf_bytepos_to_charpos, called by
>>> BYTE_TO_CHAR macro, which, in turn, is used by set_search_regs

>>> buf_bytepos_to_charpos contains the following loop:
>>> 
>>>   for (tail = BUF_MARKERS (b); tail; tail = tail->next)
>>>     {
>>>       CONSIDER (tail->bytepos, tail->charpos);
>>> 
>>>       /* If we are down to a range of 50 chars,
>>> 	 don't bother checking any other markers;
>>> 	 scan the intervening chars directly now.  */
>>>       if (best_above - bytepos < distance
>>>           || bytepos - best_below < distance)
>>> 	break;
>>>       else
>>>         distance += BYTECHAR_DISTANCE_INCREMENT;
>>>     }
>>> 
>>> I am not sure if I understand the code correctly, but that loop is
>>> clearly scaling performance with the number of markers

>> Org parser goes around this issue by updating AST positions on idle and
>> maintaining asynchronous request queue. This works relatively well
>> because AST queries are skewed to be near the buffer region being
>> edited. I am not sure if similar approach (not trivial to start with)
>> can be efficiently utilized by Emacs. IDK the typical marker access
>> pattern in Emacs core.
>
> If you already have a workaround for marker-related problems, then why
> do you need to hook into insertion and deletion on the lowest level?

Because the workaround relies on before/after-change-functions that may
be suppressed by bad third-party code.

Also, markers will not solve all the needs of Org parser even when they
become more efficient. As I mentioned earlier, we also need to keep
track whether terminal symbols appear in the changed text before/after
modification. It boils down to matching regexps around changed region in
buffer before/after each modification. Suppressed
before/after-change-functions ruin this logic as well.

> And that is my long-standing gripe aimed at developers of 3rd party
> packages: they should come here (or bug-gnu-emacs@gnu.org) and present
> the cases where they needed some missing infrastructure, instead of
> trying to jump through hoops to work around what they perceive as
> Emacs restrictions that (they think) cannot be possibly lifted.  Doing
> the former will have at least two benefits: (a) it will facilitate
> Emacs development into a better platform, and (b) it will avoid giving
> birth to some of the horrible kludges out there, which eventually
> don't work well enough, and thus make Emacs seem less professional
> than it should be.
>
> And if that is my expectation from developers of 3rd party packages, I
> definitely expect that from packages that are bundled, such as Org.
> Since Org is basically part of the core Emacs, it makes little sense
> to me to realize that it goes to such lengths trying to work around
> the limitations, instead of asking the core team to improve the
> existing implementation or add some missing ones.  I could perhaps
> understand if the request existed, but no one volunteered to work on
> it, but not having the requests in the first place I cannot
> understand.

I think I need to clarify my position here.

The important thing you need to know about Org is that it does not only
support Emacs version Org is bundled with.
We currently support Emacs >=26. See
https://orgmode.org/worg/org-maintenance.html#emacs-compatibility

So, any major feature implemented in the development version of Emacs
cannot be easily used. The new feature will mean doubling the relevant
code on Org side: (1) supporting the new feature; (2) compatibility
layer to support older Emacs versions. Which means extra maintenance.

When I am also asked to implement the patch for this new feature for
Emacs, I get triple work.

Moreover, my previous attempt to propose a patch required for Org was
sunk in the depths of emacs-devel threads. (It was a patch for
isearch.el and it does not apply anymore onto master. I plan to
re-submit it when I get more time and interest. Just FYI)

Having said that, I do know that it is a better thing to reach Emacs when
new feature is really beneficial. But I hope that my previous
explanation clarifies why there is a friction (at least, it is the case
for me personally) to contribute to Emacs. Emacs core-related items tend
to go down towards the end of todo lists.

Best,
Ihor