From unknown Thu Aug 14 21:46:20 2025 X-Loop: help-debbugs@gnu.org Subject: bug#73883: [PATCH] Fix internal_equal so that it uses at most one hash table Resent-From: Ethan Kong Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sat, 19 Oct 2024 14:26:03 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: report 73883 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: 73883@debbugs.gnu.org X-Debbugs-Original-To: bug-gnu-emacs@gnu.org Received: via spool by submit@debbugs.gnu.org id=B.172934795311670 (code B ref -1); Sat, 19 Oct 2024 14:26:03 +0000 Received: (at submit) by debbugs.gnu.org; 19 Oct 2024 14:25:53 +0000 Received: from localhost ([127.0.0.1]:44223 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1t2AOu-000327-UJ for submit@debbugs.gnu.org; Sat, 19 Oct 2024 10:25:53 -0400 Received: from lists.gnu.org ([209.51.188.17]:34540) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1t276B-00010F-M2 for submit@debbugs.gnu.org; Sat, 19 Oct 2024 06:54:20 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1t275n-0001dx-Mj for bug-gnu-emacs@gnu.org; Sat, 19 Oct 2024 06:53:55 -0400 Received: from mail-oo1-xc2c.google.com ([2607:f8b0:4864:20::c2c]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1t275l-00054E-OT for bug-gnu-emacs@gnu.org; Sat, 19 Oct 2024 06:53:55 -0400 Received: by mail-oo1-xc2c.google.com with SMTP id 006d021491bc7-5eb60f6b391so1549769eaf.3 for ; Sat, 19 Oct 2024 03:53:52 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1729335232; x=1729940032; darn=gnu.org; h=to:subject:message-id:date:from:mime-version:from:to:cc:subject :date:message-id:reply-to; bh=HmTtwiFRD71Qxj1jaNii94EjSXxpiUi4JZStvHMSm7s=; b=KGpRr7+UPPb+yx/evBghDEVi6lsioWVWLs2je83CJxAPatwvxzFFe3eKtJr7Ll3MWi cE8mkBQKpxn5DJpVOpkYHuNQ4tHoCE2rQZO9+wZiUHZLbZJUk05R/pwTW6QOpKRlBpWs m47gvgm1Pv7M0BY+NCou2M1+HbX/Ht/GTz2X2ctfzXp/8YoeYn4dTuNUyun8IlkCY0Ed ZTcMWMYV+v4fwr3hxLT+5mV9GjvoF8KbtXHY6ecsFADB1HSJkayNPb8k8WbryVQM62BV +C5Mw57tyOLkpIbL0RTid/OPpsfcRq50bISQWHeq0Ze6GLWSDcFrErEmv5rwYnB9ni1v UHvQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729335232; x=1729940032; h=to:subject:message-id:date:from:mime-version:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=HmTtwiFRD71Qxj1jaNii94EjSXxpiUi4JZStvHMSm7s=; b=Fj9sbHQiT9PziWmo+PVtd9h5I+ci4U8JrkSRgp5nOIMJtJYcyEvn4z7voa7f4IUX3T /KDWh4/DKGIlXVB6kYY9euBlOlUthoIJ6geCulq1Gsv6+7YFrKgBiS6K+i28ra0k1eBE a2CD07jvQwcMvhJw4HGamPu1kWrZPxifW+3minNlYLmQQ/T18MhknBXEOb6AENEqXfGK PEdRab+iGJZsWBVwyWdzBqdxaLWpkscm7myPhiNoqQFehG+buSOaNQ8hKtK6zPVCJKif lG1A9jd5OIyDYwN8XKNLry0KLqzHc8gZ5PfKIkaox9iSmXGQvfwpD5MfNWQhjG8ioNp1 kdRA== X-Gm-Message-State: AOJu0YxBjGQXRfpCcQZcfAoaokY80vMrsOfafHEJytxQpIXnXWInSe/t 4TPV9W7A/JyhwcSUtLF/B0dL7+ntG8JSvyOIUT8NOGRicCs2d3g54xeV7NCX1rt6WLCKbe/Fvsj EpbxHPJCZ8IGm5OQmu6pJ6/nTX3ohzyTcZc4= X-Google-Smtp-Source: AGHT+IFrXLMmjWpJ34fBbl+zQ5IMnvjsveoztdJpHRE8RoDWOklQ++qiDukxkirsguXANKmpYHRQ1w1ICKxnli/A5Ys= X-Received: by 2002:a05:6870:b487:b0:260:fbc0:96f2 with SMTP id 586e51a60fabf-2892c53d04dmr4860531fac.34.1729335231594; Sat, 19 Oct 2024 03:53:51 -0700 (PDT) MIME-Version: 1.0 From: Ethan Kong Date: Sat, 19 Oct 2024 18:53:40 +0800 Message-ID: Content-Type: multipart/mixed; boundary="0000000000002d59900624d23c14" Received-SPF: pass client-ip=2607:f8b0:4864:20::c2c; envelope-from=ek.ethan.kong@gmail.com; helo=mail-oo1-xc2c.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-Spam-Score: -1.3 (-) X-Mailman-Approved-At: Sat, 19 Oct 2024 10:25:42 -0400 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: -2.3 (--) --0000000000002d59900624d23c14 Content-Type: multipart/alternative; boundary="0000000000002d598e0624d23c12" --0000000000002d598e0624d23c12 Content-Type: text/plain; charset="UTF-8" Tags: patch Hi, When I use 'equal' on large, cyclic objects, emacs freezes. Reproduce: ;; emacs -Q (require 'org-element) ;; get two identical `org-element' trees of this file ;; https://github.com/emacs-mirror/emacs/blob/master/doc/misc/modus-themes.org (let ((file (expand-file-name "doc/misc/modus-themes.org" source-directory))) (with-current-buffer (find-file-noselect file) (setq org-o1 (org-element-parse-buffer)) (org-element-cache-reset) (setq org-o2 (org-element-parse-buffer)))) ;; the test (equal org-o1 org-o2) This equal call freezes emacs. And the memory usage of emacs grows quickly, until I quit. Reproduced with emacs 29.4 and the master branch. The cause: Current code on the master branch: static bool internal_equal (Lisp_Object o1, Lisp_Object o2, enum equal_kind equal_kind, int depth, Lisp_Object ht) { tail_recurse: if (depth > 10) { // ... if (NILP (ht)) ht = CALLN (Fmake_hash_table, QCtest, Qeq); // ... } // ... if (! internal_equal (XCAR (o1), XCAR (o2), equal_kind, depth + 1, ht)) return false; // ... } When internal_equal calls itself, it passes the hash table argument 'ht' by value. As a result, each internal_equal(depth=11) call initializes its own hash table, separately recording the objects it encounters in further recursive calls. This leads to excessive 'hash_put' and significant memory allocation. Fix: Make internal_equal pass the hash table by pointer (see the patch). With this patch, the test above returns quickly: (benchmark-run 100 (equal org-o1 org-o2)) (2.562444 20 0.30933900000000014) This will also improve the performance for smaller cyclic objects: ;; emacs -Q (defun make-cyclic (n m) (let* ((l1 (make-list n 1)) (l2 (make-list m 2))) (setf (nth (1- m) l2) l1) (setf (nth (1- n) l1) l2) l1)) (let ((a (make-cyclic 100 7)) (b (make-cyclic 100 7))) (cl-assert (equal a b)) (benchmark-run 10000 (equal a b))) Current: (0.530081 32 0.49294199999999977) With the patch: (0.036401 1 0.0173350000000001) And it passes all the tests in 'make fns-tests'. P.S. Could I get the copyright assignment paperwork please? Best, Ethan Kong In GNU Emacs 29.4 (build 2, x86_64-w64-mingw32) of 2024-07-05 built on AVALON Windowing system distributor 'Microsoft Corp.', version 10.0.22631 System Description: Microsoft Windows 10 Pro (v10.0.2009.22631.4317) Configured using: 'configure --with-modules --without-dbus --with-native-compilation=aot --without-compress-install --with-sqlite3 --with-tree-sitter CFLAGS=-O2' --0000000000002d598e0624d23c12 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Tags: patch

Hi,

When I use 'equal' o= n large, cyclic objects, emacs freezes.

Reproduce:

