GNU bug report logs - #29439
Quadratic complexity in sweep_markers

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 29439 in the body.
You can then email your comments to 29439 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: Pip Cet <pipcet <at> gmail.com>
To: bug-gnu-emacs <at> gnu.org
Subject: Quadratic complexity in sweep_markers
Date: Sat, 25 Nov 2017 17:06:07 +0000

I've sat on this patch for way too long, and I think I previously
reported the issue, but I can't find it right now.

sweep_markers() calls unchain_marker() for every unmarked
marker. unchain_marker() walks the list of all markers in the buffer
for every one of them. This causes performance problems during GC,
since it's O(n^2) in the number of markers per buffer.

I've often noticed this dominating GC time, and in one instance
experienced a GC call that lasted for more than an hour.

At this point I think this is an actual bug, and one that severely
affects at least one user (me).  Please consider fixing this.

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

From: Noam Postavsky <npostavs <at> users.sourceforge.net>
To: Pip Cet <pipcet <at> gmail.com>
Cc: 29439 <at> debbugs.gnu.org
Subject: Re: bug#29439: Quadratic complexity in sweep_markers
Date: Sat, 25 Nov 2017 19:01:05 -0500

tags 24548 + patch
merge 29439 24548
quit

Pip Cet <pipcet <at> gmail.com> writes:

> I've sat on this patch for way too long, and I think I previously
> reported the issue, but I can't find it right now.

You can find your outstanding bugs here:
https://debbugs.gnu.org/cgi/pkgreport.cgi?submitter=pipcet%40gmail.com

Looks like it's #24548.

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

From: Pip Cet <pipcet <at> gmail.com>
To: Noam Postavsky <npostavs <at> users.sourceforge.net>
Cc: 29439 <at> debbugs.gnu.org
Subject: Re: bug#29439: Quadratic complexity in sweep_markers
Date: Sun, 26 Nov 2017 00:06:55 +0000

Thanks! It is.

Of course, with markers being relatively expensive anyway, a
doubly-linked list would also solve the issue and be easier to
understand.

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

From: Noam Postavsky <npostavs <at> users.sourceforge.net>
To: Pip Cet <pipcet <at> gmail.com>
Cc: 29439 <at> debbugs.gnu.org
Subject: Re: bug#29439: Quadratic complexity in sweep_markers
Date: Sat, 25 Nov 2017 19:13:38 -0500

Pip Cet <pipcet <at> gmail.com> writes:

> I've sat on this patch for way too long
              ^^^^

Did you mean to attach a new patch here, or is the one you have right
now the same as what you posted in #24548 earlier?

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

From: Pip Cet <pipcet <at> gmail.com>
To: Noam Postavsky <npostavs <at> users.sourceforge.net>
Cc: 29439 <at> debbugs.gnu.org
Subject: Re: bug#29439: Quadratic complexity in sweep_markers
Date: Mon, 27 Nov 2017 23:53:55 +0000

I did mean to attach a patch, but the most vexing thing happened: I
can't find it. I might have reset a git repository prematurely. I'll
try to recreate it and (more importantly, since this is GC code and I
definitely don't want to introduce GC bugs) test it, and get back to
you.

Previous Next

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