bug#64391: 30.0.50; buffer narrowing slowdown regression in emacs 29

[Andrew Cohen]

I have noticed a huge slowdown in parsing email headers in gnus. After
some debugging with help from Mattias Engdegård, the problem has been
traced to the narrowing code introduced in

commit ba9315b1641b483f2bf843c38dcdba0cd1643a55 (HEAD)
Merge: aef803d6c3d a3b654e069e
Author: Gregory Heytings <gregory@heytings.org>
Date:   Thu Nov 24 14:21:30 2022 +0100

    Merge master into feature/improved-locked-narrowing.

Gnus populates a buffer with headers from a set of email messages and
then parses them by: narrowing the buffer to the headers for an
individual message; parsing the headers; widening; and then repeating
for the next message.  As part of the parsing the headers are "unfolded"
so that each header doesn't include line breaks. I noticed that for a
long list of messages (10,000) this takes between one and two orders of
magnitude more time in Emacs 30 than in Emacs 28. Unfolding all the
headers in the full buffer before the parsing process removes most of
the slowdown. The slowdown seems to grow quadratically with the size of
the buffer.

The problem seems fairly general and Mattias has produced a simple test
case to demonstrate the issue (code at the end of this message):

1. Create a buffer with 100,000 lines each containing two characters  "ab".
2. Loop through the buffer narrowing to each line, and immediately widening
    back to the full buffer (so no change is made to the buffer
    contents).
3.  Loop through the buffer removing the first character of each line.

This takes a very long time compared with reversing the order of 2. and 3.

Emacs 28.2
Modify after narrowing:  0.173 s elapsed, 0 GCs, 0.000 s GC, 0.173 s non-GC
Modify before narrowing: 0.160 s elapsed, 0 GCs, 0.000 s GC, 0.160 s non-GC

Emacs 29.0.92
Modify after narrowing:  4.454 s elapsed, 9 GCs, 0.115 s GC, 4.339 s non-GC
Modify before narrowing: 0.291 s elapsed, 9 GCs, 0.114 s GC, 0.177 s non-GC

The problem may be the creation of markers in the narrowing process that
slows down further mutation. (Also note that the new code has introduced
some significant GC that was previously absent).

abench2.el
Description: Demonstrate narrowing slowdown

-- 
Andrew Cohen