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 20:25:45 +0100
> 
> (with-temp-buffer
>   (dotimes (_ 1000)
>     (insert-file-contents "~/src/emacs/trunk/src/ChangeLog.11")
>     (goto-char (point-max)))
>   (benchmark-run 1
>     (dotimes (i 100)
>       (goto-char (* (/ (buffer-size) 100) i))
>       (line-number-at-pos (point)))))
> 
> (Adjusted down to 100, because it takes too long.)  Let's see...
> 
> Yup, still 10x faster.

This one traverses each 1/100th region of the file just once, no?

> OK, I've now bumped the benchmark-run to 10 (and decreased the buffer
> size by a factor of 10)...  let's see...  The new version takes exactly
> the same amount of time, of course...
> 
> And so does the old one.  Well, it's 10% faster in this?

10% or 10-fold?

> (with-temp-buffer
>   (dotimes (_ 100)
>     (insert-file-contents "~/src/emacs/trunk/src/ChangeLog.11")
>     (goto-char (point-max)))
>   (benchmark-run 10
>     (dotimes (i 100)
>       (goto-char (* (/ (buffer-size) 100) i))
>       (line-number-at-pos (point)))))
> 
> Hm.  I guess this doesn't update the newline cache in any useful way?

Why not?  It should.

> > 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.
> 
> So ... it's using the cache is only faster when we have monumentally
> long lines, since memchr is so fast?

Yes.

> And in buffers with lines with normal line lengths, it's 10x slower?

In my benchmarks some years ago it was about twice slower, not 10
times.