Subject: bug#77924: 31.0.50; [Feature branch] Change marker implementation

From: Gerd Möllmann <[email-masked]>
Date: Tue, 22 Apr 2025 10:34:50 +0200

Gerd Möllmann <[email-masked]> writes:

> Stefan Kangas <[email-masked]> writes:
>
>> This sounds great.  I pushed a couple of typo fixes while reading the
>> patches, please use them as you see fit (squash, etc.).
>
> Thanks, I've ported that back to my side.
>
>>
>> - Any chance you could add a comment explaining how you arrived at
>>   text_index_interval=4*1024?  If it's arbitrarily chosen, adding a
>>   comment to that effect might be useful.
>
> It's neither completely arbitrary nor can I really say much about it.
> INTERVAL / 2 is basically the worst-case distance one has to scan
> through text. Don't really know what to say more, and the above is
> pretty obvious.
>
>>
>> - Maybe rename `text-index-interval` to `text-index--interval` (to
>>   indicate that it's internal)?
>>
>> - I guess `use-text-index` can be removed?
>
> I've removed these Lisp variables a few days ago or so. They were only
> for experimenting with the whole thing.
>
>>> Please see the comments at the start of marker-vector.c and text-index.c
>>> for more details. Also see the thread(s) on emacs-devel with Stef an me.
>>
>> For posterity, I guess that would be:
>>
>> Re: Question about region caches
>> https://lists.gnu.org/r/emacs-devel/2025-03/msg01382.html
>>
>> PS. BTW, a small procedural thing.  Instead of merging master into a
>>     scratch/ branch, I recommend deleting the branch, rebasing it on
>>     master, and then pushing it again.  This way, when we later merge it
>>     into master, we avoid the merge commits, and the history is kept
>>     clean and more easily reviewable.  Not the end of the world either
>>     way, but something to consider.
>
> Sorry, too much work :-).
>
> (For reviewing a branch with merges from master I recommend to find the
> latest merge commit, take the parent commit on the master side, and
> range diff with that. (If you have the merge in the reflog, that
> speeds up finding the latest merge, but that's only the case if you did
> the merge in that repo.))

There was the open question left whether or not it pays off to avoid the
binary search in charpos -> bytepos conversion. Benchmarked it with

(defun elb-replace-region-contents-entry ()
  (with-temp-buffer
    (let ((step (apply #'concat (make-list 2000 "🙂été👶🏿 "))))
      (dotimes (_ (/ 100000 (length step)))
        (insert step)))

    (dotimes (_ 100000)
      (let* ((a (1+ (random (point-max))))
	     (b (1+ (random (point-max))))
	     (beg (min a b))
	     (end (max a b)))
	(replace-region-contents beg end "🙂été👶🏿 🙂été👶🏿 ")))))

2000 runs on my idle Mac mini, M1 etc.

* Without optimization Results

  | test                    | non-gc (s) | gc (s) | gcs | total (s) | err (s) |
  |-------------------------+------------+--------+-----+-----------+---------|
  | replace-region-contents |       0.93 |   0.00 |   0 |      0.93 |    0.33 |
  |-------------------------+------------+--------+-----+-----------+---------|
  | total                   |       0.93 |   0.00 |   0 |      0.93 |    0.33 |

* With opt. Results

  | test                    | non-gc (s) | gc (s) | gcs | total (s) | err (s) |
  |-------------------------+------------+--------+-----+-----------+---------|
  | replace-region-contents |       0.89 |   0.00 |   0 |      0.89 |    0.32 |
  |-------------------------+------------+--------+-----+-----------+---------|
  | total                   |       0.89 |   0.00 |   0 |      0.89 |    0.32 |

I think the large err values are because of the random and the O(ND) in
replace-region-contents. Whatever, the optimization seems to pay off, so
I'll add that to scratch/text-index on savannah later.

Tests with the change:

SUMMARY OF TEST RESULTS
-----------------------
Files examined: 530
Ran 8041 tests, 7765 results as expected, 0 unexpected, 276 skipped

I consider this feature done when that is in, and play with arm64 NEON a
bit instead. In C++ ;-).