From unknown Tue Jun 17 01:27:05 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#56199 <56199@debbugs.gnu.org> To: bug#56199 <56199@debbugs.gnu.org> Subject: Status: hash table equality predicate [PATCH] Reply-To: bug#56199 <56199@debbugs.gnu.org> Date: Tue, 17 Jun 2025 08:27:05 +0000 retitle 56199 hash table equality predicate [PATCH] reassign 56199 emacs submitter 56199 Mattias Engdeg=C3=A5rd severity 56199 normal tag 56199 patch thanks From debbugs-submit-bounces@debbugs.gnu.org Fri Jun 24 13:20:11 2022 Received: (at submit) by debbugs.gnu.org; 24 Jun 2022 17:20:11 +0000 Received: from localhost ([127.0.0.1]:43404 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1o4myZ-0004Lk-J6 for submit@debbugs.gnu.org; Fri, 24 Jun 2022 13:20:11 -0400 Received: from lists.gnu.org ([209.51.188.17]:57168) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1o4myX-0004LY-MI for submit@debbugs.gnu.org; Fri, 24 Jun 2022 13:20:10 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:37712) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1o4myT-0000zP-Sx for bug-gnu-emacs@gnu.org; Fri, 24 Jun 2022 13:20:07 -0400 Received: from mail75c50.megamailservers.eu ([91.136.10.85]:37050 helo=mail92c50.megamailservers.eu) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1o4myQ-00008w-VP for bug-gnu-emacs@gnu.org; Fri, 24 Jun 2022 13:20:05 -0400 X-Authenticated-User: mattiase@bredband.net DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=megamailservers.eu; s=maildub; t=1656091196; bh=GKCVD2srbJvCxWU1mMWODUL9pCTFCqMsl5UwYvSqH90=; h=From:Subject:Date:To:From; b=AkF3HSW1bwu2bxaXgHk+loit5wzg7d3axEv40F+/EYFmqY1Xn2ZEiGKNR0hGPpTz0 E8HrBGsWf2w4CrH8dzRcjvvqWZEizTxpvfrOmlJVhj9qxsKOFgxZlXCA6wZAklNNk+ 6eJVq4syHaoncYvnSY4fb1N1178xOij3RbXd8eC4= Feedback-ID: mattiase@acm.or Received: from smtpclient.apple (c188-150-171-71.bredband.tele2.se [188.150.171.71]) (authenticated bits=0) by mail92c50.megamailservers.eu (8.14.9/8.13.1) with ESMTP id 25OHJsHo078813 for ; Fri, 24 Jun 2022 17:19:56 +0000 From: =?utf-8?Q?Mattias_Engdeg=C3=A5rd?= Content-Type: multipart/mixed; boundary="Apple-Mail=_F9224A7E-2BFE-499E-9803-001F81A49C5D" Mime-Version: 1.0 (Mac OS X Mail 14.0 \(3654.120.0.1.13\)) Subject: hash table equality predicate [PATCH] Message-Id: <8928CA50-5999-47DD-A002-46B7E9005E62@acm.org> Date: Fri, 24 Jun 2022 19:19:54 +0200 To: bug-gnu-emacs@gnu.org X-Mailer: Apple Mail (2.3654.120.0.1.13) X-CTCH-RefID: str=0001.0A782F26.62B5F23C.002C, ss=1, re=0.000, recu=0.000, reip=0.000, cl=1, cld=1, fgs=0 X-CTCH-VOD: Unknown X-CTCH-Spam: Unknown X-CTCH-Score: 0.000 X-CTCH-Rules: X-CTCH-Flags: 0 X-CTCH-ScoreCust: 0.000 X-Origin-Country: SE Received-SPF: softfail client-ip=91.136.10.85; envelope-from=mattiase@acm.org; helo=mail92c50.megamailservers.eu X-Spam_score_int: -11 X-Spam_score: -1.2 X-Spam_bar: - X-Spam_report: (-1.2 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, SPF_HELO_NONE=0.001, SPF_SOFTFAIL=0.665, T_SCC_BODY_TEXT_LINE=-0.01 autolearn=no autolearn_force=no X-Spam_action: no action X-Spam-Score: -1.3 (-) X-Debbugs-Envelope-To: submit X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -2.3 (--) --Apple-Mail=_F9224A7E-2BFE-499E-9803-001F81A49C5D Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=us-ascii Recently[1] a predicate for structural equality was requested that also = recurses through hash tables. It showed that Emacs doesn't even come with a way of comparing hash = tables. Third-party implementations exist but if the code quoted in [2] = is representative, perhaps it would make sense to add a = `hash-table-equal-p` predicate? Even implemented entirely in Lisp it would be an order of magnitude = faster (and actually correct). The attached code is not without flaws but provides a rough starting = point. (This is not meant as a strong argument for or against adding it in the = first place.) --Apple-Mail=_F9224A7E-2BFE-499E-9803-001F81A49C5D Content-Disposition: attachment; filename=hash-table-equal-p.diff Content-Type: application/octet-stream; x-unix-mode=0644; name="hash-table-equal-p.diff" Content-Transfer-Encoding: 7bit diff --git a/lisp/emacs-lisp/subr-x.el b/lisp/emacs-lisp/subr-x.el index 9cd793d05c..17ca80a297 100644 --- a/lisp/emacs-lisp/subr-x.el +++ b/lisp/emacs-lisp/subr-x.el @@ -93,6 +93,28 @@ hash-table-values "Return a list of values in HASH-TABLE." (cl-loop for v being the hash-values of hash-table collect v)) +(defun hash-table-equal-p (h1 h2 &optional value-eq) + "Whether the hash tables H1 and H2 are equal with respect to VALUE-EQ. +Equality means that the tables have the same equality predicate +and the same set of key-value pairs where keys are compared by +that predicate and values by VALUE-EQ, which defaults to `eq'." + (or (eq h1 h2) + (and (= (hash-table-count h1) (hash-table-count h2)) + (eq (hash-table-test h1) (hash-table-test h2)) + (progn + (unless value-eq + (setq value-eq #'eq)) + ;; Loop over the physically smaller table. + (when (> (hash-table-size h1) (hash-table-size h2)) + (cl-rotatef h1 h2)) + (catch 'done + (maphash + (lambda (k v) + (unless (funcall value-eq v (gethash k h2 (not v))) + (throw 'done nil))) + h1) + t))))) + (defsubst string-empty-p (string) "Check whether STRING is empty." (string= string "")) diff --git a/test/lisp/emacs-lisp/subr-x-tests.el b/test/lisp/emacs-lisp/subr-x-tests.el index 7f3916c2c0..923155eedb 100644 --- a/test/lisp/emacs-lisp/subr-x-tests.el +++ b/test/lisp/emacs-lisp/subr-x-tests.el @@ -743,6 +743,55 @@ test-with-buffer-unmodified-if-unchanged (with-current-buffer inner (should-not (buffer-modified-p)))))))) +(ert-deftest subr-x--hash-table-equal-p () + (cl-flet ((hashtab (test &rest elts) + (let ((h (make-hash-table :test test))) + (while elts + (let* ((key (pop elts)) + (val (pop elts))) + (puthash key val h))) + h))) + + (let ((h1 (hashtab #'eq 'a (list 1) 'b (list 2)) + (h2 (hashtab #'eq 'a (list 1) 'b (list 2))))) + (should (hash-table-equal-p h1 h2 #'equal)) + (should (hash-table-equal-p h2 h1 #'equal)) + (should (not (hash-table-equal-p h1 h2 #'eq))) + (should (not (hash-table-equal-p h2 h1 #'eq))) + (should (hash-table-equal-p h1 h1 #'eq))) + + (let ((h1 (hashtab #'eql 1 'a 2 'b) + (h2 (hashtab #'equal 1 'a 2 'b)))) + (should (not (hash-table-equal-p h1 h2))) + (should (not (hash-table-equal-p h2 h1)))) + + (let ((h1 (hashtab #'eql 1 'a 2 'a) + (h2 (hashtab #'eql 1 'a)))) + (should (not (hash-table-equal-p h1 h2))) + (should (not (hash-table-equal-p h2 h1)))) + + (let ((h1 (hashtab #'eql 1 'a 2 'a) + (h2 (hashtab #'eql 1 'a 2 'b)))) + (should (not (hash-table-equal-p h1 h2))) + (should (not (hash-table-equal-p h2 h1)))) + + (let ((h1 (hashtab #'eql 1 'a 2 'a) + (h2 (hashtab #'eql 1 'a 3 'a)))) + (should (not (hash-table-equal-p h1 h2))) + (should (not (hash-table-equal-p h2 h1)))) + + (let ((h1 (hashtab #'eql) + (h2 (hashtab #'eql)))) + (should (hash-table-equal-p h1 h2)) + (should (hash-table-equal-p h2 h1))) + + (let ((h1 (make-hash-table :test #'eql :size 1000 :rehash-size 3.5)) + (h2 (hashtab #'eql 10 'a 20 'b))) + (puthash 10 'a h1) + (puthash 20 'b h1) + (should (hash-table-equal-p h1 h2)) + (should (hash-table-equal-p h2 h1))) + )) (provide 'subr-x-tests) ;;; subr-x-tests.el ends here --Apple-Mail=_F9224A7E-2BFE-499E-9803-001F81A49C5D Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset=us-ascii -- [1] https://lists.gnu.org/archive/html/emacs-devel/2022-06/msg00444.html [2] https://lists.gnu.org/archive/html/emacs-devel/2022-06/msg00553.html --Apple-Mail=_F9224A7E-2BFE-499E-9803-001F81A49C5D-- From debbugs-submit-bounces@debbugs.gnu.org Fri Jun 24 14:21:57 2022 Received: (at 56199) by debbugs.gnu.org; 24 Jun 2022 18:21:57 +0000 Received: from localhost ([127.0.0.1]:43496 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1o4nwK-00062o-T4 for submit@debbugs.gnu.org; Fri, 24 Jun 2022 14:21:57 -0400 Received: from quimby.gnus.org ([95.216.78.240]:34674) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1o4nwI-00062a-SA for 56199@debbugs.gnu.org; Fri, 24 Jun 2022 14:21:55 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnus.org; s=20200322; h=Content-Transfer-Encoding:Content-Type:MIME-Version:Message-ID :In-Reply-To:Date:References:Subject:Cc:To:From:Sender:Reply-To:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=wj3DRxetT95Aksat5P7e1DjsRv4iewS59PBRhB4G59Y=; b=LQx76Qfp0tgIq6kz/QC0M6jUiX Tlov6yjb36ATheozl04gsz8Ys0cOPMKvZx0/HtTh0/fVck9ou74TAac2/ydBM7tRv7Dbp0laXHHke 3lIVquoI7uLr9syq+ZgLVku5N86rD86d6ZkQG0XHBViD7BnxCfsE9aezRfaiv3086sTI=; Received: from [84.212.220.105] (helo=xo) by quimby.gnus.org with esmtpsa (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1o4nw9-0003Us-P4; Fri, 24 Jun 2022 20:21:48 +0200 From: Lars Ingebrigtsen To: Mattias =?utf-8?Q?Engdeg=C3=A5rd?= Subject: Re: bug#56199: hash table equality predicate [PATCH] References: <8928CA50-5999-47DD-A002-46B7E9005E62@acm.org> Face: iVBORw0KGgoAAAANSUhEUgAAADAAAAAwBAMAAAClLOS0AAAABGdBTUEAALGPC/xhBQAAACBj SFJNAAB6JgAAgIQAAPoAAACA6AAAdTAAAOpgAAA6mAAAF3CculE8AAAAIVBMVEUxLCgiHRlhXFdD Pjr19PDEwbuGgnumo53W1M6AfHb///9QeSwYAAAAAWJLR0QKaND0VgAAAAd0SU1FB+YGGBIUCsf9 kboAAAGoSURBVDjLjZO9b9swEMVPUlJ5lB0IWkWLjNVNdm1UY6BQpUZ/yBCyuV2ySi0Fc3Qlu1TG Fh3y5zZLhpAskBvvh3ePdw8EeK0xmMuKPDOaULQwAnu5KdemSd9IPWOGYTe0gHFFkAaCnoeW4Jmn gWZUW5UnNeAjcj/pvUgf9dstxBo0AfhNm8pe78OoOo1v8pdnq+CKItHhtWfPlf0I/S676xpdKQDc B2YFxeUuDlXzwzlvT885blQFXMRs02KuAoDM8vv2mmrXcvLH0V25yPU8KFudyvlB29GZgrv7ZUtt w5f6QDK/cCNVkyLM8zRfUnUTHOIhJyzCGwX8PZDzQKpOfH3bT3iYDlxyShNFwUMSiww3WPNAf+JZ N2o+K69ylrKeRlgUvbL4eTt8Sh7Jdq8cyz0ev/iodRtLmbSw7BLX+9UPxdniefgssjJVHADkfpBb MSxPSn/y06/YE85WawUELJ4fWdC4WuRUJAsW7xwti/AWjtNLZkgpQJVtSg/wbh/L0AAkG0R50PvO PR8600e3GWbsNtHBhAVbykyKJw8+mrwhgf+W8z7wD1jTW5FlsOchAAAAJXRFWHRkYXRlOmNyZWF0 ZQAyMDIyLTA2LTI0VDE4OjIwOjA5KzAwOjAwteW2KAAAACV0RVh0ZGF0ZTptb2RpZnkAMjAyMi0w Ni0yNFQxODoyMDowOSswMDowMMS4DpQAAAAASUVORK5CYII= X-Now-Playing: Rocketnumbernine's _Meyouweyou_: "Black And Blue" Date: Fri, 24 Jun 2022 20:21:45 +0200 In-Reply-To: <8928CA50-5999-47DD-A002-46B7E9005E62@acm.org> ("Mattias =?utf-8?Q?Engdeg=C3=A5rd=22's?= message of "Fri, 24 Jun 2022 19:19:54 +0200") Message-ID: <87zgi1ncqu.fsf@gnus.org> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Spam-Report: Spam detection software, running on the system "quimby.gnus.org", has NOT identified this incoming email as spam. The original message has been attached to this so you can view it or label similar future email. If you have any questions, see @@CONTACT_ADDRESS@@ for details. Content preview: Mattias Engdegård writes: > Even implemented entirely in Lisp it would be an order of magnitude > faster (and actually correct). > > The attached code is not without flaws but provides a rough starting point. > (This is not me [...] Content analysis details: (-2.9 points, 5.0 required) pts rule name description ---- ---------------------- -------------------------------------------------- -1.0 ALL_TRUSTED Passed through trusted hosts only via SMTP -1.9 BAYES_00 BODY: Bayes spam probability is 0 to 1% [score: 0.0000] X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 56199 Cc: 56199@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 (---) Mattias Engdeg=C3=A5rd writes: > Even implemented entirely in Lisp it would be an order of magnitude > faster (and actually correct). > > The attached code is not without flaws but provides a rough starting poin= t. > (This is not meant as a strong argument for or against adding it in > the first place.) I can't ever recall wanting to compare two hash tables for equality (like, that's not what you use a hash table for), but since people have apparently been reimplementing this a lot, then I'm for including it. And the implementation looks nice. --=20 (domestic pets only, the antidote for overdose, milk.) bloggy blog: http://lars.ingebrigtsen.no From debbugs-submit-bounces@debbugs.gnu.org Sat Jun 25 12:56:34 2022 Received: (at 56199-done) by debbugs.gnu.org; 25 Jun 2022 16:56:34 +0000 Received: from localhost ([127.0.0.1]:46147 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1o595G-0006Dm-H9 for submit@debbugs.gnu.org; Sat, 25 Jun 2022 12:56:34 -0400 Received: from mail33c50.megamailservers.eu ([91.136.10.43]:52382) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1o595D-0006Dd-Cm for 56199-done@debbugs.gnu.org; Sat, 25 Jun 2022 12:56:33 -0400 X-Authenticated-User: mattiase@bredband.net DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=megamailservers.eu; s=maildub; t=1656176189; bh=1uIK5JPRSyYV6tVKgOS2P1Yu4lD0S8wXlvzi2ofdTpU=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=Aa2zydgJCfJBNoRMpBmHtxQACzM1sUzXjzIru4eQoT2D71iLlKR4SrjqwMgJWqk5y ZNimein+S2X3e4Ck0cFuZ18e7PcLNDgwb7X3vwZfBDDWL4/eJVE0Qsc/pSEwxKuwEq YfYrZio3DvSVP91KGNjGMMgdNiAXHTKmqRUylZKQ= Feedback-ID: mattiase@acm.or Received: from smtpclient.apple (c188-150-171-71.bredband.tele2.se [188.150.171.71]) (authenticated bits=0) by mail33c50.megamailservers.eu (8.14.9/8.13.1) with ESMTP id 25PGuSIC024306; Sat, 25 Jun 2022 16:56:29 +0000 Content-Type: text/plain; charset=us-ascii Mime-Version: 1.0 (Mac OS X Mail 14.0 \(3654.120.0.1.13\)) Subject: Re: bug#56199: hash table equality predicate [PATCH] From: =?utf-8?Q?Mattias_Engdeg=C3=A5rd?= In-Reply-To: <87zgi1ncqu.fsf@gnus.org> Date: Sat, 25 Jun 2022 18:56:27 +0200 Content-Transfer-Encoding: quoted-printable Message-Id: <2AD517D9-A9BC-44E2-A3DB-51AD84D29540@acm.org> References: <8928CA50-5999-47DD-A002-46B7E9005E62@acm.org> <87zgi1ncqu.fsf@gnus.org> To: Lars Ingebrigtsen X-Mailer: Apple Mail (2.3654.120.0.1.13) X-Origin-Country: SE X-Spam-Score: 1.0 (+) X-Debbugs-Envelope-To: 56199-done Cc: 56199-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: -0.0 (/) 24 juni 2022 kl. 20.21 skrev Lars Ingebrigtsen : > I can't ever recall wanting to compare two hash tables for equality > (like, that's not what you use a hash table for) No, you're right -- it's better to wait until there is a concrete need = for it. From debbugs-submit-bounces@debbugs.gnu.org Sun Jun 26 10:32:12 2022 Received: (at 56199-done) by debbugs.gnu.org; 26 Jun 2022 14:32:12 +0000 Received: from localhost ([127.0.0.1]:48496 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1o5TJ6-0005SM-4X for submit@debbugs.gnu.org; Sun, 26 Jun 2022 10:32:12 -0400 Received: from stw1.rcdrun.com ([217.170.207.13]:60557) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1o5TJ2-0005SC-EK for 56199-done@debbugs.gnu.org; Sun, 26 Jun 2022 10:32:10 -0400 Received: from [154.227.51.100] ([::ffff:154.227.51.100]) (AUTH: PLAIN admin, TLS: TLS1.2,128bits,ECDHE_RSA_AES_128_GCM_SHA256) by stw1.rcdrun.com with ESMTPSA id 0000000000087C51.0000000062B86DE6.000014EC; Sun, 26 Jun 2022 07:32:05 -0700 Date: Sun, 26 Jun 2022 14:30:13 +0000 In-Reply-To: <2AD517D9-A9BC-44E2-A3DB-51AD84D29540@acm.org> References: <8928CA50-5999-47DD-A002-46B7E9005E62@acm.org> <87zgi1ncqu.fsf@gnus.org> <2AD517D9-A9BC-44E2-A3DB-51AD84D29540@acm.org> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Subject: Re: bug#56199: hash table equality predicate [PATCH] To: =?ISO-8859-1?Q?Mattias_Engdeg=E5rd?= , Lars Ingebrigtsen From: Jean Louis Message-ID: <9709BCF8-4AB9-4CDF-B9BF-890D634424AE@gnu.support> X-Spam-Score: -0.0 (/) X-Debbugs-Envelope-To: 56199-done Cc: 56199-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: -1.0 (-) I use database stored hashes where new edited and updated one shall be comp= ared to the stored one=2E This will become useful=2E Jean From unknown Tue Jun 17 01:27:05 2025 Received: (at fakecontrol) by fakecontrolmessage; To: internal_control@debbugs.gnu.org From: Debbugs Internal Request Subject: Internal Control Message-Id: bug archived. Date: Mon, 25 Jul 2022 11:24:14 +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