=C2=A0 =C2= =A0 ;; emacs -Q
=C2=A0 =C2=A0 (require 'org-element)

=C2=A0 = =C2=A0 ;; get two identical `org-element' trees of this file
=C2=A0 = =C2=A0 ;; https://github.com/emacs-mirror/emacs/blob/master/do= c/misc/modus-themes.org
=C2=A0 =C2=A0 (let ((file (expand-file-name = "doc/misc/modus-themes.org&quo= t;
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 source-directory)))
= =C2=A0 =C2=A0 =C2=A0 (with-current-buffer (find-file-noselect file)
=C2= =A0 =C2=A0 =C2=A0 =C2=A0 (setq org-o1 (org-element-parse-buffer))
=C2=A0= =C2=A0 =C2=A0 =C2=A0 (org-element-cache-reset)
=C2=A0 =C2=A0 =C2=A0 =C2= =A0 (setq org-o2 (org-element-parse-buffer))))

=C2=A0 =C2=A0 ;; the = test
=C2=A0 =C2=A0 (equal org-o1 org-o2)

This equal call freezes = emacs. And the memory usage of emacs grows
quickly, until I quit. Reprod= uced with emacs 29.4 and the master branch.


The cause:

Cu= rrent code on the master branch:

=C2=A0 =C2=A0 static bool
=C2=A0= =C2=A0 internal_equal (Lisp_Object o1, Lisp_Object o2, enum equal_kind equ= al_kind,
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 int depth, Lisp_Object ht)
=C2=A0 =C2=A0 {
=C2=A0 =C2=A0 =C2= =A0tail_recurse:
=C2=A0 =C2=A0 =C2=A0 if (depth > 10)
=C2=A0 =C2= =A0 =C2=A0 =C2=A0 {
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 // ...
=C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 if (NILP (ht))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 ht =3D CALLN (Fmake_hash_table, QCtest, Qeq);
=C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 // ...
=C2=A0 =C2=A0 =C2=A0 =C2=A0 }
=C2=A0 = =C2=A0 =C2=A0 // ...
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 if (! int= ernal_equal (XCAR (o1), XCAR (o2),
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 equal_kind, depth + 1, ht))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 return false;
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 // ...
=C2=A0 =C2=A0 }

When internal_equal calls itself, it p= asses the hash table argument 'ht'
by value. As a result, each i= nternal_equal(depth=3D11) call initializes
its own hash table, separatel= y recording the objects it encounters in
further recursive calls. This l= eads to excessive 'hash_put' and
significant memory allocation.<= br>

Fix:

Make internal_equal pass the hash table by pointer (= see the patch).

With this patch, the test above returns quickly:
=
=C2=A0 =C2=A0 (benchmark-run 100 (equal org-o1 org-o2))

(2.56244= 4 20 0.30933900000000014)

This will also improve the performance for= smaller cyclic objects:

=C2=A0 =C2=A0 ;; emacs -Q
=C2=A0 =C2=A0 = (defun make-cyclic (n m)
=C2=A0 =C2=A0 =C2=A0 (let* ((l1 (make-list n 1)= )
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(l2 (make-list m 2)))<= br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 (setf (nth (1- m) l2) l1)
=C2=A0 =C2=A0 = =C2=A0 =C2=A0 (setf (nth (1- n) l1) l2)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 l1))=

=C2=A0 =C2=A0 (let ((a (make-cyclic 100 7))
=C2=A0 =C2=A0 =C2=A0= =C2=A0 =C2=A0 (b (make-cyclic 100 7)))
=C2=A0 =C2=A0 =C2=A0 (cl-assert = (equal a b))
=C2=A0 =C2=A0 =C2=A0 (benchmark-run 10000 (equal a b)))
=
Current:
(0.530081 32 0.49294199999999977)

With the patch:(0.036401 1 0.0173350000000001)

And it passes all the tests in '= ;make fns-tests'.


P.S. Could I get the copyright assignment = paperwork please?

Best,
Ethan Kong


In GNU Emacs 29.4 (= build 2, x86_64-w64-mingw32) of 2024-07-05 built on
=C2=A0AVALON
Wind= owing system distributor 'Microsoft Corp.', version 10.0.22631
S= ystem Description: Microsoft Windows 10 Pro (v10.0.2009.22631.4317)

= Configured using:
=C2=A0'configure --with-modules --without-dbus --w= ith-native-compilation=3Daot
=C2=A0--without-compress-install --with-sql= ite3 --with-tree-sitter
=C2=A0CFLAGS=3D-O2'
--0000000000002d598e0624d23c12-- --0000000000002d59900624d23c14 Content-Type: application/octet-stream; name="0001-Fix-internal_equal-so-that-it-uses-at-most-one-hash-.patch" Content-Disposition: attachment; filename="0001-Fix-internal_equal-so-that-it-uses-at-most-one-hash-.patch" Content-Transfer-Encoding: base64 Content-ID: X-Attachment-Id: f_m2g17yg00 RnJvbSA0MjUyNzAxNzliYjIyNjMwYjdhZDU4NzFmY2ZjZWU4NDczN2I1NWZiIE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBFdGhhbiBLb25nIDxlay5ldGhhbi5rb25nQGdtYWlsLmNvbT4K RGF0ZTogU2F0LCAxOSBPY3QgMjAyNCAxMjo0MzoyNyArMDgwMApTdWJqZWN0OiBbUEFUQ0hdIEZp eCBpbnRlcm5hbF9lcXVhbCBzbyB0aGF0IGl0IHVzZXMgYXQgbW9zdCBvbmUgaGFzaCB0YWJsZQoK KiBzcmMvZm5zLmMgKGludGVybmFsX2VxdWFsKTogRGVsZWdhdGUgdG8gaW50ZXJuYWxfZXF1YWxf MS4KKGludGVybmFsX2VxdWFsXzEpOiBOZXcgZnVuY3Rpb24uIFBhc3MgdGhlIGhhc2ggdGFibGUg YXJndW1lbnQgYnkKcG9pbnRlciBpbnN0ZWFkIG9mIGJ5IHZhbHVlLgotLS0KIHNyYy9mbnMuYyB8 IDIzICsrKysrKysrKysrKysrKy0tLS0tLS0tCiAxIGZpbGUgY2hhbmdlZCwgMTUgaW5zZXJ0aW9u cygrKSwgOCBkZWxldGlvbnMoLSkKCmRpZmYgLS1naXQgYS9zcmMvZm5zLmMgYi9zcmMvZm5zLmMK aW5kZXggMmRlMDRkMDY1MTkuLmVmNjkyMmMxMzdiIDEwMDY0NAotLS0gYS9zcmMvZm5zLmMKKysr IGIvc3JjL2Zucy5jCkBAIC0yODIzLDggKzI4MjMsOCBAQCBlcXVhbF9ub19xdWl0IChMaXNwX09i amVjdCBvMSwgTGlzcF9PYmplY3QgbzIpCiAgICBpZiBFUVVBTF9LSU5EID09IEVRVUFMX05PX1FV SVQuICAqLwogCiBzdGF0aWMgYm9vbAotaW50ZXJuYWxfZXF1YWwgKExpc3BfT2JqZWN0IG8xLCBM aXNwX09iamVjdCBvMiwgZW51bSBlcXVhbF9raW5kIGVxdWFsX2tpbmQsCi0JCWludCBkZXB0aCwg TGlzcF9PYmplY3QgaHQpCitpbnRlcm5hbF9lcXVhbF8xIChMaXNwX09iamVjdCBvMSwgTGlzcF9P YmplY3QgbzIsIGVudW0gZXF1YWxfa2luZCBlcXVhbF9raW5kLAorCQkgIGludCBkZXB0aCwgTGlz cF9PYmplY3QgKmh0KQogewogIHRhaWxfcmVjdXJzZToKICAgaWYgKGRlcHRoID4gMTApCkBAIC0y ODMyLDEzICsyODMyLDEzIEBAIGludGVybmFsX2VxdWFsIChMaXNwX09iamVjdCBvMSwgTGlzcF9P YmplY3QgbzIsIGVudW0gZXF1YWxfa2luZCBlcXVhbF9raW5kLAogICAgICAgZWFzc2VydCAoZXF1 YWxfa2luZCAhPSBFUVVBTF9OT19RVUlUKTsKICAgICAgIGlmIChkZXB0aCA+IDIwMCkKIAllcnJv ciAoIlN0YWNrIG92ZXJmbG93IGluIGVxdWFsIik7Ci0gICAgICBpZiAoTklMUCAoaHQpKQotCWh0 ID0gQ0FMTE4gKEZtYWtlX2hhc2hfdGFibGUsIFFDdGVzdCwgUWVxKTsKKyAgICAgIGlmIChOSUxQ ICgqaHQpKQorCSpodCA9IENBTExOIChGbWFrZV9oYXNoX3RhYmxlLCBRQ3Rlc3QsIFFlcSk7CiAg ICAgICBzd2l0Y2ggKFhUWVBFIChvMSkpCiAJewogCWNhc2UgTGlzcF9Db25zOiBjYXNlIExpc3Bf VmVjdG9ybGlrZToKIAkgIHsKLQkgICAgc3RydWN0IExpc3BfSGFzaF9UYWJsZSAqaCA9IFhIQVNI X1RBQkxFIChodCk7CisJICAgIHN0cnVjdCBMaXNwX0hhc2hfVGFibGUgKmggPSBYSEFTSF9UQUJM RSAoKmh0KTsKIAkgICAgaGFzaF9oYXNoX3QgaGFzaCA9IGhhc2hfZnJvbV9rZXkgKGgsIG8xKTsK IAkgICAgcHRyZGlmZl90IGkgPSBoYXNoX2xvb2t1cF93aXRoX2hhc2ggKGgsIG8xLCBoYXNoKTsK IAkgICAgaWYgKGkgPj0gMCkKQEAgLTI4ODgsOCArMjg4OCw4IEBAIGludGVybmFsX2VxdWFsIChM aXNwX09iamVjdCBvMSwgTGlzcF9PYmplY3QgbzIsIGVudW0gZXF1YWxfa2luZCBlcXVhbF9raW5k LAogCSAgewogCSAgICBpZiAoISBDT05TUCAobzIpKQogCSAgICAgIHJldHVybiBmYWxzZTsKLQkg ICAgaWYgKCEgaW50ZXJuYWxfZXF1YWwgKFhDQVIgKG8xKSwgWENBUiAobzIpLAotCQkJCSAgZXF1 YWxfa2luZCwgZGVwdGggKyAxLCBodCkpCisJICAgIGlmICghIGludGVybmFsX2VxdWFsXzEgKFhD QVIgKG8xKSwgWENBUiAobzIpLAorCQkJCSAgICBlcXVhbF9raW5kLCBkZXB0aCArIDEsIGh0KSkK IAkgICAgICByZXR1cm4gZmFsc2U7CiAJICAgIG8yID0gWENEUiAobzIpOwogCSAgICBpZiAoRVEg KFhDRFIgKG8xKSwgbzIpKQpAQCAtMjk2NCw3ICsyOTY0LDcgQEAgaW50ZXJuYWxfZXF1YWwgKExp c3BfT2JqZWN0IG8xLCBMaXNwX09iamVjdCBvMiwgZW51bSBlcXVhbF9raW5kIGVxdWFsX2tpbmQs CiAJICAgIExpc3BfT2JqZWN0IHYxLCB2MjsKIAkgICAgdjEgPSBBUkVGIChvMSwgaSk7CiAJICAg IHYyID0gQVJFRiAobzIsIGkpOwotCSAgICBpZiAoIWludGVybmFsX2VxdWFsICh2MSwgdjIsIGVx dWFsX2tpbmQsIGRlcHRoICsgMSwgaHQpKQorCSAgICBpZiAoIWludGVybmFsX2VxdWFsXzEgKHYx LCB2MiwgZXF1YWxfa2luZCwgZGVwdGggKyAxLCBodCkpCiAJICAgICAgcmV0dXJuIGZhbHNlOwog CSAgfQogCXJldHVybiB0cnVlOwpAQCAtMjk4NSw2ICsyOTg1LDEzIEBAIGludGVybmFsX2VxdWFs IChMaXNwX09iamVjdCBvMSwgTGlzcF9PYmplY3QgbzIsIGVudW0gZXF1YWxfa2luZCBlcXVhbF9r aW5kLAogICByZXR1cm4gZmFsc2U7CiB9CiAKK3N0YXRpYyBib29sCitpbnRlcm5hbF9lcXVhbCAo TGlzcF9PYmplY3QgbzEsIExpc3BfT2JqZWN0IG8yLCBlbnVtIGVxdWFsX2tpbmQgZXF1YWxfa2lu ZCwKKwkJaW50IGRlcHRoLCBMaXNwX09iamVjdCBodCkKK3sKKyAgcmV0dXJuIGludGVybmFsX2Vx dWFsXzEgKG8xLCBvMiwgZXF1YWxfa2luZCwgZGVwdGgsICZodCk7Cit9CisKIC8qIFJldHVybiAt MS8wLzEgZm9yIHRoZSA8Lz0vPiBsZXhpY29ncmFwaGljIHJlbGF0aW9uIGJldHdlZW4gYm9vbC12 ZWN0b3JzLiAgKi8KIHN0YXRpYyBpbnQKIGJvb2xfdmVjdG9yX2NtcCAoTGlzcF9PYmplY3QgYSwg TGlzcF9PYmplY3QgYikKLS0gCjIuNDMuMC53aW5kb3dzLjEKCg== --0000000000002d59900624d23c14-- From debbugs-submit-bounces@debbugs.gnu.org Sat Oct 19 11:10:25 2024 Received: (at control) by debbugs.gnu.org; 19 Oct 2024 15:10:26 +0000 Received: from localhost ([127.0.0.1]:44415 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1t2B61-0004xc-G8 for submit@debbugs.gnu.org; Sat, 19 Oct 2024 11:10:25 -0400 Received: from eggs.gnu.org ([209.51.188.92]:55108) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1t2B5y-0004xJ-B4; Sat, 19 Oct 2024 11:10:23 -0400 Received: from fencepost.gnu.org ([2001:470:142:3::e]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1t2B5U-0001mo-VB; Sat, 19 Oct 2024 11:09:52 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org; s=fencepost-gnu-org; h=References:Subject:In-Reply-To:To:From:Date: mime-version; bh=6Gkl9h7PXGH9Wv0FeH1aSgjltkGXnTjP20XIGnmmDao=; b=Iyh+H5KLw3tu KhMTE691tzL9DPqp6wnPq86sG18WtCzKF17343wkF0b9pb4Mal9x5oXpFomCw4l4hQe6WcedRSBBI rqDrdTTp3mIvNKcZDn00Ia2c2LBW06u8Y8YqQNvSjJvWrwj423+hRcdQUMcdNkPAllCPdUSwG7azu uXHTJtBeMSyLIuBkE9hSLme8LPwDSJtwVUf5lc5sK/+9QsHX3App5wxBy8JxHW/mN+WBoYBg4SAKg Z29JSeLd5VJGMNixT0pJZXaBv9PQUY7tdOiMG0GZXr0B5iQZ/p+559f/k3EiG0ei7Qgj7Ez9s0d8d BneHuao75J8DrtCwY+EIng==; Date: Sat, 19 Oct 2024 18:09:49 +0300 Message-Id: <86v7xojfia.fsf@gnu.org> From: Eli Zaretskii To: Ethan Kong In-Reply-To: <86cyjwnsmu.fsf@gmail.com> (message from Ethan Kong on Sat, 19 Oct 2024 21:12:41 +0800) Subject: Re: bug#73885: [PATCH] Fix internal_equal so that it uses at most one hash table References: <86cyjwnsmu.fsf@gmail.com> X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: control Cc: 73885@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: -3.3 (---) merge 73885 73883 thanks > From: Ethan Kong > Date: Sat, 19 Oct 2024 21:12:41 +0800 > > Tags: patch > > Hi, > > When I use 'equal' on large, cyclic objects, emacs freezes. Thanks, this is an exact duplicate of bug#73883 that you submitted not long ago, so I'm merging them. From unknown Thu Aug 14 21:46:20 2025 X-Loop: help-debbugs@gnu.org Subject: bug#73883: [PATCH] Fix internal_equal so that it uses at most one hash table Resent-From: Stefan Kangas Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sun, 20 Oct 2024 11:58:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 73883 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: Ethan Kong , 73883@debbugs.gnu.org Received: via spool by 73883-submit@debbugs.gnu.org id=B73883.172942544913372 (code B ref 73883); Sun, 20 Oct 2024 11:58:01 +0000 Received: (at 73883) by debbugs.gnu.org; 20 Oct 2024 11:57:29 +0000 Received: from localhost ([127.0.0.1]:46175 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1t2UYq-0003Tb-Mq for submit@debbugs.gnu.org; Sun, 20 Oct 2024 07:57:28 -0400 Received: from mail-wm1-f49.google.com ([209.85.128.49]:50548) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1t2UYp-0003TM-9A for 73883@debbugs.gnu.org; Sun, 20 Oct 2024 07:57:27 -0400 Received: by mail-wm1-f49.google.com with SMTP id 5b1f17b1804b1-43161c0068bso21055995e9.1 for <73883@debbugs.gnu.org>; Sun, 20 Oct 2024 04:57:02 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1729425356; x=1730030156; darn=debbugs.gnu.org; h=to:subject:message-id:date:mime-version:references:in-reply-to:from :from:to:cc:subject:date:message-id:reply-to; bh=6nJzz+97Hinddnj1DHvozzP7HdG9e9BuanHhVB1rNK8=; b=a0Iq/DHd6z1rQjVE59v8sM8i7mdnHHy8A0fMZBcLXol0wt1v3FcGICsxqcvoP9LvYR pJWudFFy/dJAytxeWO+4tRD32wo3NZ+l4TuIv/8hRoxPQe2S2jRTa5DZmwUTuM8zdeDi APRxnxoHSIe8KQe7RJEHkzZ6kJwLGNsC57ISl4+E+VESOzRtEP0QBCafwV1yEgpCihf0 6OWJQn3fXNDlS/UgFVCndoRfiN8pIr+MrB4PZjLR0vNJ72uJmOVfcvDh8LLRmmKiBqOQ W/k/s2TgRvTvU73dh1VzA9hG5+OR6jNtFjfF7RYVjmLBhAyF9Aoubd1b2Tu7AwKgFSHS Y5MQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729425356; x=1730030156; h=to:subject:message-id:date:mime-version:references:in-reply-to:from :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=6nJzz+97Hinddnj1DHvozzP7HdG9e9BuanHhVB1rNK8=; b=j26yzjoZINFpycyzXiWdrgCugSxbiH3qV+ljRdhJWXl6gXq1kqc8VOYe9C5kBH/QRm osyjaIkFUQcEW3MdX1XBe04SoTanLfB4coR/LXtAlPUxSXBI7Hr1JTxKXeE7enxdghKE cgoMP/88GXVdfc0Ru7UzI/P/2lOT7V97AAfQu/zAI3tfn0f9Z7FAp37An83nOkDvrdCS mtsk9EAhzbgMZAApIfJ0vLnUS++hg5UOgugf+tGVFQU54GaMYCsu7VXIk6BQ8zajB6wA Oxi36tTPUXh3DXYpNNVSt+JzVDr2DHRFd2Xdfss/JtaFJ3dDZOqEq1txbZgwQUsgB09k qmNg== X-Forwarded-Encrypted: i=1; AJvYcCWvTEx+G7g9SxdchaSOrRjqcApbHyy2NUtHIfj8UuvfxiLJKtwB/OSizGZCAYiZn5cJ4IC+Yw==@debbugs.gnu.org X-Gm-Message-State: AOJu0YyFizuQer6fTCeOA8iP+GU8WHYBGguZxGVbf2Dxfe19feDw7dpJ Zq6W7jzMXf1YUKQ/ftSwAeK++6Ve2ClY5GdZ9bXyuuGSZ8v8Uez6OQEVJqKkl0FoWxm2Rd2KCWt yyd25DWVZToSNsfL2w643RL1/uww= X-Google-Smtp-Source: AGHT+IETekbEbCdH9S6dVczCD/CJtBVPJV7OjgVHy/ykS0OYFd6EJyNtG9l5aoOE/1gpyECvBn+3C6HfzDjRuQFDtiU= X-Received: by 2002:a5d:4d89:0:b0:371:9360:c4a8 with SMTP id ffacd0b85a97d-37ea21402a2mr5843358f8f.6.1729425356278; Sun, 20 Oct 2024 04:55:56 -0700 (PDT) Received: from 753933720722 named unknown by gmailapi.google.com with HTTPREST; Sun, 20 Oct 2024 04:55:56 -0700 From: Stefan Kangas In-Reply-To: References: MIME-Version: 1.0 Date: Sun, 20 Oct 2024 04:55:55 -0700 Message-ID: Content-Type: text/plain; charset="UTF-8" X-Spam-Score: 0.0 (/) 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.0 (-) Ethan Kong writes: > P.S. Could I get the copyright assignment paperwork please? Form sent off-list. From unknown Thu Aug 14 21:46:20 2025 X-Loop: help-debbugs@gnu.org Subject: bug#73883: [PATCH] Fix 'equal' freezing on large cyclic objects Resent-From: Ethan Kong Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sun, 20 Oct 2024 12:05:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 73883 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: 73883@debbugs.gnu.org Received: via spool by 73883-submit@debbugs.gnu.org id=B73883.172942588614634 (code B ref 73883); Sun, 20 Oct 2024 12:05:02 +0000 Received: (at 73883) by debbugs.gnu.org; 20 Oct 2024 12:04:46 +0000 Received: from localhost ([127.0.0.1]:46198 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1t2Ufu-0003nx-0k for submit@debbugs.gnu.org; Sun, 20 Oct 2024 08:04:46 -0400 Received: from mail-pl1-f177.google.com ([209.85.214.177]:49555) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1t2UQr-00033W-SQ for 73883@debbugs.gnu.org; Sun, 20 Oct 2024 07:49:14 -0400 Received: by mail-pl1-f177.google.com with SMTP id d9443c01a7336-20cdda5cfb6so36962265ad.3 for <73883@debbugs.gnu.org>; Sun, 20 Oct 2024 04:48:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1729424868; x=1730029668; darn=debbugs.gnu.org; h=in-reply-to:content-language:references:to:from:subject:user-agent :mime-version:date:message-id:from:to:cc:subject:date:message-id :reply-to; bh=S8oIBG/1JK+HoeNF9TrNxpw4pSGaK8GclVEdrxfOZqE=; b=YsDKyymrI0e3pdc2RvAATcfF937J4dpHmqWft4uUnlTO4nTleKwX20noq7XC1gvPf/ FSkJfScI67n9KvmSmluiINlPtdICalJJRghBT30XZt/+e/zlQEEfSn0F92MdVPlPNUCd iVqiLgBAkmgtbxBGvoW0XMcMOZ6GGDNXCmRPg5LSGHdrJjw1RjOkyZd0FTqUrKuIv9LV knXZOUObSalLzItsU9uXfhL225lhWlUyhjjAGh1smNAfNRAXHWzl8uwHR/onqpESgRwI oe3gNZFE83RIrd01S2dDnSLKJKenEYoCHL9Cf0IOW3yqE+RXY8WMyJUE5VXT6t+A+Xm3 L9Og== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729424868; x=1730029668; h=in-reply-to:content-language:references:to:from:subject:user-agent :mime-version:date:message-id:x-gm-message-state:from:to:cc:subject :date:message-id:reply-to; bh=S8oIBG/1JK+HoeNF9TrNxpw4pSGaK8GclVEdrxfOZqE=; b=RRqEjJe0FuiWhWpgi0bJw6U4uucGyq935I1a4wQtVXdWkQqMZpwG09E/gGkpJF9xBl OcM0Et5vTC5zv0FKgonwfR5leDZ+aExZFxYm7cllXWsKW0gJScnr5SE+yyVUqhJDhXEH D5sR5WPpOYet41KD+/5nSAZoc1D0wTZ2wo0mkZQFR7nANZnUtU3AylMR2vOFzhhaubHM BO1+OyrKCq0DSUrBUFerk00jI5RawoGWEhr1L9O1Yj7W3nKRoSr5wT/TJr9JQuBhz+/H orEwQDqyDURyuMxagJ0kqiVIP6K95ROrFgwaW29pCMgMvF5oZxT/uvA20PTwcB0MrIRm CekA== X-Gm-Message-State: AOJu0Yxu5jnG5eRh0aL8rgyc3p00jpHuUBHRO48Sz0LZSAWxkLoh4xJX f1wHuOnqm36iJxCBjFb5oUcvNsmbEf4FK3BZUg6BqH5yqFCYndjKjJAEvzROsKI= X-Google-Smtp-Source: AGHT+IG/415oquC+YXS63MRGh8nQTYw1ZtiKN7U732YIEiiPgT2x/KtxafkFzhRnGLdSa0gnvJ/Kqw== X-Received: by 2002:a17:902:e5c6:b0:20b:49f5:9999 with SMTP id d9443c01a7336-20e5a921da0mr120832515ad.30.1729424867322; Sun, 20 Oct 2024 04:47:47 -0700 (PDT) Received: from [127.0.0.1] ([64.176.36.230]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-20e7f106c01sm9003895ad.300.2024.10.20.04.47.45 for <73883@debbugs.gnu.org> (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Sun, 20 Oct 2024 04:47:46 -0700 (PDT) Content-Type: multipart/mixed; boundary="------------YTR8mj80epC2vzTcYP0170Ey" Message-ID: Date: Sun, 20 Oct 2024 19:47:41 +0800 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird From: Ethan Kong References: Content-Language: en-US In-Reply-To: X-Spam-Score: 0.0 (/) X-Mailman-Approved-At: Sun, 20 Oct 2024 08:04:44 -0400 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.0 (-) This is a multi-part message in MIME format. --------------YTR8mj80epC2vzTcYP0170Ey Content-Type: multipart/alternative; boundary="------------q6R8kxGBLQOK3Q8WP00xNOJv" --------------q6R8kxGBLQOK3Q8WP00xNOJv Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit I realize the previous title might have been misleading, so I'm replying with a more suitable one. The summary line of the patch is also updated. On 2024/10/19 18:53, Ethan Kong wrote: > Tags: patch > > Hi, > > When I use 'equal' on large, cyclic objects, emacs freezes. > > Reproduce: > >     ;; emacs -Q >     (require 'org-element) > >     ;; get two identical `org-element' trees of this file >     ;; > https://github.com/emacs-mirror/emacs/blob/master/doc/misc/modus-themes.org >     (let ((file (expand-file-name "doc/misc/modus-themes.org > " >                                   source-directory))) >       (with-current-buffer (find-file-noselect file) >         (setq org-o1 (org-element-parse-buffer)) >         (org-element-cache-reset) >         (setq org-o2 (org-element-parse-buffer)))) > >     ;; the test >     (equal org-o1 org-o2) > > This equal call freezes emacs. And the memory usage of emacs grows > quickly, until I quit. Reproduced with emacs 29.4 and the master branch. > > > The cause: > > Current code on the master branch: > >     static bool >     internal_equal (Lisp_Object o1, Lisp_Object o2, enum equal_kind > equal_kind, >                     int depth, Lisp_Object ht) >     { >      tail_recurse: >       if (depth > 10) >         { >           // ... >           if (NILP (ht)) >             ht = CALLN (Fmake_hash_table, QCtest, Qeq); >           // ... >         } >       // ... >             if (! internal_equal (XCAR (o1), XCAR (o2), >                                   equal_kind, depth + 1, ht)) >               return false; >             // ... >     } > > When internal_equal calls itself, it passes the hash table argument 'ht' > by value. As a result, each internal_equal(depth=11) call initializes > its own hash table, separately recording the objects it encounters in > further recursive calls. This leads to excessive 'hash_put' and > significant memory allocation. > > > Fix: > > Make internal_equal pass the hash table by pointer (see the patch). > > With this patch, the test above returns quickly: > >     (benchmark-run 100 (equal org-o1 org-o2)) > > (2.562444 20 0.30933900000000014) > > This will also improve the performance for smaller cyclic objects: > >     ;; emacs -Q >     (defun make-cyclic (n m) >       (let* ((l1 (make-list n 1)) >              (l2 (make-list m 2))) >         (setf (nth (1- m) l2) l1) >         (setf (nth (1- n) l1) l2) >         l1)) > >     (let ((a (make-cyclic 100 7)) >           (b (make-cyclic 100 7))) >       (cl-assert (equal a b)) >       (benchmark-run 10000 (equal a b))) > > Current: > (0.530081 32 0.49294199999999977) > > With the patch: > (0.036401 1 0.0173350000000001) > > And it passes all the tests in 'make fns-tests'. > > > P.S. Could I get the copyright assignment paperwork please? > > Best, > Ethan Kong > > > In GNU Emacs 29.4 (build 2, x86_64-w64-mingw32) of 2024-07-05 built on >  AVALON > Windowing system distributor 'Microsoft Corp.', version 10.0.22631 > System Description: Microsoft Windows 10 Pro (v10.0.2009.22631.4317) > > Configured using: >  'configure --with-modules --without-dbus --with-native-compilation=aot >  --without-compress-install --with-sqlite3 --with-tree-sitter >  CFLAGS=-O2' --------------q6R8kxGBLQOK3Q8WP00xNOJv Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit

I realize the previous title might have been misleading, so I'm replying with a
more suitable one. The summary line of the patch is also updated.

On 2024/10/19 18:53, Ethan Kong wrote:
Tags: patch

Hi,

When I use 'equal' on large, cyclic objects, emacs freezes.

Reproduce:

    ;; emacs -Q
    (require 'org-element)

    ;; get two identical `org-element' trees of this file
    ;; https://github.com/emacs-mirror/emacs/blob/master/doc/misc/modus-themes.org
    (let ((file (expand-file-name "doc/misc/modus-themes.org"
                                  source-directory)))
      (with-current-buffer (find-file-noselect file)
        (setq org-o1 (org-element-parse-buffer))
        (org-element-cache-reset)
        (setq org-o2 (org-element-parse-buffer))))

    ;; the test
    (equal org-o1 org-o2)

This equal call freezes emacs. And the memory usage of emacs grows
quickly, until I quit. Reproduced with emacs 29.4 and the master branch.


The cause:

Current code on the master branch:

    static bool
    internal_equal (Lisp_Object o1, Lisp_Object o2, enum equal_kind equal_kind,
                    int depth, Lisp_Object ht)
    {
     tail_recurse:
      if (depth > 10)
        {
          // ...
          if (NILP (ht))
            ht = CALLN (Fmake_hash_table, QCtest, Qeq);
          // ...
        }
      // ...
            if (! internal_equal (XCAR (o1), XCAR (o2),
                                  equal_kind, depth + 1, ht))
              return false;
            // ...
    }

When internal_equal calls itself, it passes the hash table argument 'ht'
by value. As a result, each internal_equal(depth=11) call initializes
its own hash table, separately recording the objects it encounters in
further recursive calls. This leads to excessive 'hash_put' and
significant memory allocation.


Fix:

Make internal_equal pass the hash table by pointer (see the patch).

With this patch, the test above returns quickly:

    (benchmark-run 100 (equal org-o1 org-o2))

(2.562444 20 0.30933900000000014)

This will also improve the performance for smaller cyclic objects:

    ;; emacs -Q
    (defun make-cyclic (n m)
      (let* ((l1 (make-list n 1))
             (l2 (make-list m 2)))
        (setf (nth (1- m) l2) l1)
        (setf (nth (1- n) l1) l2)
        l1))

    (let ((a (make-cyclic 100 7))
          (b (make-cyclic 100 7)))
      (cl-assert (equal a b))
      (benchmark-run 10000 (equal a b)))

Current:
(0.530081 32 0.49294199999999977)

With the patch:
(0.036401 1 0.0173350000000001)

And it passes all the tests in 'make fns-tests'.


P.S. Could I get the copyright assignment paperwork please?

Best,
Ethan Kong


In GNU Emacs 29.4 (build 2, x86_64-w64-mingw32) of 2024-07-05 built on
 AVALON
Windowing system distributor 'Microsoft Corp.', version 10.0.22631
System Description: Microsoft Windows 10 Pro (v10.0.2009.22631.4317)

Configured using:
 'configure --with-modules --without-dbus --with-native-compilation=aot
 --without-compress-install --with-sqlite3 --with-tree-sitter
 CFLAGS=-O2'
--------------q6R8kxGBLQOK3Q8WP00xNOJv-- --------------YTR8mj80epC2vzTcYP0170Ey Content-Type: text/plain; charset=UTF-8; name="0001-Fix-equal-freezing-on-large-cyclic-objects.patch" Content-Disposition: attachment; filename="0001-Fix-equal-freezing-on-large-cyclic-objects.patch" Content-Transfer-Encoding: base64 RnJvbSA5ZmJiNzZlYWYwYjUzZGMzYzcyOWQ4NzU5NzA2M2U2MTIzNzE3NWQ3IE1vbiBTZXAg MTcgMDA6MDA6MDAgMjAwMQpGcm9tOiBFdGhhbiBLb25nIDxlay5ldGhhbi5rb25nQGdtYWls LmNvbT4KRGF0ZTogU2F0LCAxOSBPY3QgMjAyNCAxMjo0MzoyNyArMDgwMApTdWJqZWN0OiBb UEFUQ0hdIEZpeCAnZXF1YWwnIGZyZWV6aW5nIG9uIGxhcmdlIGN5Y2xpYyBvYmplY3RzCgoq IHNyYy9mbnMuYyAoaW50ZXJuYWxfZXF1YWwpOiBEZWxlZ2F0ZSB0byBpbnRlcm5hbF9lcXVh bF8xLgooaW50ZXJuYWxfZXF1YWxfMSk6IE5ldyBmdW5jdGlvbi4gUGFzcyB0aGUgaGFzaCB0 YWJsZSBhcmd1bWVudCBieQpwb2ludGVyIGluc3RlYWQgb2YgYnkgdmFsdWUuCi0tLQogc3Jj L2Zucy5jIHwgMjMgKysrKysrKysrKysrKysrLS0tLS0tLS0KIDEgZmlsZSBjaGFuZ2VkLCAx NSBpbnNlcnRpb25zKCspLCA4IGRlbGV0aW9ucygtKQoKZGlmZiAtLWdpdCBhL3NyYy9mbnMu YyBiL3NyYy9mbnMuYwppbmRleCAyZGUwNGQwNjUxOS4uZWY2OTIyYzEzN2IgMTAwNjQ0Ci0t LSBhL3NyYy9mbnMuYworKysgYi9zcmMvZm5zLmMKQEAgLTI4MjMsOCArMjgyMyw4IEBAIGVx dWFsX25vX3F1aXQgKExpc3BfT2JqZWN0IG8xLCBMaXNwX09iamVjdCBvMikKICAgIGlmIEVR VUFMX0tJTkQgPT0gRVFVQUxfTk9fUVVJVC4gICovCiAKIHN0YXRpYyBib29sCi1pbnRlcm5h bF9lcXVhbCAoTGlzcF9PYmplY3QgbzEsIExpc3BfT2JqZWN0IG8yLCBlbnVtIGVxdWFsX2tp bmQgZXF1YWxfa2luZCwKLQkJaW50IGRlcHRoLCBMaXNwX09iamVjdCBodCkKK2ludGVybmFs X2VxdWFsXzEgKExpc3BfT2JqZWN0IG8xLCBMaXNwX09iamVjdCBvMiwgZW51bSBlcXVhbF9r aW5kIGVxdWFsX2tpbmQsCisJCSAgaW50IGRlcHRoLCBMaXNwX09iamVjdCAqaHQpCiB7CiAg dGFpbF9yZWN1cnNlOgogICBpZiAoZGVwdGggPiAxMCkKQEAgLTI4MzIsMTMgKzI4MzIsMTMg QEAgaW50ZXJuYWxfZXF1YWwgKExpc3BfT2JqZWN0IG8xLCBMaXNwX09iamVjdCBvMiwgZW51 bSBlcXVhbF9raW5kIGVxdWFsX2tpbmQsCiAgICAgICBlYXNzZXJ0IChlcXVhbF9raW5kICE9 IEVRVUFMX05PX1FVSVQpOwogICAgICAgaWYgKGRlcHRoID4gMjAwKQogCWVycm9yICgiU3Rh Y2sgb3ZlcmZsb3cgaW4gZXF1YWwiKTsKLSAgICAgIGlmIChOSUxQIChodCkpCi0JaHQgPSBD QUxMTiAoRm1ha2VfaGFzaF90YWJsZSwgUUN0ZXN0LCBRZXEpOworICAgICAgaWYgKE5JTFAg KCpodCkpCisJKmh0ID0gQ0FMTE4gKEZtYWtlX2hhc2hfdGFibGUsIFFDdGVzdCwgUWVxKTsK ICAgICAgIHN3aXRjaCAoWFRZUEUgKG8xKSkKIAl7CiAJY2FzZSBMaXNwX0NvbnM6IGNhc2Ug TGlzcF9WZWN0b3JsaWtlOgogCSAgewotCSAgICBzdHJ1Y3QgTGlzcF9IYXNoX1RhYmxlICpo ID0gWEhBU0hfVEFCTEUgKGh0KTsKKwkgICAgc3RydWN0IExpc3BfSGFzaF9UYWJsZSAqaCA9 IFhIQVNIX1RBQkxFICgqaHQpOwogCSAgICBoYXNoX2hhc2hfdCBoYXNoID0gaGFzaF9mcm9t X2tleSAoaCwgbzEpOwogCSAgICBwdHJkaWZmX3QgaSA9IGhhc2hfbG9va3VwX3dpdGhfaGFz aCAoaCwgbzEsIGhhc2gpOwogCSAgICBpZiAoaSA+PSAwKQpAQCAtMjg4OCw4ICsyODg4LDgg QEAgaW50ZXJuYWxfZXF1YWwgKExpc3BfT2JqZWN0IG8xLCBMaXNwX09iamVjdCBvMiwgZW51 bSBlcXVhbF9raW5kIGVxdWFsX2tpbmQsCiAJICB7CiAJICAgIGlmICghIENPTlNQIChvMikp CiAJICAgICAgcmV0dXJuIGZhbHNlOwotCSAgICBpZiAoISBpbnRlcm5hbF9lcXVhbCAoWENB UiAobzEpLCBYQ0FSIChvMiksCi0JCQkJICBlcXVhbF9raW5kLCBkZXB0aCArIDEsIGh0KSkK KwkgICAgaWYgKCEgaW50ZXJuYWxfZXF1YWxfMSAoWENBUiAobzEpLCBYQ0FSIChvMiksCisJ CQkJICAgIGVxdWFsX2tpbmQsIGRlcHRoICsgMSwgaHQpKQogCSAgICAgIHJldHVybiBmYWxz ZTsKIAkgICAgbzIgPSBYQ0RSIChvMik7CiAJICAgIGlmIChFUSAoWENEUiAobzEpLCBvMikp CkBAIC0yOTY0LDcgKzI5NjQsNyBAQCBpbnRlcm5hbF9lcXVhbCAoTGlzcF9PYmplY3QgbzEs IExpc3BfT2JqZWN0IG8yLCBlbnVtIGVxdWFsX2tpbmQgZXF1YWxfa2luZCwKIAkgICAgTGlz cF9PYmplY3QgdjEsIHYyOwogCSAgICB2MSA9IEFSRUYgKG8xLCBpKTsKIAkgICAgdjIgPSBB UkVGIChvMiwgaSk7Ci0JICAgIGlmICghaW50ZXJuYWxfZXF1YWwgKHYxLCB2MiwgZXF1YWxf a2luZCwgZGVwdGggKyAxLCBodCkpCisJICAgIGlmICghaW50ZXJuYWxfZXF1YWxfMSAodjEs IHYyLCBlcXVhbF9raW5kLCBkZXB0aCArIDEsIGh0KSkKIAkgICAgICByZXR1cm4gZmFsc2U7 CiAJICB9CiAJcmV0dXJuIHRydWU7CkBAIC0yOTg1LDYgKzI5ODUsMTMgQEAgaW50ZXJuYWxf ZXF1YWwgKExpc3BfT2JqZWN0IG8xLCBMaXNwX09iamVjdCBvMiwgZW51bSBlcXVhbF9raW5k IGVxdWFsX2tpbmQsCiAgIHJldHVybiBmYWxzZTsKIH0KIAorc3RhdGljIGJvb2wKK2ludGVy bmFsX2VxdWFsIChMaXNwX09iamVjdCBvMSwgTGlzcF9PYmplY3QgbzIsIGVudW0gZXF1YWxf a2luZCBlcXVhbF9raW5kLAorCQlpbnQgZGVwdGgsIExpc3BfT2JqZWN0IGh0KQoreworICBy ZXR1cm4gaW50ZXJuYWxfZXF1YWxfMSAobzEsIG8yLCBlcXVhbF9raW5kLCBkZXB0aCwgJmh0 KTsKK30KKwogLyogUmV0dXJuIC0xLzAvMSBmb3IgdGhlIDwvPS8+IGxleGljb2dyYXBoaWMg cmVsYXRpb24gYmV0d2VlbiBib29sLXZlY3RvcnMuICAqLwogc3RhdGljIGludAogYm9vbF92 ZWN0b3JfY21wIChMaXNwX09iamVjdCBhLCBMaXNwX09iamVjdCBiKQotLSAKMi40My4wLndp bmRvd3MuMQoK --------------YTR8mj80epC2vzTcYP0170Ey-- From unknown Thu Aug 14 21:46:20 2025 X-Loop: help-debbugs@gnu.org Subject: bug#73883: [PATCH] Fix 'equal' freezing on large cyclic objects Resent-From: Eli Zaretskii Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sat, 02 Nov 2024 11:42:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 73883 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: Ethan Kong , Stefan Monnier , Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= Cc: 73883@debbugs.gnu.org Received: via spool by 73883-submit@debbugs.gnu.org id=B73883.173054771431618 (code B ref 73883); Sat, 02 Nov 2024 11:42:02 +0000 Received: (at 73883) by debbugs.gnu.org; 2 Nov 2024 11:41:54 +0000 Received: from localhost ([127.0.0.1]:53349 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1t7CVt-0008Du-VG for submit@debbugs.gnu.org; Sat, 02 Nov 2024 07:41:54 -0400 Received: from eggs.gnu.org ([209.51.188.92]:49318) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1t7CVs-0008Dk-04 for 73883@debbugs.gnu.org; Sat, 02 Nov 2024 07:41:52 -0400 Received: from fencepost.gnu.org ([2001:470:142:3::e]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1t7CVk-0004wD-Sp; Sat, 02 Nov 2024 07:41:44 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org; s=fencepost-gnu-org; h=MIME-version:References:Subject:In-Reply-To:To:From: Date; bh=Hf3+B9vu4yuBxpeAL62BO7itZk4u0TZK9AxcC2Istck=; b=TfItr9scQft2svskKq3V zyUFrwaXMAhOot7cHdzfJ539oxAymUQL6HX3Gxc3c5ZtyEm7b3YqdkzWc7jwQOGRw0l1fiOVPH7IK 1lF7/I/PiG2e7e7ukdDp/XNGVKBR3dHhxPqIUPT26heUnkGfLryM3QOFyYLY4CI7Aazr0E98PCEXF xB5zVbMfn6Oc5CSBZxI2vLrksvcZarnc1YZjD5WYjxUixmiHrrUQo3KA89rpYB+XnKdS1i9dBUtwA j76zm4dBKMzXY1qaFyEO90bEn9e0Z0xxgzwCjYSUee+bgBhiPgIoTSswX9rnGqdBFij/i08wpM/z0 u82+Lie47lTXMg==; Date: Sat, 02 Nov 2024 13:41:42 +0200 Message-Id: <861pztzwuh.fsf@gnu.org> From: Eli Zaretskii In-Reply-To: (message from Ethan Kong on Sun, 20 Oct 2024 19:47:41 +0800) References: MIME-version: 1.0 Content-type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Spam-Score: -2.3 (--) 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.3 (---) > Date: Sun, 20 Oct 2024 19:47:41 +0800 > From: Ethan Kong > > I realize the previous title might have been misleading, so I'm replying with a > more suitable one. The summary line of the patch is also updated. > > On 2024/10/19 18:53, Ethan Kong wrote: > > Tags: patch > > Hi, > > When I use 'equal' on large, cyclic objects, emacs freezes. > > Reproduce: > > ;; emacs -Q > (require 'org-element) > > ;; get two identical `org-element' trees of this file > ;; https://github.com/emacs-mirror/emacs/blob/master/doc/misc/modus-themes.org > (let ((file (expand-file-name "doc/misc/modus-themes.org" > source-directory))) > (with-current-buffer (find-file-noselect file) > (setq org-o1 (org-element-parse-buffer)) > (org-element-cache-reset) > (setq org-o2 (org-element-parse-buffer)))) > > ;; the test > (equal org-o1 org-o2) > > This equal call freezes emacs. And the memory usage of emacs grows > quickly, until I quit. Reproduced with emacs 29.4 and the master branch. > > The cause: > > Current code on the master branch: > > static bool > internal_equal (Lisp_Object o1, Lisp_Object o2, enum equal_kind equal_kind, > int depth, Lisp_Object ht) > { > tail_recurse: > if (depth > 10) > { > // ... > if (NILP (ht)) > ht = CALLN (Fmake_hash_table, QCtest, Qeq); > // ... > } > // ... > if (! internal_equal (XCAR (o1), XCAR (o2), > equal_kind, depth + 1, ht)) > return false; > // ... > } > > When internal_equal calls itself, it passes the hash table argument 'ht' > by value. As a result, each internal_equal(depth=11) call initializes > its own hash table, separately recording the objects it encounters in > further recursive calls. This leads to excessive 'hash_put' and > significant memory allocation. > > Fix: > > Make internal_equal pass the hash table by pointer (see the patch). > > With this patch, the test above returns quickly: > > (benchmark-run 100 (equal org-o1 org-o2)) > > (2.562444 20 0.30933900000000014) > > This will also improve the performance for smaller cyclic objects: > > ;; emacs -Q > (defun make-cyclic (n m) > (let* ((l1 (make-list n 1)) > (l2 (make-list m 2))) > (setf (nth (1- m) l2) l1) > (setf (nth (1- n) l1) l2) > l1)) > > (let ((a (make-cyclic 100 7)) > (b (make-cyclic 100 7))) > (cl-assert (equal a b)) > (benchmark-run 10000 (equal a b))) > > Current: > (0.530081 32 0.49294199999999977) > > With the patch: > (0.036401 1 0.0173350000000001) > > And it passes all the tests in 'make fns-tests'. > > P.S. Could I get the copyright assignment paperwork please? > > Best, > Ethan Kong > > In GNU Emacs 29.4 (build 2, x86_64-w64-mingw32) of 2024-07-05 built on > AVALON > Windowing system distributor 'Microsoft Corp.', version 10.0.22631 > System Description: Microsoft Windows 10 Pro (v10.0.2009.22631.4317) > > Configured using: > 'configure --with-modules --without-dbus --with-native-compilation=aot > --without-compress-install --with-sqlite3 --with-tree-sitter > CFLAGS=-O2' Stefan and Mattias, any comments or suggestions? From unknown Thu Aug 14 21:46:20 2025 X-Loop: help-debbugs@gnu.org Subject: bug#73883: [PATCH] Fix 'equal' freezing on large cyclic objects Resent-From: Ethan Kong Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Fri, 08 Nov 2024 13:56:03 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 73883 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: Eli Zaretskii , Stefan Monnier , Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= , Stefan Kangas Cc: 73883@debbugs.gnu.org Received: via spool by 73883-submit@debbugs.gnu.org id=B73883.173107414530513 (code B ref 73883); Fri, 08 Nov 2024 13:56:03 +0000 Received: (at 73883) by debbugs.gnu.org; 8 Nov 2024 13:55:45 +0000 Received: from localhost ([127.0.0.1]:51581 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1t9PSf-0007w1-Mt for submit@debbugs.gnu.org; Fri, 08 Nov 2024 08:55:44 -0500 Received: from mail-pf1-f177.google.com ([209.85.210.177]:51427) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1t9PCC-000785-Ut for 73883@debbugs.gnu.org; Fri, 08 Nov 2024 08:38:42 -0500 Received: by mail-pf1-f177.google.com with SMTP id d2e1a72fcca58-71e52582cf8so1711809b3a.2 for <73883@debbugs.gnu.org>; Fri, 08 Nov 2024 05:38:40 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1731073055; x=1731677855; darn=debbugs.gnu.org; h=content-transfer-encoding:in-reply-to:from:content-language :references:cc:to:subject:user-agent:mime-version:date:message-id :from:to:cc:subject:date:message-id:reply-to; bh=KgsjyNIH2kqRVkYh4UbRmry82yP75TsEdKbXAVt2+qg=; b=attvgThcrjT700d6xV2JgOw97Xw7dxH143C0B22KLT/2wTXD+t6qjdQpcTmVAvmIbA Tjy5vr5KrtssKqQtm3D/r2z/SqzyMFuHSFD0ZqjVDcLNvimMaA8ue9X4CQ2fHT+10uDN /r8sYvpPKl3+DIRp5vtGxeBAyw+hf9rFWPrxvnXRN5kE7o0gfxqPL0yOnLv6B+xX48mb zeKZ7cBo81xmWXwDMBj3mKcGDzo/KtjKTNfqGIcvT2o4l1IQnxTMhRok4+FhWUgx8u2j i5BJxYZuF4h1kDC+PHgIGPWwdg5wYhnRhuph/xytMYX0xSiBSpoFrYXUXr59sR/hY4Ty VT9w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1731073055; x=1731677855; h=content-transfer-encoding:in-reply-to:from:content-language :references:cc:to:subject:user-agent:mime-version:date:message-id :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=KgsjyNIH2kqRVkYh4UbRmry82yP75TsEdKbXAVt2+qg=; b=gtfgqM07T65BhL59Tbb+P2uHXfJSHlz7Zx5RCWWMR+7eAcqzjY3J42AOZyOQwcMiB8 srpGIjk6/XTIT5P4jfosTeUcnkjRxqi1bhYz9YsO6noFE34Fymzqwi3QFt8jKqJqZsGT oK7O1xnQsHQkaB19JXFzTvPnnhoKpw/Ry8cGjSTyb3mMkeP0phRuORTbhL7lf20QW5mz xgqOd2qWm4UUxybwtoUSwcNZh4miuJwnBSL5c+TjLNFKM75vUEtCPcO6Jz8aHK4SxCpB uTc9S2A6lZMD25+IvobQYEpqOHBSNQN99s9e8SyfK1MygW0fFBYcn25WfymaiE71Lr+r t2Ig== X-Gm-Message-State: AOJu0Yw0PXf2tkvV/RNiTorV1EK9TjrLQbba54bUgxtyYDuf/XE2nniU 864RgopIqeep6hffTMt17bGNDlOmzqGsF4BTln44oYwiY4wYFVmi X-Google-Smtp-Source: AGHT+IEIOzqCV16LywL9+rjbUiJzyCAU73ylZ7dyx9wm6ekoIhDvF3FKpUQ+5vHxuRWcIsoyVYstcA== X-Received: by 2002:a05:6a00:22cb:b0:71e:5de:ad6d with SMTP id d2e1a72fcca58-7241338c2ccmr3820138b3a.24.1731073054895; Fri, 08 Nov 2024 05:37:34 -0800 (PST) Received: from [127.0.0.1] ([64.176.36.230]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-724079aa994sm3742482b3a.129.2024.11.08.05.37.32 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 08 Nov 2024 05:37:34 -0800 (PST) Message-ID: Date: Fri, 8 Nov 2024 21:37:27 +0800 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird References: <861pztzwuh.fsf@gnu.org> Content-Language: en-US From: Ethan Kong In-Reply-To: <861pztzwuh.fsf@gnu.org> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 0.0 (/) X-Mailman-Approved-At: Fri, 08 Nov 2024 08:55:40 -0500 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.0 (-) Hi, On 24/10/20 19:55, Stefan Kangas wrote: > Ethan Kong writes: > >> P.S. Could I get the copyright assignment paperwork please? > Form sent off-list. Just to let you know that my FSF Copyright Assignment process is complete. Best, Ethan Kong From unknown Thu Aug 14 21:46:20 2025 X-Loop: help-debbugs@gnu.org Subject: bug#73883: [PATCH] Fix 'equal' freezing on large cyclic objects Resent-From: Stefan Monnier Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Fri, 08 Nov 2024 18:59:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 73883 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: Eli Zaretskii Cc: Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= , Ethan Kong , 73883@debbugs.gnu.org Received: via spool by 73883-submit@debbugs.gnu.org id=B73883.173109228919274 (code B ref 73883); Fri, 08 Nov 2024 18:59:01 +0000 Received: (at 73883) by debbugs.gnu.org; 8 Nov 2024 18:58:09 +0000 Received: from localhost ([127.0.0.1]:52164 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1t9UBN-00050o-5B for submit@debbugs.gnu.org; Fri, 08 Nov 2024 13:58:09 -0500 Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:27904) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1t9UBL-00050Q-16 for 73883@debbugs.gnu.org; Fri, 08 Nov 2024 13:58:07 -0500 Received: from pmg3.iro.umontreal.ca (localhost [127.0.0.1]) by pmg3.iro.umontreal.ca (Proxmox) with ESMTP id E5447444636; Fri, 8 Nov 2024 13:58:00 -0500 (EST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca; s=mail; t=1731092279; bh=AXbMf6iCVZbDxBZBlMX3L49Grb7ptLkr0/z33WTbiGs=; h=From:To:Cc:Subject:In-Reply-To:References:Date:From; b=kK+x4+yb6W/L+CArfoMiMAeZ3tJw/xWn9HOA05t8EXzA+7ATv7Ae+katn+hhKkNYF N2IbX1trLsOFRoNPl0iAQ72aNJbgt8q3KwfeKnlOgsdaVykIhFFMZgWF3sXC7Mr/1h 8M0g3YMF0Gl0HmRs787UIdDb5plCr4jxdxX+ae8cR5JUYccRdPfxSOHGZkKQEiCLEc yrzsA3XkA/SQr+4YIbTyS6qZFZh5NwK7gJFDwv7F2s8dOfQFNqEgESZqrwut/lHubR oK5w1MCuvCnY7fIAGbUEjmiT4kxVPEEulQlSCQBLicD1OC+xd6i8OYTkOETH7MjnyD jSmHB4LBNo/1w== Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1]) by pmg3.iro.umontreal.ca (Proxmox) with ESMTP id E6A6F444633; Fri, 8 Nov 2024 13:57:59 -0500 (EST) Received: from asado (bras-base-mtrlpq0776w-grc-08-184-145-223-228.dsl.bell.ca [184.145.223.228]) by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id D4B88120065; Fri, 8 Nov 2024 13:57:59 -0500 (EST) From: Stefan Monnier In-Reply-To: <861pztzwuh.fsf@gnu.org> (Eli Zaretskii's message of "Sat, 02 Nov 2024 13:41:42 +0200") Message-ID: References: <861pztzwuh.fsf@gnu.org> Date: Fri, 08 Nov 2024 13:57:59 -0500 User-Agent: Gnus/5.13 (Gnus v5.13) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-SPAM-INFO: Spam detection results: 0 ALL_TRUSTED -1 Passed through trusted hosts only via SMTP AWL -0.119 Adjusted score from AWL reputation of From: address BAYES_00 -1.9 Bayes spam probability is 0 to 1% DKIM_SIGNED 0.1 Message has a DKIM or DK signature, not necessarily valid DKIM_VALID -0.1 Message has at least one valid DKIM or DK signature DKIM_VALID_AU -0.1 Message has a valid DKIM or DK signature from author's domain DKIM_VALID_EF -0.1 Message has a valid DKIM or DK signature from envelope-from domain X-SPAM-LEVEL: X-Spam-Score: -2.3 (--) 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.3 (---) >> I realize the previous title might have been misleading, so I'm >> replying with a more suitable one. The summary line of the patch is >> also updated. While the new title is arguably better for a bug report, the old one was better at describing your patch. =F0=9F=99=82 > Stefan and Mattias, any comments or suggestions? Looks good to me, Stefan From unknown Thu Aug 14 21:46:20 2025 X-Loop: help-debbugs@gnu.org Subject: bug#73883: [PATCH] Fix 'equal' freezing on large cyclic objects Resent-From: Ethan Kong Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sat, 09 Nov 2024 08:22:03 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 73883 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: Stefan Monnier Cc: 73883@debbugs.gnu.org Received: via spool by 73883-submit@debbugs.gnu.org id=B73883.173114048728956 (code B ref 73883); Sat, 09 Nov 2024 08:22:03 +0000 Received: (at 73883) by debbugs.gnu.org; 9 Nov 2024 08:21:27 +0000 Received: from localhost ([127.0.0.1]:53285 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1t9gii-0007Wr-Fr for submit@debbugs.gnu.org; Sat, 09 Nov 2024 03:21:27 -0500 Received: from mail-pl1-f174.google.com ([209.85.214.174]:53326) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1t9cIa-0003A2-RX for 73883@debbugs.gnu.org; Fri, 08 Nov 2024 22:38:10 -0500 Received: by mail-pl1-f174.google.com with SMTP id d9443c01a7336-20ca388d242so31339125ad.2 for <73883@debbugs.gnu.org>; Fri, 08 Nov 2024 19:38:08 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1731123423; x=1731728223; darn=debbugs.gnu.org; h=in-reply-to:cc:from:content-language:references:to:subject :user-agent:mime-version:date:message-id:from:to:cc:subject:date :message-id:reply-to; bh=ZN9+M7eCakhm2Exw0/MnJ7qUVsIk9rFotWa5Ma2OfD8=; b=NoUf90XuGAx/Dgbgznt9RKn6zbiseH8vckMPhA1ZQG9MmJlEWmq7fdgm+ideikjrfq gvCdWj8hONHtlM9P4Pc72Pljt90DWgAyUSkJz+kB99XM4VX7ZeUBCykHcu2EfGBhzgIC xQDXtki5m/tlbi1ZW/qxyUL6CZkiX6h7LkM2gbx6AzL8guC5v8UEOih9ertWoLiUuhT8 8OfvYoKPRYCLODRvTKNG23usxMWQiFEDore/I6icmqyEDEDFxrvkcAUH2zu1h2W8jhcn kPm0GKyLOKg7Rk9QWoszwcHISugM3Jfi3mMAkDwL96MvggD8WT8UeEikLIJ3Hm8DPvjV Hr8w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1731123423; x=1731728223; h=in-reply-to:cc:from:content-language:references:to:subject :user-agent:mime-version:date:message-id:x-gm-message-state:from:to :cc:subject:date:message-id:reply-to; bh=ZN9+M7eCakhm2Exw0/MnJ7qUVsIk9rFotWa5Ma2OfD8=; b=v9MHAmU3wMWOaUZb9G6UOal1s1W1MgrIDT9arij6+FoNJ5qzLpcAQPYebZ6oCuos2l NhwUosnQOuDW9fxjd7TiSFbhLwj9anbk2eEhL4srkyT26axDr26f6h7w5r3CNZsRGJ3q LwJXkU3XONHzq6PQ1B1lXCk7C9stj7Kbtah84Etvfb/nqN7BIR/D3i25oA5j64YWZ2Tr yP24jSdLxVGerMNPx16JWQMrY1oleQ/XOpQpZUH8DxQzL9e3YE0U84WSJDaltdsM71bB TYtj43duPhUwqoa5zmLEdylO4/hxrNbH+zLtiiS6EmX702/uZMxYZzi74KIvE4GVoiP8 logA== X-Gm-Message-State: AOJu0YyZs5FGx3WmHrH4uPFxc3VhfNFolavn9NJjqCNylOpCph5WjCic MpaAyHmSjCghr8Sj3M/kyPL9vqQnIyZXdAkrX9GbL86rjAhfPUTh X-Google-Smtp-Source: AGHT+IHsxLi6UAHb0OFOpn7xO8oIacMBUORvRYx7WW6B1fpj31OXbi7MJL+bhp2mldkyjQOiMh2F6Q== X-Received: by 2002:a17:903:230a:b0:20b:b75d:e8c1 with SMTP id d9443c01a7336-21183d10969mr66214745ad.4.1731123422944; Fri, 08 Nov 2024 19:37:02 -0800 (PST) Received: from [127.0.0.1] ([64.176.36.230]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-21177e80019sm38340825ad.266.2024.11.08.19.37.01 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 08 Nov 2024 19:37:02 -0800 (PST) Content-Type: multipart/mixed; boundary="------------YK0obQDFzSGk5GfZU2RRJcP0" Message-ID: <84de8b8c-eecf-4c56-8c82-5b0236130efb@gmail.com> Date: Sat, 9 Nov 2024 11:36:56 +0800 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird References: <861pztzwuh.fsf@gnu.org> Content-Language: en-US From: Ethan Kong In-Reply-To: X-Spam-Score: 0.0 (/) X-Mailman-Approved-At: Sat, 09 Nov 2024 03:21:20 -0500 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.0 (-) This is a multi-part message in MIME format. --------------YK0obQDFzSGk5GfZU2RRJcP0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit On 24/11/09 02:57, Stefan Monnier wrote: > While the new title is arguably better for a bug report, the old one was > better at describing your patch. 🙂 I see. Here is the patch with the old summary line. --------------YK0obQDFzSGk5GfZU2RRJcP0 Content-Type: text/plain; charset=UTF-8; name="0001-Fix-internal_equal-so-that-it-uses-at-most-one-hash-.patch" Content-Disposition: attachment; filename*0="0001-Fix-internal_equal-so-that-it-uses-at-most-one-hash-.pa"; filename*1="tch" Content-Transfer-Encoding: base64 RnJvbSA0MjUyNzAxNzliYjIyNjMwYjdhZDU4NzFmY2ZjZWU4NDczN2I1NWZiIE1vbiBTZXAg MTcgMDA6MDA6MDAgMjAwMQpGcm9tOiBFdGhhbiBLb25nIDxlay5ldGhhbi5rb25nQGdtYWls LmNvbT4KRGF0ZTogU2F0LCAxOSBPY3QgMjAyNCAxMjo0MzoyNyArMDgwMApTdWJqZWN0OiBb UEFUQ0hdIEZpeCBpbnRlcm5hbF9lcXVhbCBzbyB0aGF0IGl0IHVzZXMgYXQgbW9zdCBvbmUg aGFzaCB0YWJsZQoKKiBzcmMvZm5zLmMgKGludGVybmFsX2VxdWFsKTogRGVsZWdhdGUgdG8g aW50ZXJuYWxfZXF1YWxfMS4KKGludGVybmFsX2VxdWFsXzEpOiBOZXcgZnVuY3Rpb24uIFBh c3MgdGhlIGhhc2ggdGFibGUgYXJndW1lbnQgYnkKcG9pbnRlciBpbnN0ZWFkIG9mIGJ5IHZh bHVlLgotLS0KIHNyYy9mbnMuYyB8IDIzICsrKysrKysrKysrKysrKy0tLS0tLS0tCiAxIGZp bGUgY2hhbmdlZCwgMTUgaW5zZXJ0aW9ucygrKSwgOCBkZWxldGlvbnMoLSkKCmRpZmYgLS1n aXQgYS9zcmMvZm5zLmMgYi9zcmMvZm5zLmMKaW5kZXggMmRlMDRkMDY1MTkuLmVmNjkyMmMx MzdiIDEwMDY0NAotLS0gYS9zcmMvZm5zLmMKKysrIGIvc3JjL2Zucy5jCkBAIC0yODIzLDgg KzI4MjMsOCBAQCBlcXVhbF9ub19xdWl0IChMaXNwX09iamVjdCBvMSwgTGlzcF9PYmplY3Qg bzIpCiAgICBpZiBFUVVBTF9LSU5EID09IEVRVUFMX05PX1FVSVQuICAqLwogCiBzdGF0aWMg Ym9vbAotaW50ZXJuYWxfZXF1YWwgKExpc3BfT2JqZWN0IG8xLCBMaXNwX09iamVjdCBvMiwg ZW51bSBlcXVhbF9raW5kIGVxdWFsX2tpbmQsCi0JCWludCBkZXB0aCwgTGlzcF9PYmplY3Qg aHQpCitpbnRlcm5hbF9lcXVhbF8xIChMaXNwX09iamVjdCBvMSwgTGlzcF9PYmplY3QgbzIs IGVudW0gZXF1YWxfa2luZCBlcXVhbF9raW5kLAorCQkgIGludCBkZXB0aCwgTGlzcF9PYmpl Y3QgKmh0KQogewogIHRhaWxfcmVjdXJzZToKICAgaWYgKGRlcHRoID4gMTApCkBAIC0yODMy LDEzICsyODMyLDEzIEBAIGludGVybmFsX2VxdWFsIChMaXNwX09iamVjdCBvMSwgTGlzcF9P YmplY3QgbzIsIGVudW0gZXF1YWxfa2luZCBlcXVhbF9raW5kLAogICAgICAgZWFzc2VydCAo ZXF1YWxfa2luZCAhPSBFUVVBTF9OT19RVUlUKTsKICAgICAgIGlmIChkZXB0aCA+IDIwMCkK IAllcnJvciAoIlN0YWNrIG92ZXJmbG93IGluIGVxdWFsIik7Ci0gICAgICBpZiAoTklMUCAo aHQpKQotCWh0ID0gQ0FMTE4gKEZtYWtlX2hhc2hfdGFibGUsIFFDdGVzdCwgUWVxKTsKKyAg ICAgIGlmIChOSUxQICgqaHQpKQorCSpodCA9IENBTExOIChGbWFrZV9oYXNoX3RhYmxlLCBR Q3Rlc3QsIFFlcSk7CiAgICAgICBzd2l0Y2ggKFhUWVBFIChvMSkpCiAJewogCWNhc2UgTGlz cF9Db25zOiBjYXNlIExpc3BfVmVjdG9ybGlrZToKIAkgIHsKLQkgICAgc3RydWN0IExpc3Bf SGFzaF9UYWJsZSAqaCA9IFhIQVNIX1RBQkxFIChodCk7CisJICAgIHN0cnVjdCBMaXNwX0hh c2hfVGFibGUgKmggPSBYSEFTSF9UQUJMRSAoKmh0KTsKIAkgICAgaGFzaF9oYXNoX3QgaGFz aCA9IGhhc2hfZnJvbV9rZXkgKGgsIG8xKTsKIAkgICAgcHRyZGlmZl90IGkgPSBoYXNoX2xv b2t1cF93aXRoX2hhc2ggKGgsIG8xLCBoYXNoKTsKIAkgICAgaWYgKGkgPj0gMCkKQEAgLTI4 ODgsOCArMjg4OCw4IEBAIGludGVybmFsX2VxdWFsIChMaXNwX09iamVjdCBvMSwgTGlzcF9P YmplY3QgbzIsIGVudW0gZXF1YWxfa2luZCBlcXVhbF9raW5kLAogCSAgewogCSAgICBpZiAo ISBDT05TUCAobzIpKQogCSAgICAgIHJldHVybiBmYWxzZTsKLQkgICAgaWYgKCEgaW50ZXJu YWxfZXF1YWwgKFhDQVIgKG8xKSwgWENBUiAobzIpLAotCQkJCSAgZXF1YWxfa2luZCwgZGVw dGggKyAxLCBodCkpCisJICAgIGlmICghIGludGVybmFsX2VxdWFsXzEgKFhDQVIgKG8xKSwg WENBUiAobzIpLAorCQkJCSAgICBlcXVhbF9raW5kLCBkZXB0aCArIDEsIGh0KSkKIAkgICAg ICByZXR1cm4gZmFsc2U7CiAJICAgIG8yID0gWENEUiAobzIpOwogCSAgICBpZiAoRVEgKFhD RFIgKG8xKSwgbzIpKQpAQCAtMjk2NCw3ICsyOTY0LDcgQEAgaW50ZXJuYWxfZXF1YWwgKExp c3BfT2JqZWN0IG8xLCBMaXNwX09iamVjdCBvMiwgZW51bSBlcXVhbF9raW5kIGVxdWFsX2tp bmQsCiAJICAgIExpc3BfT2JqZWN0IHYxLCB2MjsKIAkgICAgdjEgPSBBUkVGIChvMSwgaSk7 CiAJICAgIHYyID0gQVJFRiAobzIsIGkpOwotCSAgICBpZiAoIWludGVybmFsX2VxdWFsICh2 MSwgdjIsIGVxdWFsX2tpbmQsIGRlcHRoICsgMSwgaHQpKQorCSAgICBpZiAoIWludGVybmFs X2VxdWFsXzEgKHYxLCB2MiwgZXF1YWxfa2luZCwgZGVwdGggKyAxLCBodCkpCiAJICAgICAg cmV0dXJuIGZhbHNlOwogCSAgfQogCXJldHVybiB0cnVlOwpAQCAtMjk4NSw2ICsyOTg1LDEz IEBAIGludGVybmFsX2VxdWFsIChMaXNwX09iamVjdCBvMSwgTGlzcF9PYmplY3QgbzIsIGVu dW0gZXF1YWxfa2luZCBlcXVhbF9raW5kLAogICByZXR1cm4gZmFsc2U7CiB9CiAKK3N0YXRp YyBib29sCitpbnRlcm5hbF9lcXVhbCAoTGlzcF9PYmplY3QgbzEsIExpc3BfT2JqZWN0IG8y LCBlbnVtIGVxdWFsX2tpbmQgZXF1YWxfa2luZCwKKwkJaW50IGRlcHRoLCBMaXNwX09iamVj dCBodCkKK3sKKyAgcmV0dXJuIGludGVybmFsX2VxdWFsXzEgKG8xLCBvMiwgZXF1YWxfa2lu ZCwgZGVwdGgsICZodCk7Cit9CisKIC8qIFJldHVybiAtMS8wLzEgZm9yIHRoZSA8Lz0vPiBs ZXhpY29ncmFwaGljIHJlbGF0aW9uIGJldHdlZW4gYm9vbC12ZWN0b3JzLiAgKi8KIHN0YXRp YyBpbnQKIGJvb2xfdmVjdG9yX2NtcCAoTGlzcF9PYmplY3QgYSwgTGlzcF9PYmplY3QgYikK LS0gCjIuNDMuMC53aW5kb3dzLjEKCg== --------------YK0obQDFzSGk5GfZU2RRJcP0-- From unknown Thu Aug 14 21:46:20 2025 MIME-Version: 1.0 X-Mailer: MIME-tools 5.505 (Entity 5.505) X-Loop: help-debbugs@gnu.org From: help-debbugs@gnu.org (GNU bug Tracking System) To: Ethan Kong Subject: bug#73883: closed (Re: bug#73883: [PATCH] Fix 'equal' freezing on large cyclic objects) Message-ID: References: <868qtsok59.fsf@gnu.org> X-Gnu-PR-Message: they-closed 73883 X-Gnu-PR-Package: emacs X-Gnu-PR-Keywords: patch Reply-To: 73883@debbugs.gnu.org Date: Sat, 09 Nov 2024 09:03:02 +0000 Content-Type: multipart/mixed; boundary="----------=_1731142982-3518-1" This is a multi-part message in MIME format... ------------=_1731142982-3518-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Your bug report #73883: [PATCH] Fix internal_equal so that it uses at most one hash table which was filed against the emacs package, has been closed. The explanation is attached below, along with your original report. If you require more details, please reply to 73883@debbugs.gnu.org. --=20 73883: https://debbugs.gnu.org/cgi/bugreport.cgi?bug=3D73883 GNU Bug Tracking System Contact help-debbugs@gnu.org with problems ------------=_1731142982-3518-1 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit Received: (at 73883-done) by debbugs.gnu.org; 9 Nov 2024 09:02:12 +0000 Received: from localhost ([127.0.0.1]:53361 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1t9hMC-0000td-8w for submit@debbugs.gnu.org; Sat, 09 Nov 2024 04:02:12 -0500 Received: from eggs.gnu.org ([209.51.188.92]:33162) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1t9hM9-0000tR-UL for 73883-done@debbugs.gnu.org; Sat, 09 Nov 2024 04:02:10 -0500 Received: from fencepost.gnu.org ([2001:470:142:3::e]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1t9hM0-0000Oa-7X; Sat, 09 Nov 2024 04:02:01 -0500 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org; s=fencepost-gnu-org; h=MIME-version:References:Subject:In-Reply-To:To:From: Date; bh=2iBVhCyMm0qBVAbClcqFONW4hGtAKs/ZnHxUvmKrx+w=; b=USgKhVBPwjUfeyTOjL/o E4gTZXGZlda3IHecqfQh7gZDTXQEB9sgXmuUhpelfqOHPZSBkznQXf9g4oqRJ+AkAUjTsaK4OmgdE zv3b35HML8z9/HPhcf2Pg6uMkfHNGwIgdvkb9PP57ZARcFSZUlYnFf+vkrrHKKuik6GeKLnRKl9RL /jPsHs+lb5psx/zep5Wt49/RdjckXQNi1bfq9UPFBLip0ORhXCmkqC/1Tirq0ac4u/NzqMFyCmSa5 74bA9LC3SNdpjvq6DeEtkNjYj83QhUHHw+4c74HarryysFcgiKpFJ0yvphl5A49Ih3+33i0Ve3mhj XIB+Kcbo9vdVjA==; Date: Sat, 09 Nov 2024 11:01:54 +0200 Message-Id: <868qtsok59.fsf@gnu.org> From: Eli Zaretskii To: Ethan Kong In-Reply-To: <84de8b8c-eecf-4c56-8c82-5b0236130efb@gmail.com> (message from Ethan Kong on Sat, 9 Nov 2024 11:36:56 +0800) Subject: Re: bug#73883: [PATCH] Fix 'equal' freezing on large cyclic objects References: <861pztzwuh.fsf@gnu.org> <84de8b8c-eecf-4c56-8c82-5b0236130efb@gmail.com> MIME-version: 1.0 Content-type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 73883-done Cc: monnier@iro.umontreal.ca, 73883-done@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: -3.3 (---) > Cc: 73883@debbugs.gnu.org > Date: Sat, 9 Nov 2024 11:36:56 +0800 > From: Ethan Kong > > On 24/11/09 02:57, Stefan Monnier wrote: > > While the new title is arguably better for a bug report, the old one was > > better at describing your patch. 🙂 > > I see. Here is the patch with the old summary line. Thanks, installed on the master branch, and closing the bug. ------------=_1731142982-3518-1 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit Received: (at submit) by debbugs.gnu.org; 19 Oct 2024 14:25:53 +0000 Received: from localhost ([127.0.0.1]:44223 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1t2AOu-000327-UJ for submit@debbugs.gnu.org; Sat, 19 Oct 2024 10:25:53 -0400 Received: from lists.gnu.org ([209.51.188.17]:34540) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1t276B-00010F-M2 for submit@debbugs.gnu.org; Sat, 19 Oct 2024 06:54:20 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1t275n-0001dx-Mj for bug-gnu-emacs@gnu.org; Sat, 19 Oct 2024 06:53:55 -0400 Received: from mail-oo1-xc2c.google.com ([2607:f8b0:4864:20::c2c]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1t275l-00054E-OT for bug-gnu-emacs@gnu.org; Sat, 19 Oct 2024 06:53:55 -0400 Received: by mail-oo1-xc2c.google.com with SMTP id 006d021491bc7-5eb60f6b391so1549769eaf.3 for ; Sat, 19 Oct 2024 03:53:52 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1729335232; x=1729940032; darn=gnu.org; h=to:subject:message-id:date:from:mime-version:from:to:cc:subject :date:message-id:reply-to; bh=HmTtwiFRD71Qxj1jaNii94EjSXxpiUi4JZStvHMSm7s=; b=KGpRr7+UPPb+yx/evBghDEVi6lsioWVWLs2je83CJxAPatwvxzFFe3eKtJr7Ll3MWi cE8mkBQKpxn5DJpVOpkYHuNQ4tHoCE2rQZO9+wZiUHZLbZJUk05R/pwTW6QOpKRlBpWs m47gvgm1Pv7M0BY+NCou2M1+HbX/Ht/GTz2X2ctfzXp/8YoeYn4dTuNUyun8IlkCY0Ed ZTcMWMYV+v4fwr3hxLT+5mV9GjvoF8KbtXHY6ecsFADB1HSJkayNPb8k8WbryVQM62BV +C5Mw57tyOLkpIbL0RTid/OPpsfcRq50bISQWHeq0Ze6GLWSDcFrErEmv5rwYnB9ni1v UHvQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729335232; x=1729940032; h=to:subject:message-id:date:from:mime-version:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=HmTtwiFRD71Qxj1jaNii94EjSXxpiUi4JZStvHMSm7s=; b=Fj9sbHQiT9PziWmo+PVtd9h5I+ci4U8JrkSRgp5nOIMJtJYcyEvn4z7voa7f4IUX3T /KDWh4/DKGIlXVB6kYY9euBlOlUthoIJ6geCulq1Gsv6+7YFrKgBiS6K+i28ra0k1eBE a2CD07jvQwcMvhJw4HGamPu1kWrZPxifW+3minNlYLmQQ/T18MhknBXEOb6AENEqXfGK PEdRab+iGJZsWBVwyWdzBqdxaLWpkscm7myPhiNoqQFehG+buSOaNQ8hKtK6zPVCJKif lG1A9jd5OIyDYwN8XKNLry0KLqzHc8gZ5PfKIkaox9iSmXGQvfwpD5MfNWQhjG8ioNp1 kdRA== X-Gm-Message-State: AOJu0YxBjGQXRfpCcQZcfAoaokY80vMrsOfafHEJytxQpIXnXWInSe/t 4TPV9W7A/JyhwcSUtLF/B0dL7+ntG8JSvyOIUT8NOGRicCs2d3g54xeV7NCX1rt6WLCKbe/Fvsj EpbxHPJCZ8IGm5OQmu6pJ6/nTX3ohzyTcZc4= X-Google-Smtp-Source: AGHT+IFrXLMmjWpJ34fBbl+zQ5IMnvjsveoztdJpHRE8RoDWOklQ++qiDukxkirsguXANKmpYHRQ1w1ICKxnli/A5Ys= X-Received: by 2002:a05:6870:b487:b0:260:fbc0:96f2 with SMTP id 586e51a60fabf-2892c53d04dmr4860531fac.34.1729335231594; Sat, 19 Oct 2024 03:53:51 -0700 (PDT) MIME-Version: 1.0 From: Ethan Kong Date: Sat, 19 Oct 2024 18:53:40 +0800 Message-ID: Subject: [PATCH] Fix internal_equal so that it uses at most one hash table To: bug-gnu-emacs@gnu.org Content-Type: multipart/mixed; boundary="0000000000002d59900624d23c14" Received-SPF: pass client-ip=2607:f8b0:4864:20::c2c; envelope-from=ek.ethan.kong@gmail.com; helo=mail-oo1-xc2c.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-Spam-Score: -1.3 (-) X-Debbugs-Envelope-To: submit X-Mailman-Approved-At: Sat, 19 Oct 2024 10:25:42 -0400 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: -2.3 (--) --0000000000002d59900624d23c14 Content-Type: multipart/alternative; boundary="0000000000002d598e0624d23c12" --0000000000002d598e0624d23c12 Content-Type: text/plain; charset="UTF-8" Tags: patch Hi, When I use 'equal' on large, cyclic objects, emacs freezes. Reproduce: ;; emacs -Q (require 'org-element) ;; get two identical `org-element' trees of this file ;; https://github.com/emacs-mirror/emacs/blob/master/doc/misc/modus-themes.org (let ((file (expand-file-name "doc/misc/modus-themes.org" source-directory))) (with-current-buffer (find-file-noselect file) (setq org-o1 (org-element-parse-buffer)) (org-element-cache-reset) (setq org-o2 (org-element-parse-buffer)))) ;; the test (equal org-o1 org-o2) This equal call freezes emacs. And the memory usage of emacs grows quickly, until I quit. Reproduced with emacs 29.4 and the master branch. The cause: Current code on the master branch: static bool internal_equal (Lisp_Object o1, Lisp_Object o2, enum equal_kind equal_kind, int depth, Lisp_Object ht) { tail_recurse: if (depth > 10) { // ... if (NILP (ht)) ht = CALLN (Fmake_hash_table, QCtest, Qeq); // ... } // ... if (! internal_equal (XCAR (o1), XCAR (o2), equal_kind, depth + 1, ht)) return false; // ... } When internal_equal calls itself, it passes the hash table argument 'ht' by value. As a result, each internal_equal(depth=11) call initializes its own hash table, separately recording the objects it encounters in further recursive calls. This leads to excessive 'hash_put' and significant memory allocation. Fix: Make internal_equal pass the hash table by pointer (see the patch). With this patch, the test above returns quickly: (benchmark-run 100 (equal org-o1 org-o2)) (2.562444 20 0.30933900000000014) This will also improve the performance for smaller cyclic objects: ;; emacs -Q (defun make-cyclic (n m) (let* ((l1 (make-list n 1)) (l2 (make-list m 2))) (setf (nth (1- m) l2) l1) (setf (nth (1- n) l1) l2) l1)) (let ((a (make-cyclic 100 7)) (b (make-cyclic 100 7))) (cl-assert (equal a b)) (benchmark-run 10000 (equal a b))) Current: (0.530081 32 0.49294199999999977) With the patch: (0.036401 1 0.0173350000000001) And it passes all the tests in 'make fns-tests'. P.S. Could I get the copyright assignment paperwork please? Best, Ethan Kong In GNU Emacs 29.4 (build 2, x86_64-w64-mingw32) of 2024-07-05 built on AVALON Windowing system distributor 'Microsoft Corp.', version 10.0.22631 System Description: Microsoft Windows 10 Pro (v10.0.2009.22631.4317) Configured using: 'configure --with-modules --without-dbus --with-native-compilation=aot --without-compress-install --with-sqlite3 --with-tree-sitter CFLAGS=-O2' --0000000000002d598e0624d23c12 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Tags: patch

Hi,

When I use 'equal' o= n large, cyclic objects, emacs freezes.

Reproduce:

=C2=A0 =C2= =A0 ;; emacs -Q
=C2=A0 =C2=A0 (require 'org-element)

=C2=A0 = =C2=A0 ;; get two identical `org-element' trees of this file
=C2=A0 = =C2=A0 ;; https://github.com/emacs-mirror/emacs/blob/master/do= c/misc/modus-themes.org
=C2=A0 =C2=A0 (let ((file (expand-file-name = "doc/misc/modus-themes.org&quo= t;
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 source-directory)))
= =C2=A0 =C2=A0 =C2=A0 (with-current-buffer (find-file-noselect file)
=C2= =A0 =C2=A0 =C2=A0 =C2=A0 (setq org-o1 (org-element-parse-buffer))
=C2=A0= =C2=A0 =C2=A0 =C2=A0 (org-element-cache-reset)
=C2=A0 =C2=A0 =C2=A0 =C2= =A0 (setq org-o2 (org-element-parse-buffer))))

=C2=A0 =C2=A0 ;; the = test
=C2=A0 =C2=A0 (equal org-o1 org-o2)

This equal call freezes = emacs. And the memory usage of emacs grows
quickly, until I quit. Reprod= uced with emacs 29.4 and the master branch.


The cause:

Cu= rrent code on the master branch:

=C2=A0 =C2=A0 static bool
=C2=A0= =C2=A0 internal_equal (Lisp_Object o1, Lisp_Object o2, enum equal_kind equ= al_kind,
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 int depth, Lisp_Object ht)
=C2=A0 =C2=A0 {
=C2=A0 =C2=A0 =C2= =A0tail_recurse:
=C2=A0 =C2=A0 =C2=A0 if (depth > 10)
=C2=A0 =C2= =A0 =C2=A0 =C2=A0 {
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 // ...
=C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 if (NILP (ht))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 ht =3D CALLN (Fmake_hash_table, QCtest, Qeq);
=C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 // ...
=C2=A0 =C2=A0 =C2=A0 =C2=A0 }
=C2=A0 = =C2=A0 =C2=A0 // ...
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 if (! int= ernal_equal (XCAR (o1), XCAR (o2),
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 equal_kind, depth + 1, ht))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 return false;
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 // ...
=C2=A0 =C2=A0 }

When internal_equal calls itself, it p= asses the hash table argument 'ht'
by value. As a result, each i= nternal_equal(depth=3D11) call initializes
its own hash table, separatel= y recording the objects it encounters in
further recursive calls. This l= eads to excessive 'hash_put' and
significant memory allocation.<= br>

Fix:

Make internal_equal pass the hash table by pointer (= see the patch).

With this patch, the test above returns quickly:
=
=C2=A0 =C2=A0 (benchmark-run 100 (equal org-o1 org-o2))

(2.56244= 4 20 0.30933900000000014)

This will also improve the performance for= smaller cyclic objects:

=C2=A0 =C2=A0 ;; emacs -Q
=C2=A0 =C2=A0 = (defun make-cyclic (n m)
=C2=A0 =C2=A0 =C2=A0 (let* ((l1 (make-list n 1)= )
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(l2 (make-list m 2)))<= br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 (setf (nth (1- m) l2) l1)
=C2=A0 =C2=A0 = =C2=A0 =C2=A0 (setf (nth (1- n) l1) l2)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 l1))=

=C2=A0 =C2=A0 (let ((a (make-cyclic 100 7))
=C2=A0 =C2=A0 =C2=A0= =C2=A0 =C2=A0 (b (make-cyclic 100 7)))
=C2=A0 =C2=A0 =C2=A0 (cl-assert = (equal a b))
=C2=A0 =C2=A0 =C2=A0 (benchmark-run 10000 (equal a b)))
=
Current:
(0.530081 32 0.49294199999999977)

With the patch:(0.036401 1 0.0173350000000001)

And it passes all the tests in '= ;make fns-tests'.


P.S. Could I get the copyright assignment = paperwork please?

Best,
Ethan Kong


In GNU Emacs 29.4 (= build 2, x86_64-w64-mingw32) of 2024-07-05 built on
=C2=A0AVALON
Wind= owing system distributor 'Microsoft Corp.', version 10.0.22631
S= ystem Description: Microsoft Windows 10 Pro (v10.0.2009.22631.4317)

= Configured using:
=C2=A0'configure --with-modules --without-dbus --w= ith-native-compilation=3Daot
=C2=A0--without-compress-install --with-sql= ite3 --with-tree-sitter
=C2=A0CFLAGS=3D-O2'
--0000000000002d598e0624d23c12-- --0000000000002d59900624d23c14 Content-Type: application/octet-stream; name="0001-Fix-internal_equal-so-that-it-uses-at-most-one-hash-.patch" Content-Disposition: attachment; filename="0001-Fix-internal_equal-so-that-it-uses-at-most-one-hash-.patch" Content-Transfer-Encoding: base64 Content-ID: X-Attachment-Id: f_m2g17yg00 RnJvbSA0MjUyNzAxNzliYjIyNjMwYjdhZDU4NzFmY2ZjZWU4NDczN2I1NWZiIE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBFdGhhbiBLb25nIDxlay5ldGhhbi5rb25nQGdtYWlsLmNvbT4K RGF0ZTogU2F0LCAxOSBPY3QgMjAyNCAxMjo0MzoyNyArMDgwMApTdWJqZWN0OiBbUEFUQ0hdIEZp eCBpbnRlcm5hbF9lcXVhbCBzbyB0aGF0IGl0IHVzZXMgYXQgbW9zdCBvbmUgaGFzaCB0YWJsZQoK KiBzcmMvZm5zLmMgKGludGVybmFsX2VxdWFsKTogRGVsZWdhdGUgdG8gaW50ZXJuYWxfZXF1YWxf MS4KKGludGVybmFsX2VxdWFsXzEpOiBOZXcgZnVuY3Rpb24uIFBhc3MgdGhlIGhhc2ggdGFibGUg YXJndW1lbnQgYnkKcG9pbnRlciBpbnN0ZWFkIG9mIGJ5IHZhbHVlLgotLS0KIHNyYy9mbnMuYyB8 IDIzICsrKysrKysrKysrKysrKy0tLS0tLS0tCiAxIGZpbGUgY2hhbmdlZCwgMTUgaW5zZXJ0aW9u cygrKSwgOCBkZWxldGlvbnMoLSkKCmRpZmYgLS1naXQgYS9zcmMvZm5zLmMgYi9zcmMvZm5zLmMK aW5kZXggMmRlMDRkMDY1MTkuLmVmNjkyMmMxMzdiIDEwMDY0NAotLS0gYS9zcmMvZm5zLmMKKysr IGIvc3JjL2Zucy5jCkBAIC0yODIzLDggKzI4MjMsOCBAQCBlcXVhbF9ub19xdWl0IChMaXNwX09i amVjdCBvMSwgTGlzcF9PYmplY3QgbzIpCiAgICBpZiBFUVVBTF9LSU5EID09IEVRVUFMX05PX1FV SVQuICAqLwogCiBzdGF0aWMgYm9vbAotaW50ZXJuYWxfZXF1YWwgKExpc3BfT2JqZWN0IG8xLCBM aXNwX09iamVjdCBvMiwgZW51bSBlcXVhbF9raW5kIGVxdWFsX2tpbmQsCi0JCWludCBkZXB0aCwg TGlzcF9PYmplY3QgaHQpCitpbnRlcm5hbF9lcXVhbF8xIChMaXNwX09iamVjdCBvMSwgTGlzcF9P YmplY3QgbzIsIGVudW0gZXF1YWxfa2luZCBlcXVhbF9raW5kLAorCQkgIGludCBkZXB0aCwgTGlz cF9PYmplY3QgKmh0KQogewogIHRhaWxfcmVjdXJzZToKICAgaWYgKGRlcHRoID4gMTApCkBAIC0y ODMyLDEzICsyODMyLDEzIEBAIGludGVybmFsX2VxdWFsIChMaXNwX09iamVjdCBvMSwgTGlzcF9P YmplY3QgbzIsIGVudW0gZXF1YWxfa2luZCBlcXVhbF9raW5kLAogICAgICAgZWFzc2VydCAoZXF1 YWxfa2luZCAhPSBFUVVBTF9OT19RVUlUKTsKICAgICAgIGlmIChkZXB0aCA+IDIwMCkKIAllcnJv ciAoIlN0YWNrIG92ZXJmbG93IGluIGVxdWFsIik7Ci0gICAgICBpZiAoTklMUCAoaHQpKQotCWh0 ID0gQ0FMTE4gKEZtYWtlX2hhc2hfdGFibGUsIFFDdGVzdCwgUWVxKTsKKyAgICAgIGlmIChOSUxQ ICgqaHQpKQorCSpodCA9IENBTExOIChGbWFrZV9oYXNoX3RhYmxlLCBRQ3Rlc3QsIFFlcSk7CiAg ICAgICBzd2l0Y2ggKFhUWVBFIChvMSkpCiAJewogCWNhc2UgTGlzcF9Db25zOiBjYXNlIExpc3Bf VmVjdG9ybGlrZToKIAkgIHsKLQkgICAgc3RydWN0IExpc3BfSGFzaF9UYWJsZSAqaCA9IFhIQVNI X1RBQkxFIChodCk7CisJICAgIHN0cnVjdCBMaXNwX0hhc2hfVGFibGUgKmggPSBYSEFTSF9UQUJM RSAoKmh0KTsKIAkgICAgaGFzaF9oYXNoX3QgaGFzaCA9IGhhc2hfZnJvbV9rZXkgKGgsIG8xKTsK IAkgICAgcHRyZGlmZl90IGkgPSBoYXNoX2xvb2t1cF93aXRoX2hhc2ggKGgsIG8xLCBoYXNoKTsK IAkgICAgaWYgKGkgPj0gMCkKQEAgLTI4ODgsOCArMjg4OCw4IEBAIGludGVybmFsX2VxdWFsIChM aXNwX09iamVjdCBvMSwgTGlzcF9PYmplY3QgbzIsIGVudW0gZXF1YWxfa2luZCBlcXVhbF9raW5k LAogCSAgewogCSAgICBpZiAoISBDT05TUCAobzIpKQogCSAgICAgIHJldHVybiBmYWxzZTsKLQkg ICAgaWYgKCEgaW50ZXJuYWxfZXF1YWwgKFhDQVIgKG8xKSwgWENBUiAobzIpLAotCQkJCSAgZXF1 YWxfa2luZCwgZGVwdGggKyAxLCBodCkpCisJICAgIGlmICghIGludGVybmFsX2VxdWFsXzEgKFhD QVIgKG8xKSwgWENBUiAobzIpLAorCQkJCSAgICBlcXVhbF9raW5kLCBkZXB0aCArIDEsIGh0KSkK IAkgICAgICByZXR1cm4gZmFsc2U7CiAJICAgIG8yID0gWENEUiAobzIpOwogCSAgICBpZiAoRVEg KFhDRFIgKG8xKSwgbzIpKQpAQCAtMjk2NCw3ICsyOTY0LDcgQEAgaW50ZXJuYWxfZXF1YWwgKExp c3BfT2JqZWN0IG8xLCBMaXNwX09iamVjdCBvMiwgZW51bSBlcXVhbF9raW5kIGVxdWFsX2tpbmQs CiAJICAgIExpc3BfT2JqZWN0IHYxLCB2MjsKIAkgICAgdjEgPSBBUkVGIChvMSwgaSk7CiAJICAg IHYyID0gQVJFRiAobzIsIGkpOwotCSAgICBpZiAoIWludGVybmFsX2VxdWFsICh2MSwgdjIsIGVx dWFsX2tpbmQsIGRlcHRoICsgMSwgaHQpKQorCSAgICBpZiAoIWludGVybmFsX2VxdWFsXzEgKHYx LCB2MiwgZXF1YWxfa2luZCwgZGVwdGggKyAxLCBodCkpCiAJICAgICAgcmV0dXJuIGZhbHNlOwog CSAgfQogCXJldHVybiB0cnVlOwpAQCAtMjk4NSw2ICsyOTg1LDEzIEBAIGludGVybmFsX2VxdWFs IChMaXNwX09iamVjdCBvMSwgTGlzcF9PYmplY3QgbzIsIGVudW0gZXF1YWxfa2luZCBlcXVhbF9r aW5kLAogICByZXR1cm4gZmFsc2U7CiB9CiAKK3N0YXRpYyBib29sCitpbnRlcm5hbF9lcXVhbCAo TGlzcF9PYmplY3QgbzEsIExpc3BfT2JqZWN0IG8yLCBlbnVtIGVxdWFsX2tpbmQgZXF1YWxfa2lu ZCwKKwkJaW50IGRlcHRoLCBMaXNwX09iamVjdCBodCkKK3sKKyAgcmV0dXJuIGludGVybmFsX2Vx dWFsXzEgKG8xLCBvMiwgZXF1YWxfa2luZCwgZGVwdGgsICZodCk7Cit9CisKIC8qIFJldHVybiAt MS8wLzEgZm9yIHRoZSA8Lz0vPiBsZXhpY29ncmFwaGljIHJlbGF0aW9uIGJldHdlZW4gYm9vbC12 ZWN0b3JzLiAgKi8KIHN0YXRpYyBpbnQKIGJvb2xfdmVjdG9yX2NtcCAoTGlzcF9PYmplY3QgYSwg TGlzcF9PYmplY3QgYikKLS0gCjIuNDMuMC53aW5kb3dzLjEKCg== --0000000000002d59900624d23c14-- ------------=_1731142982-3518-1-- From unknown Thu Aug 14 21:46:20 2025 MIME-Version: 1.0 X-Mailer: MIME-tools 5.505 (Entity 5.505) X-Loop: help-debbugs@gnu.org From: help-debbugs@gnu.org (GNU bug Tracking System) To: Ethan Kong Subject: bug#73885: closed (Re: bug#73883: [PATCH] Fix 'equal' freezing on large cyclic objects) Message-ID: References: <868qtsok59.fsf@gnu.org> <86cyjwnsmu.fsf@gmail.com> X-Gnu-PR-Message: they-closed 73885 X-Gnu-PR-Package: emacs X-Gnu-PR-Keywords: patch Reply-To: 73885@debbugs.gnu.org Date: Sat, 09 Nov 2024 09:03:03 +0000 Content-Type: multipart/mixed; boundary="----------=_1731142983-3518-3" This is a multi-part message in MIME format... ------------=_1731142983-3518-3 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Your bug report #73883: [PATCH] Fix internal_equal so that it uses at most one hash table which was filed against the emacs package, has been closed. The explanation is attached below, along with your original report. If you require more details, please reply to 73885@debbugs.gnu.org. --=20 73883: https://debbugs.gnu.org/cgi/bugreport.cgi?bug=3D73883 GNU Bug Tracking System Contact help-debbugs@gnu.org with problems ------------=_1731142983-3518-3 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit Received: (at 73883-done) by debbugs.gnu.org; 9 Nov 2024 09:02:12 +0000 Received: from localhost ([127.0.0.1]:53361 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1t9hMC-0000td-8w for submit@debbugs.gnu.org; Sat, 09 Nov 2024 04:02:12 -0500 Received: from eggs.gnu.org ([209.51.188.92]:33162) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1t9hM9-0000tR-UL for 73883-done@debbugs.gnu.org; Sat, 09 Nov 2024 04:02:10 -0500 Received: from fencepost.gnu.org ([2001:470:142:3::e]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1t9hM0-0000Oa-7X; Sat, 09 Nov 2024 04:02:01 -0500 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org; s=fencepost-gnu-org; h=MIME-version:References:Subject:In-Reply-To:To:From: Date; bh=2iBVhCyMm0qBVAbClcqFONW4hGtAKs/ZnHxUvmKrx+w=; b=USgKhVBPwjUfeyTOjL/o E4gTZXGZlda3IHecqfQh7gZDTXQEB9sgXmuUhpelfqOHPZSBkznQXf9g4oqRJ+AkAUjTsaK4OmgdE zv3b35HML8z9/HPhcf2Pg6uMkfHNGwIgdvkb9PP57ZARcFSZUlYnFf+vkrrHKKuik6GeKLnRKl9RL /jPsHs+lb5psx/zep5Wt49/RdjckXQNi1bfq9UPFBLip0ORhXCmkqC/1Tirq0ac4u/NzqMFyCmSa5 74bA9LC3SNdpjvq6DeEtkNjYj83QhUHHw+4c74HarryysFcgiKpFJ0yvphl5A49Ih3+33i0Ve3mhj XIB+Kcbo9vdVjA==; Date: Sat, 09 Nov 2024 11:01:54 +0200 Message-Id: <868qtsok59.fsf@gnu.org> From: Eli Zaretskii To: Ethan Kong In-Reply-To: <84de8b8c-eecf-4c56-8c82-5b0236130efb@gmail.com> (message from Ethan Kong on Sat, 9 Nov 2024 11:36:56 +0800) Subject: Re: bug#73883: [PATCH] Fix 'equal' freezing on large cyclic objects References: <861pztzwuh.fsf@gnu.org> <84de8b8c-eecf-4c56-8c82-5b0236130efb@gmail.com> MIME-version: 1.0 Content-type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 73883-done Cc: monnier@iro.umontreal.ca, 73883-done@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: -3.3 (---) > Cc: 73883@debbugs.gnu.org > Date: Sat, 9 Nov 2024 11:36:56 +0800 > From: Ethan Kong > > On 24/11/09 02:57, Stefan Monnier wrote: > > While the new title is arguably better for a bug report, the old one was > > better at describing your patch. 🙂 > > I see. Here is the patch with the old summary line. Thanks, installed on the master branch, and closing the bug. ------------=_1731142983-3518-3 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit Received: (at submit) by debbugs.gnu.org; 19 Oct 2024 14:25:55 +0000 Received: from localhost ([127.0.0.1]:44227 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1t2AOw-00032J-Pg for submit@debbugs.gnu.org; Sat, 19 Oct 2024 10:25:55 -0400 Received: from lists.gnu.org ([209.51.188.17]:40474) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1t29Gf-0007UF-3h for submit@debbugs.gnu.org; Sat, 19 Oct 2024 09:13:17 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1t29GG-00037q-WD for bug-gnu-emacs@gnu.org; Sat, 19 Oct 2024 09:12:53 -0400 Received: from mail-pl1-x635.google.com ([2607:f8b0:4864:20::635]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1t29GF-0004xj-2U for bug-gnu-emacs@gnu.org; Sat, 19 Oct 2024 09:12:52 -0400 Received: by mail-pl1-x635.google.com with SMTP id d9443c01a7336-20c803787abso23748265ad.0 for ; Sat, 19 Oct 2024 06:12:50 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1729343569; x=1729948369; darn=gnu.org; h=mime-version:message-id:date:subject:to:from:from:to:cc:subject :date:message-id:reply-to; bh=5HXFYeXpE1DCOcWaIFclriKjSKoSWevTGrp2ZG0fyNY=; b=V/jwmPfzQCn//7IVc0929g9Rmf0ePzzJc8SwnuB6ZG8L8G5IM/wvd43VXZv5sQ5avf Ys27drW5JrN65Y7yutbM3RbULMXPhgk8hX44PRujT53JooEBkJzZAAym6kNLWZJNx3aT RLIHivG6cvK1RTVvgEOfXrmi2SW1wnUX4k2m+hIYQv3ZtkA9g4Ywexv4Qr4kY2UDPiQn 85wzDoTN4cUIxVCZC57MYSbCQ1lg+RKNWKK3eZdAJTFjgUUO1enIRdnWwM88l8y/mux1 AlQOtR04J5ts2JLCDINq3Ev9y8i9nStRqwsY7FdmMSS9tDLBPeVu1xzm+hwyhHSD7PfF w3tg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729343569; x=1729948369; h=mime-version:message-id:date:subject:to:from:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=5HXFYeXpE1DCOcWaIFclriKjSKoSWevTGrp2ZG0fyNY=; b=FxfgY2SJXAbHeOj+SmhdRgK3iq8NCpYMA0tTaPzpfIo/512+bIt2ax902zKYxE0jlu mqrnIps+d2QobL4GFeZtX/PPfwhihpqhMVL/AY2oi3d1FJRH9ej0RENTQi8+QwP3zTOC DaBa/JSa0IAv8dXlyL46bni9omLI8ntgz89U7tQEMovRuBz8ZOdYIr95KxfxhFEJEUcb AMrG6Wg3UuaudUseHISI66TOe3OMQpY70MI67qT9WvabMcvOBPjqiKUpR89V4hfzIWhv 8N4K9vjaFerGaUcmPPTDJfd1O5GeMOEPoRJZp45qSAkwREJsVYWqCR5Nd3ass4Pa0C4o 2Kdw== X-Gm-Message-State: AOJu0YywB+k7yfgX2MubRxVaco01jbCsMgklO6YEy2GkypVcpW23mWCp XvyfTDHc3fG2/1heurQGtuY+i12a5MtFva0TjosIz13VvtdW0lDJoQE7vyWH X-Google-Smtp-Source: AGHT+IF1e13MGmr5FUcydeL2PKca0t33yIFi0YtRZn7gKS6NgFohRFmwcC7/J6ZoKVYNwfy5blkI0w== X-Received: by 2002:a17:902:e543:b0:20c:f6c5:7f6c with SMTP id d9443c01a7336-20d479132famr150680715ad.16.1729343568706; Sat, 19 Oct 2024 06:12:48 -0700 (PDT) Received: from FATBOY ([113.83.62.123]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-20e5a90dbcfsm27559265ad.250.2024.10.19.06.12.47 for (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Sat, 19 Oct 2024 06:12:48 -0700 (PDT) From: Ethan Kong To: bug-gnu-emacs@gnu.org Subject: [PATCH] Fix internal_equal so that it uses at most one hash table Date: Sat, 19 Oct 2024 21:12:41 +0800 Message-ID: <86cyjwnsmu.fsf@gmail.com> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" Received-SPF: pass client-ip=2607:f8b0:4864:20::635; envelope-from=ek.ethan.kong@gmail.com; helo=mail-pl1-x635.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-Spam-Score: -1.3 (-) X-Debbugs-Envelope-To: submit X-Mailman-Approved-At: Sat, 19 Oct 2024 10:25:42 -0400 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: -2.3 (--) --=-=-= Content-Type: text/plain Tags: patch Hi, When I use 'equal' on large, cyclic objects, emacs freezes. Reproduce: ;; emacs -Q (require 'org-element) ;; get two identical `org-element' trees of this file ;; https://github.com/emacs-mirror/emacs/blob/master/doc/misc/modus-themes.org (let ((file (expand-file-name "doc/misc/modus-themes.org" source-directory))) (with-current-buffer (find-file-noselect file) (setq org-o1 (org-element-parse-buffer)) (org-element-cache-reset) (setq org-o2 (org-element-parse-buffer)))) ;; the test (equal org-o1 org-o2) This equal call freezes emacs. And the memory usage of emacs grows quickly, until I quit. Reproduced with emacs 29.4 and the master branch. The cause: Current code on the master branch: static bool internal_equal (Lisp_Object o1, Lisp_Object o2, enum equal_kind equal_kind, int depth, Lisp_Object ht) { tail_recurse: if (depth > 10) { // ... if (NILP (ht)) ht = CALLN (Fmake_hash_table, QCtest, Qeq); // ... } // ... if (! internal_equal (XCAR (o1), XCAR (o2), equal_kind, depth + 1, ht)) return false; // ... } When internal_equal calls itself, it passes the hash table argument 'ht' by value. As a result, each internal_equal(depth=11) call initializes its own hash table, separately recording the objects it encounters in further recursive calls. This leads to excessive 'hash_put' and significant memory allocation. Fix: Make internal_equal pass the hash table by pointer (see the patch). With this patch, the test above returns quickly: (benchmark-run 100 (equal org-o1 org-o2)) (2.562444 20 0.30933900000000014) This will also improve the performance for smaller cyclic objects: ;; emacs -Q (defun make-cyclic (n m) (let* ((l1 (make-list n 1)) (l2 (make-list m 2))) (setf (nth (1- m) l2) l1) (setf (nth (1- n) l1) l2) l1)) (let ((a (make-cyclic 100 7)) (b (make-cyclic 100 7))) (cl-assert (equal a b)) (benchmark-run 10000 (equal a b))) Current: (0.530081 32 0.49294199999999977) With the patch: (0.036401 1 0.0173350000000001) And it passes all the tests in 'make fns-tests'. P.S. Could I get the copyright assignment paperwork please? Best, Ethan Kong In GNU Emacs 29.4 (build 2, x86_64-w64-mingw32) of 2024-07-05 built on AVALON Windowing system distributor 'Microsoft Corp.', version 10.0.22631 System Description: Microsoft Windows 10 Pro (v10.0.2009.22631.4317) Configured using: 'configure --with-modules --without-dbus --with-native-compilation=aot --without-compress-install --with-sqlite3 --with-tree-sitter CFLAGS=-O2' --=-=-= Content-Type: text/patch Content-Disposition: attachment; filename=0001-Fix-internal_equal-so-that-it-uses-at-most-one-hash-.patch >From 425270179bb22630b7ad5871fcfcee84737b55fb Mon Sep 17 00:00:00 2001 From: Ethan Kong Date: Sat, 19 Oct 2024 12:43:27 +0800 Subject: [PATCH] Fix internal_equal so that it uses at most one hash table * src/fns.c (internal_equal): Delegate to internal_equal_1. (internal_equal_1): New function. Pass the hash table argument by pointer instead of by value. --- src/fns.c | 23 +++++++++++++++-------- 1 file changed, 15 insertions(+), 8 deletions(-) diff --git a/src/fns.c b/src/fns.c index 2de04d06519..ef6922c137b 100644 --- a/src/fns.c +++ b/src/fns.c @@ -2823,8 +2823,8 @@ equal_no_quit (Lisp_Object o1, Lisp_Object o2) if EQUAL_KIND == EQUAL_NO_QUIT. */ static bool -internal_equal (Lisp_Object o1, Lisp_Object o2, enum equal_kind equal_kind, - int depth, Lisp_Object ht) +internal_equal_1 (Lisp_Object o1, Lisp_Object o2, enum equal_kind equal_kind, + int depth, Lisp_Object *ht) { tail_recurse: if (depth > 10) @@ -2832,13 +2832,13 @@ internal_equal (Lisp_Object o1, Lisp_Object o2, enum equal_kind equal_kind, eassert (equal_kind != EQUAL_NO_QUIT); if (depth > 200) error ("Stack overflow in equal"); - if (NILP (ht)) - ht = CALLN (Fmake_hash_table, QCtest, Qeq); + if (NILP (*ht)) + *ht = CALLN (Fmake_hash_table, QCtest, Qeq); switch (XTYPE (o1)) { case Lisp_Cons: case Lisp_Vectorlike: { - struct Lisp_Hash_Table *h = XHASH_TABLE (ht); + struct Lisp_Hash_Table *h = XHASH_TABLE (*ht); hash_hash_t hash = hash_from_key (h, o1); ptrdiff_t i = hash_lookup_with_hash (h, o1, hash); if (i >= 0) @@ -2888,8 +2888,8 @@ internal_equal (Lisp_Object o1, Lisp_Object o2, enum equal_kind equal_kind, { if (! CONSP (o2)) return false; - if (! internal_equal (XCAR (o1), XCAR (o2), - equal_kind, depth + 1, ht)) + if (! internal_equal_1 (XCAR (o1), XCAR (o2), + equal_kind, depth + 1, ht)) return false; o2 = XCDR (o2); if (EQ (XCDR (o1), o2)) @@ -2964,7 +2964,7 @@ internal_equal (Lisp_Object o1, Lisp_Object o2, enum equal_kind equal_kind, Lisp_Object v1, v2; v1 = AREF (o1, i); v2 = AREF (o2, i); - if (!internal_equal (v1, v2, equal_kind, depth + 1, ht)) + if (!internal_equal_1 (v1, v2, equal_kind, depth + 1, ht)) return false; } return true; @@ -2985,6 +2985,13 @@ internal_equal (Lisp_Object o1, Lisp_Object o2, enum equal_kind equal_kind, return false; } +static bool +internal_equal (Lisp_Object o1, Lisp_Object o2, enum equal_kind equal_kind, + int depth, Lisp_Object ht) +{ + return internal_equal_1 (o1, o2, equal_kind, depth, &ht); +} + /* Return -1/0/1 for the lexicographic relation between bool-vectors. */ static int bool_vector_cmp (Lisp_Object a, Lisp_Object b) -- 2.43.0.windows.1 --=-=-=-- ------------=_1731142983-3518-3--