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

Previous Next

Full log

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

From: Lars Ingebrigtsen <larsi <at> gnus.org>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 22763 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>,
 Keith David Bershatsky <esq <at> lawlist.com>
Subject: Re: bug#22763: 25.1.50; Feature Request -- A faster method to
 obtain line number at position.
Date: Sun, 07 Feb 2021 19:07:08 +0100

Lars Ingebrigtsen <larsi <at> gnus.org> writes:

> Stefan Monnier <monnier <at> iro.umontreal.ca> writes:
>
>> Why is it faster?
>>
>> Is it still always Θ(N) just with a smaller constant (if so, what makes
>> the constant smaller), or does it benefit from some kind of caching
>> (which I fail to see in the code) such that it's O(N) sometimes but much
>> faster other times (and if so, what are the cases that are sped up)?
>
> There's no caching.  I guess find_newline is just slow compared to
> display_count_lines?  (How many of these functions do we have in the C
> layer, anyway?)

Oh, I see that find_newline has a lot of caching going on, and the logic
isn't...  quite...  obvious.  I guess it's possible there may be cases
where the new implementation is slower, then?  I'm not sure how to
measure that, though -- it takes 10x more time to call the old
`line-number-at-pos' ten times, so if the function is supposed to cache
something, it's not doing that.

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

Previous Next

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