From unknown Wed Aug 20 05:18:00 2025 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-Mailer: MIME-tools 5.509 (Entity 5.509) Content-Type: text/plain; charset=utf-8 From: bug#24548 <24548@debbugs.gnu.org> To: bug#24548 <24548@debbugs.gnu.org> Subject: Status: 25.2.50; Long GC delays with many non-detached markers (PATCH) Reply-To: bug#24548 <24548@debbugs.gnu.org> Date: Wed, 20 Aug 2025 12:18:00 +0000 retitle 24548 25.2.50; Long GC delays with many non-detached markers (PATCH) reassign 24548 emacs submitter 24548 Pip Cet severity 24548 normal tag 24548 patch thanks From debbugs-submit-bounces@debbugs.gnu.org Mon Sep 26 11:14:12 2016 Received: (at submit) by debbugs.gnu.org; 26 Sep 2016 15:14:12 +0000 Received: from localhost ([127.0.0.1]:36558 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1boXbf-0001iV-Fd for submit@debbugs.gnu.org; Mon, 26 Sep 2016 11:14:12 -0400 Received: from eggs.gnu.org ([208.118.235.92]:50113) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1boXbc-0001iG-Cf for submit@debbugs.gnu.org; Mon, 26 Sep 2016 11:14:10 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1boXbU-000862-VF for submit@debbugs.gnu.org; Mon, 26 Sep 2016 11:14:03 -0400 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: * X-Spam-Status: No, score=1.3 required=5.0 tests=BAYES_50,FREEMAIL_FROM, RCVD_IN_SORBS_SPAM,T_DKIM_INVALID autolearn=disabled version=3.3.2 Received: from lists.gnu.org ([2001:4830:134:3::11]:35589) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1boXbU-00085J-Sy for submit@debbugs.gnu.org; Mon, 26 Sep 2016 11:14:00 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:41057) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1boXbS-0006rl-2W for bug-gnu-emacs@gnu.org; Mon, 26 Sep 2016 11:13:59 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1boXbM-000843-Qp for bug-gnu-emacs@gnu.org; Mon, 26 Sep 2016 11:13:56 -0400 Received: from mail-wm0-f44.google.com ([74.125.82.44]:37145) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1boXbM-00083r-FS for bug-gnu-emacs@gnu.org; Mon, 26 Sep 2016 11:13:52 -0400 Received: by mail-wm0-f44.google.com with SMTP id b130so154226993wmc.0 for ; Mon, 26 Sep 2016 08:13:52 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:from:date:message-id:subject:to; bh=5Ux3UkaEY4T2jP+lPp0jSMjAiMTj26w7bmVUP4fxSok=; b=avfbwlYRPLYkBnx6irzhlWDO6CClW6He9xUsaa/mpZQb7wpmhYJ81POfovulZZih9z rUZL0Jzd3w9AhvrENWHmtfjTsvQTM5oVZOv5iSxBKL1oiY9Q4jO+QkbUeZRWgmoNARXE ceVo7JCGj04Ii/dSs8mDcN7waUw1FUCO4tmVkZCSX8h5tRGV4r1U/WE+McZkrca0NKny +BlGQZ4owN4SSKSEmTTmZDwX6U0ngZdSBp3MG+1TCfTs8POcvmaoGyrdQj+qBV6FJcrn bgYd4pJO3ScNduZhjAdqydx67v6w4uD+deqK8PHFnGRIyYZb+kk6HEuaSKynPQMVOcky cl2A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=5Ux3UkaEY4T2jP+lPp0jSMjAiMTj26w7bmVUP4fxSok=; b=JmwJRq+2PXvjSeQ3GZvXUAev18ZK7pp+Urc0311t+e9q1OTRzngKYu6FHCjEpfKhGp 930drlnecOciyA8K832XCLUwMFJKhL5MnaX3tlGzOQnmFIU+tEIurUMXK/zUY9LrBq/c uVqoUpKTcYEKGb6qObC/017rKfrjY3/etiGkWLIySJi57tEgPv1A41+utPd5uwONN+bi sWqGk8mAHBrrle6tGwYcsTxTHEEpyULUtKxuCyiE595RcJUhe0jJxWAKIJnnHuFckz0S F29FqOJKNEQjL75yyd26TXAm6licZfSOeh4qDZdhV01OLj/Yu2Ech7pm1szrZPfizoX2 3GZA== X-Gm-Message-State: AA6/9Rm4gRO+RVhv9zcbYYRy1Qhps/blDNk52wtO259z4wCSMKTYyEOosoasesK//kjRZx7hoYtJoW1PRu5pSg== X-Received: by 10.194.22.136 with SMTP id d8mr1883429wjf.5.1474902771121; Mon, 26 Sep 2016 08:12:51 -0700 (PDT) MIME-Version: 1.0 Received: by 10.80.179.236 with HTTP; Mon, 26 Sep 2016 08:12:10 -0700 (PDT) From: Pip Cet Date: Mon, 26 Sep 2016 15:12:10 +0000 Message-ID: Subject: 25.2.50; Long GC delays with many non-detached markers (PATCH) To: bug-gnu-emacs@gnu.org Content-Type: multipart/mixed; boundary=047d7b5d5b82c10f25053d6a8f06 X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] [fuzzy] X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x X-Received-From: 2001:4830:134:3::11 X-Spam-Score: -3.5 (---) X-Debbugs-Envelope-To: submit X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.5 (---) --047d7b5d5b82c10f25053d6a8f06 Content-Type: text/plain; charset=UTF-8 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)) --047d7b5d5b82c10f25053d6a8f06 Content-Type: text/plain; charset=US-ASCII; name="emacs-bug-001-002.diff" Content-Disposition: attachment; filename="emacs-bug-001-002.diff" Content-Transfer-Encoding: base64 X-Attachment-Id: f_itk6ti1q0 ZGlmZiAtLWdpdCBhL3NyYy9hbGxvYy5jIGIvc3JjL2FsbG9jLmMKaW5kZXggNDFiMmY5ZS4uMWU5 MTg5YSAxMDA2NDQKLS0tIGEvc3JjL2FsbG9jLmMKKysrIGIvc3JjL2FsbG9jLmMKQEAgLTM2NzUs NiArMzY3NSw3IEBAIGFsbG9jYXRlX21pc2MgKGVudW0gTGlzcF9NaXNjX1R5cGUgdHlwZSkKICAg bWlzY19vYmplY3RzX2NvbnNlZCsrOwogICBYTUlTQ0FOWSAodmFsKS0+dHlwZSA9IHR5cGU7CiAg IFhNSVNDQU5ZICh2YWwpLT5nY21hcmtiaXQgPSAwOworICBYTUlTQ0FOWSAodmFsKS0+Z2Nzd2Vl cGJpdCA9IDA7CiAgIHJldHVybiB2YWw7CiB9CiAKQEAgLTY4OTMsNiArNjg5NCwyNCBAQCBzd2Vl cF9taXNjICh2b2lkKQogICBmb3IgKG1ibGsgPSBtYXJrZXJfYmxvY2s7IG1ibGs7IG1ibGsgPSAq bXByZXYpCiAgICAgewogICAgICAgcmVnaXN0ZXIgaW50IGk7CisKKyAgICAgIGZvciAoaSA9IDA7 IGkgPCBsaW07IGkrKykKKyAgICAgICAgeworICAgICAgICAgIGlmIChtYmxrLT5tYXJrZXJzW2ld Lm0udV9hbnkudHlwZSA9PSBMaXNwX01pc2NfTWFya2VyKQorICAgICAgICAgICAgeworICAgICAg ICAgICAgICBpZiAoIW1ibGstPm1hcmtlcnNbaV0ubS51X2FueS5nY21hcmtiaXQpCisgICAgICAg ICAgICAgICAgeworICAgICAgICAgICAgICAgICAgbWJsay0+bWFya2Vyc1tpXS5tLnVfbWFya2Vy Lmdjc3dlZXBiaXQgPSAxOworICAgICAgICAgICAgICAgIH0KKyAgICAgICAgICAgIH0KKyAgICAg ICAgfQorICAgICAgbGltID0gTUFSS0VSX0JMT0NLX1NJWkU7CisgICAgICBtcHJldiA9ICZtYmxr LT5uZXh0OworICAgIH0KKyAgbGltID0gbWFya2VyX2Jsb2NrX2luZGV4OworICBmb3IgKG1ibGsg PSBtYXJrZXJfYmxvY2s7IG1ibGs7IG1ibGsgPSAqbXByZXYpCisgICAgeworICAgICAgcmVnaXN0 ZXIgaW50IGk7CiAgICAgICBpbnQgdGhpc19mcmVlID0gMDsKIAogICAgICAgZm9yIChpID0gMDsg aSA8IGxpbTsgaSsrKQpAQCAtNjkwMCw3ICs2OTE5LDcgQEAgc3dlZXBfbWlzYyAodm9pZCkKICAg ICAgICAgICBpZiAoIW1ibGstPm1hcmtlcnNbaV0ubS51X2FueS5nY21hcmtiaXQpCiAgICAgICAg ICAgICB7CiAgICAgICAgICAgICAgIGlmIChtYmxrLT5tYXJrZXJzW2ldLm0udV9hbnkudHlwZSA9 PSBMaXNwX01pc2NfTWFya2VyKQotICAgICAgICAgICAgICAgIHVuY2hhaW5fbWFya2VyICgmbWJs ay0+bWFya2Vyc1tpXS5tLnVfbWFya2VyKTsKKyAgICAgICAgICAgICAgICB1bmNoYWluX2NvbGxl Y3RlZF9tYXJrZXJzKG1ibGstPm1hcmtlcnNbaV0ubS51X21hcmtlci5idWZmZXIpOwogICAgICAg ICAgICAgICBlbHNlIGlmIChtYmxrLT5tYXJrZXJzW2ldLm0udV9hbnkudHlwZSA9PSBMaXNwX01p c2NfRmluYWxpemVyKQogICAgICAgICAgICAgICAgIHVuY2hhaW5fZmluYWxpemVyICgmbWJsay0+ bWFya2Vyc1tpXS5tLnVfZmluYWxpemVyKTsKICNpZmRlZiBIQVZFX01PRFVMRVMKZGlmZiAtLWdp dCBhL3NyYy9saXNwLmggYi9zcmMvbGlzcC5oCmluZGV4IGY2NTNkODUuLjFhZjRjMzQgMTAwNjQ0 Ci0tLSBhL3NyYy9saXNwLmgKKysrIGIvc3JjL2xpc3AuaApAQCAtMjA0MCwxNCArMjA0MCwxNiBA QCBzdHJ1Y3QgTGlzcF9NaXNjX0FueQkJLyogU3VwZXJ0eXBlIG9mIGFsbCBNaXNjIHR5cGVzLiAg Ki8KIHsKICAgRU5VTV9CRiAoTGlzcF9NaXNjX1R5cGUpIHR5cGUgOiAxNjsJCS8qID0gTGlzcF9N aXNjXz8/PyAqLwogICBib29sX2JmIGdjbWFya2JpdCA6IDE7Ci0gIHVuc2lnbmVkIHNwYWNlciA6 IDE1OworICBib29sX2JmIGdjc3dlZXBiaXQgOiAxOworICB1bnNpZ25lZCBzcGFjZXIgOiAxNDsK IH07CiAKIHN0cnVjdCBMaXNwX01hcmtlcgogewogICBFTlVNX0JGIChMaXNwX01pc2NfVHlwZSkg dHlwZSA6IDE2OwkJLyogPSBMaXNwX01pc2NfTWFya2VyICovCiAgIGJvb2xfYmYgZ2NtYXJrYml0 IDogMTsKLSAgdW5zaWduZWQgc3BhY2VyIDogMTM7CisgIGJvb2xfYmYgZ2Nzd2VlcGJpdCA6IDE7 CisgIHVuc2lnbmVkIHNwYWNlciA6IDEyOwogICAvKiBUaGlzIGZsYWcgaXMgdGVtcG9yYXJpbHkg dXNlZCBpbiB0aGUgZnVuY3Rpb25zCiAgICAgIGRlY29kZS9lbmNvZGVfY29kaW5nX29iamVjdCB0 byByZWNvcmQgdGhhdCB0aGUgbWFya2VyIHBvc2l0aW9uCiAgICAgIG11c3QgYmUgYWRqdXN0ZWQg YWZ0ZXIgdGhlIGNvbnZlcnNpb24uICAqLwpAQCAtMzk3Niw2ICszOTc4LDcgQEAgZXh0ZXJuIHZv aWQgY2xlYXJfY2hhcnBvc19jYWNoZSAoc3RydWN0IGJ1ZmZlciAqKTsKIGV4dGVybiBwdHJkaWZm X3QgYnVmX2NoYXJwb3NfdG9fYnl0ZXBvcyAoc3RydWN0IGJ1ZmZlciAqLCBwdHJkaWZmX3QpOwog ZXh0ZXJuIHB0cmRpZmZfdCBidWZfYnl0ZXBvc190b19jaGFycG9zIChzdHJ1Y3QgYnVmZmVyICos IHB0cmRpZmZfdCk7CiBleHRlcm4gdm9pZCB1bmNoYWluX21hcmtlciAoc3RydWN0IExpc3BfTWFy a2VyICptYXJrZXIpOworZXh0ZXJuIHZvaWQgdW5jaGFpbl9jb2xsZWN0ZWRfbWFya2VycyAoc3Ry dWN0IGJ1ZmZlciAqYnVmZmVyKTsKIGV4dGVybiBMaXNwX09iamVjdCBzZXRfbWFya2VyX3Jlc3Ry aWN0ZWQgKExpc3BfT2JqZWN0LCBMaXNwX09iamVjdCwgTGlzcF9PYmplY3QpOwogZXh0ZXJuIExp c3BfT2JqZWN0IHNldF9tYXJrZXJfYm90aCAoTGlzcF9PYmplY3QsIExpc3BfT2JqZWN0LCBwdHJk aWZmX3QsIHB0cmRpZmZfdCk7CiBleHRlcm4gTGlzcF9PYmplY3Qgc2V0X21hcmtlcl9yZXN0cmlj dGVkX2JvdGggKExpc3BfT2JqZWN0LCBMaXNwX09iamVjdCwKZGlmZiAtLWdpdCBhL3NyYy9tYXJr ZXIuYyBiL3NyYy9tYXJrZXIuYwppbmRleCAwNWU1YmI4Li45Y2Q3ZDI2IDEwMDY0NAotLS0gYS9z cmMvbWFya2VyLmMKKysrIGIvc3JjL21hcmtlci5jCkBAIC02MjksNiArNjI5LDQ2IEBAIHVuY2hh aW5fbWFya2VyIChyZWdpc3RlciBzdHJ1Y3QgTGlzcF9NYXJrZXIgKm1hcmtlcikKICAgICB9CiB9 CiAKKy8qIFJlbW92ZSBhbGwgbWFya2VycyB0aGF0IGFyZSBkdWUgdG8gYmUgc3dlcHQgZnJvbSB0 aGUgY2hhaW4gb2YKKyAgIEJVRkZFUiwgbGVhdmluZyB0aGVtIHBvaW50aW5nIHRvIG5vd2hlcmUu ICBUaGlzIGlzIGNhbGxlZCBkdXJpbmcKKyAgIGdhcmJhZ2UgY29sbGVjdGlvbiwgc28gd2UgbXVz dCBiZSBjYXJlZnVsIHRvIGlnbm9yZSBhbmQgcHJlc2VydmUKKyAgIG1hcmsgYml0cywgaW5jbHVk aW5nIHRob3NlIGluIGNoYWluIGZpZWxkcyBvZiBtYXJrZXJzLiAgKi8KKwordm9pZAordW5jaGFp bl9jb2xsZWN0ZWRfbWFya2VycyAocmVnaXN0ZXIgc3RydWN0IGJ1ZmZlciAqYnVmZmVyKQorewor ICByZWdpc3RlciBzdHJ1Y3QgTGlzcF9NYXJrZXIgKnRhaWwsICoqcHJldjsKKworICBpZiAoIWJ1 ZmZlcikKKyAgICByZXR1cm47CisKKyAgLyogTm8gZGVhZCBidWZmZXJzIGhlcmUuICAqLworICBl YXNzZXJ0IChCVUZGRVJfTElWRV9QIChidWZmZXIpKTsKKworICBwcmV2ID0gJkJVRl9NQVJLRVJT IChidWZmZXIpOworCisgIGZvciAodGFpbCA9IEJVRl9NQVJLRVJTIChidWZmZXIpOyB0YWlsOyBw cmV2ID0gJnRhaWwtPm5leHQsIHRhaWwgPSAqcHJldikKKyAgICBpZiAodGFpbC0+Z2Nzd2VlcGJp dCkKKyAgICAgIHsKKyAgICAgICAgcmVnaXN0ZXIgc3RydWN0IExpc3BfTWFya2VyICpuZXh0Owor ICAgICAgICBmb3IgKG5leHQgPSB0YWlsOyBuZXh0ICYmIG5leHQtPmdjc3dlZXBiaXQ7IG5leHQg PSBuZXh0LT5uZXh0KQorICAgICAgICAgIHsKKyAgICAgICAgICAgIG5leHQtPmdjc3dlZXBiaXQg PSAwOworICAgICAgICAgICAgbmV4dC0+YnVmZmVyID0gTlVMTDsKKyAgICAgICAgICB9CisgICAg ICAgIGlmICgqcHJldiA9PSBCVUZfTUFSS0VSUyAoYnVmZmVyKSkKKyAgICAgICAgICB7CisgICAg ICAgICAgICAvKiBEZWxldGluZyBmaXJzdCBtYXJrZXIgZnJvbSB0aGUgYnVmZmVyJ3MgY2hhaW4u ICBDcmFzaAorICAgICAgICAgICAgICAgaWYgbmV3IGZpcnN0IG1hcmtlciBpbiBjaGFpbiBkb2Vz IG5vdCBzYXkgaXQgYmVsb25ncworICAgICAgICAgICAgICAgdG8gdGhlIHNhbWUgYnVmZmVyLCBv ciBhdCBsZWFzdCB0aGF0IHRoZXkgaGF2ZSB0aGUgc2FtZQorICAgICAgICAgICAgICAgYmFzZSBi dWZmZXIuICAqLworICAgICAgICAgICAgaWYgKG5leHQgJiYgYnVmZmVyLT50ZXh0ICE9IG5leHQt PmJ1ZmZlci0+dGV4dCkKKyAgICAgICAgICAgICAgZW1hY3NfYWJvcnQgKCk7CisgICAgICAgICAg fQorICAgICAgICAqcHJldiA9IG5leHQ7CisgICAgICB9Cit9CisKIC8qIFJldHVybiB0aGUgY2hh ciBwb3NpdGlvbiBvZiBtYXJrZXIgTUFSS0VSLCBhcyBhIEMgaW50ZWdlci4gICovCiAKIHB0cmRp ZmZfdAo= --047d7b5d5b82c10f25053d6a8f06-- From debbugs-submit-bounces@debbugs.gnu.org Sat Nov 25 19:01:14 2017 Received: (at control) by debbugs.gnu.org; 26 Nov 2017 00:01:14 +0000 Received: from localhost ([127.0.0.1]:58340 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1eIkNm-0007QH-9y for submit@debbugs.gnu.org; Sat, 25 Nov 2017 19:01:14 -0500 Received: from mail-io0-f182.google.com ([209.85.223.182]:43349) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1eIkNk-0007Q2-VC; Sat, 25 Nov 2017 19:01:13 -0500 Received: by mail-io0-f182.google.com with SMTP id s37so21853249ioe.10; Sat, 25 Nov 2017 16:01:12 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=sender:from:to:cc:subject:references:date:in-reply-to:message-id :user-agent:mime-version; bh=D2+o/tcTuF4zINFu6kwrJaj0XtP754QLzhPL81UZG+I=; b=dmivBAGDczney4i56FfDEPycDc0+AX1KyCyKxZ2xFLcrgVNk2Ic1KphUuDj2Apb9rS 0JeGEUqlONJD7fXL3TLNnqFp1RJ2RbBWC4H82WuaVxaCd0dyjk19lcNzjt7wzOH2dwXn zLTAKRRMIe4y91pEZDH2quvb9vOBSylvaCQ9ux1M+Hm44T4h2pawvGybEKZQltTfeMGe 9aGXuT6QWerKrZw43yFm5fBSdh/nYzOMUUB/nlSTqjWAPvT78gZpjIiZjdWxReuarW5O eXi1R2wflh8FTOogV7AQigsVnQdX+C15MKOnrh6lEtiaYM381YqLsVfRtESjeNMmi7rJ 67SA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:sender:from:to:cc:subject:references:date :in-reply-to:message-id:user-agent:mime-version; bh=D2+o/tcTuF4zINFu6kwrJaj0XtP754QLzhPL81UZG+I=; b=eT5KVNJaNPnmfm9lqmlH0lnmxNmUSkEjQbda726nDhYg6kARgsrfjZlAiW7swHP2KY 8J8HxaiVvqihbSwSmrd5iozpmQzI28qwBbQt1MgJ9sEPS415qJKQtQB01Tfqndc/0CQW QTzq91zf5L2qGKTLKtPjLeZTmazH0pgk4Y/jyK1sZFyaUYW1bBY3Qv30s7JxlpgL/O8X NyC4z8zfZaGLj1uhm+WpB8vC0ZH7G7FCtyDmlPl0beQ8Ad0a/fmoteXKCtbksIaZC71I ARox282Ucwoqfy7ZHEuMwmfmaCSiCK6tYwiijd53zpAgGuPe+Nwm/Sg0zUF1VVYiU3IO 7vow== X-Gm-Message-State: AJaThX4u1v6aPB4koiOn5lJ7SosT6yODpb7NDZnxwyQsu+RnlAc9H9mu r1797wJxdz+8CL4vfztGSTXJUw== X-Google-Smtp-Source: AGs4zMZaZp2ncDRhpzDSCqWv5MAWJ05WY4mRB3pJE7+4q1D0fsPj/mYFQ8s5EqqWwSjL0MCiVQvQrA== X-Received: by 10.107.139.8 with SMTP id n8mr40736828iod.9.1511654467105; Sat, 25 Nov 2017 16:01:07 -0800 (PST) Received: from zebian ([45.2.119.34]) by smtp.googlemail.com with ESMTPSA id 129sm5854974itx.37.2017.11.25.16.01.05 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Sat, 25 Nov 2017 16:01:06 -0800 (PST) From: Noam Postavsky To: Pip Cet Subject: Re: bug#29439: Quadratic complexity in sweep_markers References: Date: Sat, 25 Nov 2017 19:01:05 -0500 In-Reply-To: (Pip Cet's message of "Sat, 25 Nov 2017 17:06:07 +0000") Message-ID: <87shd1ykla.fsf@users.sourceforge.net> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.0.90 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: 0.2 (/) X-Debbugs-Envelope-To: control Cc: 29439@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: 0.2 (/) tags 24548 + patch merge 29439 24548 quit Pip Cet 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. From debbugs-submit-bounces@debbugs.gnu.org Fri Mar 23 09:55:19 2018 Received: (at 24548) by debbugs.gnu.org; 23 Mar 2018 13:55:19 +0000 Received: from localhost ([127.0.0.1]:49689 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ezNA6-0004ao-Tz for submit@debbugs.gnu.org; Fri, 23 Mar 2018 09:55:19 -0400 Received: from pruche.dit.umontreal.ca ([132.204.246.22]:34824) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ezNA4-0004WZ-G8 for 24548@debbugs.gnu.org; Fri, 23 Mar 2018 09:55:17 -0400 Received: from pastel.home (lechon.iro.umontreal.ca [132.204.27.242]) by pruche.dit.umontreal.ca (8.14.7/8.14.1) with ESMTP id w2NDtFtv032439; Fri, 23 Mar 2018 09:55:15 -0400 Received: by pastel.home (Postfix, from userid 20848) id 320F560223; Fri, 23 Mar 2018 09:55:15 -0400 (EDT) From: Stefan Monnier To: Pip Cet Subject: Re: bug#24548: 25.2.50; Long GC delays with many non-detached markers (PATCH) Message-ID: References: Date: Fri, 23 Mar 2018 09:55:15 -0400 In-Reply-To: (Pip Cet's message of "Mon, 26 Sep 2016 15:12:10 +0000") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.0.50 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-NAI-Spam-Flag: NO X-NAI-Spam-Threshold: 5 X-NAI-Spam-Score: 0 X-NAI-Spam-Rules: 2 Rules triggered EDT_SA_DN_PASS=0, RV6249=0 X-NAI-Spam-Version: 2.3.0.9418 : core <6249> : inlines <6514> : streams <1782034> : uri <2613418> X-Spam-Score: -1.3 (-) X-Debbugs-Envelope-To: 24548 Cc: 24548@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.3 (-) > 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 From debbugs-submit-bounces@debbugs.gnu.org Fri Mar 23 10:22:23 2018 Received: (at 24548) by debbugs.gnu.org; 23 Mar 2018 14:22:23 +0000 Received: from localhost ([127.0.0.1]:49829 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ezNaI-0005Er-Oz for submit@debbugs.gnu.org; Fri, 23 Mar 2018 10:22:22 -0400 Received: from chene.dit.umontreal.ca ([132.204.246.20]:56374) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ezNaG-0005Eg-IS for 24548@debbugs.gnu.org; Fri, 23 Mar 2018 10:22:21 -0400 Received: from pastel.home (lechon.iro.umontreal.ca [132.204.27.242]) by chene.dit.umontreal.ca (8.14.7/8.14.1) with ESMTP id w2NEMJ7x004841; Fri, 23 Mar 2018 10:22:19 -0400 Received: by pastel.home (Postfix, from userid 20848) id ED88D60223; Fri, 23 Mar 2018 10:22:18 -0400 (EDT) From: Stefan Monnier To: Pip Cet Subject: Re: bug#24548: 25.2.50; Long GC delays with many non-detached markers (PATCH) Message-ID: References: Date: Fri, 23 Mar 2018 10:22:18 -0400 In-Reply-To: (Stefan Monnier's message of "Fri, 23 Mar 2018 09:55:15 -0400") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.0.50 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-NAI-Spam-Flag: NO X-NAI-Spam-Threshold: 5 X-NAI-Spam-Score: 0 X-NAI-Spam-Rules: 2 Rules triggered EDT_SA_DN_PASS=0, RV6249=0 X-NAI-Spam-Version: 2.3.0.9418 : core <6249> : inlines <6516> : streams <1782036> : uri <2613430> X-Spam-Score: -1.3 (-) X-Debbugs-Envelope-To: 24548 Cc: 24548@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.3 (-) > 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); } From debbugs-submit-bounces@debbugs.gnu.org Fri Mar 23 11:11:14 2018 Received: (at 24548) by debbugs.gnu.org; 23 Mar 2018 15:11:14 +0000 Received: from localhost ([127.0.0.1]:49896 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ezOLa-0006MS-3d for submit@debbugs.gnu.org; Fri, 23 Mar 2018 11:11:14 -0400 Received: from mail-wm0-f52.google.com ([74.125.82.52]:55269) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ezOLY-0006MF-6U for 24548@debbugs.gnu.org; Fri, 23 Mar 2018 11:11:12 -0400 Received: by mail-wm0-f52.google.com with SMTP id h76so4182963wme.4 for <24548@debbugs.gnu.org>; Fri, 23 Mar 2018 08:11:12 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=CAHBTKJDX2JJ+vmumod89Lh/JOMzNYFHKY/mJWwmEkg=; b=gYSnaqQCErBoNzxnzLuSr40zS8wrXd/hAmlS0RDmzHh49AO4pcWDJ0C1ruiTXEAhoi W4AdcmjR38FK11f196WrhA8cRuMMzRDzAaNfWWo+/jO2UeGpoJ/dzXNf3kAbuUScBGJO AzxSMuIKAoqGelTuExmHiygaGkD+3s9WQ7L8bPiu677iqOP9Zipv5S8PVdwo684XEYcX qVsrRjZeeCsPHgPUDldHyYyhBHM5iPd6Q2zY3wnwqazc1n3EZQnqXmDiIXQH/Oz+oXFZ L71jTSudoyQkHRQpJppSDW/f9l+L61xtieh0VAHUZM3qZhmc5ksxGjnoN8erngkdF+7i IyDQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=CAHBTKJDX2JJ+vmumod89Lh/JOMzNYFHKY/mJWwmEkg=; b=dlugkgU3sCPUoVBATeyvfhfOYqv0WrA8gJuLdmSzpOSu0bgv5kFmFJN4gynejmh4Ns Vjgrt0G6vWxRtAlNxRaFR0yxSli6YGczLbfm64Z3etriXY806D6r5AURuZnCJnPMR8+X rvjHYdDTPrNir4a2QVqZQr418XrpcrUfgIXjuz2tawmZucLgNF4YxWTGDlRnUuznFBYq taWdxCjsR1P3AByomgrJp5nlMjGhNCeggi2CZLB+fFIBhw6EiZbuHCQULKCFw8RvV5Lv taLn/WB+qEJa8eEZ2mJsVxyHylCOGY5uF1wgYTqS7ZW6ux1pD0uNr/6dKqEjDD3x3Oy+ XZ4g== X-Gm-Message-State: AElRT7E+mA1n/bw/koPRZL2Mg6nAdrV7sfzB1QxJM6YQfgr7MxJ/Pb8t k/Td/7/KBezUzleTGbWkzXRYHySfcaK+cru09H0= X-Google-Smtp-Source: AG47ELsq6/txWuU4upvAa6KVVQxfMzKohmB/d/cKbRODuDC3h+Lc/WfXrUzjbzZ4yDMS/Vm+edppvrTBQ9O0egJPR/8= X-Received: by 10.80.217.206 with SMTP id x14mr15406550edj.208.1521817866460; Fri, 23 Mar 2018 08:11:06 -0700 (PDT) MIME-Version: 1.0 Received: by 10.80.129.230 with HTTP; Fri, 23 Mar 2018 08:10:26 -0700 (PDT) In-Reply-To: References: From: Pip Cet Date: Fri, 23 Mar 2018 15:10:26 +0000 Message-ID: Subject: Re: bug#24548: 25.2.50; Long GC delays with many non-detached markers (PATCH) To: Stefan Monnier Content-Type: text/plain; charset="UTF-8" X-Spam-Score: -0.0 (/) X-Debbugs-Envelope-To: 24548 Cc: 24548@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.0 (/) 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. From debbugs-submit-bounces@debbugs.gnu.org Fri Mar 23 11:11:04 2018 Received: (at 24548-done) by debbugs.gnu.org; 23 Mar 2018 15:11:04 +0000 Received: from localhost ([127.0.0.1]:49893 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ezOLP-0006M3-SS for submit@debbugs.gnu.org; Fri, 23 Mar 2018 11:11:04 -0400 Received: from pruche.dit.umontreal.ca ([132.204.246.22]:47123) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ezOLN-0006Le-DS for 24548-done@debbugs.gnu.org; Fri, 23 Mar 2018 11:11:01 -0400 Received: from pastel.home (lechon.iro.umontreal.ca [132.204.27.242]) by pruche.dit.umontreal.ca (8.14.7/8.14.1) with ESMTP id w2NFB0j0010683; Fri, 23 Mar 2018 11:11:00 -0400 Received: by pastel.home (Postfix, from userid 20848) id 295B560223; Fri, 23 Mar 2018 11:11:00 -0400 (EDT) From: Stefan Monnier To: 24548-done@debbugs.gnu.org Subject: Re: bug#24548: 25.2.50; Long GC delays with many non-detached markers (PATCH) Message-ID: References: Date: Fri, 23 Mar 2018 11:11:00 -0400 In-Reply-To: (Stefan Monnier's message of "Fri, 23 Mar 2018 10:22:18 -0400") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.0.50 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-NAI-Spam-Flag: NO X-NAI-Spam-Level: X-NAI-Spam-Threshold: 5 X-NAI-Spam-Score: 0.1 X-NAI-Spam-Rules: 3 Rules triggered GEN_SPAM_FEATRE=0.1, EDT_SA_DN_PASS=0, RV6249=0 X-NAI-Spam-Version: 2.3.0.9418 : core <6249> : inlines <6516> : streams <1782039> : uri <2613450> X-Spam-Score: -1.3 (-) X-Debbugs-Envelope-To: 24548-done Cc: Pip Cet X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.3 (-) 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 From unknown Wed Aug 20 05:18:00 2025 Received: (at fakecontrol) by fakecontrolmessage; To: internal_control@debbugs.gnu.org From: Debbugs Internal Request Subject: Internal Control Message-Id: bug archived. Date: Sat, 21 Apr 2018 11:24:04 +0000 User-Agent: Fakemail v42.6.9 # This is a fake control message. # # The action: # bug archived. thanks # This fakemail brought to you by your local debbugs # administrator