Markers in a gap array

Markers in a gap array

[Stefan Monnier]

I've just pushed to `scratch/markers-as-gap-array` code that seems to be
working correctly (passes all the tests, for example).
The code is not ready for `master` (there are some cleanups to do), but
if you use code that uses many markers, I'd be interested to hear about
your experience with it.

What it does: replace the unordered singly-linked list of markers that
we keep in every buffer, with an "ordered array (with gap) of markers".
The main purpose is to try and eliminate some pathological behavior in
the bytepos<->charpos conversion routines (which "abuse" markers as
a cache of bytepos<->charpos conversions) when you have many markers in
large buffers.

There's no free lunch, so this comes at the cost of slowing down other
marker operations, which is why I'd like to hear about your experience.
Here are those operations and how the performance is expected to compare:

The good:
- Conversion bytepos<->charpos used to be O(N), now it's O(lg N).
  The frequency of such conversions can vary drastically depending on
  the circumstances, so a lot of use-cases will see no difference at all,
  whereas some particular use-cases should see a significant speed up.

The indifferent:
- `make-marker`: Was and is still O(1).
- `marker-position`: Was and is still O(1).
- Adjustments when performing text insertion/deletion: Used to be O(N)
  and is still O(N), but with a smaller constant factor because
  it can fetch the markers in parallel whereas that used to be
  sequentialized by the pointer chasing of the singly-linked list and
  its branch instructions should be easier to predict.
  It's unlikely you'll see the gain, tho, because those adjustments are
  usually drowned in the noise of everything else we do upon text
  insertion/deletion.

The bad:
- `copy-marker`: Used to be O(1), now will cost time O(M + lg N) where
  N is the number of markers and M is the distance between where this
  marker is inserted and the previous position of the gap.
  The `lg N` factor should be hopefully cheap enough.
  The `M` factor could be more worrisome, since M can be as large as N,
  but there are two reasons to be optimistic:
  - The locality which makes our "gap buffer" usually efficient should
    hopefully work its same magic here keeping M usually small.
  - Moving the gap is a `memmove` and this can be performed quite fast
    even for fairly large M (i.e. the constant factor applied to
    M should be quite small).
- `(set-marker m nil)`: Used to be O(N), now costs the same as
  `copy-marker`, hence O(M + lg N).
  Even when M=N, this should be much better than the previous worst case
  because the constant factor applied to M should be *much* smaller.
  So it could be considered to be part of "The good" except that
  (set-marker m nil) was often near O(1) in practice if `m` was recently
  created (in which case it was found near the beginning of the
  singly-linked list).

So, for instance, `save-excursion` used to do a `copy-marker` followed
by a (set-marker m nil), both of which were, typically, O(1) and are now
made slower.

Side note: IIUC this design is similar to the one used in XEmacs, so
we're slowly catching up to them.  🙂


        Stefan

Re: Markers in a gap array

[Ihor Radchenko]

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

> There's no free lunch, so this comes at the cost of slowing down other
> marker operations, which is why I'd like to hear about your experience.
> ...
> So, for instance, `save-excursion` used to do a `copy-marker` followed
> by a (set-marker m nil), both of which were, typically, O(1) and are now
> made slower.

First experience - severe performance degradation compared to master.

Some perf stats:

;; Switch to todo and mark next 3 times, on branch
    ;; 28.72%  emacs            emacs                                      [.] markers_sanity_check
    ;; 11.83%  emacs            emacs                                      [.] Fmemq
    ;;  5.31%  emacs            emacs                                      [.] process_mark_stack
    ;;  2.59%  emacs            emacs                                      [.] re_match_2_internal
    ;;  2.47%  emacs            emacs                                      [.] buf_bytepos_to_charpos
    ;;  1.60%  emacs            emacs                                      [.] Ffuncall
    ;;  1.56%  emacs            emacs                                      [.] vector_marked_p

;; master
    ;; 14.31%  emacs            emacs                                          [.] Fmemq
    ;; 11.18%  emacs            emacs                                          [.] re_match_2_internal
    ;;  3.97%  emacs            emacs                                          [.] buf_bytepos_to_charpos
    ;;  2.60%  emacs            emacs                                          [.] process_mark_stack
    ;;  2.00%  emacs            emacs                                          [.] scan_sexps_forward

;; Just building agenda, on branch
    ;; 24.69%  emacs         emacs                                           [.] markers_sanity_check
    ;; 11.32%  emacs         emacs                                           [.] re_search_2
    ;;  6.08%  emacs         emacs                                           [.] re_match_2_internal
    ;;  4.57%  emacs         emacs                                           [.] process_mark_stack
    ;;  3.61%  emacs         emacs                                           [.] funcall_subr
    ;;  2.98%  emacs         emacs                                           [.] Ffuncall
    ;;  2.79%  emacs         emacs                                           [.] Fmemq
    ;;  2.73%  emacs         emacs                                           [.] buf_bytepos_to_charpos
    ;;  2.38%  emacs         emacs                                           [.] buf_charpos_to_bytepos

;; Just building agenda, master
    ;; 13.56%  emacs           emacs                                          [.] re_match_2_internal
    ;; 12.02%  emacs           emacs                                          [.] exec_byte_code
    ;;  7.92%  emacs           emacs                                          [.] re_search_2
    ;;  6.98%  emacs           emacs                                          [.] Fmemq
    ;;  5.15%  emacs           emacs                                          [.] process_mark_stack
    ;;  4.60%  emacs           emacs                                          [.] funcall_subr
    ;;  2.58%  emacs           emacs                                          [.] Ffuncall
    ;;  1.93%  emacs           emacs                                          [.] funcall_general
    ;;  1.33%  emacs           org-element-ast-1c181933-d46555e0.eln          [.] F6f72672d656c656d656e742d74797065_org_element_type_0
    ;;  1.26%  emacs           emacs                                          [.] plist_get
    ;;  1.22%  emacs           emacs                                          [.] assq_no_quit
    ;;  1.22%  emacs           emacs                                          [.] buf_bytepos_to_charpos
    ;;  1.02%  emacs           emacs                                          [.] vector_marked_p
    ;;  0.95%  emacs           emacs                                          [.] buf_charpos_to_bytepos



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

Re: Markers in a gap array

[Stefan Monnier]

Ihor Radchenko [2024-07-04 10:24:01] wrote:
> Stefan Monnier <monnier@iro.umontreal.ca> writes:
>> There's no free lunch, so this comes at the cost of slowing down other
>> marker operations, which is why I'd like to hear about your experience.
>> ...
>> So, for instance, `save-excursion` used to do a `copy-marker` followed
>> by a (set-marker m nil), both of which were, typically, O(1) and are now
>> made slower.
>
> First experience - severe performance degradation compared to master.
>
> Some perf stats:
>
> ;; Switch to todo and mark next 3 times, on branch
>     ;; 28.72%  emacs            emacs                                      [.] markers_sanity_check

Did you build with or without assertions?
And indeed, I need to rework them to be "more conditional" (but I was
focused on correctness until now).  You should probably remove those
calls to `markers_sanity_check` by hand when testing performance, sorry.


        Stefan

Re: Markers in a gap array

[Ihor Radchenko]

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

>> Some perf stats:
>>
>> ;; Switch to todo and mark next 3 times, on branch
>>     ;; 28.72%  emacs            emacs                                      [.] markers_sanity_check
>
> Did you build with or without assertions?

Without.

> And indeed, I need to rework them to be "more conditional" (but I was
> focused on correctness until now).  You should probably remove those
> calls to `markers_sanity_check` by hand when testing performance, sorry.

Without these calls, I can see some speed improvement in
buf_bytepos_to_charpos, but I do not currently have a reliable
reproducer to trigger buf_bytepos_to_charpos slowdown on master, so it
is comparing very small numbers.

I do not see any noticeable overall performance degradation either
though.

My test:

(setq yant/re "\\(?:\\(?:\\<DEADLINE: *\\(\\(?:<\\(?:[[:digit:]]\\{4\\}-[[:digit:]]\\{2\\}-[[:digit:]]\\{2\\}\\(?: [[:alpha:]]+\\)?\\)\\(?: [[:digit:]]\\{1,2\\}:[[:digit:]]\\{2\\}\\(?:-[[:digit:]]\\{1,2\\}:[[:digit:]]\\{2\\}\\)?\\)?\\(?:\\(?: [+.:-]\\{1,2\\}[[:digit:]]+[dhmwy]\\(?:/[[:digit:]]+[dhmwy]\\)?\\)\\{1,2\\}\\)?>\\)\\)\\)\\|\\(?:\\(?:<\\(?:[[:digit:]]\\{4\\}-[[:digit:]]\\{2\\}-[[:digit:]]\\{2\\}\\(?: [[:alpha:]]+\\)?\\)\\(?: [[:digit:]]\\{1,2\\}:[[:digit:]]\\{2\\}\\(?:-[[:digit:]]\\{1,2\\}:[[:digit:]]\\{2\\}\\)?\\)?\\(?:\\(?: [+.:-]\\{1,2\\}[[:digit:]]+[dhmwy]\\(?:/[[:digit:]]+[dhmwy]\\)?\\)\\{1,2\\}\\)?>\\)\\|^\\*+[[:blank:]]+\\(?:[[:upper:]]+[[:blank:]]+\\)?\\[#A]\\|^[[:space:]]*:STYLE:[[:space:]]+habit[[:space:]]*$\\)\\)")
(benchmark-progn (goto-char (point-min)) (while (re-search-forward yant/re nil t)))
(benchmark-run 10 (goto-char (point-min)) (while (re-search-forward yant/re nil t)))

;; On the branch

