GNU bug report logs - #24012
25.0.95; forward-comment backwards takes O(n^2)

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 24012 in the body.
You can then email your comments to 24012 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: Leo Liu <sdl.web <at> gmail.com>
To: bug-gnu-emacs <at> gnu.org
Subject: 25.0.95; forward-comment backwards takes O(n^2)
Date: Sun, 17 Jul 2016 19:04:18 +0800

[Message part 1 (text/plain, inline)]

1. Use the attached file as an example, open it in emacs in ruby-mode
2. Move point to end of buffer and eval (forward-comment (- (point)))

The last step takes about 0.25 seconds on my MacBook 3 GHz Intel Core
i7. If you double the lines of comments, the time increase by 4 folds.

Any idea why forward-comment backwards is so slow?

Leo

[tt.rb (text/plain, attachment)]

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

From: Eli Zaretskii <eliz <at> gnu.org>
To: Leo Liu <sdl.web <at> gmail.com>
Cc: 24012 <at> debbugs.gnu.org
Subject: Re: bug#24012: 25.0.95; forward-comment backwards takes O(n^2)
Date: Sun, 17 Jul 2016 15:12:01 +0300

> From: Leo Liu <sdl.web <at> gmail.com>
> Date: Sun, 17 Jul 2016 19:04:18 +0800
> 
> 1. Use the attached file as an example, open it in emacs in ruby-mode
> 2. Move point to end of buffer and eval (forward-comment (- (point)))
> 
> The last step takes about 0.25 seconds on my MacBook 3 GHz Intel Core
> i7. If you double the lines of comments, the time increase by 4 folds.
> 
> Any idea why forward-comment backwards is so slow?

Because search functions cannot really search backwards?

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

From: Andreas Röhler <andreas.roehler <at> easy-emacs.de>
To: bug-gnu-emacs <at> gnu.org
Subject: Re: bug#24012: 25.0.95; forward-comment backwards takes O(n^2)
Date: Sun, 17 Jul 2016 15:39:17 +0200

On 17.07.2016 13:04, Leo Liu wrote:
> 1. Use the attached file as an example, open it in emacs in ruby-mode
> 2. Move point to end of buffer and eval (forward-comment (- (point)))
>
> The last step takes about 0.25 seconds on my MacBook 3 GHz Intel Core
> i7. If you double the lines of comments, the time increase by 4 folds.
>
> Any idea why forward-comment backwards is so slow?
>
> Leo
>

With last line

### @end (forward-comment (- (point)))

evaluation last expression doesn't move backward at all, returns nil

GNU Emacs 25.0.95.1 (i686-pc-linux-gnu, GTK+ Version 3.14.5) of 2016-06-12

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

From: Leo Liu <sdl.web <at> gmail.com>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: 24012 <at> debbugs.gnu.org
Subject: Re: bug#24012: 25.0.95; forward-comment backwards takes O(n^2)
Date: Mon, 18 Jul 2016 08:15:44 +0800

On 2016-07-17 15:12 +0300, Eli Zaretskii wrote:
> Because search functions cannot really search backwards?

But by changing the major mode to octave-mode you get a 12 times speedup
without doing anything.

Leo

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

From: Eli Zaretskii <eliz <at> gnu.org>
To: Leo Liu <sdl.web <at> gmail.com>
Cc: 24012 <at> debbugs.gnu.org
Subject: Re: bug#24012: 25.0.95; forward-comment backwards takes O(n^2)
Date: Mon, 18 Jul 2016 05:36:10 +0300

> From:  Leo Liu <sdl.web <at> gmail.com>
> Cc: 24012 <at> debbugs.gnu.org
> Date: Mon, 18 Jul 2016 08:15:44 +0800
> 
> On 2016-07-17 15:12 +0300, Eli Zaretskii wrote:
> > Because search functions cannot really search backwards?
> 
> But by changing the major mode to octave-mode you get a 12 times speedup
> without doing anything.

Profile it.  One guess is that the different comment syntax somehow
causes this.  But that's a guess.

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

From: Leo Liu <sdl.web <at> gmail.com>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: 24012 <at> debbugs.gnu.org
Subject: Re: bug#24012: 25.0.95; forward-comment backwards takes O(n^2)
Date: Mon, 18 Jul 2016 11:05:01 +0800

On 2016-07-18 05:36 +0300, Eli Zaretskii wrote:
> Profile it.  One guess is that the different comment syntax somehow
> causes this.  But that's a guess.

How to profile it?

Before reporting this bug I have been trying profiler and elp and came
to the conclusion that forward-comment was the issue. How do you go
further than forward-comment which is in C which I only have limited
experience with?

Leo

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

From: Eli Zaretskii <eliz <at> gnu.org>
To: Leo Liu <sdl.web <at> gmail.com>
Cc: 24012 <at> debbugs.gnu.org
Subject: Re: bug#24012: 25.0.95; forward-comment backwards takes O(n^2)
Date: Mon, 18 Jul 2016 17:34:32 +0300

