* 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 external index https://git.savannah.gnu.org/cgit/emacs.git https://git.savannah.gnu.org/cgit/emacs/org-mode.git This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.