GNU bug report logs - #35675
27.0.50; Is line-number-at-pos unnecessarily slow?

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 35675 in the body.
You can then email your comments to 35675 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Alex Branham <alex.branham <at> gmail.com>
To: bug-gnu-emacs <at> gnu.org
Subject: 27.0.50; Is line-number-at-pos unnecessarily slow?
Date: Fri, 10 May 2019 15:55:09 -0500

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

Message #8 received at 35675 <at> debbugs.gnu.org (full text, mbox):

From: Eli Zaretskii <eliz <at> gnu.org>
To: Alex Branham <alex.branham <at> gmail.com>
Cc: 35675 <at> debbugs.gnu.org
Subject: Re: bug#35675: 27.0.50; Is line-number-at-pos unnecessarily slow?
Date: Sat, 11 May 2019 09:03:14 +0300

> From: Alex Branham <alex.branham <at> 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.

Message #11 received at 35675 <at> debbugs.gnu.org (full text, mbox):

From: "Basil L. Contovounesios" <contovob <at> tcd.ie>
To: Alex Branham <alex.branham <at> gmail.com>
Cc: 35675 <at> debbugs.gnu.org
Subject: Re: bug#35675: 27.0.50; Is line-number-at-pos unnecessarily slow?
Date: Sat, 11 May 2019 21:36:59 +0100

Alex Branham <alex.branham <at> 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

Message #16 received at 35675-done <at> debbugs.gnu.org (full text, mbox):

From: Alex Branham <alex.branham <at> gmail.com>
To: "Basil L. Contovounesios" <contovob <at> tcd.ie>
Cc: 35675-done <at> debbugs.gnu.org
Subject: Re: bug#35675: 27.0.50; Is line-number-at-pos unnecessarily slow?
Date: Tue, 14 May 2019 07:34:24 -0500

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

> Alex Branham <alex.branham <at> 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

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.