From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Paul Eggert Newsgroups: gmane.emacs.devel Subject: Re: Using the GNU GMP Library for Bignums in Emacs Date: Wed, 18 Jul 2018 03:20:40 -0700 Organization: UCLA Computer Science Department Message-ID: <765767b2-d2e5-a9a6-f724-d58ecf4847bb@cs.ucla.edu> References: <29f933ac-a6bf-8742-66a7-0a9d6d3e5a88@disroot.org> <83bmecy6fx.fsf@gnu.org> <0d3175d8-d996-651e-b221-71978bde3a65@cs.ucla.edu> <87tvpdnzgy.fsf@tromey.com> <4c2a814f-c254-29e5-39cf-11b5f2e5c9c8@cs.ucla.edu> <49d8ba62-c9a5-9203-d882-8e900b441ff3@cs.ucla.edu> <8e0320d9-e0d0-2b57-57cc-2df4399f133c@cs.ucla.edu> <87lgaio7xd.fsf@tromey.com> <877em1cb0i.fsf@tromey.com> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="------------27F9820B61013C658C9ED65C" X-Trace: blaine.gmane.org 1531909172 347 195.159.176.226 (18 Jul 2018 10:19:32 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Wed, 18 Jul 2018 10:19:32 +0000 (UTC) User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.9.1 Cc: Tom Tromey , emacs-devel@gnu.org To: Stefan Monnier , Richard Stallman Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Wed Jul 18 12:19:27 2018 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ffjYL-0008N0-Co for ged-emacs-devel@m.gmane.org; Wed, 18 Jul 2018 12:19:25 +0200 Original-Received: from localhost ([::1]:35761 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ffjaS-0005qE-IC for ged-emacs-devel@m.gmane.org; Wed, 18 Jul 2018 06:21:36 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:58728) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ffjZg-0005PI-Hl for emacs-devel@gnu.org; Wed, 18 Jul 2018 06:20:50 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ffjZd-0002K0-9B for emacs-devel@gnu.org; Wed, 18 Jul 2018 06:20:48 -0400 Original-Received: from zimbra.cs.ucla.edu ([131.179.128.68]:36732) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1ffjZc-0002JP-Sw; Wed, 18 Jul 2018 06:20:45 -0400 Original-Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id 1025016050C; Wed, 18 Jul 2018 03:20:43 -0700 (PDT) Original-Received: from zimbra.cs.ucla.edu ([127.0.0.1]) by localhost (zimbra.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10032) with ESMTP id SQV2Kj4cUzC1; Wed, 18 Jul 2018 03:20:41 -0700 (PDT) Original-Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id C8FA8160564; Wed, 18 Jul 2018 03:20:41 -0700 (PDT) X-Virus-Scanned: amavisd-new at zimbra.cs.ucla.edu Original-Received: from zimbra.cs.ucla.edu ([127.0.0.1]) by localhost (zimbra.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10026) with ESMTP id j_nonSq2m3Hq; Wed, 18 Jul 2018 03:20:41 -0700 (PDT) Original-Received: from [192.168.1.9] (unknown [47.154.30.119]) by zimbra.cs.ucla.edu (Postfix) with ESMTPSA id 5A72016050C; Wed, 18 Jul 2018 03:20:41 -0700 (PDT) Openpgp: preference=signencrypt Autocrypt: addr=eggert@cs.ucla.edu; prefer-encrypt=mutual; keydata= xsFNBEyAcmQBEADAAyH2xoTu7ppG5D3a8FMZEon74dCvc4+q1XA2J2tBy2pwaTqfhpxxdGA9 Jj50UJ3PD4bSUEgN8tLZ0san47l5XTAFLi2456ciSl5m8sKaHlGdt9XmAAtmXqeZVIYX/UFS 96fDzf4xhEmm/y7LbYEPQdUdxu47xA5KhTYp5bltF3WYDz1Ygd7gx07Auwp7iw7eNvnoDTAl KAl8KYDZzbDNCQGEbpY3efZIvPdeI+FWQN4W+kghy+P6au6PrIIhYraeua7XDdb2LS1en3Ss mE3QjqfRqI/A2ue8JMwsvXe/WK38Ezs6x74iTaqI3AFH6ilAhDqpMnd/msSESNFt76DiO1ZK QMr9amVPknjfPmJISqdhgB1DlEdw34sROf6V8mZw0xfqT6PKE46LcFefzs0kbg4GORf8vjG2 Sf1tk5eU8MBiyN/bZ03bKNjNYMpODDQQwuP84kYLkX2wBxxMAhBxwbDVZudzxDZJ1C2VXujC OJVxq2kljBM9ETYuUGqd75AW2LXrLw6+MuIsHFAYAgRr7+KcwDgBAfwhPBYX34nSSiHlmLC+ KaHLeCLF5ZI2vKm3HEeCTtlOg7xZEONgwzL+fdKo+D6SoC8RRxJKs8a3sVfI4t6CnrQzvJbB n6gxdgCu5i29J1QCYrCYvql2UyFPAK+do99/1jOXT4m2836j1wARAQABzSBQYXVsIEVnZ2Vy dCA8ZWdnZXJ0QGNzLnVjbGEuZWR1PsLBfgQTAQIAKAUCTIByZAIbAwUJEswDAAYLCQgHAwIG FQgCCQoLBBYCAwECH In-Reply-To: Content-Language: en-US X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x [fuzzy] X-Received-From: 131.179.128.68 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.org gmane.emacs.devel:227533 Archived-At: This is a multi-part message in MIME format. --------------27F9820B61013C658C9ED65C Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: quoted-printable Stefan Monnier wrote: > I recently posted a patch which makes EQ behave like `eql` attached. > I just tried to see its impact on the ELisp compilation time > (i.e. I did `rm **/*.elc; make`). I tried to reproduce this on my machine, and ran into some trouble (the c= ode had=20 warnings that caused compilation to fail). Although your patch is evident= ly=20 intended only as a quick benchmark and not as an actual change, I worry t= hat the=20 benchmark isn't realistic enough, as some usage of EQ in C code will need= to=20 change to Feql or equivalent. Also, the C code will need to change how ha= shing=20 works since XHASH etc. must be consistent with eq. Looking into this a bit more, I discovered that eql currently operates=20 incorrectly on NaNs, as it's inconsistent with how hash tables work. I in= stalled=20 the attached patch into master to fix that. I'll try to look into doing a benchmark like yours with all the above in = mind. --------------27F9820B61013C658C9ED65C Content-Type: text/x-patch; name="0001-Fix-bug-with-eql-etc.-on-NaNs.patch" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="0001-Fix-bug-with-eql-etc.-on-NaNs.patch" =46rom c70d22f70b77b053d01c7380122d166ecb728610 Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Wed, 18 Jul 2018 03:16:54 -0700 Subject: [PATCH] Fix bug with eql etc. on NaNs Fix a bug where eql, sxhash-eql, memql, and make-hash-table were not consistent on NaNs. Likewise for equal, sxhash-equal, member, and make-hash-table. Some of these functions ignored NaN significands, whereas others treated them as significant. It's more logical to treat significands as significant, and this typically makes eql a bit more efficient on floats, with just one integer comparison instead of one to three floating-point comparisons. * doc/lispref/numbers.texi (Float Basics): Document that NaNs are never numerically equal, but might be eql. * src/fns.c (WORDS_PER_DOUBLE): Move to top level of this file. (union double_and_words): Now named, and at the top level of this file. (same_float): New function. (Fmemql, Feql, internal_equal, cmpfn_eql): Use it, so that the corresponding functions treat NaNs consistently. (sxhash_float): Simplify based on above-mentioned changes. * test/src/fns-tests.el (fns-tests-equality-nan): New test. --- doc/lispref/numbers.texi | 9 +++++-- src/fns.c | 68 +++++++++++++++++++++++++-----------------= ------ test/src/fns-tests.el | 11 ++++++++ 3 files changed, 53 insertions(+), 35 deletions(-) diff --git a/doc/lispref/numbers.texi b/doc/lispref/numbers.texi index 2fed2b6..6c51b84 100644 --- a/doc/lispref/numbers.texi +++ b/doc/lispref/numbers.texi @@ -232,13 +232,18 @@ Float Basics @cindex negative infinity @cindex infinity @cindex NaN +@findex eql +@findex sxhash-eql The @acronym{IEEE} floating-point standard supports positive infinity and negative infinity as floating-point values. It also provides for a class of values called NaN, or ``not a number''; numerical functions return such values in cases where there is no correct answer. For example, @code{(/ 0.0 0.0)} returns a NaN@. -Although NaN values carry a sign, for practical purposes there is no oth= er -significant difference between different NaN values in Emacs Lisp. +A NaN is never numerically equal to any value, not even to itself. +NaNs carry a sign and a significand, and non-numeric functions like +@code{eql} and @code{sxhash-eql} treat two NaNs as equal when their +signs and significands agree. Significands of NaNs are +machine-dependent and are not directly visible to Emacs Lisp. =20 Here are read syntaxes for these special floating-point values: =20 diff --git a/src/fns.c b/src/fns.c index c171784..10997da 100644 --- a/src/fns.c +++ b/src/fns.c @@ -1419,6 +1419,29 @@ DEFUN ("elt", Felt, Selt, 2, 2, 0, return Faref (sequence, n); } =20 +enum { WORDS_PER_DOUBLE =3D (sizeof (double) / sizeof (EMACS_UINT) + + (sizeof (double) % sizeof (EMACS_UINT) !=3D = 0)) }; +union double_and_words +{ + double val; + EMACS_UINT word[WORDS_PER_DOUBLE]; +}; + +/* Return true if X and Y are the same floating-point value. + This looks at X's and Y's representation, since (unlike '=3D=3D') + it returns true if X and Y are the same NaN. */ +static bool +same_float (Lisp_Object x, Lisp_Object y) +{ + union double_and_words + xu =3D { .val =3D XFLOAT_DATA (x) }, + yu =3D { .val =3D XFLOAT_DATA (y) }; + EMACS_UINT neql =3D 0; + for (int i =3D 0; i < WORDS_PER_DOUBLE; i++) + neql |=3D xu.word[i] ^ yu.word[i]; + return !neql; +} + DEFUN ("member", Fmember, Smember, 2, 2, 0, doc: /* Return non-nil if ELT is an element of LIST. Comparison = done with `equal'. The value is actually the tail of LIST whose car is ELT. */) @@ -1457,7 +1480,7 @@ The value is actually the tail of LIST whose car is= ELT. */) FOR_EACH_TAIL (tail) { Lisp_Object tem =3D XCAR (tail); - if (FLOATP (tem) && equal_no_quit (elt, tem)) + if (FLOATP (tem) && same_float (elt, tem)) return tail; } CHECK_LIST_END (tail, list); @@ -2175,7 +2198,7 @@ Floating-point numbers of equal value are `eql', bu= t they may not be `eq'. */) (Lisp_Object obj1, Lisp_Object obj2) { if (FLOATP (obj1)) - return equal_no_quit (obj1, obj2) ? Qt : Qnil; + return FLOATP (obj2) && same_float (obj1, obj2) ? Qt : Qnil; else return EQ (obj1, obj2) ? Qt : Qnil; } @@ -2266,13 +2289,7 @@ internal_equal (Lisp_Object o1, Lisp_Object o2, en= um equal_kind equal_kind, switch (XTYPE (o1)) { case Lisp_Float: - { - double d1 =3D XFLOAT_DATA (o1); - double d2 =3D XFLOAT_DATA (o2); - /* If d is a NaN, then d !=3D d. Two NaNs should be `equal' even - though they are not =3D. */ - return d1 =3D=3D d2 || (d1 !=3D d1 && d2 !=3D d2); - } + return same_float (o1, o2); =20 case Lisp_Cons: if (equal_kind =3D=3D EQUAL_NO_QUIT) @@ -3706,24 +3723,20 @@ HASH_INDEX (struct Lisp_Hash_Table *h, ptrdiff_t = idx) return XINT (AREF (h->index, idx)); } =20 -/* Compare KEY1 which has hash code HASH1 and KEY2 with hash code - HASH2 in hash table H using `eql'. Value is true if KEY1 and - KEY2 are the same. */ +/* Compare KEY1 and KEY2 in hash table HT using `eql'. Value is true + if KEY1 and KEY2 are the same. KEY1 and KEY2 must not be eq. */ =20 static bool cmpfn_eql (struct hash_table_test *ht, Lisp_Object key1, Lisp_Object key2) { - return (FLOATP (key1) - && FLOATP (key2) - && XFLOAT_DATA (key1) =3D=3D XFLOAT_DATA (key2)); + return FLOATP (key1) && FLOATP (key2) && same_float (key1, key2); } =20 =20 -/* Compare KEY1 which has hash code HASH1 and KEY2 with hash code - HASH2 in hash table H using `equal'. Value is true if KEY1 and - KEY2 are the same. */ +/* Compare KEY1 and KEY2 in hash table HT using `equal'. Value is + true if KEY1 and KEY2 are the same. */ =20 static bool cmpfn_equal (struct hash_table_test *ht, @@ -3734,9 +3747,8 @@ cmpfn_equal (struct hash_table_test *ht, } =20 =20 -/* Compare KEY1 which has hash code HASH1, and KEY2 with hash code - HASH2 in hash table H using H->user_cmp_function. Value is true - if KEY1 and KEY2 are the same. */ +/* Compare KEY1 and KEY2 in hash table HT using HT->user_cmp_function. + Value is true if KEY1 and KEY2 are the same. */ =20 static bool cmpfn_user_defined (struct hash_table_test *ht, @@ -4328,18 +4340,8 @@ static EMACS_UINT sxhash_float (double val) { EMACS_UINT hash =3D 0; - enum { - WORDS_PER_DOUBLE =3D (sizeof val / sizeof hash - + (sizeof val % sizeof hash !=3D 0)) - }; - union { - double val; - EMACS_UINT word[WORDS_PER_DOUBLE]; - } u; - int i; - u.val =3D val; - memset (&u.val + 1, 0, sizeof u - sizeof u.val); - for (i =3D 0; i < WORDS_PER_DOUBLE; i++) + union double_and_words u =3D { .val =3D val }; + for (int i =3D 0; i < WORDS_PER_DOUBLE; i++) hash =3D sxhash_combine (hash, u.word[i]); return SXHASH_REDUCE (hash); } diff --git a/test/src/fns-tests.el b/test/src/fns-tests.el index d9cca55..e4b9cbe 100644 --- a/test/src/fns-tests.el +++ b/test/src/fns-tests.el @@ -23,6 +23,17 @@ =20 (require 'cl-lib) =20 +;; Test that equality predicates work correctly on NaNs when combined +;; with hash tables based on those predicates. This was not the case +;; for eql in Emacs 26. +(ert-deftest fns-tests-equality-nan () + (dolist (test (list #'eq #'eql #'equal)) + (let* ((h (make-hash-table :test test)) + (nan 0.0e+NaN) + (-nan (- nan))) + (puthash nan t h) + (should (eq (funcall test nan -nan) (gethash -nan h)))))) + (ert-deftest fns-tests-reverse () (should-error (reverse)) (should-error (reverse 1)) --=20 2.7.4 --------------27F9820B61013C658C9ED65C--