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

[Lars Ingebrigtsen <larsi@gnus.org>]

Eli Zaretskii <eliz@gnu.org> writes:

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

Oops, that's not what I meant to test...  I meant to skip to 1000 places
in the buffer, so that's:

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

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

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?

(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?
Is that a bug?  I haven't actually read the code in the function
closely.

> 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?  And in buffers with lines with
normal line lengths, it's 10x slower?  That sounds like a rather drastic
trade-off.

I'll try to whip up a benchmark with really long lines and see what
happens.

Eli Zaretskii <eliz@gnu.org> writes:

> Oops, I now see that you insert the file 1000 times, so it's 31
> thousand lines.  Still, not a very large number, and the lines are
> very short.

Yes, short lines, but the ChangeLog file is pretty typical...  

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no