From unknown Sat Jun 21 03:11:05 2025 X-Loop: help-debbugs@gnu.org Subject: bug#73885: [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:04 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: report 73885 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: 73885@debbugs.gnu.org X-Debbugs-Original-To: bug-gnu-emacs@gnu.org Received: via spool by submit@debbugs.gnu.org id=B.172934795511684 (code B ref -1); Sat, 19 Oct 2024 14:26:04 +0000 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 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-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 --=-=-=-- From unknown Sat Jun 21 03:11:05 2025 X-Loop: help-debbugs@gnu.org Subject: bug#73885: [PATCH] Fix internal_equal so that it uses at most one hash table Resent-From: Eli Zaretskii Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sat, 19 Oct 2024 15:11:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 73885 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: patch To: Ethan Kong Cc: 73885@debbugs.gnu.org Received: via spool by 73885-submit@debbugs.gnu.org id=B73885.172935062519075 (code B ref 73885); Sat, 19 Oct 2024 15:11:02 +0000 Received: (at 73885) by debbugs.gnu.org; 19 Oct 2024 15:10:25 +0000 Received: from localhost ([127.0.0.1]:44413 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1t2B61-0004xa-6D 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 In-Reply-To: <86cyjwnsmu.fsf@gmail.com> (message from Ethan Kong on Sat, 19 Oct 2024 21:12:41 +0800) References: <86cyjwnsmu.fsf@gmail.com> 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 (---) 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.