bug#71644: 30.0.50; Severe slowdown in larger files with markers beginning in emacs 29+

[Eli Zaretskii <eliz@gnu.org>]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Cc: Mitchell <mitchellahren@gmail.com>,  Eli Zaretskii <eliz@gnu.org>,
>   71644@debbugs.gnu.org
> Date: Tue, 25 Jun 2024 16:54:44 -0400
> 
> I instrumented the bytes<->chars routines to try and keep track of what
> happens there.  This gives me a histogram showing how many times the
> conversion routines consulted N markers as well as another histogram
> telling me how many times those routines scanned between M*100B and
> (M+1)*100B of text.
> Oh and it gives me the number of markers in the buffer as well (the
> histogram is not buffer-local, but there's basically only one buffer in
> that session).
> 
> The result are below (followed by the actual code).
> There are several odd things in there:
> 
> - The markers histogram is weirdly flat.
> - The markers histogram seems to have a threshold around 800
>   I can't explain.  It seems directly related to the buffer size, tho:
>   with a file half the size, I get half as many markers (40k) and
>   a threshold in the histogram around 400.
> - The number of times we consider exactly 1 marker is probably "too
>   high" because the C code happens to look at the first marker before
>   checking if it's necessary.

The fact that it's related to buffer size is probably because your
test buffer is basically N >> 1 repetitions of the same pattern, so
whatever Org does it does that N times, where N is directly
proportional to the buffer size.

Questions:

How many markers are there in this buffer during the experiment where
you produced the histogram you've posted?  My guess is 48400 or
thereabouts?

Also, what were the buffer positions where you tried your editing
operations?  In particular, where those positions distributed evenly
over the buffer?

And questions to Ihor: what are the reasons Org creates these markers?
In particular, is there any way to know or guess whether these markers
will be distributed more-or-less evenly over the buffer text, or
clustered near some specific positions?  Also, does Org move these
markers frequently, or do they stay put once created?