Re: State of the overlay tree branch?

[Eli Zaretskii <eliz@gnu.org>]

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