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

From: Stefan Monnier <[email-masked]>
Date: Tue, 25 Jun 2024 16:54:44 -0400

> One other thing I notice: If I use Emacs-29 but with Org-9.5.5 (i.e., the
> version included in Emacs-28.2) the recipe doesn't show the slowdown.

One more thing: when I use Mitchell's recipe, sometimes buffer edits are
immediate and sometimes they're not (I mean, when following the recipe
exactly, it's not immediate, but if I do things slightly differently and
sometimes after doing other(?) things, it's immediate again).

When I'm in the "state" where editing is not
immediate, it seems to apply only to edits done right before or right
after a header: edits elsewhere (e.g. within some paragraph) are
still "instant".

Oh, and typing text at the end of a header seems to get me out of that
state, somehow (and I don't know how to get back into that state, tho
it sometimes happen).

BTW, my test case is now a large (26MB, 640kLines) Org file consisting of a long
repetition of:

    * asdgasgasdfgsdéadfgasdgafg
    
    asdfadfkh asdfadfkh asdfadfkh asdfadfkh asdfadfkh asdfadfkh asdfadfkh
    asdfadfkh asdfadfkh asdfadfkh asdfadfkh asdfadfkh asdfadfkh asdfadfkh
    asdfadfkh asdfadfkh asdfadfkh asdfadfkh asdfadfkh asdfadfkh asdfadfkh
    asdfadfkh asdfadfkh asdfadfkh asdfadfkh asdfadfkh asdfadfkh asdfadfkh
    asdfadfkh asdfadfkh
    
    ** sf na;l bnsdkh bsadlfv asdl fkbasldfv alsfkg v
    
    asdfadfkh asdfadfkh asdfadfkh asdfadfkh asdfadfkh asdfadfkh asdfadfkh
    asdfadfkh asdfadfkh asdfadfkh asdfadfkh asdfadfkh asdfadfkh asdfadfkh
    asdfadfkh asdfadfkh asdfadfkh asdfadfkh asdfadfkh asdfadfkh asdfadfkh
    asdfadfkh asdfadfkh asdfadfkh asdfadfkh asdfadfkh asdfadfkh asdfadfkh
    asdfadfkh asdfadfkh

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.

