GNU bug report logs - #24548
25.2.50; Long GC delays with many non-detached markers (PATCH)

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 24548 in the body.
You can then email your comments to 24548 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: 25.2.50; Long GC delays with many non-detached markers (PATCH)
Date: Mon, 26 Sep 2016 15:12:10 +0000

[Message part 1 (text/plain, inline)]

This is an enhancement request for Emacs 25.2.

When many markers are created but not explicitly made to point to no
buffer after use, GC performance suffers severely. (Normal performance
(apparently) suffers a little. That's okay and I don't consider that a
problem.)  An automated test script that was in no way explicitly
designed to do so caused an Emacs session to be caught in garbage
collection for more than an hour.

The problem can be observed with this test code:
----------
(defvar l2 nil)

(defun loop (lim)
  (let ((i 0)
        (l nil))
    (while (< i lim)
      (push (copy-marker (point-max)) l)
      (push (copy-marker (point-min)) l)
      (push (copy-marker (point-max)) l2)
      (push (copy-marker (point-min)) l2)
      (setq i (1+ i)))))
----------

On this system, I'm seeing the following behaviour:

----------
$ time emacs -Q --load ~/git/ankol/emacs/loop.el --eval '(loop 10000)'
--eval '(garbage-collect)' --kill

real    0m2.556s
user    0m2.392s
sys    0m0.068s

$ time emacs -Q --load ~/git/ankol/emacs/loop.el --eval '(loop 20000)'
--eval '(garbage-collect)' --kill

real    0m19.576s
user    0m19.340s
sys    0m0.068s
----------

Upon investigation, it turns out that we keep a buffer's markers in a
singly-linked list, which we walk for every marker as it is
collected. That's O(n^2) (where n is the number of collected markers,
not that of markers that survive this garbage collection cycle); if
Emacs is made to grow to considerable size, this begins to dominate and
the hour-long GC problem appears.

This happened to me while testing a new programming language mode that
has a number of interactive commands that transform code without
changing its semantics; in order to make sure the transformations
weren't doing anything wrong, I ran them automatedly in large numbers,
and that's when my test sessions would appear to freeze while caught in
GC.

I thought it would be very easy to modify the code to avoid the problem;
it was a bit harder than I thought, because the GC mark bit is not
equivalent to "this object survives the current GC cycle". In the
attached patch, I ended up sacrificing one more bit to mean precisely
that, so we can walk a buffer's marker list once and unchain all
collected markers. If there's a better way of telling whether a marker
is due to be collected in the current GC cycle, I'd be happy to modify
the code.  (I tried mem_find and PURE_P, but there appear to be some
additional cases that are missed by that approach.)

As always, the patch is merely a suggestion.  However, it improves
performance (of the test code above and the actual test case) so
drastically that I think it is a good idea to fix this problem.

In GNU Emacs 25.2.50.19 (x86_64-pc-linux-gnu, X toolkit, Xaw scroll bars)
 of 2016-09-26 built on amygdala
Repository revision: 5ee56c4613e9380dbbe4bbaa97b29dd377e2134c
Windowing system distributor 'The X.Org Foundation', version 11.0.11804000
System Description:    Debian GNU/Linux unstable (sid)

Recent messages:
For information about GNU Emacs and the GNU system, type C-h C-a.

Configured features:
XPM JPEG TIFF GIF PNG SOUND DBUS GSETTINGS NOTIFY GNUTLS LIBXML2
FREETYPE XFT ZLIB TOOLKIT_SCROLL_BARS LUCID X11

Important settings:
  value of $LANG: en_US.UTF-8
  locale-coding-system: utf-8-unix

Major mode: Lisp Interaction

Minor modes in effect:
  tooltip-mode: t
  global-eldoc-mode: t
  electric-indent-mode: t
  mouse-wheel-mode: t
  tool-bar-mode: t
  menu-bar-mode: t
  file-name-shadow-mode: t
  global-font-lock-mode: t
  font-lock-mode: t
  blink-cursor-mode: t
  auto-composition-mode: t
  auto-encryption-mode: t
  auto-compression-mode: t
  line-number-mode: t
  transient-mark-mode: t

Load-path shadows:
None found.

Features:
(shadow sort mail-extr emacsbug message subr-x puny seq byte-opt gv
bytecomp byte-compile cl-extra help-mode cconv cl-loaddefs pcase cl-lib
dired dired-loaddefs format-spec rfc822 mml easymenu mml-sec
password-cache epa derived epg epg-config gnus-util rmail rmail-loaddefs
mm-decode mm-bodies mm-encode mail-parse rfc2231 mailabbrev gmm-utils
mailheader sendmail rfc2047 rfc2045 ietf-drums mm-util mail-prsvr
mail-utils time-date mule-util tooltip eldoc electric uniquify
ediff-hook vc-hooks lisp-float-type mwheel term/x-win x-win
term/common-win x-dnd tool-bar dnd fontset image regexp-opt fringe
tabulated-list newcomment elisp-mode lisp-mode prog-mode register page
menu-bar rfn-eshadow timer select scroll-bar mouse jit-lock font-lock
syntax facemenu font-core term/tty-colors frame cl-generic cham georgian
utf-8-lang misc-lang vietnamese tibetan thai tai-viet lao korean
japanese eucjp-ms cp51932 hebrew greek romanian slovak czech european
ethiopic indian cyrillic chinese charscript case-table epa-hook
jka-cmpr-hook help simple abbrev obarray minibuffer cl-preloaded nadvice
loaddefs button faces cus-face macroexp files text-properties overlay
sha1 md5 base64 format env code-pages mule custom widget
hashtable-print-readable backquote dbusbind inotify dynamic-setting
system-font-setting font-render-setting x-toolkit x multi-tty
make-network-process emacs)

