GNU bug report logs - #29439
Quadratic complexity in sweep_markers

Previous Next

Full log

View this message in rfc822 format

From: Pip Cet <pipcet <at> gmail.com>
To: 29439 <at> debbugs.gnu.org
Subject: bug#29439: 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.

Previous Next

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