From unknown Fri Jun 20 17:51:36 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#73883 <73883@debbugs.gnu.org> To: bug#73883 <73883@debbugs.gnu.org> Subject: Status: [PATCH] Fix internal_equal so that it uses at most one hash table Reply-To: bug#73883 <73883@debbugs.gnu.org> Date: Sat, 21 Jun 2025 00:51:36 +0000 retitle 73883 [PATCH] Fix internal_equal so that it uses at most one hash t= able reassign 73883 emacs submitter 73883 Ethan Kong severity 73883 normal tag 73883 patch thanks From debbugs-submit-bounces@debbugs.gnu.org Sat Oct 19 10:25:53 2024 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-- 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 debbugs-submit-bounces@debbugs.gnu.org Sun Oct 20 07:57:29 2024 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: Subject: Re: bug#73883: [PATCH] Fix internal_equal so that it uses at most one hash table To: Ethan Kong , 73883@debbugs.gnu.org Content-Type: text/plain; charset="UTF-8" X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 73883 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 debbugs-submit-bounces@debbugs.gnu.org Sun Oct 20 08:04:46 2024 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 Subject: Re: bug#73883: [PATCH] Fix 'equal' freezing on large cyclic objects From: Ethan Kong To: 73883@debbugs.gnu.org References: Content-Language: en-US In-Reply-To: X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 73883 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 debbugs-submit-bounces@debbugs.gnu.org Sat Nov 02 07:41:54 2024 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 To: Ethan Kong , Stefan Monnier , Mattias =?utf-8?Q?Engdeg=C3=A5rd?= In-Reply-To: (message from Ethan Kong on Sun, 20 Oct 2024 19:47:41 +0800) Subject: Re: bug#73883: [PATCH] Fix 'equal' freezing on large cyclic objects References: 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 Cc: 73883@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 (---) > 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 debbugs-submit-bounces@debbugs.gnu.org Fri Nov 08 08:55:45 2024 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 Subject: Re: bug#73883: [PATCH] Fix 'equal' freezing on large cyclic objects To: Eli Zaretskii , Stefan Monnier , =?UTF-8?Q?Mattias_Engdeg=C3=A5rd?= , Stefan Kangas 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-Debbugs-Envelope-To: 73883 X-Mailman-Approved-At: Fri, 08 Nov 2024 08:55:40 -0500 Cc: 73883@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.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 debbugs-submit-bounces@debbugs.gnu.org Fri Nov 08 13:58:09 2024 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 To: Eli Zaretskii Subject: Re: bug#73883: [PATCH] Fix 'equal' freezing on large cyclic objects 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-Debbugs-Envelope-To: 73883 Cc: Mattias =?windows-1252?Q?Engdeg?= =?windows-1252?Q?=E5rd?= , Ethan Kong , 73883@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 (---) >> 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 debbugs-submit-bounces@debbugs.gnu.org Sat Nov 09 03:21:27 2024 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 Subject: Re: bug#73883: [PATCH] Fix 'equal' freezing on large cyclic objects To: Stefan Monnier References: <861pztzwuh.fsf@gnu.org> Content-Language: en-US From: Ethan Kong In-Reply-To: X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 73883 X-Mailman-Approved-At: Sat, 09 Nov 2024 03:21:20 -0500 Cc: 73883@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.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 debbugs-submit-bounces@debbugs.gnu.org Sat Nov 09 04:02:12 2024 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. From unknown Fri Jun 20 17:51:36 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, 07 Dec 2024 12:24:13 +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