bug#64391: buffer narrowing slowdown regression in emacs 29

["Mattias Engdegård" <mattias.engdegard@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 717 bytes --]

How expensive markers can be when a buffer is modified is often unappreciated. Here are the results of a benchmark to illustrate the cost (code attached).
A buffer contains "abababab...", we optionally add a marker to every other position, and then time the deletion of all the "a"s. Results:

|   size | without markers | with markers |
|--------+-----------------+--------------|
|    500 |           0.000 |        0.001 |
|   1000 |           0.001 |        0.004 |
|   5000 |           0.002 |        0.089 |
|  10000 |           0.005 |        0.363 |
|  50000 |           0.024 |        9.527 |
| 100000 |           0.049 |       58.048 |

Now there's something for the curve-fitters among you.


[-- Attachment #2: abench4.el --]
[-- Type: application/octet-stream, Size: 1519 bytes --]

;;; -*- lexical-binding: t -*-

(require 'cl-lib)

(defun abench-run ()
  (let ((buffer-undo-list t))
    (goto-char (point-min))
    (while (not (eobp))
      (delete-char 1)
      (forward-char))))

(defun abench (size use-markers)
  (with-temp-buffer
    ;; Populate buffer
    (insert (mapconcat #'identity (make-list size "ab") nil))
    ;; Insert markers
    (let ((markers nil))
      (when use-markers
        (dotimes (i size)
          (push (set-marker (make-marker) (* i 2)) markers)))
      ;; Run operation
      (garbage-collect)
      (let ((gcs0 gcs-done)
            (gc-e0 gc-elapsed)
            (t0 (float-time)))
        (abench-run)
        (let ((dt (- (float-time) t0))
              (gcs (- gcs-done gcs0))
              (gc-time (- gc-elapsed gc-e0)))
          (cl-assert
           (equal (buffer-string)
                  (mapconcat #'identity (make-list size "b") nil)))
          (list dt gcs gc-time))))))

(defun abench-main ()
  (princ (format "Emacs %s\n" emacs-version))
  (princ (format "| size | without markers | with markers |\n"))
  (princ (format "|------+-----------------+--------------|\n"))
  (dolist (size '(500 1000 5000 10000 50000 100000))
    (let ((res-without (abench size nil))
          (res-with (abench size t)))
        (princ (format "| %d | %.3f | %.3f |\n"
                       size
                       (nth 0 res-without)
                       (nth 0 res-with)))))
  (princ (format "|------+-----------------+--------------|\n"))
  )

(abench-main)