Memory information:
((conses 16 96543 9103)
 (symbols 48 20425 0)
 (miscs 40 47 168)
 (strings 32 18288 5117)
 (string-bytes 1 571191)
 (vectors 16 13407)
 (vector-slots 8 447852 3741)
 (floats 8 185 69)
 (intervals 56 221 0)
 (buffers 976 11))

[emacs-bug-001-002.diff (text/plain, attachment)]

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

From: Stefan Monnier <monnier <at> IRO.UMontreal.CA>
To: Pip Cet <pipcet <at> gmail.com>
Cc: 24548 <at> debbugs.gnu.org
Subject: Re: bug#24548: 25.2.50;
 Long GC delays with many non-detached markers (PATCH)
Date: Fri, 23 Mar 2018 09:55:15 -0400

> I thought it would be very easy to modify the code to avoid the problem;
> it was a bit harder than I thought, because the GC mark bit is not
> equivalent to "this object survives the current GC cycle".

Could you give a bit more details about what you mean by that?

During the mark phase, indeed the markbit only says "if true then this
object won't be GC'd but if false than maybe it's only because we
haven't finished marking".  Is that what you're referring to?

But if we call unchain_collected_markers from within the sweep phase
(e.g. on every buffer we find), `gcmarkbit` should be
sufficient/reliable.  Or am I missing something?


        Stefan

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

From: Stefan Monnier <monnier <at> IRO.UMontreal.CA>
To: Pip Cet <pipcet <at> gmail.com>
Cc: 24548 <at> debbugs.gnu.org
Subject: Re: bug#24548: 25.2.50;
 Long GC delays with many non-detached markers (PATCH)
Date: Fri, 23 Mar 2018 10:22:18 -0400

> But if we call unchain_collected_markers from within the sweep phase
> (e.g. on every buffer we find), `gcmarkbit` should be
> sufficient/reliable.  Or am I missing something?

At least the patch below seems to work as well.


        Stefan


diff --git a/src/alloc.c b/src/alloc.c
index da01173fba..369592d70e 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -7095,7 +7091,9 @@ sweep_misc (void)
           if (!mblk->markers[i].m.u_any.gcmarkbit)
             {
               if (mblk->markers[i].m.u_any.type == Lisp_Misc_Marker)
-                unchain_marker (&mblk->markers[i].m.u_marker);
+                /* Make sure markers have been unchained from their buffer
+                   in sweep_buffer before we collect them.  */
+                eassert (!mblk->markers[i].m.u_marker.buffer);
               else if (mblk->markers[i].m.u_any.type == Lisp_Misc_Finalizer)
                 unchain_finalizer (&mblk->markers[i].m.u_finalizer);
 #ifdef HAVE_MODULES
@@ -7142,6 +7140,23 @@ sweep_misc (void)
   total_free_markers = num_free;
 }
 
+/* Remove BUFFER's markers that are due to be swept.  This is needed since
+   we treat BUF_MARKERS and markers's `next' field as weak pointers.  */
+static void
+unchain_dead_markers (struct buffer *buffer)
+{
+  struct Lisp_Marker *this, **prev = &BUF_MARKERS (buffer);
+
+  while ((this = *prev))
+    if (this->gcmarkbit)
+      prev = &this->next;
+    else
+      {
+        this->buffer = NULL;
+        *prev = this->next;
+      }
+}
+
 NO_INLINE /* For better stack traces */
 static void
 sweep_buffers (void)
@@ -7160,6 +7175,7 @@ sweep_buffers (void)
         VECTOR_UNMARK (buffer);
         /* Do not use buffer_(set|get)_intervals here.  */
         buffer->text->intervals = balance_intervals (buffer->text->intervals);
+        unchain_dead_markers (buffer);
         total_buffers++;
         bprev = &buffer->next;
       }
@@ -7179,8 +7195,8 @@ gc_sweep (void)
   sweep_floats ();
   sweep_intervals ();
   sweep_symbols ();
-  sweep_misc ();
   sweep_buffers ();
+  sweep_misc ();
   sweep_vectors ();
   check_string_bytes (!noninteractive);
 }

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

From: Pip Cet <pipcet <at> gmail.com>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 24548 <at> debbugs.gnu.org
Subject: Re: bug#24548: 25.2.50;
 Long GC delays with many non-detached markers (PATCH)
Date: Fri, 23 Mar 2018 15:10:26 +0000

I'm afraid I can't make sense of my earlier comment, so please ignore
it. There's nothing I can think of today that would prevent your patch
from working, so if it does work that would fix the bug.

Message #23 received at 24548-done <at> debbugs.gnu.org (full text, mbox):

From: Stefan Monnier <monnier <at> IRO.UMontreal.CA>
To: 24548-done <at> debbugs.gnu.org
Cc: Pip Cet <pipcet <at> gmail.com>
Subject: Re: bug#24548: 25.2.50;
 Long GC delays with many non-detached markers (PATCH)
Date: Fri, 23 Mar 2018 11:11:00 -0400

Version: 27.1

> At least the patch below seems to work as well.

Yes, I'm sufficiently confident that I installed it into master.


        Stefan

Previous Next

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