* bug#29439: Quadratic complexity in sweep_markers
@ 2017-11-25 17:06 Pip Cet
2017-11-26 0:01 ` Noam Postavsky
2017-11-26 0:13 ` Noam Postavsky
0 siblings, 2 replies; 5+ messages in thread
From: Pip Cet @ 2017-11-25 17:06 UTC (permalink / raw)
To: 29439
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.
^ permalink raw reply [flat|nested] 5+ messages in thread
* bug#29439: Quadratic complexity in sweep_markers
2017-11-25 17:06 bug#29439: Quadratic complexity in sweep_markers Pip Cet
@ 2017-11-26 0:01 ` Noam Postavsky
2017-11-26 0:06 ` Pip Cet
2017-11-26 0:13 ` Noam Postavsky
1 sibling, 1 reply; 5+ messages in thread
From: Noam Postavsky @ 2017-11-26 0:01 UTC (permalink / raw)
To: Pip Cet; +Cc: 29439
tags 24548 + patch
merge 29439 24548
quit
Pip Cet <pipcet@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.
^ permalink raw reply [flat|nested] 5+ messages in thread
* bug#29439: Quadratic complexity in sweep_markers
2017-11-26 0:01 ` Noam Postavsky
@ 2017-11-26 0:06 ` Pip Cet
0 siblings, 0 replies; 5+ messages in thread
From: Pip Cet @ 2017-11-26 0:06 UTC (permalink / raw)
To: Noam Postavsky; +Cc: 29439
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.
^ permalink raw reply [flat|nested] 5+ messages in thread
* bug#29439: Quadratic complexity in sweep_markers
2017-11-25 17:06 bug#29439: Quadratic complexity in sweep_markers Pip Cet
2017-11-26 0:01 ` Noam Postavsky
@ 2017-11-26 0:13 ` Noam Postavsky
2017-11-27 23:53 ` Pip Cet
1 sibling, 1 reply; 5+ messages in thread
From: Noam Postavsky @ 2017-11-26 0:13 UTC (permalink / raw)
To: Pip Cet; +Cc: 29439
Pip Cet <pipcet@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?
^ permalink raw reply [flat|nested] 5+ messages in thread
* bug#29439: Quadratic complexity in sweep_markers
2017-11-26 0:13 ` Noam Postavsky
@ 2017-11-27 23:53 ` Pip Cet
0 siblings, 0 replies; 5+ messages in thread
From: Pip Cet @ 2017-11-27 23:53 UTC (permalink / raw)
To: Noam Postavsky; +Cc: 29439
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.
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2017-11-27 23:53 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2017-11-25 17:06 bug#29439: Quadratic complexity in sweep_markers Pip Cet
2017-11-26 0:01 ` Noam Postavsky
2017-11-26 0:06 ` Pip Cet
2017-11-26 0:13 ` Noam Postavsky
2017-11-27 23:53 ` Pip Cet
Code repositories for project(s) associated with this public inbox
https://git.savannah.gnu.org/cgit/emacs.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).