Re: State of the overlay tree branch?

[Eli Zaretskii <eliz@gnu.org>]

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