Re: Markers in a gap array

[Stefan Monnier <monnier@iro.umontreal.ca>]

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