bug#22763: 25.1.50; Feature Request -- A faster method to obtain line number at position.

[Eli Zaretskii <eliz@gnu.org>]

> From: Lars Ingebrigtsen <larsi@gnus.org>
> Cc: 22763@debbugs.gnu.org,  esq@lawlist.com,  monnier@iro.umontreal.ca
> Date: Sun, 07 Feb 2021 19:23:53 +0100
> 
> Lars Ingebrigtsen <larsi@gnus.org> writes:
> 
> >> find_newline does the same as display_count_lines: it calls memchr.
> >> But it also maintains a newline cache.  If you disable that cache (by
> >> turning of cache-long-scans), you might see a different speedup.
> >
> > Shouldn't the cache speed things up?
> 
> No, you're right -- if I set `cache-long-scans' to nil and
> `line-number-at-pos' in Emacs 27 becomes ~8x faster in my test, which is
> currently
> 
> (with-temp-buffer
>   (setq cache-long-scans nil)
>   (dotimes (_ 1000)
>     (insert-file-contents "~/src/emacs/trunk/src/ChangeLog.11")
>     (goto-char (point-max)))
>   (benchmark-run 1
>     (dotimes (i 1000)
>       (goto-char (/ (buffer-size) 1000))
>       (line-number-at-pos (point)))))

This benchmark is not very fair.  For starters, 1 thousands of
ChangeLog.11's size is on line 31 of the file, so you have just 31
lines to count.  And those lines are quite short.

Try counting a much larger number of lines, and make the lines
longer.  Then you may see different results.

It is also interesting to compare the first iterations with all the
rest, when the newlines are already cached.

But in general, the raw speed of memchr is very hard to beat,
especially given that using the cache requires calls to CHAR_TO_BYTE
and BYTE_TO_CHAR, which can be expensive.