Subject: bug#29439: Quadratic complexity in sweep_markers

From: Pip Cet <[email-masked]>
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.