> From:  Leo Liu <sdl.web <at> gmail.com>
> Cc: 24012 <at> debbugs.gnu.org
> Date: Mon, 18 Jul 2016 11:05:01 +0800
> 
> On 2016-07-18 05:36 +0300, Eli Zaretskii wrote:
> > Profile it.  One guess is that the different comment syntax somehow
> > causes this.  But that's a guess.
> 
> How to profile it?
> 
> Before reporting this bug I have been trying profiler and elp and came
> to the conclusion that forward-comment was the issue. How do you go
> further than forward-comment which is in C which I only have limited
> experience with?

I meant a comparative profile between the two major modes.

As for profiling primitives, there's 'prof' that can make wonders, if
you are using a platform which it supports.

Thanks.

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

From: Dmitry Gutov <dgutov <at> yandex.ru>
To: Leo Liu <sdl.web <at> gmail.com>, 24012 <at> debbugs.gnu.org
Subject: Re: bug#24012: 25.0.95; forward-comment backwards takes O(n^2)
Date: Mon, 25 Dec 2017 17:24:38 +0200

On 7/17/16 2:04 PM, Leo Liu wrote:
> 
> 1. Use the attached file as an example, open it in emacs in ruby-mode
> 2. Move point to end of buffer and eval (forward-comment (- (point)))
> 
> The last step takes about 0.25 seconds on my MacBook 3 GHz Intel Core
> i7. If you double the lines of comments, the time increase by 4 folds.

FWIW, it looks fixed in the master branch now.

Probably by 14b95587520959c5b54356547a0a69932a9bb480, so no idea what 
exactly was causing it.

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

From: Stefan Kangas <stefan <at> marxist.se>
To: Dmitry Gutov <dgutov <at> yandex.ru>
Cc: 24012 <at> debbugs.gnu.org, Leo Liu <sdl.web <at> gmail.com>
Subject: Re: bug#24012: 25.0.95; forward-comment backwards takes O(n^2)
Date: Sun, 29 Sep 2019 07:15:22 +0200

Dmitry Gutov <dgutov <at> yandex.ru> writes:

> On 7/17/16 2:04 PM, Leo Liu wrote:
>> 1. Use the attached file as an example, open it in emacs in ruby-mode
>> 2. Move point to end of buffer and eval (forward-comment (- (point)))
>> The last step takes about 0.25 seconds on my MacBook 3 GHz Intel Core
>> i7. If you double the lines of comments, the time increase by 4 folds.
>
> FWIW, it looks fixed in the master branch now.
>
> Probably by 14b95587520959c5b54356547a0a69932a9bb480, so no idea what exactly
> was causing it.

Indeed.  I only see O(n) on current master -- that is, if I use the
source code from the original report, and double the amount of lines
by C-x h M-w C-y, the time to evaluate this expression in a buffer
only doubles:

    (progn (end-of-buffer) (forward-comment (- (point))))

Leo, are you still seeing this issue?  If I don't hear back within a
couple of weeks, I'll just assume that this has been fixed and close
this bug.

Best regards,
Stefan Kangas

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

From: Stefan Kangas <stefan <at> marxist.se>
To: Dmitry Gutov <dgutov <at> yandex.ru>
Cc: 24012-done <at> debbugs.gnu.org, Leo Liu <sdl.web <at> gmail.com>
Subject: Re: bug#24012: 25.0.95; forward-comment backwards takes O(n^2)
Date: Fri, 08 Nov 2019 04:59:14 +0100

Stefan Kangas <stefan <at> marxist.se> writes:

> Dmitry Gutov <dgutov <at> yandex.ru> writes:
>
>> On 7/17/16 2:04 PM, Leo Liu wrote:
>>> 1. Use the attached file as an example, open it in emacs in ruby-mode
>>> 2. Move point to end of buffer and eval (forward-comment (- (point)))
>>> The last step takes about 0.25 seconds on my MacBook 3 GHz Intel Core
>>> i7. If you double the lines of comments, the time increase by 4 folds.
>>
>> FWIW, it looks fixed in the master branch now.
>>
>> Probably by 14b95587520959c5b54356547a0a69932a9bb480, so no idea what exactly
>> was causing it.
>
> Indeed.  I only see O(n) on current master -- that is, if I use the
> source code from the original report, and double the amount of lines
> by C-x h M-w C-y, the time to evaluate this expression in a buffer
> only doubles:
>
>     (progn (end-of-buffer) (forward-comment (- (point))))
>
> Leo, are you still seeing this issue?  If I don't hear back within a
> couple of weeks, I'll just assume that this has been fixed and close
> this bug.

More information was requested, but none was given within 5 weeks, so
I'm closing this bug.  If this is still an issue, please reopen the
bug report.

Best regards,
Stefan Kangas

Previous Next

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