(80044 :markers
 ((0 16) (1 3290720) (2 28912) (3 34427) (4 30479) (5 71089) (6 29858)
  (7 29855) (8 29953) (9 30156) (10 30251) (11 30185) (12 30999)
  (13 30270) (14 30530) (15 30332) (16 30175) (17 30278) (18 30187)
  (19 30316) (20 29698) (21 29760) (22 29674) (23 29695) (24 29682)
  (25 29689) (26 29699) (27 29835) (28 30483) (29 30455) (30 30444)
  (31 30313) (32 29666) (33 29696) (34 29739) (35 29781) (36 29694)
  (37 29726) (38 29722) (39 29729) (40 29721) (41 29800) (42 29846)
  (43 29751) (44 29775) (45 29780) (46 29782) (47 29788) (48 29869)
  (49 29891) (50 29811) (51 29823) (52 29834) (53 29817) (54 29833)
  (55 29901) (56 29927) (57 29854) (58 29836) (59 29856) (60 29843)
  (61 29835) (62 29918) (63 29928) (64 29851) (65 29858) (66 29857)
  (67 29859) (68 29854) (69 29934) (70 29907) (71 29859) (72 29848)
  (73 29859) (74 29859) (75 29875) (76 29916) (77 29904) (78 29865)
  (79 29840) (80 29867) (81 29857) (82 29853) (83 29948) (84 29887)
  (85 29861) (86 29852) (87 29850) (88 29866) (89 29880) (90 29935)
  (91 29881) (92 29862) (93 29843) (94 29858) (95 29857) (96 29892)
  (97 29931) (98 29878) (99 29856) (100 29848) (101 29855) (102 29856)
  (103 29904) (104 29931) (105 29866) (106 29867) (107 29849)
  (108 29843) (109 29876) (110 29906) (111 29917) (112 29859)
  (113 29862) (114 29851) (115 29852) (116 29867) (117 29910)
  (118 29922) (119 29848) (120 29862) (121 29858) (122 29837)
  (123 29873) (124 29922) (125 29910) (126 29852) (127 29864)
  (128 29852) (129 29852) (130 29866) (131 29916) (132 29928)
  (133 29833) (134 29863) (135 29864) (136 29844) (137 29864)
  (138 29923) (139 29923) (140 29842) (141 29854) (142 29864)
  (143 29844) (144 29882) (145 29907) (146 29921) (147 29856)
  (148 29838) (149 29864) (150 29873) (151 29854) (152 29925)
  (153 29906) (154 29844) (155 29854) (156 29858) (157 29866)
  (158 29885) (159 29917) (160 29888) (161 29860) (162 29831)
  (163 29865) (164 29874) (165 29888) (166 29907) (167 29887)
  (168 29862) (169 29844) (170 29850) (171 29880) (172 29887)
  (173 29929) (174 29861) (175 29864) (176 29849) (177 29843)
  (178 29880) (179 29909) (180 29916) (181 29853) (182 29864)
  (183 29852) (184 29840) (185 29898) (186 29894) (187 29919)
  (188 29845) (189 29864) (190 29858) (191 29850) (192 29880)
  (193 29908) (194 29914) (195 29842) (196 29860) (197 29860)
  (198 29854) (199 29891) (200 29903) (201 29931) (202 29847)
  (203 29865) (204 29874) (205 29860) (206 29892) (207 29913)
  (208 29921) (209 29860) (210 29850) (211 29872) (212 29877)
  (213 29888) (214 29924) (215 29945) (216 29875) (217 29884)
  (218 29892) (219 29903) (220 29892) (221 29960) (222 29931)
  (223 29884) (224 29877) (225 29898) (226 29919) (227 29927)
  (228 29973) (229 29964) (230 29925) (231 29902) (232 29923)
  (233 29936) (234 29929) (235 29999) (236 29948) (237 29920)
  (238 29913) (239 29917) (240 29938) (241 29948) (242 29994)
  (243 29930) (244 29928) (245 29893) (246 29461) (247 29304)
  (248 29906) (249 29983) (250 29929) (251 29922) (252 29909)
  (253 29917) (254 29930) (255 29947) (256 30002) (257 29913)
  (258 29928) (259 29919) (260 29908) (261 29927) (262 29978)
  (263 29977) (264 29914) (265 29921) (266 29921) (267 29914)
  (268 29924) (269 29963) (270 29998) (271 29903) (272 29921)
  (273 29928) (274 29903) (275 29931) (276 29978) (277 29978)
  (278 29908) (279 29921) (280 29923) (281 29926) (282 29920)
  (283 29969) (284 29987) (285 29899) (286 29919) (287 29930)
  (288 29922) (289 29918) (290 29978) (291 29976) (292 29911)
  (293 29911) (294 29930) (295 29920) (296 29918) (297 29979)
  (298 29977) (299 29918) (300 29904) (301 29928) (302 29929)
  (303 29920) (304 29986) (305 29961) (306 29916) (307 29911)
  (308 29921) (309 29932) (310 29931) (311 29991) (312 29942)
  (313 29924) (314 29902) (315 29922) (316 29940) (317 29934)
  (318 29982) (319 29940) (320 29926) (321 29913) (322 29921)
  (323 29928) (324 29936) (325 30000) (326 29920) (327 29928)
  (328 29915) (329 29915) (330 29930) (331 29959) (332 29983)
  (333 29918) (334 29924) (335 29920) (336 29913) (337 29927)
  (338 29960) (339 29991) (340 29911) (341 29922) (342 29928)
  (343 29907) (344 29931) (345 29966) (346 29984) (347 29909)
  (348 29921) (349 29924) (350 29919) (351 29925) (352 29965)
  (353 29989) (354 29901) (355 29921) (356 29930) (357 29917)
  (358 29917) (359 29979) (360 29981) (361 29913) (362 29909)
  (363 29934) (364 29914) (365 29920) (366 29972) (367 29984)
  (368 29908) (369 29914) (370 29930) (371 29931) (372 29914)
  (373 29990) (374 29959) (375 29914) (376 29913) (377 29927)
  (378 29926) (379 29932) (380 29968) (381 29964) (382 29921)
  (383 29908) (384 29925) (385 29938) (386 29911) (387 29995)
  (388 29946) (389 29920) (390 29913) (391 29925) (392 29928)
  (393 29940) (394 29990) (395 29928) (396 29928) (397 29907)
  (398 29919) (399 29938) (400 29948) (401 29979) (402 29929)
  (403 29922) (404 29917) (405 29917) (406 29932) (407 29941)
  (408 29998) (409 29915) (410 29930) (411 29923) (412 29912)
  (413 29927) (414 29966) (415 29979) (416 29912) (417 29927)
  (418 29925) (419 29916) (420 29920) (421 29955) (422 30000)
  (423 29901) (424 29927) (425 29932) (426 29907) (427 29921)
  (428 29974) (429 29978) (430 29910) (431 29923) (432 29929)
  (433 29922) (434 29918) (435 29965) (436 29987) (437 29899)
  (438 29923) (439 29932) (440 29926) (441 29912) (442 29974)
  (443 29978) (444 29909) (445 29919) (446 29930) (447 29922)
  (448 29914) (449 29973) (450 29979) (451 29920) (452 29908)
  (453 29932) (454 29929) (455 29908) (456 29988) (457 29959)
  (458 29922) (459 29915) (460 29923) (461 29928) (462 29923)
  (463 29993) (464 29940) (465 29928) (466 29908) (467 29926)
  (468 29930) (469 29930) (470 29982) (471 29940) (472 29930)
  (473 29919) (474 29917) (475 29926) (476 29934) (477 29998)
  (478 29920) (479 29932) (480 29917) (481 29921) (482 29924)
  (483 29953) (484 29985) (485 29916) (486 29932) (487 29920)
  (488 29915) (489 29923) (490 29908) (491 29377) (492 28865)
  (493 29336) (494 29924) (495 29905) (496 29917) (497 29966)
  (498 29982) (499 29907) (500 29927) (501 29922) (502 29913)
  (503 29915) (504 29965) (505 29987) (506 29903) (507 29923)
  (508 29928) (509 29909) (510 29911) (511 29975) (512 29981)
  (513 29915) (514 29911) (515 29926) (516 29914) (517 29912)
  (518 29968) (519 29984) (520 29910) (521 29912) (522 29932)
  (523 29921) (524 29908) (525 29990) (526 29955) (527 29922)
  (528 29909) (529 29923) (530 29920) (531 29926) (532 29966)
  (533 29962) (534 29927) (535 29906) (536 29923) (537 29924)
  (538 29911) (539 29993) (540 29944) (541 29926) (542 29911)
  (543 29921) (544 29920) (545 29936) (546 29988) (547 29930)
  (548 29930) (549 29905) (550 29917) (551 29926) (552 29944)
  (553 29979) (554 29931) (555 29924) (556 29911) (557 29915)
  (558 29924) (559 29937) (560 29998) (561 29917) (562 29928)
  (563 29925) (564 29902) (565 29921) (566 29964) (567 29977)
  (568 29918) (569 29925) (570 29921) (571 29910) (572 29914)
  (573 29953) (574 29998) (575 29907) (576 29925) (577 29930)
  (578 29897) (579 29917) (580 29972) (581 29976) (582 29916)
  (583 29921) (584 29927) (585 29912) (586 29914) (587 29963)
  (588 29989) (589 29903) (590 29919) (591 29930) (592 29914)
  (593 29908) (594 29974) (595 29980) (596 29911) (597 29913)
  (598 29928) (599 29912) (600 29912) (601 29973) (602 29981)
  (603 29918) (604 29910) (605 29922) (606 29923) (607 29906)
  (608 29986) (609 29963) (610 29922) (611 29911) (612 29917)
  (613 29922) (614 29921) (615 29991) (616 29944) (617 29930)
  (618 29904) (619 29916) (620 29926) (621 29928) (622 29980)
  (623 29948) (624 29926) (625 29917) (626 29907) (627 29922)
  (628 29932) (629 30000) (630 29924) (631 29928) (632 29915)
  (633 29907) (634 29922) (635 29953) (636 29987) (637 29918)
  (638 29926) (639 29918) (640 29905) (641 29921) (642 29954)
  (643 29995) (644 29911) (645 29928) (646 29922) (647 29901)
  (648 29917) (649 29966) (650 29986) (651 29915) (652 29921)
  (653 29920) (654 29909) (655 29915) (656 29965) (657 29991)
  (658 29907) (659 29923) (660 29924) (661 29905) (662 29911)
  (663 29975) (664 29989) (665 29913) (666 29911) (667 29924)
  (668 29910) (669 29912) (670 29972) (671 29988) (672 29908)
  (673 29914) (674 29924) (675 29921) (676 29908) (677 29994)
  (678 29959) (679 29916) (680 29911) (681 29919) (682 29920)
  (683 29926) (684 29972) (685 29964) (686 29927) (687 29902)
  (688 29919) (689 29924) (690 29911) (691 29997) (692 29952)
  (693 29920) (694 29909) (695 29917) (696 29920) (697 29936)
  (698 29992) (699 29932) (700 29930) (701 29903) (702 29913)
  (703 29926) (704 29944) (705 29987) (706 29929) (707 29924)
  (708 29909) (709 29911) (710 29924) (711 29941) (712 30002)
  (713 29915) (714 29930) (715 29917) (716 29902) (717 29921)
  (718 29970) (719 29979) (720 29914) (721 29925) (722 29917)
  (723 29910) (724 29914) (725 29959) (726 30000) (727 29907)
  (728 29921) (729 29926) (730 29897) (731 29917) (732 29976)
  (733 29982) (734 29908) (735 29845) (736 29275) (737 28476)
  (738 28898) (739 29693) (740 29989) (741 29897) (742 29915)
  (743 29924) (744 29912) (745 29908) (746 29980) (747 29974)
  (748 29907) (749 29909) (750 29922) (751 29912) (752 29914)
  (753 29975) (754 29975) (755 29914) (756 29902) (757 29920)
  (758 29921) (759 29910) (760 29988) (761 29957) (762 29914)
  (763 29907) (764 29915) (765 29920) (766 29925) (767 29993)
  (768 29938) (769 29922) (770 29898) (771 29916) (772 29924)
  (773 29930) (774 29984) (775 29938) (776 29922) (777 29911)
  (778 29907) (779 29920) (780 29934) (781 30000) (782 29918)
  (783 29924) (784 29909) (785 29907) (786 29920) (787 29959)
  (788 29981) (789 29914) (790 29795) (791 21494) (792 8509) (793 804)
  (794 804) (795 800) (796 800) (797 800) (798 717) (799 323)
  (800 200) (801 202) (802 200) (803 200) (804 172) (805 26) (5533 1)
  (5548 1) (26958 1) (26974 1) (48384 1) (48400 1))
 :distance
 ((0 26807330) (1 5518) (2 941) (3 160056) (4 2) (5 87) (6 25) (8 2)
  (9 2) (10 7) (11 1) (12 22) (13 1) (15 7) (28 1) (30 4) (32 5)
  (35 7) (39 3) (40 1) (42 5) (45 4) (48 2) (49 3) (51 1) (52 1)
  (54 22) (55 7) (82 1) (2762 1) (2772 1) (13478 1) (13485 1)
  (24191 1) (24198 1)))

