bug#35675: 27.0.50; Is line-number-at-pos unnecessarily slow?

bug#35675: 27.0.50; Is line-number-at-pos unnecessarily slow?

[Alex Branham]

Hi all -

I ran into a bottleneck at line-number-at-pos in ESS's indentation
engine. line-number-at-pos basically regex searches forward for \n's and
counts them up. This can be slow in a large buffer. It looks like
someone else has ran into this issue as well.[1]

With the advent of display-line-numbers-mode, I imagine there's a C
implementation of line-number-at-pos. I imagine the C implementation is
faster. Does it make sense for line-number-at-pos to just use the C
implementation?

Thanks,
Alex

Footnotes:
[1]  https://fuco1.github.io/2018-08-12-WAR-STORY:-When-turning-to-the-profiler-turns-out-to-be-a-good-call.html

bug#35675: 27.0.50; Is line-number-at-pos unnecessarily slow?

[Eli Zaretskii]

> From: Alex Branham <alex.branham@gmail.com>
> Date: Fri, 10 May 2019 15:55:09 -0500
> 
> I ran into a bottleneck at line-number-at-pos in ESS's indentation
> engine. line-number-at-pos basically regex searches forward for \n's and
> counts them up. This can be slow in a large buffer. It looks like
> someone else has ran into this issue as well.[1]
> 
> With the advent of display-line-numbers-mode, I imagine there's a C
> implementation of line-number-at-pos. I imagine the C implementation is
> faster. Does it make sense for line-number-at-pos to just use the C
> implementation?

The C implementation was always there: it's what's behind the Lnn
display in the mode line.  display-line-numbers-mode just reuses that
fir its purposes, but basically invents nothing new in that
department.

The usual wisdom regarding line-number-at-pos is to use count-lines
instead, counting the number of lines since some previous line whose
number is recorded.  (By contrast, line-number-at-pos always starts
from BOB.)  For example, you could always have the line number of the
first line in the window in some variable, and recompute it only when
that line goes off the window.  If this strategy somehow doesn't work
in your case, please describe that use case in more detail, as IME it
is very rare (read: non-existent).

Using the C implementation we have from Lisp might not be as
straight-forward as you'd think, because it caches various values in
the window object, and relies on them being up-to-date.  Code that
runs during redisplay can rely on some assumption that Lisp cannot.
One obvious difficulty is that you may need your Lisp program to count
line in a buffer that isn't displayed in any window.

Therefore, my suggestion is to get back to the drawing board and
analyze your use case.  I'd be very surprised if a solution simpler
than just counting all the lines from BOB will not present itself.

bug#35675: 27.0.50; Is line-number-at-pos unnecessarily slow?

[Basil L. Contovounesios]

Alex Branham <alex.branham@gmail.com> writes:

> line-number-at-pos basically regex searches forward for \n's and
> counts them up.

It only does this (via count-lines) if selective-display is t, which is
deprecated and seldom used.  Otherwise it uses the value returned by
forward-line (defined in C), which calls find_newline, which AFAIK uses
the buffer's newline cache to some extent (I'm not familiar with its
implementation).

Either way, as Eli says, there's often an algorithmic solution to
slowness in uses of count-lines.

Thanks,

-- 
Basil

bug#35675: 27.0.50; Is line-number-at-pos unnecessarily slow?

[Alex Branham]

On Sat 11 May 2019 at 15:36, Basil L. Contovounesios <contovob@tcd.ie> wrote:

> Alex Branham <alex.branham@gmail.com> writes:
>
>> line-number-at-pos basically regex searches forward for \n's and
>> counts them up.
>
> It only does this (via count-lines) if selective-display is t, which is
> deprecated and seldom used.  Otherwise it uses the value returned by
> forward-line (defined in C), which calls find_newline, which AFAIK uses
> the buffer's newline cache to some extent (I'm not familiar with its
> implementation).

Thanks, I missed/misunderstood that part.

> Either way, as Eli says, there's often an algorithmic solution to
> slowness in uses of count-lines.

I'll take that advice and see if there's a more clever way to go about it.

Thanks again,
Alex