;; # Samples: 35K of event 'cycles:Pu'
;; # Event count (approx.): 37616970588
;; #
;; # Overhead  Command       Shared Object                Symbol                                      
;; # ........  ............  ...........................  ............................................
;; #
;;     54.99%  emacs         emacs                        [.] re_match_2_internal
;;     18.19%  emacs         emacs                        [.] re_search_2
;;      8.13%  emacs         emacs                        [.] sub_char_table_ref
;;      4.49%  emacs         emacs                        [.] char_table_ref
;;      3.66%  emacs         emacs                        [.] unbind_to
;;      2.05%  emacs         emacs                        [.] unwind_re_match
;;      1.78%  emacs         emacs                        [.] extract_number_and_incr
;;      1.70%  emacs         emacs                        [.] string_char_and_length
;;      1.01%  emacs         emacs                        [.] extract_address
;;      0.96%  emacs         emacs                        [.] buf_bytepos_to_charpos
;;      0.83%  emacs         emacs                        [.] record_unwind_protect_ptr
;;      0.68%  emacs         emacs                        [.] execute_charset

;; On master

;; # Samples: 44K of event 'cycles:Pu'
;; # Event count (approx.): 40534509250
;; #
;; # Overhead  Command       Shared Object                                  Symbol                                                                                                        
;; # ........  ............  .............................................  ..............................................................................................................
;; #
;;     52.60%  emacs         emacs                                          [.] re_match_2_internal
;;     16.88%  emacs         emacs                                          [.] re_search_2
;;      7.80%  emacs         emacs                                          [.] sub_char_table_ref
;;      3.65%  emacs         emacs                                          [.] char_table_ref
;;      3.42%  emacs         emacs                                          [.] unbind_to
;;      2.21%  emacs         emacs                                          [.] buf_bytepos_to_charpos
;;      1.90%  emacs         emacs                                          [.] unwind_re_match
;;      1.87%  emacs         emacs                                          [.] extract_number_and_incr
;;      1.62%  emacs         emacs                                          [.] string_char_and_length
;;      0.97%  emacs         emacs                                          [.] extract_address
;;      0.92%  emacs         emacs                                          [.] scan_sexps_forward
;;      0.82%  emacs         emacs                                          [.] record_unwind_protect_ptr
;;      0.70%  emacs         emacs                                          [.] execute_charset

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

Re: Markers in a gap array

[Stefan Monnier]

Ihor Radchenko [2024-07-04 14:30:47] wrote:

> Stefan Monnier <monnier@iro.umontreal.ca> writes:
>
>>> Some perf stats:
>>>
>>> ;; Switch to todo and mark next 3 times, on branch
>>>     ;; 28.72%  emacs            emacs
>>> [.] markers_sanity_check
>>
>> Did you build with or without assertions?
>
> Without.
>
>> And indeed, I need to rework them to be "more conditional" (but I was
>> focused on correctness until now).  You should probably remove those
>> calls to `markers_sanity_check` by hand when testing performance, sorry.
>
> Without these calls, I can see some speed improvement in
> buf_bytepos_to_charpos, but I do not currently have a reliable
> reproducer to trigger buf_bytepos_to_charpos slowdown on master, so it
> is comparing very small numbers.