diff --git a/lisp/subr.el b/lisp/subr.el
index d9df8d1a458..1e9c768fdfe 100644
--- a/lisp/subr.el
+++ b/lisp/subr.el
@@ -6968,6 +6968,22 @@ internal--format-docstring-line
     (error "Unable to fill string containing newline: %S" string))
   (internal--fill-string-single-line (apply #'format string objects)))
 
+(defun bytechar--stats ()
+  (unless (hash-table-p internal--bytechar-marker-counts)
+    (setq internal--bytechar-marker-counts (make-hash-table)))
+  (unless (hash-table-p internal--bytechar-distance-counts)
+    (setq internal--bytechar-distance-counts (make-hash-table)))
+  (require 'map)
+  (list (internal--count-markers)
+        :markers
+        (mapcar (lambda (x) (list (car x) (cdr x)))
+             (sort (map-into internal--bytechar-marker-counts 'alist)
+                   #'car-less-than-car))
+        :distance
+        (mapcar (lambda (x) (list (car x) (cdr x)))
+             (sort (map-into internal--bytechar-distance-counts 'alist)
+              #'car-less-than-car))))
+
 (defun json-available-p ()
   "Return non-nil if Emacs has libjansson support."
   (and (fboundp 'json--available-p)
diff --git a/src/marker.c b/src/marker.c
index d220dd82692..623065de3f7 100644
--- a/src/marker.c
+++ b/src/marker.c
@@ -133,6 +133,28 @@ CHECK_MARKER (Lisp_Object x)
   CHECK_TYPE (MARKERP (x), Qmarkerp, x);
 }
 
+static void
+bytechar_stats (int marker_count, ptrdiff_t distance)
+{
+  if (HASH_TABLE_P (bytechar_marker_counts))
+    {
+      Lisp_Object key = make_fixnum (marker_count);
+      Lisp_Object oldcount = Fgethash (key, bytechar_marker_counts, Qnil);
+      Lisp_Object newcount
+	= make_fixnum (FIXNUMP (oldcount) ? 1 + XFIXNUM (oldcount) : 1);
+      Fputhash (key, newcount, bytechar_marker_counts);
+    }
+
+  if (HASH_TABLE_P (bytechar_distance_counts))
+    {
+      Lisp_Object key = make_fixnum (distance / 100);
+      Lisp_Object oldcount = Fgethash (key, bytechar_distance_counts, Qnil);
+      Lisp_Object newcount
+	= make_fixnum (FIXNUMP (oldcount) ? 1 + XFIXNUM (oldcount) : 1);
+      Fputhash (key, newcount, bytechar_distance_counts);
+    }
+}
+
 /* When converting bytes from/to chars, we look through the list of
    markers to try and find a good starting point (since markers keep
    track of both bytepos and charpos at the same time).
@@ -164,6 +186,7 @@ buf_charpos_to_bytepos (struct buffer *b, ptrdiff_t charpos)
   ptrdiff_t best_above, best_above_byte;
   ptrdiff_t best_below, best_below_byte;
   ptrdiff_t distance = BYTECHAR_DISTANCE_INITIAL;
+  int marker_count = 0;
 
   eassert (BUF_BEG (b) <= charpos && charpos <= BUF_Z (b));
 
@@ -198,6 +221,7 @@ buf_charpos_to_bytepos (struct buffer *b, ptrdiff_t charpos)
 
   for (tail = BUF_MARKERS (b); tail; tail = tail->next)
     {
+      marker_count++;
       CONSIDER (tail->charpos, tail->bytepos);
 
       /* If we are down to a range of 50 chars,
@@ -215,6 +239,10 @@ buf_charpos_to_bytepos (struct buffer *b, ptrdiff_t charpos)
      Scan, counting characters, from whichever one is closer.  */
 
   eassert (best_below <= charpos && charpos <= best_above);
+  if (!NILP (bytechar_marker_counts))
+    bytechar_stats (marker_count,
+		    min (charpos - best_below, best_above - charpos));
+
   if (charpos - best_below < best_above - charpos)
     {
       bool record = charpos - best_below > 5000;
@@ -321,6 +349,7 @@ buf_bytepos_to_charpos (struct buffer *b, ptrdiff_t bytepos)
   ptrdiff_t best_above, best_above_byte;
   ptrdiff_t best_below, best_below_byte;
   ptrdiff_t distance = BYTECHAR_DISTANCE_INITIAL;
+  int marker_count = 0;
 
   eassert (BUF_BEG_BYTE (b) <= bytepos && bytepos <= BUF_Z_BYTE (b));
 
@@ -350,6 +379,7 @@ buf_bytepos_to_charpos (struct buffer *b, ptrdiff_t bytepos)
 
   for (tail = BUF_MARKERS (b); tail; tail = tail->next)
     {
+      marker_count++;
       CONSIDER (tail->bytepos, tail->charpos);
 
       /* If we are down to a range of 50 chars,
@@ -365,6 +395,9 @@ buf_bytepos_to_charpos (struct buffer *b, ptrdiff_t bytepos)
   /* We get here if we did not exactly hit one of the known places.
      We have one known above and one known below.
      Scan, counting characters, from whichever one is closer.  */
+  if (!NILP (bytechar_marker_counts))
+    bytechar_stats (marker_count,
+		    min (bytepos - best_below_byte, best_above_byte - bytepos));
 
   if (bytepos - best_below_byte < best_above_byte - bytepos)
     {
@@ -759,22 +792,23 @@ DEFUN ("set-marker-insertion-type", Fset_marker_insertion_type,
   return type;
 }
 
-#ifdef MARKER_DEBUG
-
 /* For debugging -- count the markers in buffer BUF.  */
 
-int
-count_markers (struct buffer *buf)
+DEFUN ("internal--count-markers", Fcount_markers, Scount_markers, 0, 0, 0,
+       doc: /* Return the number of markers in the current buffer.  */)
+  (void)
 {
   int total = 0;
   struct Lisp_Marker *tail;
 
-  for (tail = BUF_MARKERS (buf); tail; tail = tail->next)
+  for (tail = BUF_MARKERS (current_buffer); tail; tail = tail->next)
     total++;
 
-  return total;
+  return make_fixnum (total);
 }
 
+#ifdef MARKER_DEBUG
+
 /* For debugging -- recompute the bytepos corresponding
    to CHARPOS in the simplest, most reliable way.  */
 
@@ -804,4 +838,18 @@ syms_of_marker (void)
   defsubr (&Scopy_marker);
   defsubr (&Smarker_insertion_type);
   defsubr (&Sset_marker_insertion_type);
+  defsubr (&Scount_markers);
+
+  DEFVAR_LISP ("internal--bytechar-marker-counts",
+	       bytechar_marker_counts, doc: /* Hihi */);
+  bytechar_marker_counts = Qnil;
+
+  DEFVAR_LISP ("internal--bytechar-distance-counts",
+	       bytechar_distance_counts, doc: /* Hoho */);
+  bytechar_distance_counts = Qnil;
+
+  DEFVAR_INT ("internal--bytechar-distance-increment",
+              bytechar_distance_increment,
+              doc: /* Haha */);
+  bytechar_distance_increment = 50;
 }