bug#58558: 29.0.50; re-search-forward is slow in some buffers

[Ihor Radchenko <yantar92@posteo.net>]

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

>> My guess: number of markers is growing somehow?
>
> `buf_bytepos_to_charpos` itself creates markers (using them as a cache
> of previous conversions), so that might be why.
>
> But we only look at the first N markers where N*50 is the distance to
> the closest marker found so far.  So growth is not sufficient (it's
> clearly a part of the reason, tho).

What about the following degenerate case:
- Most of the buffer markers are located near point-min;
- We are searching for position near point-max;
- point-max is in order of 21,677,448 (this is my actual file I use for testing)

The number of for loop cycles is then min(21,677,448/50 = ~400k, BUF_MARKERS.size())

Of course, my above argument should not matter in theory, when recent
search matches are cached by build_marker, but my break build_marker
_never_ triggered for some reason.

How can build_marker not be triggered?

From my reading of the code, it happens when the following switch does
not fire.

      bool record = bytepos - best_below_byte > 5000;

I note that this condition will not trigger if all the markers are
above.

On the other hand, this particular condition is there for the last 25
years or so. Just brainstorming...

-- 
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>