Hmm... I tried a benchmark based on:

    (defconst elb-bytechar-buffer
      (let ((buf (get-buffer-create " *elb-bytechar*")))
        (with-current-buffer buf
          (let ((step (apply #'concat "🙂 foo\n" (make-list 2000 "asdf "))))
            (dotimes (_ (/ 10000000 (length step)))
              (insert step))
            buf))))
    
    (defconst elb-bytechar-re "\\<.\\> \\<.\\> bar")
    
    (defun elb-bytechar--aux (nmarkers lookup &optional marker-fun)
      (with-current-buffer elb-bytechar-buffer
        (let ((step (/ (buffer-size) nmarkers))
              (markers nil))
          (dotimes (i nmarkers)
            (push (copy-marker (funcall (or marker-fun #'identity) (* i step)))
                  markers))
          (dotimes (_ 10)
            (goto-char (point-min))
            (let ((parse-sexp-lookup-properties lookup))
              (re-search-forward elb-bytechar-re nil t))))))

where I call `elb-bytechar--aux` with various arguments.

[ This benchmark is a test of the performance of
  bytepos->charpos conversion because the regexp engine works only with
  bytepos internally and it needs to convert it to charpos whenever it
  looks up the `syntax-table` text-property, which happens for example
  for \< and \>.  IME, this is the most important use of the
  bytepos->charpos conversion.  ]

And like you, I don't see any speed improvement from the branch.  On the
other hand, my trivial "thinko fix" b595b4598 (which I thought would
have no real-life effect) seems to make a significant difference (see
the results below).  So maybe the reason why you can't reproduce the
slowdown is because of b595b4598?  And maybe we should install that into
`emacs-30`?

In any case, these benchmarks suggest my branch isn't very exciting
performancewise.  🙁

Also I don't have an explanation for the difference in performance
between bytechar-100k (8.00) and bytechar-100k-random/rev (~9.00) on
`markers-as-gap-array`: `rev` just builds the markers in reverse order
and `random` puts the markers at random positions.  Since my gap-array
keeps the markers sorted, the order in which they're created should not
affect the end result, and I don't think that placing them randomly in
the text should make much difference either (unless the performance
difference is just due to the time needed to compute `random`?).


        Stefan


PS: Beware the "tot avg error", because the machine I used for those
benchmarks is a poor fit, with a CPU whose top-frequency varies
enormously depending on temperature and such, and I was using the
machine (lightly, but still) at the same time as the benchmarks
were running.

* markers-as-gap-array

  | test                   | non-gc avg (s) | gc avg (s) | gcs avg | tot avg (s) | tot avg err (s) |
  |------------------------+----------------+------------+---------+-------------+-----------------|
  | bytechar               |           7.86 |       0.00 |       0 |        7.86 |            0.05 |
  | bytechar-100k          |           8.00 |       0.00 |       0 |        8.00 |            0.15 |
  | bytechar-100k-nolookup |           5.99 |       0.00 |       0 |        5.99 |            0.07 |
  | bytechar-100k-random   |           9.20 |       0.00 |       0 |        9.20 |            0.23 |
  | bytechar-100k-rev      |           9.05 |       0.00 |       0 |        9.05 |            0.59 |
  | bytechar-10k-random    |           8.09 |       0.00 |       0 |        8.09 |            0.06 |
  | bytechar-1k-random     |           7.91 |       0.00 |       0 |        7.91 |            0.03 |
  | bytechar-nolookup      |           5.91 |       0.00 |       0 |        5.91 |            0.01 |
  |------------------------+----------------+------------+---------+-------------+-----------------|

* master

  | test                   | non-gc avg (s) | gc avg (s) | gcs avg | tot avg (s) | tot avg err (s) |
  |------------------------+----------------+------------+---------+-------------+-----------------|
  | bytechar               |           7.73 |       0.00 |       0 |        7.73 |            0.40 |
  | bytechar-100k          |           8.04 |       0.00 |       0 |        8.04 |            0.02 |
  | bytechar-100k-nolookup |           5.93 |       0.00 |       0 |        5.93 |            0.02 |
  | bytechar-100k-random   |          10.05 |       0.00 |       0 |       10.05 |            0.01 |
  | bytechar-100k-rev      |           7.99 |       0.00 |       0 |        7.99 |            0.01 |
  | bytechar-10k-random    |           8.23 |       0.00 |       0 |        8.23 |            0.05 |
  | bytechar-1k-random     |           8.05 |       0.00 |       0 |        8.05 |            0.03 |
  | bytechar-nolookup      |           5.86 |       0.00 |       0 |        5.86 |            0.01 |
  |------------------------+----------------+------------+---------+-------------+-----------------|

* master before commit b595b4598 (mixup byte/char)

  | test                   | non-gc avg (s) | gc avg (s) | gcs avg | tot avg (s) | tot avg err (s) |
  |------------------------+----------------+------------+---------+-------------+-----------------|
  | bytechar               |           7.97 |       0.00 |       0 |        7.97 |            0.60 |
  | bytechar-100k          |          16.64 |       0.00 |       0 |       16.64 |            0.43 |
  | bytechar-100k-nolookup |           6.80 |       0.00 |       0 |        6.80 |            1.07 |
  | bytechar-100k-random   |          16.85 |       0.00 |       0 |       16.85 |            1.03 |
  | bytechar-100k-rev      |          13.56 |       0.00 |       0 |       13.56 |            0.10 |
  | bytechar-10k-random    |          14.15 |       0.00 |       0 |       14.15 |            0.07 |
  | bytechar-1k-random     |          14.06 |       0.00 |       0 |       14.06 |            0.20 |
  | bytechar-nolookup      |           5.93 |       0.00 |       0 |        5.93 |            0.03 |
  |------------------------+----------------+------------+---------+-------------+-----------------|

* /usr/bin/emacs (29.4):

  | test                   | non-gc avg (s) | gc avg (s) | gcs avg | tot avg (s) | tot avg err (s) |
  |------------------------+----------------+------------+---------+-------------+-----------------|
  | bytechar               |           7.92 |       0.00 |       0 |        7.92 |            1.07 |
  | bytechar-100k          |          16.27 |       0.00 |       0 |       16.27 |            1.91 |
  | bytechar-100k-nolookup |           6.16 |       0.00 |       0 |        6.16 |            0.04 |
  | bytechar-100k-random   |          15.91 |       0.00 |       0 |       15.91 |            0.29 |
  | bytechar-100k-rev      |          13.38 |       0.00 |       0 |       13.38 |            0.06 |
  | bytechar-10k-random    |          15.47 |       0.00 |       0 |       15.47 |            3.06 |
  | bytechar-1k-random     |          14.26 |       0.00 |       0 |       14.26 |            1.22 |
  | bytechar-nolookup      |           6.03 |       0.00 |       0 |        6.03 |            0.02 |
  |------------------------+----------------+------------+---------+-------------+-----------------|

Re: Markers in a gap array

[Pip Cet]

On Thursday, July 4th, 2024 at 20:11, Stefan Monnier <monnier@iro.umontreal.ca> wrote:
> Ihor Radchenko [2024-07-04 14:30:47] wrote:
> > Stefan Monnier monnier@iro.umontreal.ca writes:
> > 
> > > > Some perf stats:
> > > > 
> > > > ;; Switch to todo and mark next 3 times, on branch
> > > > ;; 28.72% emacs emacs
> > > > [.] markers_sanity_check
> > > 
> > > Did you build with or without assertions?
> > 
> > Without.
> > 
> > > And indeed, I need to rework them to be "more conditional" (but I was
> > > focused on correctness until now). You should probably remove those
> > > calls to `markers_sanity_check` by hand when testing performance, sorry.
> > 
> > Without these calls, I can see some speed improvement in
> > buf_bytepos_to_charpos, but I do not currently have a reliable
> > reproducer to trigger buf_bytepos_to_charpos slowdown on master, so it
> > is comparing very small numbers.
> 
> 
> Hmm... I tried a benchmark based on:
> 
> (defconst elb-bytechar-buffer
> (let ((buf (get-buffer-create " elb-bytechar")))
> (with-current-buffer buf
> (let ((step (apply #'concat "🙂 foo\n" (make-list 2000 "asdf "))))
> (dotimes (_ (/ 10000000 (length step)))
> (insert step))
> buf))))
> 
> (defconst elb-bytechar-re "\\<.\\> \\<.\\> bar")
> 
> 
> (defun elb-bytechar--aux (nmarkers lookup &optional marker-fun)
> (with-current-buffer elb-bytechar-buffer
> (let ((step (/ (buffer-size) nmarkers))
> (markers nil))
> (dotimes (i nmarkers)
> (push (copy-marker (funcall (or marker-fun #'identity) (* i step)))
> markers))
> (dotimes (_ 10)
> (goto-char (point-min))
> (let ((parse-sexp-lookup-properties lookup))
> (re-search-forward elb-bytechar-re nil t))))))
> 
> where I call `elb-bytechar--aux` with various arguments.

Could you share a more complete recipe for the benchmark? I wonder how it compares to Gerd's weak vector/freelist in scratch/igc.

I think this is very exciting, even though it might have been triggered by incorrectly-reported numbers of markers :-)

Pip

Re: Markers in a gap array

[Stefan Monnier]

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

> Could you share a more complete recipe for the benchmark? I wonder how it
> compares to Gerd's weak vector/freelist in scratch/igc.

Put it into the `benchmark` subdir of `elisp-benchmarks` and then do

    emacs --batch -Q -l .../elisp-benchmarks/elisp-benchmarks-autoloads.el \
          --eval '(elisp-benchmarks-run "bytechar")'


- Stefan


[-- Attachment #2: elb-bytechar.el --]
[-- Type: application/emacs-lisp, Size: 1565 bytes --]

Re: Markers in a gap array

[Helmut Eller]

On Thu, Jul 04 2024, Stefan Monnier wrote:

>> Could you share a more complete recipe for the benchmark? I wonder how it
>> compares to Gerd's weak vector/freelist in scratch/igc.
>
> Put it into the `benchmark` subdir of `elisp-benchmarks` and then do
>
>     emacs --batch -Q -l .../elisp-benchmarks/elisp-benchmarks-autoloads.el \
>           --eval '(elisp-benchmarks-run "bytechar")'
>

The current scratch/igc branch, configured with MPS and -O2
-fno-omit-frame-pointer:

  | test                   || tot avg (s) | tot avg err (s) |
  |------------------------++-------------+-----------------|
  | bytechar               ||       12.11 |            0.18 |
  | bytechar-100k          ||       12.38 |            0.17 |
  | bytechar-100k-nolookup ||        9.14 |            0.22 |
  | bytechar-100k-random   ||      271.52 |           14.27 |
  | bytechar-100k-rev      ||       12.38 |            0.24 |
  | bytechar-10k-random    ||       38.08 |            1.43 |
  | bytechar-1k-random     ||       14.95 |            0.48 |
  | bytechar-nolookup      ||        8.97 |            0.12 |
  |------------------------++-------------+-----------------|
  | total                  ||      379.53 |           14.36 |

and without MPS:

  | test                   || tot avg (s) | tot avg err (s) |
  |------------------------++-------------+-----------------|
  | bytechar               ||       11.42 |            0.03 |
  | bytechar-100k          ||       11.48 |            0.02 |
  | bytechar-100k-nolookup ||        9.15 |            0.00 |
  | bytechar-100k-random   ||       16.39 |            0.02 |
  | bytechar-100k-rev      ||       11.48 |            0.02 |
  | bytechar-10k-random    ||       11.97 |            0.02 |
  | bytechar-1k-random     ||       11.56 |            0.01 |
  | bytechar-nolookup      ||        9.13 |            0.04 |
  |------------------------++-------------+-----------------|
  | total                  ||       92.58 |            0.06 |

So the weak vector doesn't compare very well to the linked list.  Maybe
because the vector only grows and never shrinks.  The idea with the
sorted markers in a gap array would probably avoid the worst of this.  I
wonder why the linked list doesn't seem similar issues.

Re: Markers in a gap array

[Stefan Monnier]

> The current scratch/igc branch, configured with MPS and -O2
> -fno-omit-frame-pointer:
>
>   | test                   || tot avg (s) | tot avg err (s) |
>   |------------------------++-------------+-----------------|
>   | bytechar               ||       12.11 |            0.18 |
>   | bytechar-100k          ||       12.38 |            0.17 |
>   | bytechar-100k-nolookup ||        9.14 |            0.22 |
>   | bytechar-100k-random   ||      271.52 |           14.27 |
>   | bytechar-100k-rev      ||       12.38 |            0.24 |
>   | bytechar-10k-random    ||       38.08 |            1.43 |
>   | bytechar-1k-random     ||       14.95 |            0.48 |
>   | bytechar-nolookup      ||        8.97 |            0.12 |
>   |------------------------++-------------+-----------------|
>   | total                  ||      379.53 |           14.36 |
>
> and without MPS:
>
>   | test                   || tot avg (s) | tot avg err (s) |
>   |------------------------++-------------+-----------------|
>   | bytechar               ||       11.42 |            0.03 |
>   | bytechar-100k          ||       11.48 |            0.02 |
>   | bytechar-100k-nolookup ||        9.15 |            0.00 |
>   | bytechar-100k-random   ||       16.39 |            0.02 |
>   | bytechar-100k-rev      ||       11.48 |            0.02 |
>   | bytechar-10k-random    ||       11.97 |            0.02 |
>   | bytechar-1k-random     ||       11.56 |            0.01 |
>   | bytechar-nolookup      ||        9.13 |            0.04 |
>   |------------------------++-------------+-----------------|
>   | total                  ||       92.58 |            0.06 |
>
> So the weak vector doesn't compare very well to the linked list.

Hmm... I wonder why there is such a large difference for markers created
in a random-order compared to the cases where they're created beg-to-end
and end-to-beg.  My crystal ball is of no help but suggests that it
might hint at the fact that it's probably a silly effect that could be
fixed easily once diagnosed.

> Maybe because the vector only grows and never shrinks.

But why would that only show up when the order is random?

> The idea with the sorted markers in a gap array would probably avoid
> the worst of this.

You could try porting the code in `scratch/markers-as-gap-array`.
I haven't touched it recently, but IIRC the code itself is in reasonably
good shape: the commits themselves need to be improved (better
commit messages, maybe sliced differently) and there's a bit of cleanup
needed around the pdumper code, but it should be reliable enough.

[ I'm still not completely sure if it's a good idea, tho: I mean, I like
  the idea, but the benchmarks aren't very compelling (they're not bad,
  but they're not very enticing either).  ]


        Stefan


PS: BTW, apparently I was confused about XEmacs' markers, they don't use
    a gap-array but a doubly-linked list.  They use a gap-array for the
    extents (where we use a fancier balanced tree instead).
    Also they don't use markers to convert bytes<->chars.
    Instead they keep a (per buffer) cache in an unsorted array of 50 pairs.
    Surprisingly their markers store the bytepos rather than the
    charpos, so `marker-position` always needs to convert to charpos and
    `set-marker` does the other conversion.

Re: Markers in a gap array

[Helmut Eller]

On Thu, Jul 18 2024, Stefan Monnier wrote:

>> The current scratch/igc branch, configured with MPS and -O2
>> -fno-omit-frame-pointer:
>>
>>   | test                   || tot avg (s) | tot avg err (s) |
>>   |------------------------++-------------+-----------------|
>>   | bytechar               ||       12.11 |            0.18 |
>>   | bytechar-100k          ||       12.38 |            0.17 |
>>   | bytechar-100k-nolookup ||        9.14 |            0.22 |
>>   | bytechar-100k-random   ||      271.52 |           14.27 |
>>   | bytechar-100k-rev      ||       12.38 |            0.24 |
>>   | bytechar-10k-random    ||       38.08 |            1.43 |
>>   | bytechar-1k-random     ||       14.95 |            0.48 |
>>   | bytechar-nolookup      ||        8.97 |            0.12 |
>>   |------------------------++-------------+-----------------|
>>   | total                  ||      379.53 |           14.36 |
>>
>> and without MPS:
>>
>>   | test                   || tot avg (s) | tot avg err (s) |
>>   |------------------------++-------------+-----------------|
>>   | bytechar               ||       11.42 |            0.03 |
>>   | bytechar-100k          ||       11.48 |            0.02 |
>>   | bytechar-100k-nolookup ||        9.15 |            0.00 |
>>   | bytechar-100k-random   ||       16.39 |            0.02 |
>>   | bytechar-100k-rev      ||       11.48 |            0.02 |
>>   | bytechar-10k-random    ||       11.97 |            0.02 |
>>   | bytechar-1k-random     ||       11.56 |            0.01 |
>>   | bytechar-nolookup      ||        9.13 |            0.04 |
>>   |------------------------++-------------+-----------------|
>>   | total                  ||       92.58 |            0.06 |
>>
>> So the weak vector doesn't compare very well to the linked list.
>
> Hmm... I wonder why there is such a large difference for markers created
> in a random-order compared to the cases where they're created beg-to-end
> and end-to-beg.  My crystal ball is of no help but suggests that it
> might hint at the fact that it's probably a silly effect that could be
> fixed easily once diagnosed.

One problem with the benchmarks is that they all use the same buffer and
that the markers for the previous benchmark can still linger around.
The benchmark driver calls garbage-collect before running a benchmark
and for the old GC that may be enough to collect all the old markers;
with MPS, the old markers are definitely still there.

If I create a fresh buffer for each benchmark, the times of the MPS and
non-MPS version are much closer.

>> Maybe because the vector only grows and never shrinks.
>
> But why would that only show up when the order is random?

To figure out what is going on I run bytechar-100k followed
bytechar-10k-random; in GDB I interrupted the benchmark and printed the
marker array.  After index 100000, it contains suspicious duplicates:

  ...
  (99997 9899604)
  (99998 9899703)
  (99999 9899802)
  (100000 9899901)
  (100001 7272795)
  (100002 7272795)
  (100003 8017474)
  (100004 8017474)
  (100005 7087003)
  (100006 7087003)
  (100007 4076094)
  (100008 4076094)
  ...

The first element is the array index and the second is the charpos of
the marker.  Then I set a breakpoint in build_marker and got this:

#0  build_marker (buf=0x7fffe46c9a10, charpos=6001308, bytepos=6003108)
    at alloc.c:4191
#1  0x00005555557be1a7 in buf_charpos_to_bytepos
    (b=0x7fffe46c9a10, charpos=6001308) at marker.c:238
#2  0x00005555557bf184 in set_marker_internal
    (marker=0x7fffe5a0f4dd, position=0x16e4a72, buffer=0x0, restricted=false)
    at marker.c:587
#3  0x00005555557bf2a3 in Fset_marker
    (marker=0x7fffe5a0f4dd, position=0x16e4a72, buffer=0x0) at marker.c:630
#4  0x00005555557bf640 in Fcopy_marker (marker=0x16e4a72, type=0x0)
    at marker.c:788

It looks like Fcopy_marker calls (indirectly) buf_charpos_to_bytepos and
that creates another marker at the same position (0x16e4a72 is the
fixnum for 6001308).  I doubt that this is intentional, but it may not
be a serious problem.

So why does the problem only show up for random positions?  Maybe
because the benchmark is spending most of the time not in
re-search-forward, but in copy-marker and for random positions the
caching is ineffective?

MPS: marker-vector (was: Markers in a gap array)

[Helmut Eller]

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

What would you think about changing the marker-vector-with-free-list to
a mundane growable array like in the patch below?

The main motivation for this would that we could then iterate in
reverse, or more precisely, in an order that is more like the order used
for the linked-list-of-markers.  This is relevant for the heuristic in
buf_charpos_to_bytepos that creates a temporary marker; it works better
if those temporary markers are visited first.

Using Stefan's elb-bytechar benchmark, I get for the
linked-list-of-markers:

  | test                   || tot avg (s) | tot avg err (s) |
  |------------------------++-------------+-----------------|
  | bytechar               ||       11.80 |            0.00 |
  | bytechar-100k          ||       11.85 |            0.00 |
  | bytechar-100k-nolookup ||        9.19 |            0.00 |
  | bytechar-100k-random   ||       16.73 |            0.02 |
  | bytechar-100k-rev      ||       11.86 |            0.00 |
  | bytechar-10k-random    ||       12.36 |            0.01 |
  | bytechar-1k-random     ||       11.93 |            0.00 |
  | bytechar-nolookup      ||        9.15 |            0.00 |
  |------------------------++-------------+-----------------|
  | total                  ||       94.88 |            0.02 |

for the vector-with-free-list:

  | test                   || tot avg (s) | tot avg err (s) |
  |------------------------++-------------+-----------------|
  | bytechar               ||       11.63 |            0.01 |
  | bytechar-100k          ||       11.91 |            0.37 |
  | bytechar-100k-nolookup ||        8.80 |            0.01 |
  | bytechar-100k-random   ||      248.07 |            3.84 |
  | bytechar-100k-rev      ||       11.71 |            0.02 |
  | bytechar-10k-random    ||       35.24 |            0.53 |
  | bytechar-1k-random     ||       14.01 |            0.06 |
  | bytechar-nolookup      ||        8.69 |            0.13 |
  |------------------------++-------------+-----------------|
  | total                  ||      350.06 |            3.89 |

and for the growable array:

  | test                   || tot avg (s) | tot avg err (s) |
  |------------------------++-------------+-----------------|
  | bytechar               ||       11.34 |            0.08 |
  | bytechar-100k          ||       11.59 |            0.47 |
  | bytechar-100k-nolookup ||        8.78 |            0.12 |
  | bytechar-100k-random   ||       16.17 |            0.33 |
  | bytechar-100k-rev      ||       11.31 |            0.03 |
  | bytechar-10k-random    ||       11.76 |            0.01 |
  | bytechar-1k-random     ||       11.34 |            0.08 |
  | bytechar-nolookup      ||        8.70 |            0.09 |
  |------------------------++-------------+-----------------|
  | total                  ||       91.00 |            0.61 |

So the results of the growable array and the linked-list-of-markers
would be closer.  A downside of the growable array is that it needs a
bit of extra code for the dumper.  I didn't try to port the gap array
code, because it seems like it would require many more changes and would
make it even harder to merge with master.



[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Introduce-a-struct-marker_vector.patch --]
[-- Type: text/x-diff, Size: 17150 bytes --]

From f640e13343183f0ad04edcfdc8d1576b7714b0f7 Mon Sep 17 00:00:00 2001
From: Helmut Eller <eller.helmut@gmail.com>
Date: Sat, 27 Jul 2024 19:42:00 +0200
Subject: [PATCH] Introduce a struct marker_vector

This replaces the vector-with-free-list by a growable vector, i.e. the
free entries are always kept at the end of the vector.

This allows us to iterate in reverse more easily because we can skip
over unused entries quickly.  Iterating in reverse is useful because
buf_charpos_to_bytepos creates "temporary" markers to speed up the
translation; this heuristic works better if we visit those recently
created temporary markers early, like the non-MPS code does with the
linked-list-of-markers.

* src/buffer.h (struct marker_vector): New struct.
(struct buffer_text, struct marker_it): Use it.
(marker_vector_swap_remove): New helper.
(marker_it_init, marker_it_valid, marker_it_next, marker_it_marker):
Iterate in reverse order.
* src/buffer.c (Fget_buffer_create, Fset_buffer_multibyte): Use struct
marker_vector.
* src/marker.c (buf_bytepos_to_charpos): Use struct marker_vector.
* src/pdumper.c (dump_marker_vector): New helper.
(dump_buffer): Use it.
* src/igc.c (fix_marker_vector, dflt_scan_obj, fix_marker_vector)
(fix_buffer, alloc_marker_vector, larger_marker_vector, igc_add_marker)
(igc_remove_marker, igc_remove_all_markers, igc_resurrect_markers):
Update for new data structure.
(is_in_weak_pool): Renamed from weak_vector_p.
---
 src/buffer.c  |   8 +--
 src/buffer.h  |  87 ++++++++++++++++++++--------
 src/igc.c     | 156 ++++++++++++++++++++++----------------------------
 src/marker.c  |   5 --
 src/pdumper.c |  52 ++++++++++++++---
 5 files changed, 178 insertions(+), 130 deletions(-)

diff --git a/src/buffer.c b/src/buffer.c
index eea0703c898..d879b2447cc 100644
--- a/src/buffer.c
+++ b/src/buffer.c
@@ -662,11 +662,7 @@ DEFUN ("get-buffer-create", Fget_buffer_create, Sget_buffer_create, 1, 2, 0,
   reset_buffer_local_variables (b, 1);
 
   bset_mark (b, Fmake_marker ());
-#ifdef HAVE_MPS
-  BUF_MARKERS (b) = Qnil;
-#else
   BUF_MARKERS (b) = NULL;
-#endif
   /* Put this in the alist of all live buffers.  */
   XSETBUFFER (buffer, b);
   Vbuffer_alist = nconc2 (Vbuffer_alist, list1 (Fcons (name, buffer)));
@@ -2938,8 +2934,8 @@ DEFUN ("set-buffer-multibyte", Fset_buffer_multibyte, Sset_buffer_multibyte,
 #ifdef HAVE_MPS
       DO_MARKERS (current_buffer, tail)
 	{
-	  Lisp_Object buf_markers = BUF_MARKERS (current_buffer);
-	  BUF_MARKERS (current_buffer) = Qnil;
+	  struct marker_vector *buf_markers = BUF_MARKERS (current_buffer);
+	  BUF_MARKERS (current_buffer) = NULL;
 	  tail->bytepos = advance_to_char_boundary (tail->bytepos);
 	  tail->charpos = BYTE_TO_CHAR (tail->bytepos);
 	  BUF_MARKERS (current_buffer) = buf_markers;
diff --git a/src/buffer.h b/src/buffer.h
index 1e1a65e339d..fe95a4ddc40 100644
--- a/src/buffer.h
+++ b/src/buffer.h
@@ -220,6 +220,21 @@ #define FETCH_BYTE(n) (*BYTE_POS_ADDR (n))
 \f
 /* Define the actual buffer data structures.  */
 
+#ifdef HAVE_MPS
+/* A marker_vector is a growable vector.  The capacity and the length
+   fields are encoded as fixnum to satisfy AWL pool constraints.
+
+   FIXME: capacity is redundant; it's also stored in the gc_header.
+*/
+struct marker_vector
+{
+  GC_HEADER
+  Lisp_Object capacity;
+  Lisp_Object length;
+  struct Lisp_Marker *data[];
+};
+#endif
+
 /* This data structure describes the actual text contents of a buffer.
    It is shared between indirect buffers and their base buffer.  */
 
@@ -272,7 +287,7 @@ #define FETCH_BYTE(n) (*BYTE_POS_ADDR (n))
     INTERVAL intervals;
 
 # ifdef HAVE_MPS
-    Lisp_Object markers;
+    struct marker_vector *markers;
 # else
     /* The markers that refer to this buffer.
        This is actually a single marker ---
@@ -715,57 +730,83 @@ #define BVAR(buf, field) ((buf)->field ## _)
 struct marker_it
 {
 #ifdef HAVE_MPS
-  Lisp_Object markers, obj;
-  ptrdiff_t i;
-# else
+  struct marker_vector *markers;
+  struct Lisp_Marker *m;
+  size_t i;
+#else
   struct Lisp_Marker *marker;
 #endif
 };
 
 #ifdef HAVE_MPS
+/* Remove the marker at position I by swapping it with the marker at the
+   last position. */
+INLINE void
+marker_vector_swap_remove (struct marker_vector *v, size_t i)
+{
+  for (size_t last = XFIXNUM (v->length) - 1; true; last--)
+    {
+      if (last == i)
+	{
+	  v->length = make_fixnum (last);
+	  return;
+	}
+      struct Lisp_Marker *m = v->data[last];
+      if (m)
+	{
+	  v->data[i] = m;
+	  m->index = i;
+	  v->length = make_fixnum (last);
+	  return;
+	}
+    }
+}
+
 INLINE struct marker_it
 marker_it_init (struct buffer *b)
 {
-  Lisp_Object v = BUF_MARKERS (b);
-  if (!VECTORP (v))
-    return (struct marker_it){ .obj = Qnil };
+  struct marker_vector *v = BUF_MARKERS (b);
 
-  Lisp_Object obj = Qnil;
-  for (ptrdiff_t i = 1; i < ASIZE (v); ++i)
-    {
-      obj = AREF (v, i);
-      if (MARKERP (obj))
-	return (struct marker_it) { .i = i, .markers = v, .obj = obj };
-    }
+  if (v)
+    while (XFIXNUM (v->length) != 0)
+      {
+	size_t i = XFIXNUM(v->length) - 1;
+	struct Lisp_Marker *m = v->data[i];
+	if (m)
+	  return (struct marker_it){ .i = i, .markers = v, .m = m };
+	v->length = make_fixnum (i);
+      }
 
-  return (struct marker_it) { .obj = Qnil };
+  return (struct marker_it){ .m = NULL };
 }
 
 INLINE bool
 marker_it_valid (struct marker_it *it)
 {
-  return MARKERP (it->obj);
+  return (it->m != NULL);
 }
 
 INLINE void
 marker_it_next (struct marker_it *it)
 {
-  it->obj = Qnil;
-  for (++it->i; it->i < ASIZE (it->markers); ++it->i)
+  while (it->i > 0)
     {
-      Lisp_Object m = AREF (it->markers, it->i);
-      if (MARKERP (m))
+      it->i--;
+      struct Lisp_Marker *m = it->markers->data[it->i];
+      if (m)
 	{
-	  it->obj = m;
-	  break;
+	  it->m = m;
+	  return;
 	}
+      marker_vector_swap_remove (it->markers, it->i);
     }
+  it->m = NULL;
 }
 
 INLINE struct Lisp_Marker *
 marker_it_marker (struct marker_it *it)
 {
-  return XMARKER (it->obj);
+  return it->m;
 }
 
 # else
diff --git a/src/igc.c b/src/igc.c
index 52d52ca7a91..30bf63d22ed 100644
--- a/src/igc.c
+++ b/src/igc.c
@@ -1797,7 +1797,7 @@ fix_charset_table (mps_ss_t ss, struct charset *table, size_t nbytes)
 }
 
 static mps_res_t fix_vector (mps_ss_t ss, struct Lisp_Vector *v);
-static mps_res_t fix_marker_vector (mps_ss_t ss, struct Lisp_Vector *v);
+static mps_res_t fix_marker_vector (mps_ss_t ss, struct marker_vector *v);
 static mps_res_t fix_weak_hash_table_strong_part (mps_ss_t ss, struct Lisp_Weak_Hash_Table_Strong_Part *t);
 static mps_res_t fix_weak_hash_table_weak_part (mps_ss_t ss, struct Lisp_Weak_Hash_Table_Weak_Part *w);
 
@@ -1889,7 +1889,7 @@ dflt_scan_obj (mps_ss_t ss, mps_addr_t base_start, mps_addr_t base_limit,
 	break;
 
       case IGC_OBJ_MARKER_VECTOR:
-	IGC_FIX_CALL_FN (ss, struct Lisp_Vector, client, fix_marker_vector);
+	IGC_FIX_CALL_FN (ss, struct marker_vector, client, fix_marker_vector);
 	break;
 
       case IGC_OBJ_ITREE_TREE:
@@ -1978,24 +1978,10 @@ fix_vectorlike (mps_ss_t ss, struct Lisp_Vector *v)
 }
 
 static mps_res_t
-fix_marker_vector (mps_ss_t ss, struct Lisp_Vector *v)
+fix_marker_vector (mps_ss_t ss, struct marker_vector *v)
 {
-  MPS_SCAN_BEGIN (ss)
-  {
-    for (size_t i = 0, n = vector_size (v); i < n; ++i)
-      {
-	Lisp_Object old = v->contents[i];
-	IGC_FIX12_OBJ (ss, &v->contents[i]);
-	/* FIXME/igc: this is right for marker vectors only.  */
-	if (NILP (v->contents[i]) && !NILP (old))
-	  {
-	    v->contents[i] = v->contents[0];
-	    v->contents[0] = make_fixnum (i);
-	  }
-      }
-  }
-  MPS_SCAN_END (ss);
-  return MPS_RES_OK;
+  size_t len = XFIXNUM (v->length);
+  return mps_scan_area (ss, &v->data[0], &v->data[len], NULL);
 }
 
 static mps_res_t
@@ -2004,8 +1990,6 @@ fix_buffer (mps_ss_t ss, struct buffer *b)
   MPS_SCAN_BEGIN (ss)
   {
     IGC_FIX_CALL_FN (ss, struct Lisp_Vector, b, fix_vectorlike);
-    IGC_FIX12_HEADER (ss, &b->own_text.intervals);
-    IGC_FIX12_OBJ (ss, &b->own_text.markers);
     IGC_FIX12_HEADER (ss, &b->overlays);
     IGC_FIX12_OBJ (ss, &b->undo_list_);
 
@@ -2013,7 +1997,11 @@ fix_buffer (mps_ss_t ss, struct buffer *b)
     if (b->base_buffer)
       b->text = &b->base_buffer->own_text;
     else
-      b->text = &b->own_text;
+      {
+	b->text = &b->own_text;
+	IGC_FIX12_HEADER (ss, &b->own_text.intervals);
+	IGC_FIX12_HEADER (ss, &b->own_text.markers);
+      }
   }
   MPS_SCAN_END (ss);
   return MPS_RES_OK;
@@ -4185,61 +4173,52 @@ igc_valid_lisp_object_p (Lisp_Object obj)
   return 1;
 }
 
-static Lisp_Object
-alloc_marker_vector (ptrdiff_t len, Lisp_Object init)
+static struct marker_vector *
+alloc_marker_vector (size_t capacity)
 {
-  struct Lisp_Vector *v
-    = alloc (header_size + len * word_size, IGC_OBJ_MARKER_VECTOR);
-  v->header.size = len;
-  for (ptrdiff_t i = 0; i < len; ++i)
-    v->contents[i] = init;
-  return make_lisp_ptr (v, Lisp_Vectorlike);
+  struct marker_vector *v = alloc ((offsetof (struct marker_vector, data)
+				    + capacity * sizeof (v->data[0])),
+				   IGC_OBJ_MARKER_VECTOR);
+  v->capacity = make_fixnum (capacity);
+  v->length = make_fixnum (0);
+  return v;
 }
 
-static Lisp_Object
-larger_marker_vector (Lisp_Object v)
-{
-  igc_assert (NILP (v) || (VECTORP (v) && XFIXNUM (AREF (v, 0)) < 0));
-  ptrdiff_t old_len = NILP (v) ? 0 : ASIZE (v);
-  ptrdiff_t new_len = max (2, 2 * old_len);
-  Lisp_Object new_v = alloc_marker_vector (new_len, Qnil);
-  ptrdiff_t i = 0;
-  if (VECTORP (v))
-    for (i = 1; i < ASIZE (v); ++i)
-      ASET (new_v, i, AREF (v, i));
-  for (; i < ASIZE (new_v) - 1; ++i)
-    ASET (new_v, i, make_fixnum (i + 1));
-  ASET (new_v, i, make_fixnum (-1));
-  ASET (new_v, 0, make_fixnum (NILP (v) ? 1 : ASIZE (v)));
-  return new_v;
+static struct marker_vector *
+larger_marker_vector (struct marker_vector *old)
+{
+  igc_assert (old->length == old->capacity);
+  size_t old_cap = XFIXNUM (old->capacity);
+  size_t new_cap = max (2, 2 * old_cap);
+  struct marker_vector *new = alloc_marker_vector (new_cap);
+  new->length = make_fixnum (old_cap);
+  memcpy (new->data, old->data, old_cap * sizeof (old->data[0]));
+  return new;
 }
 
 void
 igc_add_marker (struct buffer *b, struct Lisp_Marker *m)
 {
-  Lisp_Object v = BUF_MARKERS (b);
-  igc_assert (NILP (v) || VECTORP (v));
-  ptrdiff_t next_free = NILP (v) ? -1 : XFIXNUM (AREF (v, 0));
-  if (next_free < 0)
-    {
-      v = BUF_MARKERS (b) = larger_marker_vector (v);
-      next_free = XFIXNUM (AREF (v, 0));
-    }
-  ASET (v, 0, AREF (v, next_free));
-  ASET (v, next_free, make_lisp_ptr (m, Lisp_Vectorlike));
-  m->index = next_free;
+  struct marker_vector *v = BUF_MARKERS (b);
+  if (!v)
+    v = BUF_MARKERS (b) = alloc_marker_vector (2);
+  if (v->length == v->capacity)
+    v = BUF_MARKERS (b) = larger_marker_vector (v);
+  size_t index = XFIXNUM (v->length);
+  v->data[index] = m;
+  v->length = make_fixnum (index + 1);
+  m->index = index;
   m->buffer = b;
 }
 
 void
 igc_remove_marker (struct buffer *b, struct Lisp_Marker *m)
 {
-  Lisp_Object v = BUF_MARKERS (b);
-  igc_assert (VECTORP (v));
-  igc_assert (m->index >= 1 && m->index < ASIZE (v));
-  igc_assert (MARKERP (AREF (v, m->index)) && XMARKER (AREF (v, m->index)) == m);
-  ASET (v, m->index, AREF (v, 0));
-  ASET (v, 0, make_fixnum (m->index));
+  struct marker_vector *v = BUF_MARKERS (b);
+  igc_assert (v);
+  igc_assert (m->index >= 0 && m->index < XFIXNUM (v->length));
+  igc_assert (v->data[m->index] && v->data[m->index] == m);
+  marker_vector_swap_remove (v, m->index);
   m->index = -1;
   m->buffer = NULL;
 }
@@ -4247,44 +4226,45 @@ igc_remove_marker (struct buffer *b, struct Lisp_Marker *m)
 void
 igc_remove_all_markers (struct buffer *b)
 {
-  Lisp_Object v = BUF_MARKERS (b);
-  if (VECTORP (v))
+  struct marker_vector *v = BUF_MARKERS (b);
+  if (!v)
+    return;
+  for (size_t i = 0, len = XFIXNUM (v->length); i < len; ++i)
     {
-      for (ptrdiff_t i = 1; i < ASIZE (v); ++i)
-	if (MARKERP (AREF (v, i)))
-	  XMARKER (AREF (v, i))->buffer = NULL;
-      BUF_MARKERS (b) = Qnil;
+      struct Lisp_Marker *m = v->data[i];
+      if (m)
+	{
+	  m->buffer = NULL;
+	  m->index = -1;
+	}
     }
+  v->length = make_fixnum (0);
+  BUF_MARKERS (b) = NULL;
 }
 
 static bool
-weak_vector_p (Lisp_Object x)
+is_in_weak_pool (mps_addr_t addr)
 {
-  if (VECTORP (x))
-    {
-      struct igc *igc = global_igc;
-      mps_pool_t pool = NULL;
-      if (!mps_addr_pool (&pool, igc->arena, XVECTOR (x)))
-	return false;
-      return pool == igc->weak_pool;
-    }
-  else
-    return false;
+  struct igc *igc = global_igc;
+  mps_pool_t pool = NULL;
+  mps_addr_pool (&pool, igc->arena, addr);
+  return pool == igc->weak_pool;
 }
 
 void
 igc_resurrect_markers (struct buffer *b)
 {
-  Lisp_Object old = BUF_MARKERS (b);
-  if (NILP (old))
+  struct marker_vector *old = BUF_MARKERS (b);
+  if (!old)
     return;
-  igc_assert (!weak_vector_p (old));
-  size_t len = ASIZE (old);
-  Lisp_Object new = alloc_marker_vector (len, Qnil);
-  memcpy (XVECTOR (new)->contents, XVECTOR (old)->contents,
-	  len * sizeof (Lisp_Object));
+  igc_assert (!is_in_weak_pool (old));
+  size_t capacity = XFIXNUM (old->capacity);
+  struct marker_vector *new = alloc_marker_vector (capacity);
+  size_t nbytes = (offsetof (struct marker_vector, data)
+		   + capacity * sizeof (old->data[0]));
+  memcpy (new, old, nbytes);
   BUF_MARKERS (b) = new;
-  igc_assert (weak_vector_p (BUF_MARKERS (b)));
+  igc_assert (is_in_weak_pool (new));
 }
 
 static void
diff --git a/src/marker.c b/src/marker.c
index 5db46e599ae..005f66f6f24 100644
--- a/src/marker.c
+++ b/src/marker.c
@@ -413,13 +413,8 @@ buf_bytepos_to_charpos (struct buffer *b, ptrdiff_t bytepos)
 	 It will last until the next GC.
 	 But don't do it if BUF_MARKERS is nil;
 	 that is a signal from Fset_buffer_multibyte.  */
-#ifdef HAVE_MPS
-      if (record && VECTORP (BUF_MARKERS (b)))
-	build_marker (b, best_above, best_above_byte);
-#else
       if (record && BUF_MARKERS (b))
 	build_marker (b, best_above, best_above_byte);
-#endif
       byte_char_debug_check (b, best_above, best_above_byte);
 
       cached_buffer = b;
diff --git a/src/pdumper.c b/src/pdumper.c
index a56e0a8bfff..d4f4a7d8b6e 100644
--- a/src/pdumper.c
+++ b/src/pdumper.c
@@ -2873,10 +2873,37 @@ dump_obarray (struct dump_context *ctx, Lisp_Object object)
   return offset;
 }
 
+#ifdef HAVE_MPS
+static dump_off
+dump_marker_vector (struct dump_context *ctx, const struct marker_vector *v)
+{
+  size_t capacity = XFIXNUM (v->capacity);
+  size_t length = XFIXNUM (v->length);
+  size_t nbytes = (offsetof (struct marker_vector, data)
+		   + capacity * sizeof (v->data[0]));
+  struct marker_vector *out = alloca (nbytes);
+  memset (out, 0, nbytes);
+  dump_align_output (ctx, DUMP_ALIGNMENT);
+  dump_off offset = ctx->offset;
+  dump_object_start (ctx, v, IGC_OBJ_MARKER_VECTOR, out, nbytes);
+  DUMP_FIELD_COPY (out, v, capacity);
+  DUMP_FIELD_COPY (out, v, length);
+  for (size_t i = 0; i < length; i++)
+    {
+      struct Lisp_Marker *m = v->data[i];
+      if (m)
+	dump_field_lv_rawptr (ctx, out, v, &v->data[i], Lisp_Vectorlike,
+			      WEIGHT_NORMAL);
+    }
+  dump_object_finish (ctx, out, nbytes);
+  return offset;
+}
+#endif
+
 static dump_off
 dump_buffer (struct dump_context *ctx, const struct buffer *in_buffer)
 {
-#if CHECK_STRUCTS && !defined HASH_buffer_text_07D802E2D4
+#if CHECK_STRUCTS && !defined HASH_buffer_text_66FD568A61
 # error "buffer changed. See CHECK_STRUCTS comment in config.h."
 #endif
   struct buffer munged_buffer = *in_buffer;
@@ -2948,8 +2975,7 @@ dump_buffer (struct dump_context *ctx, const struct buffer *in_buffer)
       if (buffer->own_text.intervals)
         dump_field_fixup_later (ctx, out, buffer, &buffer->own_text.intervals);
 #ifdef HAVE_MPS
-      dump_field_lv (ctx, out, buffer, &buffer->own_text.markers,
-		     WEIGHT_NORMAL);
+      dump_field_fixup_later (ctx, out, buffer, &buffer->own_text.markers);
 #else
       dump_field_lv_rawptr (ctx, out, buffer, &buffer->own_text.markers,
                             Lisp_Vectorlike, WEIGHT_NORMAL);
@@ -3012,11 +3038,21 @@ dump_buffer (struct dump_context *ctx, const struct buffer *in_buffer)
   dump_field_lv (ctx, out, buffer, &buffer->undo_list_,
                  WEIGHT_STRONG);
   dump_off offset = finish_dump_pvec (ctx, &out->header);
-  if (!buffer->base_buffer && buffer->own_text.intervals)
-    dump_remember_fixup_ptr_raw
-      (ctx,
-       offset + dump_offsetof (struct buffer, own_text.intervals),
-       dump_interval_tree (ctx, buffer->own_text.intervals, 0));
+  if (!buffer->base_buffer)
+    {
+      if (buffer->own_text.intervals)
+	dump_remember_fixup_ptr_raw
+	  (ctx,
+	   offset + dump_offsetof (struct buffer, own_text.intervals),
+	   dump_interval_tree (ctx, buffer->own_text.intervals, 0));
+#ifdef HAVE_MPS
+      if (buffer->own_text.markers)
+	dump_remember_fixup_ptr_raw
+	  (ctx,
+	   offset + dump_offsetof (struct buffer, own_text.markers),
+	   dump_marker_vector (ctx, buffer->own_text.markers));
+#endif
+    }
 
   return offset;
 }
-- 
2.39.2

Re: MPS: marker-vector

[Pip Cet]

"Helmut Eller" <eller.helmut@gmail.com> writes:

> What would you think about changing the marker-vector-with-free-list to
> a mundane growable array like in the patch below?

> The main motivation for this would that we could then iterate in
> reverse, or more precisely, in an order that is more like the order used
> for the linked-list-of-markers.  This is relevant for the heuristic in
> buf_charpos_to_bytepos that creates a temporary marker; it works better
> if those temporary markers are visited first.

Thanks for investigating this! I finally understand why the current MPS
code is slower now, I think.

I wonder whether we couldn't reuse more of the weak hash table code for
this, though...

> This replaces the vector-with-free-list by a growable vector, i.e. the
> free entries are always kept at the end of the vector.

I don't think that's entirely accurate; it's quite possible for an entry
at the beginning of the array to be splatted and remain untouched until
the next time a DO_MARKERS reaches it, which may take a long time.

I see one somewhat theoretical problem with this patch: if a marker is
simultaneously kept in a weak hash table, it's possible for it to be
splatted from the marker vector while remaining in the weak hash table
(there's no guarantee all references will be splatted at the same time);
if it is then retrieved from the weak hash table and made to point
nowhere, we will try to remove it from the marker vector, and hit the
igc_assert.

The rest of my comments are tiny nits, really:

- capacity isn't redundant on 32-bit systems
- I'd prefer the marker index to be signed; if it is unsigned, we don't need to assert it's >= 0, and assigning -1 to it confused me...
- you shouldn't compare Lisp_Objects with ==
- I'd prefer checking for splatted elements before deciding to grow the vector, if we can do so efficiently
- I find XFIXNAT easier to read when the number is guaranteed to be nonnegative
- using alloca is problematic for large vectors (which shouldn't be dumped, thus a nit)

> Using Stefan's elb-bytechar benchmark, I get for the
> linked-list-of-markers:
>
>   | test                   || tot avg (s) | tot avg err (s) |
>   |------------------------++-------------+-----------------|
>   | bytechar               ||       11.80 |            0.00 |
>   | bytechar-100k          ||       11.85 |            0.00 |
>   | bytechar-100k-nolookup ||        9.19 |            0.00 |
>   | bytechar-100k-random   ||       16.73 |            0.02 |
>   | bytechar-100k-rev      ||       11.86 |            0.00 |
>   | bytechar-10k-random    ||       12.36 |            0.01 |
>   | bytechar-1k-random     ||       11.93 |            0.00 |
>   | bytechar-nolookup      ||        9.15 |            0.00 |
>   |------------------------++-------------+-----------------|
>   | total                  ||       94.88 |            0.02 |
>
> for the vector-with-free-list:
>
>   | test                   || tot avg (s) | tot avg err (s) |
>   |------------------------++-------------+-----------------|
>   | bytechar               ||       11.63 |            0.01 |
>   | bytechar-100k          ||       11.91 |            0.37 |
>   | bytechar-100k-nolookup ||        8.80 |            0.01 |
>   | bytechar-100k-random   ||      248.07 |            3.84 |
>   | bytechar-100k-rev      ||       11.71 |            0.02 |
>   | bytechar-10k-random    ||       35.24 |            0.53 |
>   | bytechar-1k-random     ||       14.01 |            0.06 |
>   | bytechar-nolookup      ||        8.69 |            0.13 |
>   |------------------------++-------------+-----------------|
>   | total                  ||      350.06 |            3.89 |
>
> and for the growable array:
>
>   | test                   || tot avg (s) | tot avg err (s) |
>   |------------------------++-------------+-----------------|
>   | bytechar               ||       11.34 |            0.08 |
>   | bytechar-100k          ||       11.59 |            0.47 |
>   | bytechar-100k-nolookup ||        8.78 |            0.12 |
>   | bytechar-100k-random   ||       16.17 |            0.33 |
>   | bytechar-100k-rev      ||       11.31 |            0.03 |
>   | bytechar-10k-random    ||       11.76 |            0.01 |
>   | bytechar-1k-random     ||       11.34 |            0.08 |
>   | bytechar-nolookup      ||        8.70 |            0.09 |
>   |------------------------++-------------+-----------------|
>   | total                  ||       91.00 |            0.61 |

Hard to argue with those numbers :-)

I wonder whether it wouldn't be faster, upon encountering a marker that
has been splatted, to fix the entire array all at once. That would
ensure that creation order is respected, and splatting is relatively
rare (and, when splatted, we can expect most of the array to have been
splatted; indeed, I suspect it'd be best to give up on the marker vector
and build a new one so the old one can be collected and we don't have to
worry about never shrinking it).

Pip

Re: MPS: marker-vector

[Helmut Eller]

On Mon, Aug 05 2024, Pip Cet wrote:

>> This replaces the vector-with-free-list by a growable vector, i.e. the
>> free entries are always kept at the end of the vector.
>
> I don't think that's entirely accurate; it's quite possible for an entry
> at the beginning of the array to be splatted and remain untouched until
> the next time a DO_MARKERS reaches it, which may take a long time.

Indeed, that's true.

> I see one somewhat theoretical problem with this patch: if a marker is
> simultaneously kept in a weak hash table, it's possible for it to be
> splatted from the marker vector while remaining in the weak hash table
> (there's no guarantee all references will be splatted at the same time);
> if it is then retrieved from the weak hash table and made to point
> nowhere, we will try to remove it from the marker vector, and hit the
> igc_assert.

Never thought about this.  Hm.  I think MPS could easily guarantee that
all references are splatted at the same time: we could think of
splatting a reference like moving an object to address zero.  MPS
certainly guarantees that all references to a moved object are updated
before they are seen by user code.  MPS could do the same for splatted
references.

> The rest of my comments are tiny nits, really:
>
> - capacity isn't redundant on 32-bit systems

Not sure what you mean.  Certainly igc_header_nwords works on 32-bit
systems too; and igc_header_nwords is pretty much the same as capacity.

> - I'd prefer the marker index to be signed; if it is unsigned, we
> don't need to assert it's >= 0, and assigning -1 to it confused me...

You'd have to talk to the person who designed the struct Lisp_Marker.

> - you shouldn't compare Lisp_Objects with ==
> - I'd prefer checking for splatted elements before deciding to grow
> the vector, if we can do so efficiently

Good idea.

> - I find XFIXNAT easier to read when the number is guaranteed to be nonnegative
> - using alloca is problematic for large vectors (which shouldn't be
> dumped, thus a nit)

Probably.

> I wonder whether it wouldn't be faster, upon encountering a marker that
> has been splatted, to fix the entire array all at once. That would
> ensure that creation order is respected, and splatting is relatively
> rare (and, when splatted, we can expect most of the array to have been
> splatted; indeed, I suspect it'd be best to give up on the marker vector
> and build a new one so the old one can be collected and we don't have to
> worry about never shrinking it).

Possibly.  But I also decided to ignore the issue and happily let
somebody else come up with a benchmark that shows that any of this
matters.

Re: MPS: marker-vector

[Gerd Möllmann]

Helmut Eller <eller.helmut@gmail.com> writes:

>> - I'd prefer the marker index to be signed; if it is unsigned, we
>> don't need to assert it's >= 0, and assigning -1 to it confused me...
>
> You'd have to talk to the person who designed the struct Lisp_Marker.

I didn't design Lisp_Marker, but I added the index member for MPS. I
made it signed just for the asserts, so that I could easily check if
something went wrong.

Re: MPS: marker-vector

[Pip Cet]

"Helmut Eller" <eller.helmut@gmail.com> writes:
> On Mon, Aug 05 2024, Pip Cet wrote:
>> I see one somewhat theoretical problem with this patch: if a marker is
>> simultaneously kept in a weak hash table, it's possible for it to be
>> splatted from the marker vector while remaining in the weak hash table
>> (there's no guarantee all references will be splatted at the same time);
>> if it is then retrieved from the weak hash table and made to point
>> nowhere, we will try to remove it from the marker vector, and hit the
>> igc_assert.
>
> Never thought about this.  Hm.  I think MPS could easily guarantee that
> all references are splatted at the same time: we could think of
> splatting a reference like moving an object to address zero.  MPS
> certainly guarantees that all references to a moved object are updated
> before they are seen by user code.  MPS could do the same for splatted
> references.

I don't know MPS internals very well, but IIRC weak objects can be
scanned with or without splatting depending on whether the program hit a
barrier or a regular GC opportunity.  I don't know why that is,
though. It may be related to the unfortunate
emulated-single-access-on-IA32 thing.

>> The rest of my comments are tiny nits, really:
>>
>> - capacity isn't redundant on 32-bit systems
>
> Not sure what you mean.  Certainly igc_header_nwords works on 32-bit
> systems too; and igc_header_nwords is pretty much the same as capacity.

Except it's rounded up to multiples of 64 bits on 32 bit systems, making
it impossible to represent a vector of odd length.  Of course that
doesn't happen in the code you posted (which starts with 2 entries and
doubles the vector size when a larger vector is needed, resulting in an
even number of entries at all times), so I apologize for not seeing that
right away.

>> I wonder whether it wouldn't be faster, upon encountering a marker that
>> has been splatted, to fix the entire array all at once. That would
>> ensure that creation order is respected, and splatting is relatively
>> rare (and, when splatted, we can expect most of the array to have been
>> splatted; indeed, I suspect it'd be best to give up on the marker vector
>> and build a new one so the old one can be collected and we don't have to
>> worry about never shrinking it).
>
> Possibly.  But I also decided to ignore the issue and happily let
> somebody else come up with a benchmark that shows that any of this
> matters.

Okay, let's stay with the current code for now and revisit the issue
when the time comes?

Pip

Re: MPS: marker-vector

[Helmut Eller]

On Tue, Aug 06 2024, Pip Cet wrote:

>>> - capacity isn't redundant on 32-bit systems
>>
>> Not sure what you mean.  Certainly igc_header_nwords works on 32-bit
>> systems too; and igc_header_nwords is pretty much the same as capacity.
>
> Except it's rounded up to multiples of 64 bits on 32 bit systems, making
> it impossible to represent a vector of odd length.

Ah, okay.

>> Possibly.  But I also decided to ignore the issue and happily let
>> somebody else come up with a benchmark that shows that any of this
>> matters.
>
> Okay, let's stay with the current code for now and revisit the issue
> when the time comes?

Yep.

Re: MPS: marker-vector

[Gerd Möllmann]

Helmut Eller <eller.helmut@gmail.com> writes:

> What would you think about changing the marker-vector-with-free-list to
> a mundane growable array like in the patch below?
>
> The main motivation for this would that we could then iterate in
> reverse, or more precisely, in an order that is more like the order used
> for the linked-list-of-markers.  This is relevant for the heuristic in
> buf_charpos_to_bytepos that creates a temporary marker; it works better
> if those temporary markers are visited first.
>
> Using Stefan's elb-bytechar benchmark, I get for the
> linked-list-of-markers:
>
>   | test                   || tot avg (s) | tot avg err (s) |
>   |------------------------++-------------+-----------------|
>   | bytechar               ||       11.80 |            0.00 |
>   | bytechar-100k          ||       11.85 |            0.00 |
>   | bytechar-100k-nolookup ||        9.19 |            0.00 |
>   | bytechar-100k-random   ||       16.73 |            0.02 |
>   | bytechar-100k-rev      ||       11.86 |            0.00 |
>   | bytechar-10k-random    ||       12.36 |            0.01 |
>   | bytechar-1k-random     ||       11.93 |            0.00 |
>   | bytechar-nolookup      ||        9.15 |            0.00 |
>   |------------------------++-------------+-----------------|
>   | total                  ||       94.88 |            0.02 |
>
> for the vector-with-free-list:
>
>   | test                   || tot avg (s) | tot avg err (s) |
>   |------------------------++-------------+-----------------|
>   | bytechar               ||       11.63 |            0.01 |
>   | bytechar-100k          ||       11.91 |            0.37 |
>   | bytechar-100k-nolookup ||        8.80 |            0.01 |
>   | bytechar-100k-random   ||      248.07 |            3.84 |
>   | bytechar-100k-rev      ||       11.71 |            0.02 |
>   | bytechar-10k-random    ||       35.24 |            0.53 |
>   | bytechar-1k-random     ||       14.01 |            0.06 |
>   | bytechar-nolookup      ||        8.69 |            0.13 |
>   |------------------------++-------------+-----------------|
>   | total                  ||      350.06 |            3.89 |
>
> and for the growable array:
>
>   | test                   || tot avg (s) | tot avg err (s) |
>   |------------------------++-------------+-----------------|
>   | bytechar               ||       11.34 |            0.08 |
>   | bytechar-100k          ||       11.59 |            0.47 |
>   | bytechar-100k-nolookup ||        8.78 |            0.12 |
>   | bytechar-100k-random   ||       16.17 |            0.33 |
>   | bytechar-100k-rev      ||       11.31 |            0.03 |
>   | bytechar-10k-random    ||       11.76 |            0.01 |
>   | bytechar-1k-random     ||       11.34 |            0.08 |
>   | bytechar-nolookup      ||        8.70 |            0.09 |
>   |------------------------++-------------+-----------------|
>   | total                  ||       91.00 |            0.61 |
>
> So the results of the growable array and the linked-list-of-markers
> would be closer.  A downside of the growable array is that it needs a
> bit of extra code for the dumper.  I didn't try to port the gap array
> code, because it seems like it would require many more changes and would
> make it even harder to merge with master.

Hm, can't say much about the benchmark, I'm afraid. I've been
successfully ignoring this topic so far :-). I don't even know what the
impact of these numbers in a larger context is.

That said, if you find it important, I trust that, so no objections from
me.

Technically speaking, from reading the diff, I think it's okay. The only
thing I'm wondering about is the compacting of the vector while
iterating over it. I can't put my finger on it, but Is that always safe?

(And I don't know if one can call mps_scan_area without MPS_SCAN_BEGIN/END.)

Re: MPS: marker-vector

[Helmut Eller]

On Tue, Aug 06 2024, Gerd Möllmann wrote:

>> So the results of the growable array and the linked-list-of-markers
>> would be closer.  A downside of the growable array is that it needs a
>> bit of extra code for the dumper.  I didn't try to port the gap array
>> code, because it seems like it would require many more changes and would
>> make it even harder to merge with master.
>
> Hm, can't say much about the benchmark, I'm afraid. I've been
> successfully ignoring this topic so far :-). I don't even know what the
> impact of these numbers in a larger context is.
>
> That said, if you find it important, I trust that, so no objections from
> me.

Then I will ignore this too.

> Technically speaking, from reading the diff, I think it's okay. The only
> thing I'm wondering about is the compacting of the vector while
> iterating over it. I can't put my finger on it, but Is that always safe?

Modifying/adding/removing array entries while iterating over it is
definitely problematic.  But that that's probably also problematic for
the vector-with-free-list.

Re: Markers in a gap array

[Stefan Monnier]

BTW, I just pushed to `scratch/gl-state-bytepos` an orthogonal patch
which intends to reduce the use of `bytepos_to_charpos` by changing
the `gl_state` cache so it keeps track of the byteposition of the
boundaries of the current "chunk of `syntax-table` property".

This way RE_UPDATE_SYNTAX_TABLE can take a bytepos rather than an charpos
and convert it to charpos only when moving into a different "chunk of
`syntax-table` property".

On that previous benchmark, it works wonderfully (the implementation of
markers has basically no impact any more in that benchmark):

  | test                   | non-gc avg (s) | gc avg (s) | gcs avg | tot avg (s) | tot avg err (s) |
  |------------------------+----------------+------------+---------+-------------+-----------------|
  | bytechar               |           6.25 |       0.00 |       0 |        6.25 |            0.85 |
  | bytechar-100k          |           6.41 |       0.00 |       0 |        6.41 |            0.65 |
  | bytechar-100k-nolookup |           6.61 |       0.00 |       0 |        6.61 |            0.17 |
  | bytechar-100k-random   |           8.63 |       0.00 |       0 |        8.63 |            0.06 |
  | bytechar-100k-rev      |           7.64 |       0.00 |       0 |        7.64 |            1.48 |
  | bytechar-10k-random    |           6.79 |       0.00 |       0 |        6.79 |            0.10 |
  | bytechar-1k-random     |           6.64 |       0.00 |       0 |        6.64 |            0.15 |
  | bytechar-nolookup      |           6.63 |       0.00 |       0 |        6.63 |            0.23 |
  |------------------------+----------------+------------+---------+-------------+-----------------|
  | total                  |          55.61 |       0.00 |       0 |       55.61 |            1.86 |

Of course, that's the ideal case: that buffer has no `syntax-table` text
properties, so there's only one chunk.  In buffers with many uses of the
`syntax-table` text property, the patch may end up slowing things down
because the update from one chunk to another requires not just
a bytepos->charpos but also two additional charpos->bytepos conversions.

Still, I suspect it will usually be beneficial (the cost of going from
one chunk to another is itself significant so the extra charpos->bytepos
conversions should not slow it down unduly).

The patch has a significant FIXME that needs invesitgating (it passes
all tests, but I'm not sure it's doing the right thing).


        Stefan

Re: Markers in a gap array

[Ihor Radchenko]

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

> And like you, I don't see any speed improvement from the branch.  On the
> other hand, my trivial "thinko fix" b595b4598 (which I thought would
> have no real-life effect) seems to make a significant difference (see
> the results below).  So maybe the reason why you can't reproduce the
> slowdown is because of b595b4598?  And maybe we should install that into
> `emacs-30`?

I tried with and without b595b4598. It makes a little, but noticeable
difference:

without b595b4598 (master + reverted b595b4598)
    5.66%  emacs         emacs                                        [.] buf_bytepos_to_charpos

with b595b4598 (master)
     2.38%  emacs         emacs                                        [.] buf_bytepos_to_charpos

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

Re: Markers in a gap array

[Konstantin Kharlamov]

On Thu, 2024-07-04 at 16:11 -0400, Stefan Monnier wrote:
> So maybe the reason why you can't reproduce the
> slowdown is because of b595b4598?  And maybe we should install that
> into `emacs-30`?

Although Idk the code, but reading the b595b4598 description I see that
it is a bugfix; specifically it fixes wrong calculation introduced in
the previous patch. Bugfixes definitely should be installed to the
stable branch.