State of the overlay tree branch?

State of the overlay tree branch?

[Sebastian Sturm]

Hi,

after finding that the feature/noverlay branch does wonders for my 
editing experience[1], I'd like to reinvigorate the discussion on its 
inclusion into master. Are there plans for a merge with the emacs-27 
master branch? Any critical issues blocking such a merge?

If a recent Emacs 27 variant with the overlay branch feature was 
available, I'd be happy to evaluate that in my daily work.

best regards,
Sebastian Sturm

[1] I'm using cquery for my C++ editing needs, which comes with an 
overlay-based semantic highlighting mechanism. With my emacs 
configuration, lsp-mode/lsp-ui emit 6 calls to line-number-at-pos per 
character insertion, which consume ~20 to 25 ms each when performing 
edits close to the bottom of a 66KB C++ file (measured using 
(benchmark-run 1000 (line-number-at-pos (point))) on a release build of 
emacs-27/git commit #9942734...). Using the noverlay branch, this figure 
drops to ~160us per call.

Re: State of the overlay tree branch?

[Eli Zaretskii]

> From: Sebastian Sturm <s.sturm@arkona-technologies.de>
> Date: Sun, 18 Mar 2018 21:14:53 +0100
> 
> [1] I'm using cquery for my C++ editing needs, which comes with an 
> overlay-based semantic highlighting mechanism. With my emacs 
> configuration, lsp-mode/lsp-ui emit 6 calls to line-number-at-pos per 
> character insertion, which consume ~20 to 25 ms each when performing 
> edits close to the bottom of a 66KB C++ file (measured using 
> (benchmark-run 1000 (line-number-at-pos (point))) on a release build of 
> emacs-27/git commit #9942734...). Using the noverlay branch, this figure 
> drops to ~160us per call.

If lsp-mode/lsp-ui needs a fast line counter, one can easily be
provided by exposing find_newline to Lisp.  IME, it's lightning-fast,
and should run circles around count-lines (used by line-number-at-pos).

(I'm not sure I even understand how overlays come into play here,
btw.)

Re: State of the overlay tree branch?

[Sebastian Sturm]

I also found it surprising that overlays would slow down line counting, 
but since I don't know anything about the architecture of the Emacs 
display engine, or its overlay implementation, I figured that overlays 
must be to blame because

(i) the issue went away after switching to the feature/noverlay branch

(ii) configuring the semantic highlighter to use its font-lock backend 
also resolved the performance issue (though with the font-lock backend, 
highlights are easily messed up by editing operations which makes the 
overlay variant far more appealing)

I also found that some other heavy users of overlays such as 
avy-goto-word-0-{above,below} feel faster with the feature/noverlay 
branch, so I'd welcome a merge of the overlay branch even if there was a 
technically superior alternative to line-number-at-pos that didn't 
suffer from overlay-related performance issues.

That being said, your suggestion sounds intriguing. What would be 
required to expose find_newline to Lisp? Would I simply have to wrap it 
in one of Emacs's DEFINE_<something> macros? Is there some documentation 
on the Emacs C backend?

On 03/18/2018 09:39 PM, Eli Zaretskii wrote:
 >> From: Sebastian Sturm <s.sturm@arkona-technologies.de>
 >> Date: Sun, 18 Mar 2018 21:14:53 +0100
 >>
 >> [1] I'm using cquery for my C++ editing needs, which comes with an
 >> overlay-based semantic highlighting mechanism. With my emacs
 >> configuration, lsp-mode/lsp-ui emit 6 calls to line-number-at-pos per
 >> character insertion, which consume ~20 to 25 ms each when performing
 >> edits close to the bottom of a 66KB C++ file (measured using
 >> (benchmark-run 1000 (line-number-at-pos (point))) on a release build of
 >> emacs-27/git commit #9942734...). Using the noverlay branch, this figure
 >> drops to ~160us per call.
 >
 > If lsp-mode/lsp-ui needs a fast line counter, one can easily be
 > provided by exposing find_newline to Lisp.  IME, it's lightning-fast,
 > and should run circles around count-lines (used by line-number-at-pos).
 >
 > (I'm not sure I even understand how overlays come into play here,
 > btw.)

Re: State of the overlay tree branch?

[Sebastian Sturm]

concerning the performance improvement with noverlay, it seems I spoke 
to soon. I've now had the issue reappear, both with the noverlay branch, 
and with the semantic highlighter set to use font-lock. Sorry for the 
misinformation.
Again, however, line-number-at-pos shows up as a large CPU time consumer 
in the profiler report, and benchmark-run still reports several ms per 
invocation (though this time it's usually around 2 to 4 ms instead of 
the 20 to 25 I measured earlier), so I'd still be very much interested 
in a faster line-number-at-pos implementation.

On 03/18/2018 10:04 PM, Sebastian Sturm wrote:
> I also found it surprising that overlays would slow down line counting, 
> but since I don't know anything about the architecture of the Emacs 
> display engine, or its overlay implementation, I figured that overlays 
> must be to blame because
> 
> (i) the issue went away after switching to the feature/noverlay branch
> 
> (ii) configuring the semantic highlighter to use its font-lock backend 
> also resolved the performance issue (though with the font-lock backend, 
> highlights are easily messed up by editing operations which makes the 
> overlay variant far more appealing)
> 
> I also found that some other heavy users of overlays such as 
> avy-goto-word-0-{above,below} feel faster with the feature/noverlay 
> branch, so I'd welcome a merge of the overlay branch even if there was a 
> technically superior alternative to line-number-at-pos that didn't 
> suffer from overlay-related performance issues.
> 
> That being said, your suggestion sounds intriguing. What would be 
> required to expose find_newline to Lisp? Would I simply have to wrap it 
> in one of Emacs's DEFINE_<something> macros? Is there some documentation 
> on the Emacs C backend?
> 
> On 03/18/2018 09:39 PM, Eli Zaretskii wrote:
>  >> From: Sebastian Sturm <s.sturm@arkona-technologies.de>
>  >> Date: Sun, 18 Mar 2018 21:14:53 +0100
>  >>
>  >> [1] I'm using cquery for my C++ editing needs, which comes with an
>  >> overlay-based semantic highlighting mechanism. With my emacs
>  >> configuration, lsp-mode/lsp-ui emit 6 calls to line-number-at-pos per
>  >> character insertion, which consume ~20 to 25 ms each when performing
>  >> edits close to the bottom of a 66KB C++ file (measured using
>  >> (benchmark-run 1000 (line-number-at-pos (point))) on a release build of
>  >> emacs-27/git commit #9942734...). Using the noverlay branch, this 
> figure
>  >> drops to ~160us per call.
>  >
>  > If lsp-mode/lsp-ui needs a fast line counter, one can easily be
>  > provided by exposing find_newline to Lisp.  IME, it's lightning-fast,
>  > and should run circles around count-lines (used by line-number-at-pos).
>  >
>  > (I'm not sure I even understand how overlays come into play here,
>  > btw.)
> 

Re: State of the overlay tree branch?

[Sebastian Sturm]

for the record, I just switched back to emacs master (no noverlay) and 
the time reported by (benchmark-run 1000 (line-number-at-pos (point)) 
increased by a factor of ~40, to 75-80s. At this level, editing is 
unbearably slow. With the semantic highlighter disabled, the same 
measurement yields ~2.5s (still painfully slow, but borderline usable), 
so about the same time reported by the noverlay branch.
To me, this suggests that noverlay indeed improves performance, though 
not necessarily to the level I had previously claimed. find_newline may 
solve this particular issue completely.
Since the time taken by line-number-at-pos seems to fluctuate wildly for 
(to me) unknown reasons, I'll try and see if I can set up a systematic 
way to collect reliable data.

On 03/19/2018 12:03 AM, Sebastian Sturm wrote:
> concerning the performance improvement with noverlay, it seems I spoke 
> to soon. I've now had the issue reappear, both with the noverlay branch, 
> and with the semantic highlighter set to use font-lock. Sorry for the 
> misinformation.
> Again, however, line-number-at-pos shows up as a large CPU time consumer 
> in the profiler report, and benchmark-run still reports several ms per 
> invocation (though this time it's usually around 2 to 4 ms instead of 
> the 20 to 25 I measured earlier), so I'd still be very much interested 
> in a faster line-number-at-pos implementation.
> 
> On 03/18/2018 10:04 PM, Sebastian Sturm wrote:
>> I also found it surprising that overlays would slow down line 
>> counting, but since I don't know anything about the architecture of 
>> the Emacs display engine, or its overlay implementation, I figured 
>> that overlays must be to blame because
>>
>> (i) the issue went away after switching to the feature/noverlay branch
>>
>> (ii) configuring the semantic highlighter to use its font-lock backend 
>> also resolved the performance issue (though with the font-lock 
>> backend, highlights are easily messed up by editing operations which 
>> makes the overlay variant far more appealing)
>>
>> I also found that some other heavy users of overlays such as 
>> avy-goto-word-0-{above,below} feel faster with the feature/noverlay 
>> branch, so I'd welcome a merge of the overlay branch even if there was 
>> a technically superior alternative to line-number-at-pos that didn't 
>> suffer from overlay-related performance issues.
>>
>> That being said, your suggestion sounds intriguing. What would be 
>> required to expose find_newline to Lisp? Would I simply have to wrap 
>> it in one of Emacs's DEFINE_<something> macros? Is there some 
>> documentation on the Emacs C backend?
>>
>> On 03/18/2018 09:39 PM, Eli Zaretskii wrote:
>>  >> From: Sebastian Sturm <s.sturm@arkona-technologies.de>
>>  >> Date: Sun, 18 Mar 2018 21:14:53 +0100
>>  >>
>>  >> [1] I'm using cquery for my C++ editing needs, which comes with an
>>  >> overlay-based semantic highlighting mechanism. With my emacs
>>  >> configuration, lsp-mode/lsp-ui emit 6 calls to line-number-at-pos per
>>  >> character insertion, which consume ~20 to 25 ms each when performing
>>  >> edits close to the bottom of a 66KB C++ file (measured using
>>  >> (benchmark-run 1000 (line-number-at-pos (point))) on a release 
>> build of
>>  >> emacs-27/git commit #9942734...). Using the noverlay branch, this 
>> figure
>>  >> drops to ~160us per call.
>>  >
>>  > If lsp-mode/lsp-ui needs a fast line counter, one can easily be
>>  > provided by exposing find_newline to Lisp.  IME, it's lightning-fast,
>>  > and should run circles around count-lines (used by 
>> line-number-at-pos).
>>  >
>>  > (I'm not sure I even understand how overlays come into play here,
>>  > btw.)
>>
> 

Re: State of the overlay tree branch?

[Eli Zaretskii]

> From: Sebastian Sturm <s.sturm@arkona-technologies.de>
> Date: Mon, 19 Mar 2018 00:20:13 +0100
> 
> for the record, I just switched back to emacs master (no noverlay) and 
> the time reported by (benchmark-run 1000 (line-number-at-pos (point)) 
> increased by a factor of ~40, to 75-80s. At this level, editing is 
> unbearably slow. With the semantic highlighter disabled, the same 
> measurement yields ~2.5s (still painfully slow, but borderline usable), 
> so about the same time reported by the noverlay branch.

You will have to explain why overlays and the semantic highlighter
affect line-counting.  How about presenting a profile produced by
"M-x profiler-report"?

And the timings you measure are 2.5 _milliseconds_ (the benchmark runs
1000 times), right?  If so, I cannot understand why you say that's
borderline usable, because IME such short times are imperceptible by
humans.  I guess some other factor is at work here, so I'd suggest to
describe more details about your use case.

> Since the time taken by line-number-at-pos seems to fluctuate wildly for 
> (to me) unknown reasons, I'll try and see if I can set up a systematic 
> way to collect reliable data.

Yes, please do.  I'm guessing there's some factor here that is
important to consider.

Re: State of the overlay tree branch?

[Sebastian Sturm]

On 03/19/2018 07:43 AM, Eli Zaretskii wrote:
 >> From: Sebastian Sturm <s.sturm@arkona-technologies.de>
 >> Date: Mon, 19 Mar 2018 00:20:13 +0100
 >>
 >> for the record, I just switched back to emacs master (no noverlay) and
 >> the time reported by (benchmark-run 1000 (line-number-at-pos (point))
 >> increased by a factor of ~40, to 75-80s. At this level, editing is
 >> unbearably slow. With the semantic highlighter disabled, the same
 >> measurement yields ~2.5s (still painfully slow, but borderline usable),
 >> so about the same time reported by the noverlay branch.
 >
 > You will have to explain why overlays and the semantic highlighter
 > affect line-counting.  How about presenting a profile produced by
 > "M-x profiler-report"?

please find below a profiler report taken this morning (on my PC at 
work, which doesn't suffer from the performance issue as much as my 2014 
MacBook Pro, but even here the issue is clearly noticeable)

 >
 > And the timings you measure are 2.5 _milliseconds_ (the benchmark runs
 > 1000 times), right?  If so, I cannot understand why you say that's
 > borderline usable, because IME such short times are imperceptible by
 > humans.  I guess some other factor is at work here, so I'd suggest to
 > describe more details about your use case.

well no, it's about 2.5ms per call to line-number-at-pos, which is 
called at least 6 times per character insertion (with my Emacs config, 
at least). Which already makes for 15ms per character insertion, 
excluding anything else done by cc-mode or lsp-mode.

 >> Since the time taken by line-number-at-pos seems to fluctuate wildly for
 >> (to me) unknown reasons, I'll try and see if I can set up a systematic
 >> way to collect reliable data.
 >
 > Yes, please do.  I'm guessing there's some factor here that is
 > important to consider.

I wrote a simple-minded measurement routine that can at least report the 
time taken between successive character insertions, and I noticed that 
better alternatives have been brought up in response to my other mailing 
list thread (titled "Latency profiling?"). I haven't had time to prepare 
a systematic test case yet, but I will look into it when I get home from 
work this evening.


- command-execute                                                5676  73%
  - call-interactively                                            5676  73%
   - funcall-interactively                                        5676  73%
    - self-insert-command                                         5080  66%
     - lsp-on-change                                              2144  27%
      - lsp--text-document-content-change-event                   1964  25%
       - lsp--point-to-position                                   1964  25%
          line-number-at-pos                                      1964  25%
      + json-encode                                                164   2%
      + file-truename                                               16   0%
     - c-after-change                                             1784  23%
      - mapc                                                      1772  23%
       + #<compiled 0x1a24bed>                                    1772  23%
      - c-invalidate-sws-region-after                               12   0%
       - c-invalidate-sws-region-after-ins                          12   0%
        - c-beginning-of-macro                                       8   0%
           back-to-indentation                                       4   0%
        - c-literal-limits                                           4   0%
           c-state-full-pp-to-literal                                4   0%
     - lsp-before-change                                          1016  13%
      - lsp--point-to-position                                    1016  13%
         line-number-at-pos                                       1016  13%
     - sp--post-self-insert-hook-handler                            56   0%
      - sp-insert-pair                                              28   0%
       - sp--pair-to-insert                                         24   0%
        - sp--all-pairs-to-insert                                   20   0%
         - sp--looking-back-p                                        8   0%
            sp--looking-back                                         8   0%
         + sp--do-action-p                                           8   0%
       + sp--get-closing-regexp                                      4   0%
      + sp--all-pairs-to-insert                                     16   0%
      + sp-escape-open-delimiter                                    12   0%
     + c-before-change                                              28   0%
     - jit-lock-after-change                                         4   0%
      + run-hook-with-args                                           4   0%
    + counsel-M-x                                                  360   4%
    + evil-open-below                                              232   3%
- lsp-ui-doc--make-request                                        643   8%
    line-number-at-pos                                             627   8%
  + file-truename                                                    8   0%
    url-hexify-string                                                4   0%
- lsp-ui-sideline                                                 528   6%
    line-number-at-pos                                             528   6%
+ timer-event-handler                                             327   4%
+ evil-escape-pre-command-hook                                    220   2%
+ #<compiled 0xb54291>                                            141   1%
+ redisplay_internal (C function)                                  88   1%
+ ...                                                              29   0%
+ yas--post-command-handler                                        20   0%
+ global-spacemacs-whitespace-cleanup-mode-check-buffers            4   0%
+ internal-timer-start-idle                                         4   0%
+ flycheck-display-error-at-point-soon                              4   0%
   flycheck-error-list-update-source                                 4   0%

Re: State of the overlay tree branch?

[Eli Zaretskii]

> From: Sebastian Sturm <s.sturm@arkona-technologies.de>
> Date: Mon, 19 Mar 2018 10:53:52 +0100
> 
> On 03/19/2018 07:43 AM, Eli Zaretskii wrote:
>  >> From: Sebastian Sturm <s.sturm@arkona-technologies.de>
>  >> Date: Mon, 19 Mar 2018 00:20:13 +0100
>  >>
>  >> for the record, I just switched back to emacs master (no noverlay) and
>  >> the time reported by (benchmark-run 1000 (line-number-at-pos (point))
>  >> increased by a factor of ~40, to 75-80s. At this level, editing is
>  >> unbearably slow. With the semantic highlighter disabled, the same
>  >> measurement yields ~2.5s (still painfully slow, but borderline usable),
>  >> so about the same time reported by the noverlay branch.
>  >
>  > You will have to explain why overlays and the semantic highlighter
>  > affect line-counting.  How about presenting a profile produced by
>  > "M-x profiler-report"?
> 
> please find below a profiler report taken this morning (on my PC at 
> work, which doesn't suffer from the performance issue as much as my 2014 
> MacBook Pro, but even here the issue is clearly noticeable)

That profile says that self-insert-command takes a large percentage of
the time.  So I think we should look into the reasons for such a
strange place to spend hundreds of microseconds.  According to the
profile, line-number-at-pos takes about the same percentage of time as
self-insert-command does.  And that is even before you optimize the
successive calls to line-counting code to take advantage of the
previously computed value for some close line.

>  > And the timings you measure are 2.5 _milliseconds_ (the benchmark runs
>  > 1000 times), right?  If so, I cannot understand why you say that's
>  > borderline usable, because IME such short times are imperceptible by
>  > humans.  I guess some other factor is at work here, so I'd suggest to
>  > describe more details about your use case.
> 
> well no, it's about 2.5ms per call to line-number-at-pos, which is 
> called at least 6 times per character insertion (with my Emacs config, 
> at least). Which already makes for 15ms per character insertion, 
> excluding anything else done by cc-mode or lsp-mode.

Then, as I said, I don't understand why it takes so much on your
system.  I get times that are 10 times faster.

Re: State of the overlay tree branch?

[Stefan Monnier]

> well no, it's about 2.5ms per call to line-number-at-pos, which is called at
> least 6 times per character insertion (with my Emacs config, at
> least). Which already makes for 15ms per character insertion, excluding
> anything else done by cc-mode or lsp-mode.

Since you say that the noverlay branch helps, could you check the number
of overlays involved?  E.g.

    M-: (length (overlays-in (point-min) (point-max))) RET

If there are more overlays than chars in this buffer, maybe there's
a problem in some Elisp that creates too many overlays?

If there aren't that many overlays, then I wonder why the noverlays
branch would make such a significant difference.

Also, if you can reliably reproduce the "slow editing", would it be
possible to make a recipe for it that we can try and reproduce on
our side?


        Stefan

Re: State of the overlay tree branch?

[Sebastian Sturm]

for the file I was complaining about, the number returned is 3080 
(doesn't exceed the number of chars though, (point-max) = 67641). Will 
try to obtain usable timing data later today when I get home from work. 
Thanks!

On 03/19/2018 03:56 PM, Stefan Monnier wrote:
>> well no, it's about 2.5ms per call to line-number-at-pos, which is called at
>> least 6 times per character insertion (with my Emacs config, at
>> least). Which already makes for 15ms per character insertion, excluding
>> anything else done by cc-mode or lsp-mode.
> 
> Since you say that the noverlay branch helps, could you check the number
> of overlays involved?  E.g.
> 
>      M-: (length (overlays-in (point-min) (point-max))) RET
> 
> If there are more overlays than chars in this buffer, maybe there's
> a problem in some Elisp that creates too many overlays?
> 
> If there aren't that many overlays, then I wonder why the noverlays
> branch would make such a significant difference.
> 
> Also, if you can reliably reproduce the "slow editing", would it be
> possible to make a recipe for it that we can try and reproduce on
> our side?
> 
> 
>          Stefan
> 
> 

-- 
Sebastian Sturm
Research & Development

Phone:	+49 (0) 6155 7808977
Fax:	+49 (0) 6155 7802880
Email:	s.sturm@arkona-technologies.de
Web:	www.arkona-technologies.de

arkona technologies GmbH
Im Leuschnerpark 4
64347 Griesheim
Germany
Amtsgericht / Commercial Register of Darmstadt, HRB 90080
USt-ID: DE273794666
Steuernummer / Tax-ID: 007 / 228 / 19331
Geschäftsführung / Managing Director: Rainer Sturm

This e-mail may contain confidential and/or privileged information. If 
you are not the intended recipient (or have received this e-mail in 
error) please notify the sender immediately and delete this message and 
any attachments from your system. Any unauthorised copying, disclosure 
or distribution of the material in this e-mail is strictly forbidden.

We cannot accept any responsibility for the accuracy or completeness of 
this message as it has been transmitted over a public network. If, 
despite our use of anti-virus software, a virus enters your systems in 
connection with the sending of the e-mail, you may not hold us liable 
for any damages that may possibly arise in that connection. We will 
accept liability which by law we cannot exclude.

Re: State of the overlay tree branch?

[Stefan Monnier]

> for the file I was complaining about, the number returned is 3080 (doesn't
> exceed the number of chars though, (point-max) = 67641). Will try to obtain
> usable timing data later today when I get home from work. Thanks!

Thanks.

It's large enough that noverlay might indeed make a difference for some
operations, but not large enough to explain why line-number-at-pos would
be so slow, I think.


        Stefan

Re: State of the overlay tree branch?

[Sebastian Sturm]

after disabling cquery for testing purposes (which leaves me with 45 
overlays generated by flycheck for my troublesome C++ file), I'm now 
generating a large number of overlays using the following function:

(defun test-highlight ()
         (save-excursion
           (with-silent-modifications
             (let ((stepsize 10))
               (widen)
               (goto-char 1)
               (cl-loop for n from (point-min) upto (- (point-max) 
stepsize) by stepsize do
                 (let ((ov (make-overlay n (+ (1- stepsize) n))))
                   (overlay-put ov 'cquery-sem-highlight t)))))))

Evaluating the following function without additional overlays (beyond 
the flycheck ones, that is) yields the following results:

(defun benchmark-often ()
   (cl-loop for n from 1 upto 20 do
            (message (format "iteration %d: %f" n (nth 0 (benchmark-run 
(line-number-at-pos (point))))))))

1st run:
iteration 1: 0.001213
iteration 2: 0.001170
iteration 3: 0.001170
iteration 4: 0.001238
iteration 5: 0.001163
iteration 6: 0.001153
iteration 7: 0.000421
iteration 8: 0.000426
iteration 9: 0.000322
iteration 10: 0.000301
iteration 11: 0.000291
iteration 12: 0.000292
iteration 13: 0.000291
iteration 14: 0.000291
iteration 15: 0.000295
iteration 16: 0.000289
iteration 17: 0.000289
iteration 18: 0.000288
iteration 19: 0.000288
iteration 20: 0.000287

2nd run:
iteration 1: 0.001044
iteration 2: 0.000942
iteration 3: 0.000935
iteration 4: 0.000935
iteration 5: 0.000935
iteration 6: 0.000932
iteration 7: 0.000954
iteration 8: 0.000940
iteration 9: 0.000933
iteration 10: 0.000625
iteration 11: 0.000545
iteration 12: 0.000428
iteration 13: 0.000362
iteration 14: 0.000346
iteration 15: 0.000325
iteration 16: 0.000309
iteration 17: 0.000309
iteration 18: 0.000316
iteration 19: 0.000310
iteration 20: 0.000308

after evaluating (test-highlight) the figures are as follows:
1st run:
iteration 1: 0.026012
iteration 2: 0.020334
iteration 3: 0.020250
iteration 4: 0.020349
iteration 5: 0.020501
iteration 6: 0.020635
iteration 7: 0.020302
iteration 8: 0.020426
iteration 9: 0.020440
iteration 10: 0.020441
iteration 11: 0.020515
iteration 12: 0.020525
iteration 13: 0.020383
iteration 14: 0.020510
iteration 15: 0.019829
iteration 16: 0.019899
iteration 17: 0.019950
iteration 18: 0.019828
iteration 19: 0.019901
iteration 20: 0.019819

2nd run:
iteration 1: 0.026526
iteration 2: 0.020051
iteration 3: 0.020100
iteration 4: 0.020080
iteration 5: 0.020080
iteration 6: 0.020249
iteration 7: 0.020087
iteration 8: 0.020005
iteration 9: 0.019980
iteration 10: 0.019985
iteration 11: 0.020077
iteration 12: 0.019979
iteration 13: 0.020060
iteration 14: 0.020092
iteration 15: 0.019954
iteration 16: 0.019766
iteration 17: 0.019432
iteration 18: 0.019491
iteration 19: 0.019458
iteration 20: 0.019482

I'm not allowed to share my employer's source code as a test case, so I 
tried the same procedure with the similarly large DeclBase.h from the 
public LLVM repository. To my surprise, DeclBase.h didn't suffer from 
any performance issues at all. Switching to fundamental-mode while 
visiting my file didn't change anything, so I assume that c-mode isn't 
to blame either.
There have been claims of overlay-related performance issues with cquery 
and some large(-ish) open-source C or C++ files, so I'll try to locate 
these files and hope that at least one of them exhibits this issue as well.

On 03/19/2018 04:07 PM, Sebastian Sturm wrote:
> for the file I was complaining about, the number returned is 3080 
> (doesn't exceed the number of chars though, (point-max) = 67641). Will 
> try to obtain usable timing data later today when I get home from work. 
> Thanks!
> 
> On 03/19/2018 03:56 PM, Stefan Monnier wrote:
>>> well no, it's about 2.5ms per call to line-number-at-pos, which is 
>>> called at
>>> least 6 times per character insertion (with my Emacs config, at
>>> least). Which already makes for 15ms per character insertion, excluding
>>> anything else done by cc-mode or lsp-mode.
>>
>> Since you say that the noverlay branch helps, could you check the number
>> of overlays involved?  E.g.
>>
>>      M-: (length (overlays-in (point-min) (point-max))) RET
>>
>> If there are more overlays than chars in this buffer, maybe there's
>> a problem in some Elisp that creates too many overlays?
>>
>> If there aren't that many overlays, then I wonder why the noverlays
>> branch would make such a significant difference.
>>
>> Also, if you can reliably reproduce the "slow editing", would it be
>> possible to make a recipe for it that we can try and reproduce on
>> our side?
>>
>>
>>          Stefan
>>
>>
> 

Re: State of the overlay tree branch?

[Eli Zaretskii]

> From: Sebastian Sturm <s.sturm@arkona-technologies.de>
> Date: Tue, 20 Mar 2018 02:23:02 +0100
> 
> 1st run:
> iteration 1: 0.001213
> iteration 2: 0.001170
> [...]
> 
> after evaluating (test-highlight) the figures are as follows:
> 1st run:
> iteration 1: 0.026012
> iteration 2: 0.020334

So, between 20-fold and 100-fold slow-down.

> I'm not allowed to share my employer's source code as a test case, so I 
> tried the same procedure with the similarly large DeclBase.h from the 
> public LLVM repository. To my surprise, DeclBase.h didn't suffer from 
> any performance issues at all. Switching to fundamental-mode while 
> visiting my file didn't change anything, so I assume that c-mode isn't 
> to blame either.

So it's still a mystery why your original file produces such a large
slowdown with overlays.

Can you show the results of "M-x profiler-report" for the slow test
with your original source file?  It could have some clues.  If that's
impossible, I can only repeat my suggestion to use perf to find the
code in Emacs that takes the lion's share of the processing time.

Re: State of the overlay tree branch?

[Sebastian Sturm]

 > So it's still a mystery why your original file produces such a large
 > slowdown with overlays.
 >
 > Can you show the results of "M-x profiler-report" for the slow test
 > with your original source file?  It could have some clues.  If that's
 > impossible, I can only repeat my suggestion to use perf to find the
 > code in Emacs that takes the lion's share of the processing time.

this is the profiler report I get for the slow case (BTW, is there a way 
to have the profiler resolve functions within line-number-at-pos? I 
tried increasing profiler-max-stack-depth to 32, but the profiler still 
didn't show anything below line-number-at-pos)

- command-execute                                               20522  97%
  - call-interactively                                           20522  97%
   - funcall-interactively                                       20061  94%
    - eval-expression                                            18609  87%
     - eval                                                      18609  87%
      - benchmark-often                                          18609  87%
       - let*                                                    18609  87%
        - while                                                  18609  87%
         - message                                               18388  86%
          - format                                               18376  86%
           - nth                                                 18376  86%
            - let                                                18376  86%
             - list                                              18376  86%
              - let                                              18368  86%
                 line-number-at-pos                              18348  86%
            ws-butler-after-change                                   4   0%
    + evil-open-below                                              614   2%
    + counsel-M-x                                                  575   2%
    + undo-tree-undo                                                79   0%
    + next-line                                                     68   0%
    + evil-normal-state                                             52   0%
    + evil-previous-line                                            48   0%
    + previous-line                                                  7   0%
    + evil-emacs-state                                               6   0%
    + evil-insert                                                    3   0%
   + byte-code                                                     461   2%
+ redisplay_internal (C function)                                 254   1%
+ timer-event-handler                                             116   0%
+ evil-escape-pre-command-hook                                     82   0%
+ ...                                                              63   0%
+ global-spacemacs-whitespace-cleanup-mode-check-buffers 
47   0%
+ yas--post-command-handler                                        33   0%
+ evil-repeat-post-hook                                             6   0%
+ evil-visual-post-command                                          5   0%
+ flycheck-handle-signal                                            4   0%
   evil-snipe-mode-check-buffers                                     4   0%
   global-undo-tree-mode-check-buffers                               4   0%
+ sp--save-pre-command-state                                        2   0%
+ xselect-convert-to-string                                         2   0%
+ evil-visual-pre-command                                           1   0%
+ flycheck-pos-tip-hide-messages                                    1   0%
+ which-key--hide-popup                                             1   0%

with perf, the ("self") time taken by buf_charpos_to_bytepos increases 
from ~60% (fast case) to >98%. This is the diff generated by perf diff 
<fast.perf> <slow.perf>:

# Event 'cycles'
#
# Baseline    Delta  Shared Object         Symbol 

# ........  .......  .................... 
..........................................
#
     57.77%  +40.30%  emacs-27.0.50         [.] buf_charpos_to_bytepos
     11.12%  -10.70%  libc-2.23.so          [.] __memrchr
      6.48%   -6.19%  emacs-27.0.50         [.] assq_no_quit
      5.92%   -5.62%  emacs-27.0.50         [.] find_cache_boundary
      4.26%   -4.07%  emacs-27.0.50         [.] set_buffer_internal_2
      4.10%   -3.73%  emacs-27.0.50         [.] find_newline
      3.54%           libc-2.23.so          [.] __memmove_avx_unaligned
      1.25%   -1.19%  emacs-27.0.50         [.] region_cache_forward
      0.46%   -0.41%  [kernel.kallsyms]     [k] 0xffffffff83004eb0
      0.26%   -0.26%  emacs-27.0.50         [.] 
revalidate_region_cache.isra.1
      0.25%   -0.23%  emacs-27.0.50         [.] find_interval
      0.23%   -0.23%  emacs-27.0.50         [.] swap_in_symval_forwarding
      0.19%   -0.18%  emacs-27.0.50         [.] do_symval_forwarding
      0.16%   -0.15%  emacs-27.0.50         [.] eval_sub
      0.16%   -0.15%  emacs-27.0.50         [.] x_produce_glyphs
      0.13%           libXft.so.2.3.2       [.] XftCharIndex
      0.13%   -0.12%  libXft.so.2.3.2       [.] XftGlyphExtents
      0.12%   -0.12%  emacs-27.0.50         [.] store_symval_forwarding
      0.12%   -0.11%  emacs-27.0.50         [.] exec_byte_code
      0.09%           emacs-27.0.50         [.] Fsymbol_value
      0.08%   -0.08%  emacs-27.0.50         [.] x_get_glyph_overhangs
      0.07%           emacs-27.0.50         [.] find_symbol_value
      0.07%           libc-2.23.so          [.] __memcpy_avx_unaligned
      0.07%           emacs-27.0.50         [.] Fassq
      0.07%           emacs-27.0.50         [.] insert_1_both.part.9
      0.06%           emacs-27.0.50         [.] offset_intervals
      0.06%           libc-2.23.so          [.] __memcmp_sse4_1
      0.06%           emacs-27.0.50         [.] next_element_from_buffer
      0.05%   -0.05%  emacs-27.0.50         [.] move_it_in_display_line_to
      0.05%   -0.04%  emacs-27.0.50         [.] get_next_display_element
      0.05%   -0.04%  libXft.so.2.3.2       [.] XftFontCheckGlyph
      0.05%   -0.04%  libX11.so.6.3.0       [.] _XSetClipRectangles
      0.04%           libc-2.23.so          [.] __GI___printf_fp_l
      0.04%           emacs-27.0.50         [.] styled_format
      0.04%   -0.03%  emacs-27.0.50         [.] xftfont_text_extents
      0.04%   -0.03%  emacs-27.0.50         [.] draw_glyphs
      0.04%           emacs-27.0.50         [.] display_line
      0.04%           emacs-27.0.50         [.] validate_interval_range
      0.04%           emacs-27.0.50         [.] update_window_fringes
      0.04%           libX11.so.6.3.0       [.] 0x000000000001b65a
      0.04%   -0.03%  emacs-27.0.50         [.] lookup_char_property
      0.04%           emacs-27.0.50         [.] balance_an_interval
      0.03%           emacs-27.0.50         [.] composition_compute_stop_pos
      0.03%           libpthread-2.23.so    [.] pthread_mutex_unlock
      0.03%   -0.03%  emacs-27.0.50         [.] x_draw_glyph_string
      0.03%   -0.03%  emacs-27.0.50         [.] mem_insert
      0.03%   -0.03%  libpthread-2.23.so    [.] pthread_mutex_lock
      0.03%           libc-2.23.so          [.] malloc
      0.03%           emacs-27.0.50         [.] update_window_line
      0.03%           emacs-27.0.50         [.] Ffuncall
      0.03%   -0.03%  emacs-27.0.50         [.] get_glyph_face_and_encoding
      0.03%   -0.02%  emacs-27.0.50         [.] set_internal
      0.03%   -0.02%  emacs-27.0.50         [.] update_window
      0.03%           libXft.so.2.3.2       [.] XftDrawSrcPicture
      0.03%           libc-2.23.so          [.] vfprintf
      0.03%   -0.02%  emacs-27.0.50         [.] do_one_unbind.constprop.20
      0.03%           emacs-27.0.50         [.] set_iterator_to_next
      0.02%           emacs-27.0.50         [.] specbind
      0.02%           libc-2.23.so          [.] __memset_avx2
      0.02%   -0.02%  libX11.so.6.3.0       [.] _XFlushGCCache
      0.02%           emacs-27.0.50         [.] 
lookup_glyphless_char_display
      0.02%           libc-2.23.so          [.] _int_malloc
      0.02%           emacs-27.0.50         [.] set_cursor_from_row.isra.40
      0.02%   -0.02%  emacs-27.0.50         [.] message_dolog.part.60
      0.02%           emacs-27.0.50         [.] gap_left
      0.02%   -0.02%  emacs-27.0.50         [.] unbind_to
      0.02%   -0.02%  emacs-27.0.50         [.] init_iterator
      0.02%           emacs-27.0.50         [.] Fget_buffer
      0.02%   -0.01%  emacs-27.0.50         [.] overlays_at
      0.02%   -0.01%  [wl]                  [k] osl_readl
      0.02%   -0.01%  emacs-27.0.50         [.] set_point_both
      0.02%           emacs-27.0.50         [.] message3_nolog
      0.02%           libX11.so.6.3.0       [.] _XGetRequest
      0.02%           libc-2.23.so          [.] __sprintf_chk
      0.02%           emacs-27.0.50         [.] adjust_markers_for_insert
      0.02%           emacs-27.0.50         [.] adjust_suspend_auto_hscroll
      0.02%           emacs-27.0.50         [.] 
get_char_property_and_overlay
      0.01%           emacs-27.0.50         [.] window_box_width
      0.01%           emacs-27.0.50         [.] Fcons
      0.01%           libxcb.so.1.1.0       [.] 0x0000000000009cca
      0.01%   -0.01%  emacs-27.0.50         [.] arith_driver
      0.01%   -0.01%  emacs-27.0.50         [.] resize_mini_window
      0.01%           emacs-27.0.50         [.] unchain_marker
      0.01%           emacs-27.0.50         [.] face_for_char
      0.01%           emacs-27.0.50         [.] unblock_input_to
      0.01%           emacs-27.0.50         [.] unblock_input
      0.01%           emacs-27.0.50         [.] 
balance_possible_root_interval
      0.01%           emacs-27.0.50         [.] add_text_properties_1
      0.01%           emacs-27.0.50         [.] save_restriction_restore
      0.01%           emacs-27.0.50         [.] funcall_subr
      0.01%           emacs-27.0.50         [.] gap_right
      0.01%   -0.01%  emacs-27.0.50         [.] Fcurrent_buffer
      0.01%           libXrender.so.1.3.0   [.] XRenderFillRectangle
      0.01%           libXext.so.6.4.0      [.] XdbeSwapBuffers
      0.01%           emacs-27.0.50         [.] 
get_glyph_string_clip_rects.part.72
      0.01%           emacs-27.0.50         [.] Fwhile
      0.01%           emacs-27.0.50         [.] window_wants_mode_line
      0.01%           emacs-27.0.50         [.] display_echo_area_1
      0.01%           libXft.so.2.3.2       [.] XftDrawSetClipRectangles
      0.01%           emacs-27.0.50         [.] append_space_for_newline
      0.01%           emacs-27.0.50         [.] x_update_end
      0.01%           emacs-27.0.50         [.] Fforward_line
      0.01%           emacs-27.0.50         [.] memrchr@plt
      0.01%           emacs-27.0.50         [.] make_uninit_multibyte_string
      0.01%           emacs-27.0.50         [.] prepare_to_modify_buffer_1
      0.01%           emacs-27.0.50         [.] Fstring_equal
      0.01%           emacs-27.0.50         [.] init_glyph_string
      0.01%           libc-2.23.so          [.] _IO_old_init
      0.01%           libXrender.so.1.3.0   [.] XRenderFindDisplay
      0.01%           emacs-27.0.50         [.] Fnreverse
      0.01%           emacs-27.0.50         [.] arithcompare
      0.01%           emacs-27.0.50         [.] font_get_frame_data
      0.01%           emacs-27.0.50         [.] window_box_left
      0.01%           libX11.so.6.3.0       [.] XSetClipRectangles
      0.01%   -0.01%  emacs-27.0.50         [.] Flength
      0.01%           emacs-27.0.50         [.] previous_interval
      0.01%           libXft.so.2.3.2       [.] 0x0000000000007294
      0.01%           emacs-27.0.50         [.] 
x_compute_glyph_string_overhangs
      0.01%           emacs-27.0.50         [.] XftCharIndex@plt
      0.01%           libXrender.so.1.3.0   [.] XRenderCompositeString16
      0.01%           emacs-27.0.50         [.] message3
      0.01%           emacs-27.0.50         [.] xftfont_encode_char
      0.01%           emacs-27.0.50         [.] assign_row
      0.01%           emacs-27.0.50         [.] prepare_desired_row
      0.01%           emacs-27.0.50         [.] xftfont_draw
      0.01%           libXext.so.6.4.0      [.] XextFindDisplay
      0.01%           libpthread-2.23.so    [.] 
pthread_cond_broadcast@@GLIBC_2.3.2
      0.01%           libXft.so.2.3.2       [.] XftDrawGlyphs
      0.01%           emacs-27.0.50         [.] marker_position
      0.01%           emacs-27.0.50         [.] funcall_lambda
      0.01%           emacs-27.0.50         [.] gettime
      0.01%           libpthread-2.23.so    [.] __GI___libc_recvmsg
      0.01%           emacs-27.0.50         [.] lisp_time_struct
      0.01%           emacs-27.0.50         [.] echo_area_display
      0.01%           emacs-27.0.50         [.] CHECK_MARKER
      0.01%           emacs-27.0.50         [.] del_range_2
      0.01%           emacs-27.0.50         [.] prepare_face_for_display
      0.01%           emacs-27.0.50         [.] interval_deletion_adjustment
      0.01%           libc-2.23.so          [.] strlen
      0.01%           emacs-27.0.50         [.] verify_interval_modification
      0.01%           emacs-27.0.50         [.] count_size_as_multibyte
      0.01%           emacs-27.0.50         [.] adjust_overlays_for_insert
      0.01%           libXrender.so.1.3.0   [.] 
XRenderSetPictureClipRectangles
      0.01%           emacs-27.0.50         [.] buffer_local_value
      0.01%           emacs-27.0.50         [.] adjust_window_count
      0.01%           emacs-27.0.50         [.] 
notice_overwritten_cursor.part.52
      0.01%           libc-2.23.so          [.] __GI___writev
      0.01%           emacs-27.0.50         [.] record_in_backtrace
      0.01%           emacs-27.0.50         [.] save_restriction_save
      0.01%           emacs-27.0.50         [.] Fget_text_property
      0.01%   -0.00%  [vdso]                [.] __vdso_clock_gettime
      0.01%           emacs-27.0.50         [.] window_wants_header_line
      0.01%           emacs-27.0.50         [.] Fmessage
      0.01%           emacs-27.0.50         [.] FUNCTIONP
      0.01%           emacs-27.0.50         [.] window_display_table
      0.01%           emacs-27.0.50         [.] maybe_quit
      0.01%           emacs-27.0.50         [.] clear_glyph_matrix
      0.01%   -0.00%  emacs-27.0.50         [.] with_echo_area_buffer
      0.01%           libc-2.23.so          [.] __libc_enable_asynccancel
      0.01%           emacs-27.0.50         [.] should_produce_line_number
      0.01%           emacs-27.0.50         [.] x_set_glyph_string_clipping
      0.01%           emacs-27.0.50         [.] set_message_1
      0.01%           emacs-27.0.50         [.] del_range_both
      0.01%           emacs-27.0.50         [.] record_insert
      0.01%           emacs-27.0.50         [.] adjust_overlays_for_delete
      0.01%   +0.00%  libc-2.23.so          [.] _int_free
      0.01%           libc-2.23.so          [.] __strchrnul
      0.01%           emacs-27.0.50         [.] Fgoto_char
      0.01%           emacs-27.0.50         [.] free_misc
      0.01%           emacs-27.0.50         [.] draw_window_fringes
      0.01%           emacs-27.0.50         [.] x_flush.isra.37.part.38
      0.01%           libpthread-2.23.so    [.] __errno_location
      0.01%           emacs-27.0.50         [.] make_float
      0.01%           emacs-27.0.50         [.] fill_glyph_string
      0.01%           emacs-27.0.50         [.] Fget
      0.01%           emacs-27.0.50         [.] Flocal_variable_p
      0.01%           emacs-27.0.50         [.] decode_time_components
      0.01%           emacs-27.0.50         [.] XftGlyphExtents@plt
      0.01%           emacs-27.0.50         [.] row_for_charpos_p
      0.01%           emacs-27.0.50         [.] load_overlay_strings
      0.01%           emacs-27.0.50         [.] allocate_misc
      0.01%   -0.00%  libX11.so.6.3.0       [.] _XSend
      0.01%           libX11.so.6.3.0       [.] _XData32
      0.01%   -0.00%  emacs-27.0.50         [.] buf_bytepos_to_charpos
      0.01%           emacs-27.0.50         [.] face_at_buffer_position
      0.01%           emacs-27.0.50         [.] invalidate_current_column
      0.01%           emacs-27.0.50         [.] find_composition
      0.01%           emacs-27.0.50         [.] x_draw_window_cursor
      0.01%           emacs-27.0.50         [.] x_flip_and_flush
      0.01%           libc-2.23.so          [.] _IO_no_init
      0.01%           emacs-27.0.50         [.] Ftime_subtract
      0.01%           emacs-27.0.50         [.] row_hash
      0.01%           emacs-27.0.50         [.] lookup_basic_face
      0.01%           emacs-27.0.50         [.] memcpy@plt
      0.01%           emacs-27.0.50         [.] Fset_buffer
      0.01%           emacs-27.0.50         [.] produce_special_glyphs
      0.00%           emacs-27.0.50         [.] 
x_draw_glyph_string_background.part.44
      0.00%           [vdso]                [.] 0x0000000000000939
      0.00%           emacs-27.0.50         [.] make_save_obj_obj_obj_obj
      0.00%           libc-2.23.so          [.] __GI___libc_poll
      0.00%           emacs-27.0.50         [.] do_specbind
      0.00%           libXft.so.2.3.2       [.] XftGlyphRender
      0.00%           emacs-27.0.50         [.] move_it_to
      0.00%           emacs-27.0.50         [.] make_current.isra.14
      0.00%           emacs-27.0.50         [.] Fnext_single_property_change
      0.00%           emacs-27.0.50         [.] handle_face_prop
      0.00%           libX11.so.6.3.0       [.] _XFlush
      0.00%           emacs-27.0.50         [.] unwind_with_echo_area_buffer
      0.00%           emacs-27.0.50         [.] evaporate_overlays
      0.00%           emacs-27.0.50         [.] sort_overlays
      0.00%           emacs-27.0.50         [.] del_range_1
      0.00%           libX11.so.6.3.0       [.] XFlush
      0.00%           emacs-27.0.50         [.] try_window
      0.00%           emacs-27.0.50         [.] x_set_glyph_string_gc
      0.00%           libc-2.23.so          [.] malloc_consolidate
      0.00%           emacs-27.0.50         [.] handle_stop
      0.00%           emacs-27.0.50         [.] recenter_overlay_lists
      0.00%           libX11.so.6.3.0       [.] pthread_mutex_lock@plt
      0.00%           emacs-27.0.50         [.] modify_text_properties
      0.00%           emacs-27.0.50         [.] delete_interval
      0.00%           emacs-27.0.50         [.] window_text_bottom_y
      0.00%   +0.00%  emacs-27.0.50         [.] copy_text
      0.00%           emacs-27.0.50         [.] set_default_internal
      0.00%   +0.00%  libxcb.so.1.1.0       [.] xcb_writev
      0.00%           emacs-27.0.50         [.] temp_set_point_both
      0.00%           emacs-27.0.50         [.] insert_1_both
      0.00%           emacs-27.0.50         [.] record_property_change
      0.00%           emacs-27.0.50         [.] lisp_align_malloc
      0.00%           emacs-27.0.50         [.] x_mark_frame_dirty
      0.00%   +0.00%  emacs-27.0.50         [.] text_quoting_style
      0.00%           libc-2.23.so          [.] __GI___mempcpy
      0.00%           emacs-27.0.50         [.] Ffloat_time
      0.00%           emacs-27.0.50         [.] x_write_glyphs
      0.00%   +0.00%  emacs-27.0.50         [.] insert_from_string_1
      0.00%           emacs-27.0.50         [.] Fpoint
      0.00%           libc-2.23.so          [.] __vsprintf_chk
      0.00%           libc-2.23.so          [.] hack_digit
      0.00%           emacs-27.0.50         [.] grow_specpdl
      0.00%           emacs-27.0.50         [.] time_arith
      0.00%           emacs-27.0.50         [.] update_end
      0.00%           emacs-27.0.50         [.] allocate_string_data
      0.00%           emacs-27.0.50         [.] save_excursion_restore
      0.00%   +0.00%  emacs-27.0.50         [.] Flet
      0.00%           emacs-27.0.50         [.] mem_rotate_right
      0.00%           emacs-27.0.50         [.] fetch_buffer_markers
      0.00%           emacs-27.0.50         [.] move_gap_both
      0.00%           emacs-27.0.50         [.] xmalloc
      0.00%           emacs-27.0.50         [.] update_begin
      0.00%           emacs-27.0.50         [.] float_arith_driver
      0.00%           emacs-27.0.50         [.] make_specified_string
      0.00%           emacs-27.0.50         [.] handle_composition_prop
      0.00%           emacs-27.0.50         [.] display_and_set_cursor
      0.00%           emacs-27.0.50         [.] compute_line_metrics
      0.00%           emacs-27.0.50         [.] clock_gettime@plt
      0.00%           libc-2.23.so          [.] free
      0.00%           emacs-27.0.50         [.] Fplist_get
      0.00%           libgdk-3.so.0.1800.9  [.] gdk_display_manager_get
      0.00%           emacs-27.0.50         [.] make_interval
      0.00%           libxcb.so.1.1.0       [.] xcb_poll_for_event
      0.00%           emacs-27.0.50         [.] adjust_markers_for_delete
      0.00%           emacs-27.0.50         [.] do_pending_window_change
      0.00%           emacs-27.0.50         [.] XftDrawGlyphs@plt
      0.00%           libc-2.23.so          [.] _itoa_word
      0.00%           emacs-27.0.50         [.] disassemble_lisp_time
      0.00%           emacs-27.0.50         [.] Ftext_properties_at
      0.00%           emacs-27.0.50         [.] composition_reseat_it
      0.00%           libX11.so.6.3.0       [.] _XEventsQueued
      0.00%           emacs-27.0.50         [.] minmax_driver
      0.00%           emacs-27.0.50         [.] set_marker_restricted_both
      0.00%           emacs-27.0.50         [.] graft_intervals_into_buffer
      0.00%           emacs-27.0.50         [.] disp_char_vector
      0.00%           libc-2.23.so          [.] __clock_gettime
      0.00%           emacs-27.0.50         [.] CHECK_STRING_OR_BUFFER
      0.00%           emacs-27.0.50         [.] intervals_equal
      0.00%           emacs-27.0.50         [.] ensure_echo_area_buffers
      0.00%           emacs-27.0.50         [.] invalidate_buffer_caches
      0.00%           emacs-27.0.50         [.] set_marker_both
      0.00%   +0.00%  emacs-27.0.50         [.] record_unwind_protect
      0.00%           emacs-27.0.50         [.] run_hook_with_args
      0.00%           emacs-27.0.50         [.] set_point_from_marker
      0.00%           emacs-27.0.50         [.] list4
      0.00%           libX11.so.6.3.0       [.] XSetClipMask
      0.00%           emacs-27.0.50         [.] record_buffer_markers
      0.00%           emacs-27.0.50         [.] default_value
              +0.00%  libXext.so.6.4.0      [.] 0x000000000000bf10
              +0.00%  emacs-27.0.50         [.] Fsetq
              +0.00%  emacs-27.0.50         [.] reseat_1
              +0.00%  emacs-27.0.50         [.] update_compositions

this is what perf annotate shows when invoked on buf_charpos_to_bytepos 
(slow case):

        │     ↓ jle    438 
                ▒
   4,39 │       mov    0x20(%rax),%r8 
                ▒
   8,38 │       mov    %rdx,%rbp 
                ▒
   0,05 │2f0:   mov    %rbp,%rdx 
                ▒
   0,13 │       mov    %r8,%rdi 
                ▒
   2,70 │       sub    %r13,%rdx 
                ▒
   2,22 │       sub    %rbx,%rdi 
                ▒
   0,05 │       cmp    %rdi,%rdx 
                ▒
        │     ↑ je     1e9 
                ▒
        │ 
                ▒
        │           /* If we are down to a range of 50 chars, 
                ▒
        │              don't bother checking any other markers; 
                ▒
        │              scan the intervening chars directly now.  */ 
                ▒
        │           if (best_above - best_below < 50) 
                ▒
   3,21 │305:   cmp    $0x31,%rdx 
                ▒
        │     ↓ jle    480 
                ▒
        │       CONSIDER (BUF_ZV (b), BUF_ZV_BYTE (b)); 
                ▒
        │ 
                ▒
        │       if (b == cached_buffer && BUF_MODIFF (b) == 
cached_modiff)              ▒
        │         CONSIDER (cached_charpos, cached_bytepos); 
                ▒
        │ 
                ▒
        │       for (tail = BUF_MARKERS (b); tail; tail = tail->next) 
                ▒
   2,50 │       mov    0x10(%rax),%rax 
                ▒
   4,25 │       test   %rax,%rax 
                ▒
        │     ↓ je     480 
                ▒
        │         { 
                ◆
        │           CONSIDER (tail->charpos, tail->bytepos); 
                ▒
   2,64 │31c:   mov    0x18(%rax),%rdx 
                ▒
  59,16 │       cmp    %rdx,%rsi 
                ▒
        │     ↓ je     638 
                ▒
   5,70 │       cmp    %rdx,%rsi 
                ▒
        │     ↑ jl     2e0 
                ▒
   0,00 │       cmp    %rdx,%r13 
                ▒
        │     ↓ jge    438 
                ▒
   0,00 │       mov    0x20(%rax),%rbx 
                ▒
   0,01 │       mov    %rdx,%r13 
                ▒
        │     ↑ jmp    2f0 
                ▒
        │     marker_byte_position(): 
                ▒
        │       if (!buf) 
                ▒
        │         error ("Marker does not point anywhere"); 
                ▒
        │ 
                ▒
        │       eassert (BUF_BEG_BYTE (buf) <= m->bytepos && m->bytepos 
<= BUF_Z_BYTE (b▒
        │ 
                ▒
        │       return m->bytepos; 
                ▒
        │340:   mov    0x20(%rdi),%rbx 
                ▒
        │     ↑ jmpq   cb 
                ▒
        │       nop 
                ▒
        │     buf_charpos_to_bytepos(): 
                ▒
        │ 
                ▒
        │          If at any point we can tell that the space between 
those             ▒
        │          two best approximations is all single-byte, 
                ▒
        │          we interpolate the result immediately.  */ 
                ▒
        │ 
                ▒
        │       CONSIDER (BUF_PT (b), BUF_PT_BYTE (b)); 
                ▒
        │350:   mov    0x2f0(%rdi),%r13 
                ▒
        │       cmp    %rsi,%r13 
                ▒

to my eyes, the fast case doesn't look too different though:

        │     ↓ jle    438
   0,83 │       mov    0x20(%rax),%r8
   0,93 │       mov    %rdx,%rbp
        │2f0:   mov    %rbp,%rdx
   0,06 │       mov    %r8,%rdi
   0,20 │       sub    %r13,%rdx
   0,11 │       sub    %rbx,%rdi
   0,12 │       cmp    %rdi,%rdx
        │     ↑ je     1e9
        │
        │           /* If we are down to a range of 50 chars,
        │              don't bother checking any other markers;
        │              scan the intervening chars directly now.  */
        │           if (best_above - best_below < 50)
  11,24 │305:   cmp    $0x31,%rdx
        │     ↓ jle    480
        │       CONSIDER (BUF_ZV (b), BUF_ZV_BYTE (b));
        │
        │       if (b == cached_buffer && BUF_MODIFF (b) == cached_modiff)
        │         CONSIDER (cached_charpos, cached_bytepos);
        │
        │       for (tail = BUF_MARKERS (b); tail; tail = tail->next)
   0,16 │       mov    0x10(%rax),%rax
  10,41 │       test   %rax,%rax
        │     ↓ je     480
        │         {
        │           CONSIDER (tail->charpos, tail->bytepos);
   3,19 │31c:   mov    0x18(%rax),%rdx
  42,86 │       cmp    %rdx,%rsi
        │     ↓ je     638
  10,36 │       cmp    %rdx,%rsi
        │     ↑ jl     2e0
   2,24 │       cmp    %rdx,%r13
        │     ↓ jge    438
   0,76 │       mov    0x20(%rax),%rbx
   0,43 │       mov    %rdx,%r13
        │     ↑ jmp    2f0
        │     marker_byte_position():
        │       if (!buf)
        │         error ("Marker does not point anywhere");
        │
        │       eassert (BUF_BEG_BYTE (buf) <= m->bytepos && m->bytepos 
<= BUF_Z_BYTE (bu
        │
        │       return m->bytepos;
        │340:   mov    0x20(%rdi),%rbx
        │     ↑ jmpq   cb
        │       nop
        │     buf_charpos_to_bytepos():
        │
        │          If at any point we can tell that the space between those
        │          two best approximations is all single-byte,
        │          we interpolate the result immediately.  */
        │
        │       CONSIDER (BUF_PT (b), BUF_PT_BYTE (b));
        │350:   mov    0x2f0(%rdi),%r13
        │       cmp    %rsi,%r13

I hope this is of some use, but I'll keep looking for open source files 
to reproduce the issue

Re: State of the overlay tree branch?

[Eli Zaretskii]

> From: Sebastian Sturm <s.sturm@arkona-technologies.de>
> Date: Wed, 21 Mar 2018 01:36:38 +0100
> 
> this is the profiler report I get for the slow case (BTW, is there a way 
> to have the profiler resolve functions within line-number-at-pos?

Yes: load simple.el manually before running the benchmark.

> with perf, the ("self") time taken by buf_charpos_to_bytepos increases 
> from ~60% (fast case) to >98%. This is the diff generated by perf diff 
> <fast.perf> <slow.perf>:
> 
> # Event 'cycles'
> #
> # Baseline    Delta  Shared Object         Symbol 
> 
> # ........  .......  .................... 
> ..........................................
> #
>      57.77%  +40.30%  emacs-27.0.50         [.] buf_charpos_to_bytepos

This seems to confirm Stefan's guess that converting character
positions to byte positions takes most of the time, which might make
sense with a lot of overlays (because each overlay uses 2 markers).

Does your code call line-number-at-pos at random positions in the
buffer, or are the positions close to one another?  If the latter, you
might be better off calling count-lines directly, starting at the line
where you previously calculated the line number, instead of calling
line-number-at-pos, which always begins at point-min.

Re: State of the overlay tree branch?

[Stefan Monnier]

> this is the profiler report I get for the slow case (BTW, is there a way to
> have the profiler resolve functions within line-number-at-pos?

It should do that without you asking.  I mean, it won't show you
`goto-char` and `point-min` kind of things since these are "inlined"
(actually turned into their own byte-code), but `count-lines` should
definitely be there.

>              - let                                              18368  86%
>                 line-number-at-pos                              18348  86%

It's very odd that there's no `count-lines` down here (and `count-lines`
is a perfectly normal Elisp function that's not inlined or otherwise
treated specially), since it should be where most of the time is spent!

If we assume the code works as intended, it would imply that the time is
not spent in `count-lines` but elsewhere, e.g. in `goto-char`.

> with perf, the ("self") time taken by buf_charpos_to_bytepos increases from
> ~60% (fast case) to >98%. This is the diff generated by perf diff
> <fast.perf> <slow.perf>:

So I guess that could be it: the (goto-char opoint) spends an inordinate
amount of time in buf_charpos_to_bytepos.

Could you try the patch below, to see if it makes a difference?


        Stefan


diff --git a/src/marker.c b/src/marker.c
index 7773c4fce0..3d808fd6fa 100644
--- a/src/marker.c
+++ b/src/marker.c
@@ -141,6 +141,7 @@ buf_charpos_to_bytepos (struct buffer *b, ptrdiff_t charpos)
   struct Lisp_Marker *tail;
   ptrdiff_t best_above, best_above_byte;
   ptrdiff_t best_below, best_below_byte;
+  ptrdiff_t distance = 50;
 
   eassert (BUF_BEG (b) <= charpos && charpos <= BUF_Z (b));
 
@@ -180,8 +181,10 @@ buf_charpos_to_bytepos (struct buffer *b, ptrdiff_t charpos)
       /* If we are down to a range of 50 chars,
 	 don't bother checking any other markers;
 	 scan the intervening chars directly now.  */
-      if (best_above - best_below < 50)
+      if (best_above - best_below < distance)
 	break;
+      else
+        distance = distance + 10;
     }
 
   /* We get here if we did not exactly hit one of the known places.

Re: State of the overlay tree branch?

[Sebastian Sturm]

 >
 > It should do that without you asking.  I mean, it won't show you
 > `goto-char` and `point-min` kind of things since these are "inlined"
 > (actually turned into their own byte-code), but `count-lines` should
 > definitely be there.
 >
 >>               - let 
18368  86%
 >>                  line-number-at-pos 
18348  86%
 >
 > It's very odd that there's no `count-lines` down here (and `count-lines`
 > is a perfectly normal Elisp function that's not inlined or otherwise
 > treated specially), since it should be where most of the time is spent!

when first evaluating simple.el as Eli suggested, the profiler indeed 
shows that pretty much all time is spent somewhere within `count-lines`. 
Unfortunately the patch didn't seem to help though I'll double-check at 
home (also, it seemed to improve baseline performance, but I'm not sure 
if I should regard that as a random fluctuation, will need to do more 
measurements).
Also, this time even the first measurement with a small number of 
overlays was extremely slow, not sure what to make of that.

In general however, the trend seems clear to me --- for this one file, 
overlays hurt `line-number-at-pos` performance very much, except when 
using the noverlay branch.
Are there other things I should look for in my file that might 
negatively affect performance (strange codepoints or anything else that 
might perhaps upset `buf_charpos_to_bytepos`)?

baseline (emacs-27 master #667cdf42..., approx. 5-10 overlays created by 
flycheck):
iteration 1: 0.012696
iteration 2: 0.002595
iteration 3: 0.002606
iteration 4: 0.002601
iteration 5: 0.002649
iteration 6: 0.002605
iteration 7: 0.002594
iteration 8: 0.002601
iteration 9: 0.002603
iteration 10: 0.002601
iteration 11: 0.002606
iteration 12: 0.002626
iteration 13: 0.002603
iteration 14: 0.002642
iteration 15: 0.002599
iteration 16: 0.002598
iteration 17: 0.002600
iteration 18: 0.002601
iteration 19: 0.002599
iteration 20: 0.002608

emacs-27 master, approx. 6200 overlays created by (test-highlight)
iteration 1: 0.022795
iteration 2: 0.015560
iteration 3: 0.015697
iteration 4: 0.015913
iteration 5: 0.015894
iteration 6: 0.016063
iteration 7: 0.015928
iteration 8: 0.015890
iteration 9: 0.015278
iteration 10: 0.015515
iteration 11: 0.015327
iteration 12: 0.015326
iteration 13: 0.015574
iteration 14: 0.015319
iteration 15: 0.015370
iteration 16: 0.015354
iteration 17: 0.015333
iteration 18: 0.015312
iteration 19: 0.015481
iteration 20: 0.015411

emacs-27 master + patch "distance+10", ~10 overlays created by flycheck:
iteration 1: 0.002938
iteration 2: 0.001132
iteration 3: 0.000550
iteration 4: 0.000468
iteration 5: 0.000470
iteration 6: 0.000451
iteration 7: 0.000449
iteration 8: 0.000451
iteration 9: 0.000450
iteration 10: 0.000449
iteration 11: 0.000448
iteration 12: 0.000452
iteration 13: 0.000451
iteration 14: 0.000443
iteration 15: 0.000448
iteration 16: 0.000443
iteration 17: 0.000444
iteration 18: 0.000445
iteration 19: 0.000445
iteration 20: 0.000445

emacs-27 master + patch "distance+10", ~6200 overlays created by 
(test-highlight):
iteration 1: 0.019673
iteration 2: 0.014469
iteration 3: 0.014491
iteration 4: 0.014430
iteration 5: 0.014493
iteration 6: 0.014704
iteration 7: 0.014741
iteration 8: 0.014536
iteration 9: 0.014433
iteration 10: 0.014469
iteration 11: 0.014429
iteration 12: 0.014509
iteration 13: 0.014484
iteration 14: 0.014487
iteration 15: 0.014524
iteration 16: 0.014449
iteration 17: 0.014501
iteration 18: 0.014469
iteration 19: 0.014429
iteration 20: 0.014507

noverlay branch (#886933...), ~10 overlays:
iteration 1: 0.002370
iteration 2: 0.001191
iteration 3: 0.001189
iteration 4: 0.001162
iteration 5: 0.001095
iteration 6: 0.001096
iteration 7: 0.000522
iteration 8: 0.000531
iteration 9: 0.000369
iteration 10: 0.000365
iteration 11: 0.000365
iteration 12: 0.000366
iteration 13: 0.000365
iteration 14: 0.000380
iteration 15: 0.000367
iteration 16: 0.000365
iteration 17: 0.000365
iteration 18: 0.000365
iteration 19: 0.000363
iteration 20: 0.000368

noverlay branch, ~6200 overlays:
iteration 1: 0.001878
iteration 2: 0.001831
iteration 3: 0.001838
iteration 4: 0.001826
iteration 5: 0.001027
iteration 6: 0.000722
iteration 7: 0.000531
iteration 8: 0.000479
iteration 9: 0.000480
iteration 10: 0.000479
iteration 11: 0.000479
iteration 12: 0.000479
iteration 13: 0.000478
iteration 14: 0.000479
iteration 15: 0.000478
iteration 16: 0.000478
iteration 17: 0.000482
iteration 18: 0.000479
iteration 19: 0.000480
iteration 20: 0.000476

Re: State of the overlay tree branch?

[Sebastian Sturm]

for the record, this is what I get with the (non-noverlay, non-patched) 
emacs-27 master branch after calling `(set-buffer-multibyte nil)`. Guess 
this merely confirms what you already found out, but for me this is a 
viable workaround until the issue is properly resolved. Will keep 
looking for an open source test file over the weekend

emacs-27 master, ~6200 overlays, enable-multibyte-characters = nil:
iteration 1: 0.000300
iteration 2: 0.000268
iteration 3: 0.000267
iteration 4: 0.000268
iteration 5: 0.000267
iteration 6: 0.000266
iteration 7: 0.000263
iteration 8: 0.000263
iteration 9: 0.000277
iteration 10: 0.000269
iteration 11: 0.000264
iteration 12: 0.000266
iteration 13: 0.000263
iteration 14: 0.000265
iteration 15: 0.000273
iteration 16: 0.000267
iteration 17: 0.000266
iteration 18: 0.000266
iteration 19: 0.000265
iteration 20: 0.000263


On 03/22/2018 08:54 PM, Sebastian Sturm wrote:
>  >
>  > It should do that without you asking.  I mean, it won't show you
>  > `goto-char` and `point-min` kind of things since these are "inlined"
>  > (actually turned into their own byte-code), but `count-lines` should
>  > definitely be there.
>  >
>  >>               - let 18368  86%
>  >>                  line-number-at-pos 18348  86%
>  >
>  > It's very odd that there's no `count-lines` down here (and `count-lines`
>  > is a perfectly normal Elisp function that's not inlined or otherwise
>  > treated specially), since it should be where most of the time is spent!
> 
> when first evaluating simple.el as Eli suggested, the profiler indeed 
> shows that pretty much all time is spent somewhere within `count-lines`. 
> Unfortunately the patch didn't seem to help though I'll double-check at 
> home (also, it seemed to improve baseline performance, but I'm not sure 
> if I should regard that as a random fluctuation, will need to do more 
> measurements).
> Also, this time even the first measurement with a small number of 
> overlays was extremely slow, not sure what to make of that.
> 
> In general however, the trend seems clear to me --- for this one file, 
> overlays hurt `line-number-at-pos` performance very much, except when 
> using the noverlay branch.
> Are there other things I should look for in my file that might 
> negatively affect performance (strange codepoints or anything else that 
> might perhaps upset `buf_charpos_to_bytepos`)?
> 
> baseline (emacs-27 master #667cdf42..., approx. 5-10 overlays created by 
> flycheck):
> iteration 1: 0.012696
> iteration 2: 0.002595
> iteration 3: 0.002606
> iteration 4: 0.002601
> iteration 5: 0.002649
> iteration 6: 0.002605
> iteration 7: 0.002594
> iteration 8: 0.002601
> iteration 9: 0.002603
> iteration 10: 0.002601
> iteration 11: 0.002606
> iteration 12: 0.002626
> iteration 13: 0.002603
> iteration 14: 0.002642
> iteration 15: 0.002599
> iteration 16: 0.002598
> iteration 17: 0.002600
> iteration 18: 0.002601
> iteration 19: 0.002599
> iteration 20: 0.002608
> 
> emacs-27 master, approx. 6200 overlays created by (test-highlight)
> iteration 1: 0.022795
> iteration 2: 0.015560
> iteration 3: 0.015697
> iteration 4: 0.015913
> iteration 5: 0.015894
> iteration 6: 0.016063
> iteration 7: 0.015928
> iteration 8: 0.015890
> iteration 9: 0.015278
> iteration 10: 0.015515
> iteration 11: 0.015327
> iteration 12: 0.015326
> iteration 13: 0.015574
> iteration 14: 0.015319
> iteration 15: 0.015370
> iteration 16: 0.015354
> iteration 17: 0.015333
> iteration 18: 0.015312
> iteration 19: 0.015481
> iteration 20: 0.015411
> 
> emacs-27 master + patch "distance+10", ~10 overlays created by flycheck:
> iteration 1: 0.002938
> iteration 2: 0.001132
> iteration 3: 0.000550
> iteration 4: 0.000468
> iteration 5: 0.000470
> iteration 6: 0.000451
> iteration 7: 0.000449
> iteration 8: 0.000451
> iteration 9: 0.000450
> iteration 10: 0.000449
> iteration 11: 0.000448
> iteration 12: 0.000452
> iteration 13: 0.000451
> iteration 14: 0.000443
> iteration 15: 0.000448
> iteration 16: 0.000443
> iteration 17: 0.000444
> iteration 18: 0.000445
> iteration 19: 0.000445
> iteration 20: 0.000445
> 
> emacs-27 master + patch "distance+10", ~6200 overlays created by 
> (test-highlight):
> iteration 1: 0.019673
> iteration 2: 0.014469
> iteration 3: 0.014491
> iteration 4: 0.014430
> iteration 5: 0.014493
> iteration 6: 0.014704
> iteration 7: 0.014741
> iteration 8: 0.014536
> iteration 9: 0.014433
> iteration 10: 0.014469
> iteration 11: 0.014429
> iteration 12: 0.014509
> iteration 13: 0.014484
> iteration 14: 0.014487
> iteration 15: 0.014524
> iteration 16: 0.014449
> iteration 17: 0.014501
> iteration 18: 0.014469
> iteration 19: 0.014429
> iteration 20: 0.014507
> 
> noverlay branch (#886933...), ~10 overlays:
> iteration 1: 0.002370
> iteration 2: 0.001191
> iteration 3: 0.001189
> iteration 4: 0.001162
> iteration 5: 0.001095
> iteration 6: 0.001096
> iteration 7: 0.000522
> iteration 8: 0.000531
> iteration 9: 0.000369
> iteration 10: 0.000365
> iteration 11: 0.000365
> iteration 12: 0.000366
> iteration 13: 0.000365
> iteration 14: 0.000380
> iteration 15: 0.000367
> iteration 16: 0.000365
> iteration 17: 0.000365
> iteration 18: 0.000365
> iteration 19: 0.000363
> iteration 20: 0.000368
> 
> noverlay branch, ~6200 overlays:
> iteration 1: 0.001878
> iteration 2: 0.001831
> iteration 3: 0.001838
> iteration 4: 0.001826
> iteration 5: 0.001027
> iteration 6: 0.000722
> iteration 7: 0.000531
> iteration 8: 0.000479
> iteration 9: 0.000480
> iteration 10: 0.000479
> iteration 11: 0.000479
> iteration 12: 0.000479
> iteration 13: 0.000478
> iteration 14: 0.000479
> iteration 15: 0.000478
> iteration 16: 0.000478
> iteration 17: 0.000482
> iteration 18: 0.000479
> iteration 19: 0.000480
> iteration 20: 0.000476
> 

Re: State of the overlay tree branch?

[Stefan Monnier]

> (defun benchmark-often ()
>   (cl-loop for n from 1 upto 20 do
>            (message (format "iteration %d: %f" n (nth 0 (benchmark-run
> (line-number-at-pos (point))))))))
                      ^^^^^^^
Where is this "point" in your tests (I expect the timing to vary
significantly depending on this).

> 1st run:
> iteration 1: 0.001213
> iteration 2: 0.001170
> iteration 3: 0.001170
> iteration 4: 0.001238
> iteration 5: 0.001163
> iteration 6: 0.001153
> iteration 7: 0.000421
> iteration 8: 0.000426
> iteration 9: 0.000322
> iteration 10: 0.000301
> iteration 11: 0.000291
> iteration 12: 0.000292
> iteration 13: 0.000291
> iteration 14: 0.000291
> iteration 15: 0.000295
> iteration 16: 0.000289
> iteration 17: 0.000289
> iteration 18: 0.000288
> iteration 19: 0.000288
> iteration 20: 0.000287

I recommend you don't bother outputting all 20 results: better summarize
it by getting rid of the first test and then giving e.g. the sum or the
median of the rest.

> I'm not allowed to share my employer's source code as a test case, so
> I tried the same procedure with the similarly large DeclBase.h from the
> public LLVM repository. To my surprise, DeclBase.h didn't suffer from any
> performance issues at all.

My crystal ball tells me that DeclBase.h is pure ASCII so byte<->char
conversion is trivial, whereas your file likely contains umlauts and
other disreputable characters.

Here's a similar test case to yours but which builds up its own
artificial buffer with a few non-ascii chars to spice things up:

       (with-temp-buffer
         (dotimes (i 1000)
           (insert "lksajflahalskjdféefawrgfrüegf\n"))
         (let ((txtbuf (current-buffer)))
           (dotimes (s 4)
             (with-temp-buffer
               (insert-buffer-substring txtbuf)
               (let ((stepsize (lsh 10 (* 4 s))))
                 (cl-loop for n from (point-min) upto (- (point-max) stepsize)
                          by stepsize do
                          (let ((ov (make-overlay n (+ (1- stepsize) n))))
                            (overlay-put ov 'cquery-sem-highlight t))))
               (dotimes (i 4)
                 (let ((timing
                        (benchmark-run 1000
                          (line-number-at-pos
                           (+ (point-min) (* i (/ (buffer-size) 4)))))))
                   (message "ols=%S pos=%S/4 time=%.4f (+ %S)"
                            (/ (buffer-size) (lsh 10 (* 4 s))) i
                            (car timing) (cdr timing)))
                 )))))

This gave me (on my top-of-the-line Thinkpad T61 using Debian's `emacs25`):

    ols=3000 pos=0/4 time=0.0018 (+ (0 0.0))
    ols=3000 pos=1/4 time=6.1074 (+ (0 0.0))
    ols=3000 pos=2/4 time=10.6876 (+ (0 0.0))
    ols=3000 pos=3/4 time=13.7854 (+ (0 0.0))
    ols=187 pos=0/4 time=0.0016 (+ (0 0.0))
    ols=187 pos=1/4 time=0.3055 (+ (0 0.0))
    ols=187 pos=2/4 time=0.6001 (+ (0 0.0))
    ols=187 pos=3/4 time=0.8903 (+ (0 0.0))
    ols=11 pos=0/4 time=0.0015 (+ (0 0.0))
    ols=11 pos=1/4 time=0.0769 (+ (1 0.006324223))
    ols=11 pos=2/4 time=0.1439 (+ (0 0.0))
    ols=11 pos=3/4 time=0.2215 (+ (0 0.0))
    ols=0 pos=0/4 time=0.0015 (+ (0 0.0))
    ols=0 pos=1/4 time=0.0548 (+ (0 0.0))
    ols=0 pos=2/4 time=0.1102 (+ (0 0.0))
    ols=0 pos=3/4 time=0.1690 (+ (0 0.0))



        Stefan

Re: State of the overlay tree branch?

[Sebastian Sturm]

On 03/22/2018 09:52 PM, Stefan Monnier wrote:
>> (defun benchmark-often ()
>>    (cl-loop for n from 1 upto 20 do
>>             (message (format "iteration %d: %f" n (nth 0 (benchmark-run
>> (line-number-at-pos (point))))))))
>                        ^^^^^^^
> Where is this "point" in your tests (I expect the timing to vary
> significantly depending on this).

yes, these tests were all performed close to the very bottom of the file 
as I knew the issue to get worse towards the buffer end

> My crystal ball tells me that DeclBase.h is pure ASCII so byte<->char
> conversion is trivial, whereas your file likely contains umlauts and
> other disreputable characters.
> 
> Here's a similar test case to yours but which builds up its own
> artificial buffer with a few non-ascii chars to spice things up:

thank you! I'm very glad you could come up with a reproducible test 
case, and it's true that my file contains two instances of the greek 
letter "μ" that seem to cause this performance issue (though I was 
surprised to see that this few characters could have such a poisonous 
effect). Likewise, when replacing the topmost part in your benchmark 
function with the following:

(A)  (dotimes (i 1000)
        (insert "pure ascii pure ascii pure ascii\n"))

(B)  (dotimes (i 500)
        (insert "pure ascii pure ascii pure ascii\n"))
        (insert "μ")
      (dotimes (i 500)
        (insert "pure ascii pure ascii pure ascii\n"))

respectively, I obtain the following timing results:

(A)
ols=3300 pos=0/4 time=0.0014 (+ (0 0.0))
ols=3300 pos=1/4 time=0.0155 (+ (0 0.0))
ols=3300 pos=2/4 time=0.0281 (+ (0 0.0))
ols=3300 pos=3/4 time=0.0447 (+ (0 0.0))
ols=206 pos=0/4 time=0.0007 (+ (0 0.0))
ols=206 pos=1/4 time=0.0130 (+ (0 0.0))
ols=206 pos=2/4 time=0.0283 (+ (0 0.0))
ols=206 pos=3/4 time=0.0447 (+ (0 0.0))
ols=12 pos=0/4 time=0.0007 (+ (0 0.0))
ols=12 pos=1/4 time=0.0129 (+ (0 0.0))
ols=12 pos=2/4 time=0.0281 (+ (0 0.0))
ols=12 pos=3/4 time=0.0447 (+ (0 0.0))
ols=0 pos=0/4 time=0.0007 (+ (0 0.0))
ols=0 pos=1/4 time=0.0134 (+ (0 0.0))
ols=0 pos=2/4 time=0.0297 (+ (0 0.0))
ols=0 pos=3/4 time=0.0463 (+ (0 0.0))

(B)
ols=3300 pos=0/4 time=0.0007 (+ (0 0.0))
ols=3300 pos=1/4 time=0.0301 (+ (0 0.0))
ols=3300 pos=2/4 time=0.0482 (+ (0 0.0))
ols=3300 pos=3/4 time=8.0213 (+ (0 0.0))
ols=206 pos=0/4 time=0.0007 (+ (0 0.0))
ols=206 pos=1/4 time=0.0141 (+ (0 0.0))
ols=206 pos=2/4 time=0.0325 (+ (0 0.0))
ols=206 pos=3/4 time=0.1786 (+ (0 0.0))
ols=12 pos=0/4 time=0.0007 (+ (0 0.0))
ols=12 pos=1/4 time=0.0136 (+ (0 0.0))
ols=12 pos=2/4 time=0.0323 (+ (0 0.0))
ols=12 pos=3/4 time=0.0794 (+ (0 0.0))
ols=0 pos=0/4 time=0.0009 (+ (0 0.0))
ols=0 pos=1/4 time=0.0139 (+ (0 0.0))
ols=0 pos=2/4 time=0.0326 (+ (0 0.0))
ols=0 pos=3/4 time=0.0632 (+ (0 0.0))

by comparison, these are my results using the noverlay branch:

(A)
ols=3300 pos=0/4 time=0.0012 (+ (0 0.0))
ols=3300 pos=1/4 time=0.0132 (+ (0 0.0))
ols=3300 pos=2/4 time=0.0291 (+ (0 0.0))
ols=3300 pos=3/4 time=0.0448 (+ (0 0.0))
ols=206 pos=0/4 time=0.0007 (+ (0 0.0))
ols=206 pos=1/4 time=0.0132 (+ (0 0.0))
ols=206 pos=2/4 time=0.0290 (+ (0 0.0))
ols=206 pos=3/4 time=0.0454 (+ (0 0.0))
ols=12 pos=0/4 time=0.0008 (+ (0 0.0))
ols=12 pos=1/4 time=0.0131 (+ (0 0.0))
ols=12 pos=2/4 time=0.0287 (+ (0 0.0))
ols=12 pos=3/4 time=0.0452 (+ (0 0.0))
ols=0 pos=0/4 time=0.0007 (+ (0 0.0))
ols=0 pos=1/4 time=0.0131 (+ (0 0.0))
ols=0 pos=2/4 time=0.0289 (+ (0 0.0))
ols=0 pos=3/4 time=0.0457 (+ (0 0.0))

(B)
ols=3300 pos=0/4 time=0.0015 (+ (0 0.0))
ols=3300 pos=1/4 time=0.0177 (+ (0 0.0))
ols=3300 pos=2/4 time=0.0345 (+ (0 0.0))
ols=3300 pos=3/4 time=0.0544 (+ (0 0.0))
ols=206 pos=0/4 time=0.0008 (+ (0 0.0))
ols=206 pos=1/4 time=0.0136 (+ (0 0.0))
ols=206 pos=2/4 time=0.0317 (+ (0 0.0))
ols=206 pos=3/4 time=0.0537 (+ (0 0.0))
ols=12 pos=0/4 time=0.0007 (+ (0 0.0))
ols=12 pos=1/4 time=0.0135 (+ (0 0.0))
ols=12 pos=2/4 time=0.0319 (+ (0 0.0))
ols=12 pos=3/4 time=0.0537 (+ (0 0.0))
ols=0 pos=0/4 time=0.0007 (+ (0 0.0))
ols=0 pos=1/4 time=0.0146 (+ (0 0.0))
ols=0 pos=2/4 time=0.0318 (+ (0 0.0))
ols=0 pos=3/4 time=0.0554 (+ (0 0.0))

since noverlay performs so well, I guess the technical issue here is 
already solved and I'll just have to wait for it to make it into the 
master branch. Until then I'll continue using feature/noverlay, but if a 
more recent merge with master was made available, I'd be interested in 
testing that.
thanks again for all the helpful responses in this thread,
Sebastian

Re: State of the overlay tree branch?

[Stefan Monnier]

> since noverlay performs so well, I guess the technical issue here is already
> solved and I'll just have to wait for it to make it into the master
> branch.

Yes and no: there can still be many markers (even without having any
overlays) and that poses the same problem (and the noverlays branch
doesn't change that).

I've made some further tests and found that the patch I sent indeed
doesn't help tremendously with "distance += 10" but that when we reach
"+= 50" the effect is more significant.

Could you try the patch below (ideally not just with artificial tests
but also in actual use) to see if it helps?


        Stefan


diff --git a/src/marker.c b/src/marker.c
index 7773c4fce0..6ab0d3d61e 100644
--- a/src/marker.c
+++ b/src/marker.c
@@ -133,6 +133,28 @@ CHECK_MARKER (Lisp_Object x)
   CHECK_TYPE (MARKERP (x), Qmarkerp, x);
 }
 
+/* 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).
+   But if there are many markers, it can take too much time to find a "good"
+   marker from which to start.  Worse yet: if it takes a long time and we end
+   up finding a nearby markers, we won't add a new marker to cache this
+   result, so next time around we'll have to go through this same long list
+   to (re)find this best marker.  So the further down the list of
+   markers we go, the less demanding we are w.r.t what is a good marker.
+
+   The previous code used INITIAL=50 and INCREMENT=0 and this lead to
+   really poor performance when there are many markers.
+   I haven't tried to tweak INITIAL, but my experiments on my trusty Thinkpad
+   T61 using various artificial test cases seem to suggest that INCREMENT=50
+   might be "the best compromise": it significantly improved the
+   worst case and it was rarely slower and never by much.
+
+   The asymptotic behavior is still poor, tho, so in largish buffers with many
+   overlays (e.g. 300KB and 30K overlays), it can still be a bottlneck.  */
+#define BYTECHAR_DISTANCE_INITIAL 50
+#define BYTECHAR_DISTANCE_INCREMENT 50
+
 /* Return the byte position corresponding to CHARPOS in B.  */
 
 ptrdiff_t
@@ -141,6 +163,7 @@ buf_charpos_to_bytepos (struct buffer *b, ptrdiff_t charpos)
   struct Lisp_Marker *tail;
   ptrdiff_t best_above, best_above_byte;
   ptrdiff_t best_below, best_below_byte;
+  ptrdiff_t distance = BYTECHAR_DISTANCE_INITIAL;
 
   eassert (BUF_BEG (b) <= charpos && charpos <= BUF_Z (b));
 
@@ -180,8 +203,10 @@ buf_charpos_to_bytepos (struct buffer *b, ptrdiff_t charpos)
       /* If we are down to a range of 50 chars,
 	 don't bother checking any other markers;
 	 scan the intervening chars directly now.  */
-      if (best_above - best_below < 50)
+      if (best_above - best_below < distance)
 	break;
+      else
+        distance += BYTECHAR_DISTANCE_INCREMENT;
     }
 
   /* We get here if we did not exactly hit one of the known places.
@@ -293,6 +318,7 @@ buf_bytepos_to_charpos (struct buffer *b, ptrdiff_t bytepos)
   struct Lisp_Marker *tail;
   ptrdiff_t best_above, best_above_byte;
   ptrdiff_t best_below, best_below_byte;
+  ptrdiff_t distance = BYTECHAR_DISTANCE_INITIAL;
 
   eassert (BUF_BEG_BYTE (b) <= bytepos && bytepos <= BUF_Z_BYTE (b));
 
@@ -323,8 +349,10 @@ buf_bytepos_to_charpos (struct buffer *b, ptrdiff_t bytepos)
       /* If we are down to a range of 50 chars,
 	 don't bother checking any other markers;
 	 scan the intervening chars directly now.  */
-      if (best_above - best_below < 50)
+      if (best_above - best_below < distance)
 	break;
+      else
+        distance += BYTECHAR_DISTANCE_INCREMENT;
     }
 
   /* We get here if we did not exactly hit one of the known places.

Re: State of the overlay tree branch?

[Sebastian Sturm]

I haven't tested this very extensively yet, but artificial benchmark 
results are now comparable to the noverlay branch and editing seems 
similarly fluid. Many thanks for that!
On a tangential note, removing the bottleneck now brought up another 
hotspot in my performance profile (less severe than the one previously 
reported) that seems to be due to cc-mode itself. Since I don't want to 
derail this thread, I'll try to implement some of the suggestions made 
in the "Latency profiling?" thread and come up with some reproducible 
data on that other issue.

On 03/23/2018 06:03 AM, Stefan Monnier wrote:
>> since noverlay performs so well, I guess the technical issue here is already
>> solved and I'll just have to wait for it to make it into the master
>> branch.
> 
> Yes and no: there can still be many markers (even without having any
> overlays) and that poses the same problem (and the noverlays branch
> doesn't change that).
> 
> I've made some further tests and found that the patch I sent indeed
> doesn't help tremendously with "distance += 10" but that when we reach
> "+= 50" the effect is more significant.
> 
> Could you try the patch below (ideally not just with artificial tests
> but also in actual use) to see if it helps?
> 
> 
>          Stefan
> 
> 
> diff --git a/src/marker.c b/src/marker.c
> index 7773c4fce0..6ab0d3d61e 100644
> --- a/src/marker.c
> +++ b/src/marker.c
> @@ -133,6 +133,28 @@ CHECK_MARKER (Lisp_Object x)
>     CHECK_TYPE (MARKERP (x), Qmarkerp, x);
>   }
>   
> +/* 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).
> +   But if there are many markers, it can take too much time to find a "good"
> +   marker from which to start.  Worse yet: if it takes a long time and we end
> +   up finding a nearby markers, we won't add a new marker to cache this
> +   result, so next time around we'll have to go through this same long list
> +   to (re)find this best marker.  So the further down the list of
> +   markers we go, the less demanding we are w.r.t what is a good marker.
> +
> +   The previous code used INITIAL=50 and INCREMENT=0 and this lead to
> +   really poor performance when there are many markers.
> +   I haven't tried to tweak INITIAL, but my experiments on my trusty Thinkpad
> +   T61 using various artificial test cases seem to suggest that INCREMENT=50
> +   might be "the best compromise": it significantly improved the
> +   worst case and it was rarely slower and never by much.
> +
> +   The asymptotic behavior is still poor, tho, so in largish buffers with many
> +   overlays (e.g. 300KB and 30K overlays), it can still be a bottlneck.  */
> +#define BYTECHAR_DISTANCE_INITIAL 50
> +#define BYTECHAR_DISTANCE_INCREMENT 50
> +
>   /* Return the byte position corresponding to CHARPOS in B.  */
>   
>   ptrdiff_t
> @@ -141,6 +163,7 @@ buf_charpos_to_bytepos (struct buffer *b, ptrdiff_t charpos)
>     struct Lisp_Marker *tail;
>     ptrdiff_t best_above, best_above_byte;
>     ptrdiff_t best_below, best_below_byte;
> +  ptrdiff_t distance = BYTECHAR_DISTANCE_INITIAL;
>   
>     eassert (BUF_BEG (b) <= charpos && charpos <= BUF_Z (b));
>   
> @@ -180,8 +203,10 @@ buf_charpos_to_bytepos (struct buffer *b, ptrdiff_t charpos)
>         /* If we are down to a range of 50 chars,
>   	 don't bother checking any other markers;
>   	 scan the intervening chars directly now.  */
> -      if (best_above - best_below < 50)
> +      if (best_above - best_below < distance)
>   	break;
> +      else
> +        distance += BYTECHAR_DISTANCE_INCREMENT;
>       }
>   
>     /* We get here if we did not exactly hit one of the known places.
> @@ -293,6 +318,7 @@ buf_bytepos_to_charpos (struct buffer *b, ptrdiff_t bytepos)
>     struct Lisp_Marker *tail;
>     ptrdiff_t best_above, best_above_byte;
>     ptrdiff_t best_below, best_below_byte;
> +  ptrdiff_t distance = BYTECHAR_DISTANCE_INITIAL;
>   
>     eassert (BUF_BEG_BYTE (b) <= bytepos && bytepos <= BUF_Z_BYTE (b));
>   
> @@ -323,8 +349,10 @@ buf_bytepos_to_charpos (struct buffer *b, ptrdiff_t bytepos)
>         /* If we are down to a range of 50 chars,
>   	 don't bother checking any other markers;
>   	 scan the intervening chars directly now.  */
> -      if (best_above - best_below < 50)
> +      if (best_above - best_below < distance)
>   	break;
> +      else
> +        distance += BYTECHAR_DISTANCE_INCREMENT;
>       }
>   
>     /* We get here if we did not exactly hit one of the known places.
> 
> 

-- 
Sebastian Sturm
Research & Development

Phone:	+49 (0) 6155 7808977
Fax:	+49 (0) 6155 7802880
Email:	s.sturm@arkona-technologies.de
Web:	www.arkona-technologies.de

arkona technologies GmbH
Im Leuschnerpark 4
64347 Griesheim
Germany
Amtsgericht / Commercial Register of Darmstadt, HRB 90080
USt-ID: DE273794666
Steuernummer / Tax-ID: 007 / 228 / 19331
Geschäftsführung / Managing Director: Rainer Sturm

This e-mail may contain confidential and/or privileged information. If 
you are not the intended recipient (or have received this e-mail in 
error) please notify the sender immediately and delete this message and 
any attachments from your system. Any unauthorised copying, disclosure 
or distribution of the material in this e-mail is strictly forbidden.

We cannot accept any responsibility for the accuracy or completeness of 
this message as it has been transmitted over a public network. If, 
despite our use of anti-virus software, a virus enters your systems in 
connection with the sending of the e-mail, you may not hold us liable 
for any damages that may possibly arise in that connection. We will 
accept liability which by law we cannot exclude.

Re: State of the overlay tree branch?

[Eli Zaretskii]

> From: Sebastian Sturm <s.sturm@arkona-technologies.de>
> Date: Fri, 23 Mar 2018 13:25:19 +0100
> 
> I haven't tested this very extensively yet, but artificial benchmark 
> results are now comparable to the noverlay branch and editing seems 
> similarly fluid. Many thanks for that!

I'd be interested to see a comparison with a code that ignores the
markers entirely, and uses just these 4:

  CONSIDER (BUF_PT (b), BUF_PT_BYTE (b));
  CONSIDER (BUF_GPT (b), BUF_GPT_BYTE (b));
  CONSIDER (BUF_BEGV (b), BUF_BEGV_BYTE (b));
  CONSIDER (BUF_ZV (b), BUF_ZV_BYTE (b));

That's because BYTECHAR_DISTANCE_INCREMENT is probably a function of
the number of markers.

Re: State of the overlay tree branch?

[Stefan Monnier]

> I'd be interested to see a comparison with a code that ignores the
> markers entirely, and uses just these 4:
>
>   CONSIDER (BUF_PT (b), BUF_PT_BYTE (b));
>   CONSIDER (BUF_GPT (b), BUF_GPT_BYTE (b));
>   CONSIDER (BUF_BEGV (b), BUF_BEGV_BYTE (b));
>   CONSIDER (BUF_ZV (b), BUF_ZV_BYTE (b));

I tried that, and in the synthetic benchmark which tries to reproduce
Sebastian's lsp-mode situation the result was indeed much better, but
then in other benchmarks it caused very significant slowdowns.

> That's because BYTECHAR_DISTANCE_INCREMENT is probably a function of
> the number of markers.

I haven't investigated closely enough to be sure, but in my tests with
INCREMENT=50 I reached points where adding more overlays did not make
things worse any more, so I suspect that the ideal INCREMENT depends on
the buffer size more than on the number of markers.

In any case, my patch is just a "quick hack" to try and reduce the pain,
but it doesn't really solve the problem: the slow down with many markers
and a large buffer still grows pretty significantly with the size of
the buffer.  I think it's worse than O(sqrt N).

If we want to really solve this problem, we should use an algorithm with
at most an O(log N) complexity, e.g. keeping the markers in
a red-black tree, or inside a sorted array (probably with a gap like we
have for the buffer text) so we can do a binary search.


        Stefan

Re: State of the overlay tree branch?

[Noam Postavsky]

On 23 March 2018 at 09:19, Stefan Monnier <monnier@iro.umontreal.ca> wrote:

> In any case, my patch is just a "quick hack" to try and reduce the pain,
> but it doesn't really solve the problem: the slow down with many markers
> and a large buffer still grows pretty significantly with the size of
> the buffer.  I think it's worse than O(sqrt N).
>
> If we want to really solve this problem, we should use an algorithm with
> at most an O(log N) complexity, e.g. keeping the markers in
> a red-black tree, or inside a sorted array (probably with a gap like we
> have for the buffer text) so we can do a binary search.

Is this related to Bug#24548 "Long GC delays with many non-detached
markers (PATCH)"
aka Bug#29439 "Quadratic complexity in sweep_markers"?

https://debbugs.gnu.org/cgi/bugreport.cgi?bug=24548
https://debbugs.gnu.org/cgi/bugreport.cgi?bug=29439

Re: State of the overlay tree branch?

[Stefan Monnier]

>> If we want to really solve this problem, we should use an algorithm with
>> at most an O(log N) complexity, e.g. keeping the markers in
>> a red-black tree, or inside a sorted array (probably with a gap like we
>> have for the buffer text) so we can do a binary search.
>
> Is this related to Bug#24548 "Long GC delays with many non-detached
> markers (PATCH)"
> aka Bug#29439 "Quadratic complexity in sweep_markers"?

Not directly, no,


        Stefan

Re: State of the overlay tree branch?

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Date: Fri, 23 Mar 2018 09:19:11 -0400
> 
> > I'd be interested to see a comparison with a code that ignores the
> > markers entirely, and uses just these 4:
> >
> >   CONSIDER (BUF_PT (b), BUF_PT_BYTE (b));
> >   CONSIDER (BUF_GPT (b), BUF_GPT_BYTE (b));
> >   CONSIDER (BUF_BEGV (b), BUF_BEGV_BYTE (b));
> >   CONSIDER (BUF_ZV (b), BUF_ZV_BYTE (b));
> 
> I tried that, and in the synthetic benchmark which tries to reproduce
> Sebastian's lsp-mode situation the result was indeed much better, but
> then in other benchmarks it caused very significant slowdowns.

In what benchmarks did it cause significant slowdowns?

> > That's because BYTECHAR_DISTANCE_INCREMENT is probably a function of
> > the number of markers.
> 
> I haven't investigated closely enough to be sure, but in my tests with
> INCREMENT=50 I reached points where adding more overlays did not make
> things worse any more, so I suspect that the ideal INCREMENT depends on
> the buffer size more than on the number of markers.

Could be.  My point was that it isn't a constant.

> If we want to really solve this problem, we should use an algorithm with
> at most an O(log N) complexity, e.g. keeping the markers in
> a red-black tree, or inside a sorted array (probably with a gap like we
> have for the buffer text) so we can do a binary search.

Yes, agreed.

Re: State of the overlay tree branch?

[Stefan Monnier]

>> > I'd be interested to see a comparison with a code that ignores the
>> > markers entirely, and uses just these 4:
>> >   CONSIDER (BUF_PT (b), BUF_PT_BYTE (b));
>> >   CONSIDER (BUF_GPT (b), BUF_GPT_BYTE (b));
>> >   CONSIDER (BUF_BEGV (b), BUF_BEGV_BYTE (b));
>> >   CONSIDER (BUF_ZV (b), BUF_ZV_BYTE (b));
>> I tried that, and in the synthetic benchmark which tries to reproduce
>> Sebastian's lsp-mode situation the result was indeed much better, but
>> then in other benchmarks it caused very significant slowdowns.
> In what benchmarks did it cause significant slowdowns?

Can't remember exactly, I think it was bad enough for a test case
which seemed pretty realistic so I discarded that option.
Basically what I remember is that I got the impression that it would
probably harm more users than the problem at hand.


        Stefan


PS: BTW, the number of markers is not the only issue: the order in which
they are created also matters.  Maybe we should try Sebastian's test
case but creating the markers/overlays in random order (and if that
helps, we could get a similar effect by making the GC randomly shuffle
the buffers's list of markers ;-).

Re: State of the overlay tree branch?

[Stefan Monnier]

OK, I think I'm tired of these experiments.
Here's my current test, along with the patches I use with it.

You can test it with something like

    src/emacs -Q --batch -l ~/tmp/foo.el --eval '(setq internal--bytechar-distance-increment 50 internal--randomize-markers t)' --eval '(bytechar-test 3000 nil)' 

Shuffling the markers can make a noticeable difference in some cases but
we're only talking about a factor of 2 or 3.  It doesn't have much
negative impact, so it's not a bad option, but the algorithmic
problem remains anyway.


        Stefan


(defun bytechar-test (buffer-kb &optional forward)
  (random "seed")
  (with-temp-buffer
    (dotimes (i (* buffer-kb 33))
      (insert "lksajflahalskjdféefawrgfrüegf\n"))
    (message "buffer-size = %SkB" (/ (buffer-size) 1024))
    (let ((txtbuf (current-buffer))
          (goto-iterations (/ 10000000 buffer-kb))
          (line-iterations (/ 20000 buffer-kb))
          (markers ()))
      (dotimes (s 4)
        (with-temp-buffer
          (insert-buffer-substring txtbuf)
          (let ((stepsize (lsh 10 (* 4 s))))
            (if forward
                (cl-loop for n from (point-min) upto (point-max) by stepsize do
                         (push (copy-marker n) markers))
              (cl-loop for n from (point-max) downto (point-min) by stepsize do
                       (push (copy-marker n) markers))))
          ;; The GC's internal--randomize-markers just brings-to-front every
          ;; 8th marker, so when starting with an ordered list of markers (like
          ;; in our case), we need to run the GC at least 8 times before the
          ;; whole list starts to look somewhat shuffled.
          (dotimes (i 20) (garbage-collect))
          (let ((timing
                 (benchmark-run goto-iterations
                   (goto-char (+ (point-min) (random (buffer-size)))))))
            (message "ols=%S goto-random time=%.4f (+ %S)"
                     (/ (buffer-size) (lsh 10 (* 4 s)))
                     (car timing) (cdr timing)))
          (garbage-collect)             ;throw away the transient markers
          (let ((timing
                 (benchmark-run line-iterations
                   (dotimes (i 5)
                     (line-number-at-pos
                      (+ (point-min) (* i (/ (buffer-size) 4))))))))
            (message "nbmks=%S pos=*/4 time=%.4f (+ %S)"
                     (/ (buffer-size) (lsh 10 (* 4 s)))
                     (car timing) (cdr timing)))
          (dotimes (i 5)
            (let ((timing
                   (benchmark-run line-iterations
                     (line-number-at-pos
                      (+ (point-min) (* i (/ (buffer-size) 4)))))))
              (message "nbmks=%S pos=%S/4 time=%.4f (+ %S)"
                       (/ (buffer-size) (lsh 10 (* 4 s))) i
                       (car timing) (cdr timing))))
          )))))

diff --git a/lisp/emacs-lisp/benchmark.el b/lisp/emacs-lisp/benchmark.el
index b86b56b81e..2f4e38fe35 100644
--- a/lisp/emacs-lisp/benchmark.el
+++ b/lisp/emacs-lisp/benchmark.el
@@ -50,7 +50,7 @@ benchmark-run
 garbage collections that ran, and the time taken by garbage collection.
 See also `benchmark-run-compiled'."
   (declare (indent 1) (debug t))
-  (unless (natnump repetitions)
+  (unless (or (natnump repetitions) (symbolp repetitions))
     (setq forms (cons repetitions forms)
 	  repetitions 1))
   (let ((i (make-symbol "i"))
@@ -58,7 +58,7 @@ benchmark-run
 	(gc (make-symbol "gc")))
     `(let ((,gc gc-elapsed)
 	   (,gcs gcs-done))
-       (list ,(if (> repetitions 1)
+       (list ,(if (or (symbolp repetitions) (> repetitions 1))
 		  ;; Take account of the loop overhead.
 		  `(- (benchmark-elapse (dotimes (,i ,repetitions)
 					  ,@forms))
@@ -101,7 +101,7 @@ benchmark
 For non-interactive use see also `benchmark-run' and
 `benchmark-run-compiled'."
   (interactive "p\nxForm: ")
-  (let ((result (eval `(benchmark-run ,repetitions ,form))))
+  (let ((result (eval `(benchmark-run ,repetitions ,form) t)))
     (if (zerop (nth 1 result))
 	(message "Elapsed time: %fs" (car result))
       (message "Elapsed time: %fs (%fs in %d GCs)" (car result)
diff --git a/src/alloc.c b/src/alloc.c
index 7ba872aaee..16d11e34cd 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -7270,10 +7270,22 @@ static void
 unchain_dead_markers (struct buffer *buffer)
 {
   struct Lisp_Marker *this, **prev = &BUF_MARKERS (buffer);
+  /* In order to try and avoid worst case behaviors in buf_charpos_to_bytepos
+     we try and randomize the order of markers here.  */
+  unsigned i = 4;
 
   while ((this = *prev))
     if (this->gcmarkbit)
-      prev = &this->next;
+      {
+        if (!randomize_markers || i++ % 8)
+          prev = &this->next;
+        else
+          { /* Move this one to front, just to randomize things a bit.  */
+            *prev = this->next;
+            this->next = BUF_MARKERS (buffer);
+            BUF_MARKERS (buffer) = this;
+          }
+      }
     else
       {
         this->buffer = NULL;
@@ -7752,6 +7764,9 @@ The time is in seconds as a floating point value.  */);
   DEFVAR_INT ("gcs-done", gcs_done,
               doc: /* Accumulated number of garbage collections done.  */);
 
+  DEFVAR_BOOL ("internal--randomize-markers", randomize_markers, doc: /*  */);
+  randomize_markers = true;
+  
   defsubr (&Scons);
   defsubr (&Slist);
   defsubr (&Svector);
diff --git a/src/marker.c b/src/marker.c
index 3d808fd6fa..7c1d164927 100644
--- a/src/marker.c
+++ b/src/marker.c
@@ -133,6 +133,28 @@ CHECK_MARKER (Lisp_Object x)
   CHECK_TYPE (MARKERP (x), Qmarkerp, x);
 }
 
+/* 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).
+   But if there are many markers, it can take too much time to find a "good"
+   marker from which to start.  Worse yet: if it takes a long time and we end
+   up finding a nearby markers, we won't add a new marker to cache this
+   result, so next time around we'll have to go through this same long list
+   to (re)find this best marker.  So the further down the list of
+   markers we go, the less demanding we are w.r.t what is a good marker.
+
+   The previous code used INITIAL=50 and INCREMENT=0 and this lead to
+   really poor performance when there are many markers.
+   I haven't tried to tweak INITIAL, but my experiments on my trusty Thinkpad
+   T61 using various artificial test cases seem to suggest that INCREMENT=50
+   might be "the best compromise": it significantly improved the
+   worst case and it was rarely slower and never by much.
+
+   The asymptotic behavior is still poor, tho, so in largish buffers with many
+   overlays (e.g. 300KB and 30K overlays), it can still be a bottlneck.  */
+#define BYTECHAR_DISTANCE_INITIAL 50
+#define BYTECHAR_DISTANCE_INCREMENT bytechar_distance_increment
+
 /* Return the byte position corresponding to CHARPOS in B.  */
 
 ptrdiff_t
@@ -141,7 +163,7 @@ buf_charpos_to_bytepos (struct buffer *b, ptrdiff_t charpos)
   struct Lisp_Marker *tail;
   ptrdiff_t best_above, best_above_byte;
   ptrdiff_t best_below, best_below_byte;
-  ptrdiff_t distance = 50;
+  ptrdiff_t distance = BYTECHAR_DISTANCE_INITIAL;
 
   eassert (BUF_BEG (b) <= charpos && charpos <= BUF_Z (b));
 
@@ -184,7 +206,7 @@ buf_charpos_to_bytepos (struct buffer *b, ptrdiff_t charpos)
       if (best_above - best_below < distance)
 	break;
       else
-        distance++;
+        distance += BYTECHAR_DISTANCE_INCREMENT;
     }
 
   /* We get here if we did not exactly hit one of the known places.
@@ -296,7 +318,7 @@ buf_bytepos_to_charpos (struct buffer *b, ptrdiff_t bytepos)
   struct Lisp_Marker *tail;
   ptrdiff_t best_above, best_above_byte;
   ptrdiff_t best_below, best_below_byte;
-  ptrdiff_t distance = 50;
+  ptrdiff_t distance = BYTECHAR_DISTANCE_INITIAL;
 
   eassert (BUF_BEG_BYTE (b) <= bytepos && bytepos <= BUF_Z_BYTE (b));
 
@@ -330,7 +352,7 @@ buf_bytepos_to_charpos (struct buffer *b, ptrdiff_t bytepos)
       if (best_above - best_below < distance)
 	break;
       else
-        distance++;
+        distance += BYTECHAR_DISTANCE_INCREMENT;
     }
 
   /* We get here if we did not exactly hit one of the known places.
@@ -756,4 +778,9 @@ syms_of_marker (void)
   defsubr (&Scopy_marker);
   defsubr (&Smarker_insertion_type);
   defsubr (&Sset_marker_insertion_type);
+
+  DEFVAR_INT ("internal--bytechar-distance-increment",
+              bytechar_distance_increment,
+              doc: /* Haha */);
+  bytechar_distance_increment = 50;
 }

Re: State of the overlay tree branch?

[Stefan Monnier]

> OK, I think I'm tired of these experiments.

Taking a break finally let me get rid of my blinders so I could see
more clearly what's going on:

All this time is really spent in find_newline (rather than in things
like goto-char).  The problem goes as follows:

A - (line-number-at-pos POS) will call find_newline, making it scan all
    positions between point-min and POS.
B1- if find_newline uses the newline cache, at each newline encountered it
    will call buf_charpos_to_bytepos.
B2- if find_newline does not use the newline cache, at each newline
    encountered it will call buf_bytepos_to_charpos.
  - Each time buf_charpos_to_bytepos/buf_bytepos_to_charpos is called
    it will "CONSIDER" the known positions at point-min, point-max, and at
    the position of the last-call (i.e. at the previous newline).
    Then it will loop through all the markers until the distance between
    the nearest position before POS and the nearest position after POS
    are within 50 of each other.
C - since one of the known positions is the one of the last newline, the
    distance between the nearest position and POS (before considering any
    marker) is usually pretty small: the length of the current line.
    It's even often smaller than 50.  But that doesn't let us stop because
    the marker loop doesn't pay attention to the distance to POS in order
    to decide to stop: it only consider the distance between the current upper
    and lower bound and since we're scanning in one direction, all the
    recently seen positions (added as markers) are on the same side of
    POS as the last seen newline so they don't help.

So there are various ways to solve this problem.  So far, I tried to
make the markers-loop give up earlier, which helps (C) to some extent but
without attacking the core of its problem which is to pay attention to
the case where one of the bounds is already very close to POS even tho
the other is still way off.

The patch below tweaks my previous patch to take this into account.
The result is now that my test cases stay fast (mostly unaffected by the
number of markers) even for large buffers with a large number of markers.

Note that the above shows that there are other optimisations which would
also solve this problem (and would be worthwhile independently).
A - change line-number-at-pos so it doesn't always rescan all the way
    from point-min.  This would really circumvent the whole problem
    (contrarily to what I thought before with my blinders on, thanks Eli
    for insisting on that).
B - change find_newline so it doesn't call
    buf_charpos_to_bytepos/buf_bytepos_to_charpos at each newline.
    E.g. in the no-newline-cache case it'd probably be faster to
    loop through each char using INC/DEC_BOTH and checking if we're at
    \n, than the current code which uses mem(r)chr to look for the
    bytepos of the next \n and then calls buf_bytepos_to_charpos to get
    the corresponding charpos.  Alternatively, we could just delay the
    computation of the charpos until the end (currently we update it
    at each newline, for the purpose of filling the newline-cache).


-- Stefan


diff --git a/src/marker.c b/src/marker.c
index 7773c4fce0..f869b3f948 100644
--- a/src/marker.c
+++ b/src/marker.c
@@ -133,6 +133,28 @@ CHECK_MARKER (Lisp_Object x)
   CHECK_TYPE (MARKERP (x), Qmarkerp, x);
 }
 
+/* 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).
+   But if there are many markers, it can take too much time to find a "good"
+   marker from which to start.  Worse yet: if it takes a long time and we end
+   up finding a nearby markers, we won't add a new marker to cache this
+   result, so next time around we'll have to go through this same long list
+   to (re)find this best marker.  So the further down the list of
+   markers we go, the less demanding we are w.r.t what is a good marker.
+
+   The previous code used INITIAL=50 and INCREMENT=0 and this lead to
+   really poor performance when there are many markers.
+   I haven't tried to tweak INITIAL, but my experiments on my trusty Thinkpad
+   T61 using various artificial test cases seem to suggest that INCREMENT=50
+   might be "the best compromise": it significantly improved the
+   worst case and it was rarely slower and never by much.
+
+   The asymptotic behavior is still poor, tho, so in largish buffers with many
+   overlays (e.g. 300KB and 30K overlays), it can still be a bottlneck.  */
+#define BYTECHAR_DISTANCE_INITIAL 50
+#define BYTECHAR_DISTANCE_INCREMENT 50
+
 /* Return the byte position corresponding to CHARPOS in B.  */
 
 ptrdiff_t
@@ -141,6 +163,7 @@ buf_charpos_to_bytepos (struct buffer *b, ptrdiff_t charpos)
   struct Lisp_Marker *tail;
   ptrdiff_t best_above, best_above_byte;
   ptrdiff_t best_below, best_below_byte;
+  ptrdiff_t distance = BYTECHAR_DISTANCE_INITIAL;
 
   eassert (BUF_BEG (b) <= charpos && charpos <= BUF_Z (b));
 
@@ -180,8 +203,11 @@ buf_charpos_to_bytepos (struct buffer *b, ptrdiff_t charpos)
       /* If we are down to a range of 50 chars,
 	 don't bother checking any other markers;
 	 scan the intervening chars directly now.  */
-      if (best_above - best_below < 50)
+      if (best_above - charpos < distance
+          || charpos - best_below < distance)
 	break;
+      else
+        distance += BYTECHAR_DISTANCE_INCREMENT;
     }
 
   /* We get here if we did not exactly hit one of the known places.
@@ -293,6 +319,7 @@ buf_bytepos_to_charpos (struct buffer *b, ptrdiff_t bytepos)
   struct Lisp_Marker *tail;
   ptrdiff_t best_above, best_above_byte;
   ptrdiff_t best_below, best_below_byte;
+  ptrdiff_t distance = BYTECHAR_DISTANCE_INITIAL;
 
   eassert (BUF_BEG_BYTE (b) <= bytepos && bytepos <= BUF_Z_BYTE (b));
 
@@ -323,8 +350,11 @@ buf_bytepos_to_charpos (struct buffer *b, ptrdiff_t bytepos)
       /* If we are down to a range of 50 chars,
 	 don't bother checking any other markers;
 	 scan the intervening chars directly now.  */
-      if (best_above - best_below < 50)
+      if (best_above - bytepos < distance
+          || bytepos - best_below < distance)
 	break;
+      else
+        distance += BYTECHAR_DISTANCE_INCREMENT;
     }
 
   /* We get here if we did not exactly hit one of the known places.

Re: State of the overlay tree branch?

[Eli Zaretskii]

> From: Stefan Monnier <monnier@IRO.UMontreal.CA>
> Cc: emacs-devel@gnu.org
> Date: Sun, 25 Mar 2018 11:11:14 -0400
> 
> B1- if find_newline uses the newline cache, at each newline encountered it
>     will call buf_charpos_to_bytepos.
> B2- if find_newline does not use the newline cache, at each newline
>     encountered it will call buf_bytepos_to_charpos.

Agree with B1, but not with B2.  Unless I'm overlooking something,
when the newline cache is disabled, we use memchr, which can search a
contiguous sequence of bytes in a loop, without translating
byte-to-character positions.  It only needs this translation at the
beginning of search, after hitting the gap, and when the search is
completed.

> So there are various ways to solve this problem.  So far, I tried to
> make the markers-loop give up earlier, which helps (C) to some extent but
> without attacking the core of its problem which is to pay attention to
> the case where one of the bounds is already very close to POS even tho
> the other is still way off.
> 
> The patch below tweaks my previous patch to take this into account.
> The result is now that my test cases stay fast (mostly unaffected by the
> number of markers) even for large buffers with a large number of markers.

This is a good change, I think.  But it emphasizes even more the fact
that if we instead expose to Lisp display_count_lines, which is
basically a stripped-down version of find_newline with all the
unnecessary ballast removed, we will get an even better performance in
applications that need to count lines a lot.

> Note that the above shows that there are other optimisations which would
> also solve this problem (and would be worthwhile independently).
> A - change line-number-at-pos so it doesn't always rescan all the way
>     from point-min.  This would really circumvent the whole problem
>     (contrarily to what I thought before with my blinders on, thanks Eli
>     for insisting on that).
> B - change find_newline so it doesn't call
>     buf_charpos_to_bytepos/buf_bytepos_to_charpos at each newline.
>     E.g. in the no-newline-cache case it'd probably be faster to
>     loop through each char using INC/DEC_BOTH and checking if we're at
>     \n, than the current code which uses mem(r)chr to look for the
>     bytepos of the next \n and then calls buf_bytepos_to_charpos to get
>     the corresponding charpos.  Alternatively, we could just delay the
>     computation of the charpos until the end (currently we update it
>     at each newline, for the purpose of filling the newline-cache).

I think we need not touch find_newline.  It is a very frequently used
workhorse, and needs to produce decent performance for every one of
its callers.  By contrast, applications whose primary need is to count
lines, let alone do that _thousands_ of times per keystroke, should
have a dedicated function optimized for that job alone.  It's not a
coincidence the native line-number display uses display_count_lines ;-)

Thanks.

Re: State of the overlay tree branch?

[Stefan Monnier]

> Agree with B1, but not with B2.  Unless I'm overlooking something,
> when the newline cache is disabled, we use memchr, which can search a
> contiguous sequence of bytes in a loop, without translating
> byte-to-character positions.  It only needs this translation at the
> beginning of search, after hitting the gap, and when the search is
> completed.

Hmm... indeed, when the newline cache is completely disabled the problem should
not appear.

>> The patch below tweaks my previous patch to take this into account.
>> The result is now that my test cases stay fast (mostly unaffected by the
>> number of markers) even for large buffers with a large number of markers.
> This is a good change, I think.  But it emphasizes even more the fact
> that if we instead expose to Lisp display_count_lines, which is
> basically a stripped-down version of find_newline with all the
> unnecessary ballast removed, we will get an even better performance in
> applications that need to count lines a lot.

Yes, fixing A is definitely worthwhile.


        Stefan

Re: State of the overlay tree branch?

[Eli Zaretskii]

> From: Sebastian Sturm <s.sturm@arkona-technologies.de>
> Date: Fri, 23 Mar 2018 00:11:16 +0100
> 
> since noverlay performs so well, I guess the technical issue here is 
> already solved and I'll just have to wait for it to make it into the 
> master branch.

As Stefan points out, the overlays are not the reason.  The reason are
the number of markers in the buffer; each overlay defines 2 markers.
And there could be many markers in a buffer even if there are no
overlays.

Btw, why do you have so many overlays in these buffers?  Is this part
of lsp-mode implementation, or is the reason unrelated?

Re: State of the overlay tree branch?

[Eli Zaretskii]

> Date: Fri, 23 Mar 2018 11:07:26 +0300
> From: Eli Zaretskii <eliz@gnu.org>
> Cc: emacs-devel@gnu.org
> 
> Btw, why do you have so many overlays in these buffers?  Is this part
> of lsp-mode implementation, or is the reason unrelated?

Also, what about my suggestion to count lines in a relative manner,
using count-lines from a line with a known number?  You never replied
to that suggestion.

Re: State of the overlay tree branch?

[Sebastian Sturm]

On 03/23/2018 10:08 AM, Eli Zaretskii wrote:
>> Date: Fri, 23 Mar 2018 11:07:26 +0300
>> From: Eli Zaretskii <eliz@gnu.org>
>> Cc: emacs-devel@gnu.org
>>
>> Btw, why do you have so many overlays in these buffers?  Is this part
>> of lsp-mode implementation, or is the reason unrelated?

this is not related to lsp-mode itself, but to the semantic highlighter 
implemented by emacs-cquery (which is built on top of lsp-mode but 
implements additional features offered by the cquery backend). When set 
to use overlays (which provides a better visual experience than 
font-lock, as font-lock tends to get out of sync with the buffer during 
editing), the semantic highlighter retrieves a list of symbols within 
the current buffer and creates overlays to provide semantically 
meaningful syntax highlighting. It's not a feature I couldn't live 
without, but it's very precise and in principle could probably be faster 
than the syntax highlighting provided by cc-mode as C++ parsing is 
handled asynchronously by the clang-based native backend.

> Also, what about my suggestion to count lines in a relative manner,
> using count-lines from a line with a known number?  You never replied
> to that suggestion.

you're right, sorry. In my opinion, a caching mechanism might be a very 
useful thing to have if it provides further performance benefits on top 
of what the noverlay branch has to offer. However, since count-lines may 
not be the only function that has to convert between char and byte 
positions (or is it?), and since the noverlay branch seems to resolve 
the overlay issue without having to introduce additional complexity in 
the elisp layer, implementing a caching mechanism before noverlay is 
merged into the master branch seems like a premature optimization to me.
Of course this is a layman's opinion (and maybe the case of "few 
overlays but many markers" is not as pathological as it appears to me); 
if you think a line number cache should be implemented, I'll go and 
discuss that with the lsp-mode maintainers (assuming that they are among 
the heaviest users of line-number-at-pos).
Sebastian

Re: State of the overlay tree branch?

[Eli Zaretskii]

> From: Sebastian Sturm <s.sturm@arkona-technologies.de>
> Date: Fri, 23 Mar 2018 11:15:48 +0100
> 
> > Also, what about my suggestion to count lines in a relative manner,
> > using count-lines from a line with a known number?  You never replied
> > to that suggestion.
> 
> you're right, sorry. In my opinion, a caching mechanism might be a very 
> useful thing to have if it provides further performance benefits on top 
> of what the noverlay branch has to offer. However, since count-lines may 
> not be the only function that has to convert between char and byte 
> positions (or is it?), and since the noverlay branch seems to resolve 
> the overlay issue without having to introduce additional complexity in 
> the elisp layer, implementing a caching mechanism before noverlay is 
> merged into the master branch seems like a premature optimization to me.

It isn't premature optimization, because a buffer could have many
markers even if it has no or only a few overlays.

> Of course this is a layman's opinion (and maybe the case of "few 
> overlays but many markers" is not as pathological as it appears to me); 
> if you think a line number cache should be implemented, I'll go and 
> discuss that with the lsp-mode maintainers (assuming that they are among 
> the heaviest users of line-number-at-pos).

I think the effect should be at least measured before the decision
whether to do that is made.

Re: State of the overlay tree branch?

[Stefan Monnier]

> Also, what about my suggestion to count lines in a relative manner,
> using count-lines from a line with a known number?  You never replied
> to that suggestion.

FWIW, I believe in his case most of the time is spent outside of the
actual "count the lines" (aka forward-line) code, so counting fewer
lines because we start from a more nearby position probably won't help
very much.


        Stefan

Re: State of the overlay tree branch?

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Date: Fri, 23 Mar 2018 08:12:41 -0400
> 
> > Also, what about my suggestion to count lines in a relative manner,
> > using count-lines from a line with a known number?  You never replied
> > to that suggestion.
> 
> FWIW, I believe in his case most of the time is spent outside of the
> actual "count the lines" (aka forward-line) code, so counting fewer
> lines because we start from a more nearby position probably won't help
> very much.

I'm not sure, because the profile indicates memrchr is a significant
runner-up in the CPU time usage.

Re: State of the overlay tree branch?

[Stefan Monnier]

> I'm not sure, because the profile indicates memrchr is a significant
> runner-up in the CPU time usage.

Oh, indeed I wasn't clear: it won't solve the "too many markers" case,
but it will still be useful, especially in the case where there aren't
too many markers.

My experience with nlinum--line-number-at-pos is that it's a low-hanging
fruit.  If the solution can be implemented directly inside
line-number-at-pos it'd be even better.


        Stefan

Re: State of the overlay tree branch?

[Eli Zaretskii]

> From: Sebastian Sturm <s.sturm@arkona-technologies.de>
> Date: Mon, 19 Mar 2018 00:03:11 +0100
> 
> Again, however, line-number-at-pos shows up as a large CPU time consumer 
> in the profiler report, and benchmark-run still reports several ms per 
> invocation (though this time it's usually around 2 to 4 ms instead of 
> the 20 to 25 I measured earlier), so I'd still be very much interested 
> in a faster line-number-at-pos implementation.

2 to 4 ms for 6 calls is as fast as you can get for a 70K file.  But
you should be able to issue just one call, and replace the other 5
with relative counting using count-lines or forward-line, which should
then count only a small number of lines from the original location.
Right?

Re: State of the overlay tree branch?

[Eli Zaretskii]

> From: Sebastian Sturm <s.sturm@arkona-technologies.de>
> Date: Sun, 18 Mar 2018 22:04:13 +0100
> 
> I also found it surprising that overlays would slow down line counting, 
> but since I don't know anything about the architecture of the Emacs 
> display engine, or its overlay implementation, I figured that overlays 
> must be to blame because
> 
> (i) the issue went away after switching to the feature/noverlay branch
> 
> (ii) configuring the semantic highlighter to use its font-lock backend 
> also resolved the performance issue (though with the font-lock backend, 
> highlights are easily messed up by editing operations which makes the 
> overlay variant far more appealing)

If you look at the implementation of count-lines, you will see it just
calls forward-line, which pays no attention to overlays (as I'd
expect).

> I also found that some other heavy users of overlays such as 
> avy-goto-word-0-{above,below} feel faster with the feature/noverlay 
> branch, so I'd welcome a merge of the overlay branch even if there was a 
> technically superior alternative to line-number-at-pos that didn't 
> suffer from overlay-related performance issues.

That's unrelated: we want to merge that branch when it's ready for
several good reasons.  But counting lines shouldn't be one of those
reasons.

> That being said, your suggestion sounds intriguing. What would be 
> required to expose find_newline to Lisp? Would I simply have to wrap it 
> in one of Emacs's DEFINE_<something> macros?

DEFUN, more accurately.  But yes.

Actually, I see that forward-line already calls find_newline almost
directly, so it should be fast enough.  Exposing find_line should
perhaps be able to produce some speedup (because you don't need to set
point, like forward-line does), but I doubt that it would be
significant.

> Is there some documentation on the Emacs C backend?

There's the "Writing Emacs Primitives" section of the "Internals"
appendix.

Turning back to your original problem, viz.:

 >> [1] I'm using cquery for my C++ editing needs, which comes with an
 >> overlay-based semantic highlighting mechanism. With my emacs
 >> configuration, lsp-mode/lsp-ui emit 6 calls to line-number-at-pos per
 >> character insertion, which consume ~20 to 25 ms each when performing
 >> edits close to the bottom of a 66KB C++ file (measured using
 >> (benchmark-run 1000 (line-number-at-pos (point))) on a release build of
 >> emacs-27/git commit #9942734...). Using the noverlay branch, this figure
 >> drops to ~160us per call.

it looks strange to me that you get such long times.  I just tried
Emacs 26.0.91 near the end of xdisp.c (a 1MB file with over 33K
lines), and I get 3 ms per call there.  So I wonder how come you get 4
or 5 ms per call in a file that is 50 times smaller, because if I run
the above benchmark with point at 70K, I get 0.16 ms per call.  In an
unoptimized build of the current master branch, I get 0.25 ms per call
under these conditions.  (And you could cache the result if you need 6
calls in the same vicinity, and after the initial call only call
forward-line to compute relative increments.)

This is with a 5-year old i7-2600 box with a 3.40 GHz clock.  Is your
CPU significantly slower?

Re: State of the overlay tree branch?

[Sebastien Chapuis]

Eli Zaretskii writes:

>> From: Sebastian Sturm <s.sturm@arkona-technologies.de>
>> Date: Sun, 18 Mar 2018 21:14:53 +0100
>>
>> [1] I'm using cquery for my C++ editing needs, which comes with an
>> overlay-based semantic highlighting mechanism. With my emacs
>> configuration, lsp-mode/lsp-ui emit 6 calls to line-number-at-pos per
>> character insertion, which consume ~20 to 25 ms each when performing
>> edits close to the bottom of a 66KB C++ file (measured using
>> (benchmark-run 1000 (line-number-at-pos (point))) on a release build of
>> emacs-27/git commit #9942734...). Using the noverlay branch, this figure
>> drops to ~160us per call.
>
> If lsp-mode/lsp-ui needs a fast line counter, one can easily be
> provided by exposing find_newline to Lisp.  IME, it's lightning-fast,
> and should run circles around count-lines (used by line-number-at-pos).
>
> (I'm not sure I even understand how overlays come into play here,
> btw.)

The language server protocol defines a position in file with zero-indexed
line and column offsets [1]:

```
interface Position {
	line: number;
	character: number;
}
```

lsp-mode uses heavily line-number-at-pos to convert an Emacs buffer
point to a LSP position, and vice-versa [2].
This can happen thousands times on each keystroke.

If Emacs could provide a function to do the conversion very fast (or at
least faster than with line-number-at-pos), it would be great.


[1] https://github.com/Microsoft/language-server-protocol/blob/gh-pages/specification.md#position
[2] The conversion from a LSP position to point doesn't use
line-number-at-pos, but forward-line and forward-char. It's still very slow.

--
Sebastien Chapuis

Re: State of the overlay tree branch?

[Eli Zaretskii]

> From: Sebastien Chapuis <sebastien@chapu.is>
> Cc: Sebastian Sturm <s.sturm@arkona-technologies.de>, emacs-devel@gnu.org
> Date: Wed, 21 Mar 2018 15:14:18 +0100
> 
> The language server protocol defines a position in file with zero-indexed
> line and column offsets [1]:
> 
> ```
> interface Position {
> 	line: number;
> 	character: number;
> }
> ```
> 
> lsp-mode uses heavily line-number-at-pos to convert an Emacs buffer
> point to a LSP position, and vice-versa [2].

line-number-at-pos is inefficient, in that it always counts from the
beginning of the buffer.  By keeping already computed line numbers
around, you could make a faster implementation if you count relative
line offsets using count-lines instead.

> This can happen thousands times on each keystroke.

_Thousands_ times for _each_ keystroke?  Why is that?  Most keystrokes
only change a single line, so how come you need thousands of lines
recounted each time?

> If Emacs could provide a function to do the conversion very fast (or at
> least faster than with line-number-at-pos), it would be great.

Given the above, I think you need to describe the issue in more
details, before we even begin designing the solution.

Re: State of the overlay tree branch?

[Stefan Monnier]

> after finding that the feature/noverlay branch does wonders for my editing
> experience[1], I'd like to reinvigorate the discussion on its inclusion into
> master.

While I also hope that branch can be merged soon, I've installed a patch
into Emacs's `master` which should hopefully solve your
immediate problems.


        Stefan

Re: State of the overlay tree branch?

[Sebastian Sturm]

thank you, the master branch now handles my use case a lot better than 
before

On 03/26/2018 03:06 PM, Stefan Monnier wrote:
>> after finding that the feature/noverlay branch does wonders for my editing
>> experience[1], I'd like to reinvigorate the discussion on its inclusion into
>> master.
> 
> While I also hope that branch can be merged soon, I've installed a patch
> into Emacs's `master` which should hopefully solve your
> immediate problems.
> 
> 
>          Stefan
> 
> 

RE: State of the overlay tree branch?

[Drew Adams]

> If lsp-mode/lsp-ui needs a fast line counter, one can easily be
> provided by exposing find_newline to Lisp.  IME, it's lightning-fast,
> and should run circles around count-lines (used by line-number-at-pos).

Having a fast line counter in Elisp would be terrific.

Re: State of the overlay tree branch?

[Stefan Monnier]

>> If lsp-mode/lsp-ui needs a fast line counter, one can easily be
>> provided by exposing find_newline to Lisp.  IME, it's lightning-fast,
>> and should run circles around count-lines (used by line-number-at-pos).
> Having a fast line counter in Elisp would be terrific.

It should be pretty easy to provide such a thing by relying on a cache
of the last call.  Tho Sebastian's experience seems to indicate that the
current code doesn't only suffer from the time to count LF but also from
the time to process the markers.

I seem to remember someone else experiencing a similar problem and
suggesting that the problem lies in the charpos_to_bytepos (and/or
bytepos_to_charpos) conversion function, which iterates through all the
markers to try and find a "nearby" marker (because markers keep track
of both their bytepos and their charpos).  Looking for a nearby marker
to avoid scanning the whole buffer is a good idea in many cases, but not
if scanning the list of markers takes more time than scanning the
whole buffer.


        Stefan

Re: State of the overlay tree branch?

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Date: Sun, 18 Mar 2018 21:33:05 -0400
> 
> >> If lsp-mode/lsp-ui needs a fast line counter, one can easily be
> >> provided by exposing find_newline to Lisp.  IME, it's lightning-fast,
> >> and should run circles around count-lines (used by line-number-at-pos).
> > Having a fast line counter in Elisp would be terrific.
> 
> It should be pretty easy to provide such a thing by relying on a cache
> of the last call.

This is already coded, see display_count_lines.  That's what the
native line-number display uses.  Exposing it to Lisp should be easy.
But I don't believe it could be orders of magnitude faster than
count-lines, even though it doesn't need to convert character position
to byte position.

I'm guessing something entirely different and unrelated to
line-counting per se is at work here.

> Tho Sebastian's experience seems to indicate that the
> current code doesn't only suffer from the time to count LF but also from
> the time to process the markers.

Not sure what marker processing did you have in mind.  Can you
elaborate?

> I seem to remember someone else experiencing a similar problem and
> suggesting that the problem lies in the charpos_to_bytepos (and/or
> bytepos_to_charpos) conversion function, which iterates through all the
> markers to try and find a "nearby" marker (because markers keep track
> of both their bytepos and their charpos).  Looking for a nearby marker
> to avoid scanning the whole buffer is a good idea in many cases, but not
> if scanning the list of markers takes more time than scanning the
> whole buffer.

But find_newline doesn't look for markers, and it converts character
to byte position just 2 times.  Or am I missing something?

Re: State of the overlay tree branch?

[Stefan Monnier]

>> It should be pretty easy to provide such a thing by relying on a cache
>> of the last call.
> This is already coded, see display_count_lines.

I don't see any cache in display_count_lines but yes, the code that uses
display_count_lines does do such caching and we could/should expose it
to Lisp.

In nlinum.el I also have something similar (called
nlinum--line-number-at-pos).

> But I don't believe it could be orders of magnitude faster than
> count-lines, even though it doesn't need to convert character position
> to byte position.

Scanning from the last used position can be *very* different from
scanning from point-min.  So yes, it can be orders of magnitude faster
(I wrote nlinum--line-number-at-pos for that reason: I sadly didn't
write down the test case I used back then, but the difference was
very significant).

> I'm guessing something entirely different and unrelated to
> line-counting per se is at work here.

Agreed.

>> Tho Sebastian's experience seems to indicate that the
>> current code doesn't only suffer from the time to count LF but also from
>> the time to process the markers.
> Not sure what marker processing did you have in mind.  Can you
> elaborate?

The

  for (tail = BUF_MARKERS (b); tail; tail = tail->next)

loop in buf_charpos_to_bytepos and buf_bytepos_to_charpos.

> But find_newline doesn't look for markers, and it converts character
> to byte position just 2 times.  Or am I missing something?

The idea is that the above loop (even if called only twice) might be
sufficient to make line-number-at-pos take 0.2s.

I don't know that it's the culprit, I'm just mentioning that
possibility, since noverlays removes all the overlay-induced markers
which would significantly reduce the number of markers over which the
above loops.

Note that those loops stop as soon as we're within 50 chars of the goal,
and they also stop as soon as there's no non-ascii char between the
"best bounds so far".

So for them to cause the slow down seen here, we'd need not only
a very large number of markers but also additional conditions that might
not be very likely.
But it's still a possibility.


        Stefan

Re: State of the overlay tree branch?

[Eli Zaretskii]

> From: Stefan Monnier <monnier@IRO.UMontreal.CA>
> Cc: emacs-devel@gnu.org
> Date: Mon, 19 Mar 2018 08:29:40 -0400
> 
> > But I don't believe [display_count_lines] could be orders of
> > magnitude faster than count-lines, even though it doesn't need to
> > convert character position to byte position.
> 
> Scanning from the last used position can be *very* different from
> scanning from point-min.  So yes, it can be orders of magnitude faster

Well, in my measurements it's already very fast.  I don't understand
why the OP sees times that are 10 times slower.

> The
> 
>   for (tail = BUF_MARKERS (b); tail; tail = tail->next)
> 
> loop in buf_charpos_to_bytepos and buf_bytepos_to_charpos.
> 
> > But find_newline doesn't look for markers, and it converts character
> > to byte position just 2 times.  Or am I missing something?
> 
> The idea is that the above loop (even if called only twice) might be
> sufficient to make line-number-at-pos take 0.2s.

I very much doubt that loop could take such a long time.  And running
a benchmark 1000 times means that the 2nd through 1000th iteration
find the mapping much faster, probably bypassing the loop entirely.

> So for them to cause the slow down seen here, we'd need not only
> a very large number of markers but also additional conditions that might
> not be very likely.
> But it's still a possibility.

I'll believe it when I see it.

Re: State of the overlay tree branch?

[Stefan Monnier]

>> The idea is that the above loop (even if called only twice) might be
>> sufficient to make line-number-at-pos take 0.2s.
> I very much doubt that loop could take such a long time.

I also find it unlikely.

> And running a benchmark 1000 times means that the 2nd through 1000th
> iteration find the mapping much faster, probably bypassing the
> loop entirely.

Quite likely.

BTW, when thinking about how to avoid this loop's worst case (regardless
if it's the source of the current problem), I was thinking that we could
probably make that worst case even less likely by replacing the
hardcoded "50" with a limit that grows as the loop progresses.

The patch below should make sure that the total number of iterations
(through markers + through chars) is no more than 2*buffer-size, no matter
how many markers there are.
[ Rather than incrementing by 1 we should ideally increment by
  a number that corresponds to how much slower is each iteration through
  markers compared to the iteration through chars, but I have no idea
  what that number would typically be.  ]

WDYT?


        Stefan


diff --git a/src/marker.c b/src/marker.c
index f61701f2f6..bfe6de486e 100644
--- a/src/marker.c
+++ b/src/marker.c
@@ -141,6 +141,7 @@ buf_charpos_to_bytepos (struct buffer *b, ptrdiff_t charpos)
   struct Lisp_Marker *tail;
   ptrdiff_t best_above, best_above_byte;
   ptrdiff_t best_below, best_below_byte;
+  ptrdiff_t distance = 50;
 
   eassert (BUF_BEG (b) <= charpos && charpos <= BUF_Z (b));
 
@@ -180,8 +181,10 @@ buf_charpos_to_bytepos (struct buffer *b, ptrdiff_t charpos)
       /* If we are down to a range of 50 chars,
 	 don't bother checking any other markers;
 	 scan the intervening chars directly now.  */
-      if (best_above - best_below < 50)
+      if (best_above - best_below < distance)
 	break;
+      else
+        distance++;
     }
 
   /* We get here if we did not exactly hit one of the known places.
@@ -293,6 +296,7 @@ buf_bytepos_to_charpos (struct buffer *b, ptrdiff_t bytepos)
   struct Lisp_Marker *tail;
   ptrdiff_t best_above, best_above_byte;
   ptrdiff_t best_below, best_below_byte;
+  ptrdiff_t distance = 50;
 
   eassert (BUF_BEG_BYTE (b) <= bytepos && bytepos <= BUF_Z_BYTE (b));
 
@@ -323,8 +327,10 @@ buf_bytepos_to_charpos (struct buffer *b, ptrdiff_t bytepos)
       /* If we are down to a range of 50 chars,
 	 don't bother checking any other markers;
 	 scan the intervening chars directly now.  */
-      if (best_above - best_below < 50)
+      if (best_above - best_below < distance)
 	break;
+      else
+        distance++;
     }
 
   /* We get here if we did not exactly hit one of the known places.

Re: State of the overlay tree branch?

[Eli Zaretskii]

> From: Stefan Monnier <monnier@IRO.UMontreal.CA>
> Cc: emacs-devel@gnu.org
> Date: Mon, 19 Mar 2018 09:43:12 -0400
> 
> BTW, when thinking about how to avoid this loop's worst case (regardless
> if it's the source of the current problem), I was thinking that we could
> probably make that worst case even less likely by replacing the
> hardcoded "50" with a limit that grows as the loop progresses.
> 
> The patch below should make sure that the total number of iterations
> (through markers + through chars) is no more than 2*buffer-size, no matter
> how many markers there are.
> [ Rather than incrementing by 1 we should ideally increment by
>   a number that corresponds to how much slower is each iteration through
>   markers compared to the iteration through chars, but I have no idea
>   what that number would typically be.  ]
> 
> WDYT?

Could be a good idea, but I suggest to time its improvement before we
decide.  I've seen a few surprises in that area.

Re: State of the overlay tree branch?

[Stefan Monnier]

> Could be a good idea, but I suggest to time its improvement before we
> decide.  I've seen a few surprises in that area.

I see some speed up in my artificial test (where I create an insane
number of markers at point-min and then ask to goto-char to the middle
of a midsized buffer) but I can't see any impact whatsoever (neither
positive nor negative) in real tests (unsurprisingly).

I'd rather first have a non-artificial case where I can measure
a speed up.


        Stefan

Re: State of the overlay tree branch?

[Eli Zaretskii]

> Date: Sun, 18 Mar 2018 14:37:39 -0700 (PDT)
> From: Drew Adams <drew.adams@oracle.com>
> Cc: emacs-devel@gnu.org
> 
> > If lsp-mode/lsp-ui needs a fast line counter, one can easily be
> > provided by exposing find_newline to Lisp.  IME, it's lightning-fast,
> > and should run circles around count-lines (used by line-number-at-pos).
> 
> Having a fast line counter in Elisp would be terrific.

Actually, I see that line-number-at-pos, count-lines, and forward-line
should already be fast, as they do exactly what I thought, something I
failed to see originally.  If that's not "fast enough", a test case
showing the problem would be a good starting point.