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

[Stefan Monnier]

> 1. Start emacs 29.3 (or 30.0.50) with emacs -q.
> 2. Paste the minimal config at
> https://gist.github.com/kings2u/30b7a22dfa38fe0d5dc18adaf0e5e9de into the
> scratch buffer and eval-buffer. (Note on my system I'm using the `counsel`
> version current as of counsel-20240502.743, but any recent version will
> reproduce the bug).

I used the code below:

    (customize-set-variable 'large-file-warning-threshold nil)
    (package-install 'counsel)
    (package-activate 'counsel)

> 7. Start typing `n` `space`, or `t` `space` several times very fast and
> observe how long it takes for the abbrev expansions (defined in the minimal
> config above) to show up on the screen.

Without running `counsel-outline`, the insertion is "immediate", whereas
after `counsel-outline` it takes about two seconds for me.

> Using emacs 29+, when I use `profiler-start` (CPU) between Steps 4 and 5,
> and then `profiler-stop` after Step 7, I get a very big entry (e.g., 70%)
> for `redisplay_internal (C function)` in the `profiler-report`. Using the
> `profiler` at the same points using emacs 28.2, I don’t get a big entry for
> `redisplay_internal (C function)`.

[ I haven't been able to get a meaningful profiler report yet.
  E.g. I get 82% of the time given to `read-from-minibuffer`, which is
  presumably the time spent typing `M-x profiler-report RET` or some
  such, even though I typed enough `n SPC` repetitions that it should
  dwarf that.  Not sure what's going on.  ]

Also I notice that if I do `n` and then wait, it takes the same
amount of time to see the result as if I do `n n n n`
and then wait.  So it seems that the command themselves execute
"instantly", and the delay occurs later (jit-lock? redisplay? ...).

I also notice that step 6 is important: if I just go straight to line 35
and type text, there's no delay.
Other thing I noticed

   M-g M-g 60000 RET
   n n n n n
   M-g M-g 35 RET
   n n n n n

there's no delays typing the `n` at line 60000 but there is a 2s delay
at line 35.

The fact that the absence of non-ASCII chars eliminates the problem
strongly points the finger to the bytes<->chars conversion which relies
on markers, indeed, but it's still very puzzling: line 35 is about 1.5kB
from the beginning of the buffer, so the conversion should be simple
and fast. there.  IOW, if it's a slow bytes<->chars conversion it's
probably a conversion taking place elsewhere than near point.

AFAICT the most significant change w.r.t markers in Emacs-29 is that
markers aren't used internally for overlays any more, so there are
usually *fewer* markers in Emacs-29 buffers than in Emacs-28 buffers
(which can be both favorable and detrimental to bytes<->chars
conversion, depending on details).  But in any case, (overlays-in
(point-min) (point-max)) tells me there's only one overlay and even 0 in
Emacs-28, so that can't be the reason for the change.


        Stefan "puzzled"