Bug#38708: eq vs eql in byte-compiled code

Bug#38708: eq vs eql in byte-compiled code

[Pip Cet]

Bug#38708 (https://debbugs.gnu.org/cgi/bugreport.cgi?bug=38708)
concerned a recent change to deduplicate floating point and bignum
constants in the bytecode constants vector (when compiling with or
without optimization). There was some discussion on the bugs list,
which I'll attempt to summarize here:

The previous behavior was that if

(defun f () (format "%S %S" 1.0 1.0))

was compiled, the result would have a constant vector with two
separate, distinguishable entries for 1.0.

The new behavior is that if the same function is compiled, a single
constant is generated and referenced twice.

My initial objection to the patch, and the reason I would prefer not
to see it installed on the Emacs 27 branch, is that the apparent
behavior of eq will change in ways that seem paradoxical at first.

For example, this code will produce t:

(defun my-eq (a b) (eq a b))
(defun f () (xor (eq 1.0 1.0) (my-eq 1.0 1.0)))
(byte-compile 'f)
(f)

The reason for this is that (eq 1.0 1.0) is optimized to nil before
the constants are deduplicated, but other function calls use the
deduplicated values.

All this is related to, but not the same as, the debate over whether
eq and eql should be equivalent or not. Making them equivalent would
avoid such apparently paradoxical behavior once and for all, but it
would probably incur a significant runtime cost.

Another option might be to deduplicate constants before optimizing
forms such as (eq 1.0 1.0). That would be more work, but would also
avoid the problem.

Any thoughts?

Re: Bug#38708: eq vs eql in byte-compiled code

[Andrea Corallo]

Pip Cet <pipcet@gmail.com> writes:

> The reason for this is that (eq 1.0 1.0) is optimized to nil before
> the constants are deduplicated, but other function calls use the
> deduplicated values.

If using eq (comparing words) on things that are not symbols has
unpredictable results I don't see the problem if this is true in the
run-time as in the compile-time.

I agree that having eq and eql equivalent would be probably too
expensive in terms of performance.  Generally speaking I like to be able
to use 'eq' for what it is its classical definition.

-- 
akrl@sdf.org

Re: Bug#38708: eq vs eql in byte-compiled code

[Mattias Engdegård]

31 dec. 2019 kl. 16.07 skrev Pip Cet <pipcet@gmail.com>:

> For example, this code will produce t:
> 
> (defun my-eq (a b) (eq a b))
> (defun f () (xor (eq 1.0 1.0) (my-eq 1.0 1.0)))
> (byte-compile 'f)
> (f)

The summary is correct (thank you). Let me just add that strings were already deduplicated in the same way, so if 1.0 is replaced with "A" in the code fragment above, the result is the same. And eq is no more appropriate for flonums than for string literals.

Re: Bug#38708: eq vs eql in byte-compiled code

[Paul Eggert]

On 12/31/19 7:07 AM, Pip Cet wrote:

> the reason I would prefer not
> to see it installed on the Emacs 27 branch, is that the apparent
> behavior of eq will change in ways that seem paradoxical at first.

One possible compromise would be to duplicate only bignums in the emacs-27
branch, while reserving flonum deduplication for the master branch. This would
help a bit with now-incorrect code that uses eq to compare bignum values, while
not introducing flonum "paradoxes".

> Another option might be to deduplicate constants before optimizing
> forms such as (eq 1.0 1.0). That would be more work, but would also
> avoid the problem.

How about going a bit further, and globally deduplicating all flonums and
bignums that result from low-level text-to-number conversion and module imports?
That conversion is slow and/or rare already, and if we're lucky deduplication
wouldn't make things noticeably slower and wouldn't be much work.

Re: Bug#38708: eq vs eql in byte-compiled code

[Mattias Engdegård]

[-- Attachment #1: Type: text/plain, Size: 2124 bytes --]

31 dec. 2019 kl. 18.38 skrev Paul Eggert <eggert@cs.ucla.edu>:

> One possible compromise would be to duplicate only bignums in the emacs-27
> branch, while reserving flonum deduplication for the master branch. This would
> help a bit with now-incorrect code that uses eq to compare bignum values, while
> not introducing flonum "paradoxes".

The flonum/bignum deduplication patch is only in master at this point. If you think it emacs-27 would benefit from a version of it that specifically excludes flonums, this could of course be arranged.

In general, though, my impression is that the likelihood of any trouble in practice is nil (speaking as the author of the change, of course).

More important is how to present equality semantics to the user, through documentation, NEWS, and examples. This includes:

- What 'eq' can be used for: what we recommend, and what we guarantee.
- Which equality relation to use and when: eq, eql, equal, =, string-equal, etc.

For example, while we have to guarantee that 'eq' works for fixnums for compatibility, it may be unwise to give this fact prominence in the documentation. One of the benefits of bignums is that users no longer have to worry about fixnum ranges in most cases. The standard rule should be not to use 'eq' for numbers of any kind.

Whether to specifically mention characters as eq-comparable is a matter of judgement. (Neither CL nor Scheme guarantee that characters can be used with eq/eq?.) Of course my own code is littered with eq for characters, but do as I say...

Attached is a proposed documentation patch for emacs-27. While not perfect, it should at least be an improvement (and fixes at least one error).

> How about going a bit further, and globally deduplicating all flonums and
> bignums that result from low-level text-to-number conversion and module imports?
> That conversion is slow and/or rare already, and if we're lucky deduplication
> wouldn't make things noticeably slower and wouldn't be much work.

Maybe, but wouldn't that slow down reading .elc files (and still not shorten individual constant vectors)?


[-- Attachment #2: 0001-Clarify-eq-on-numbers.patch --]
[-- Type: application/octet-stream, Size: 5209 bytes --]

From fdb4519ca621fbfd893f23f62ef0b97379f9c8a9 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Mattias=20Engdeg=C3=A5rd?= <mattiase@acm.org>
Date: Wed, 1 Jan 2020 13:06:39 +0100
Subject: [PATCH] Clarify 'eq' on numbers

* doc/lispref/numbers.texi (Integer Basics):
* doc/lispref/objects.texi (Integer Type, Equality Predicates):
* etc/NEWS:

Recommend that 'eq' not be used to compare numbers, and fix some
erroneous or misleading examples.  See discussion starting at
https://lists.gnu.org/archive/html/emacs-devel/2019-12/msg00856.html
and bug#38708.
---
 doc/lispref/numbers.texi |  2 ++
 doc/lispref/objects.texi | 32 +++++++++++++++++---------------
 etc/NEWS                 |  3 ++-
 3 files changed, 21 insertions(+), 16 deletions(-)

diff --git a/doc/lispref/numbers.texi b/doc/lispref/numbers.texi
index e952980f26..1c6f8ae7be 100644
--- a/doc/lispref/numbers.texi
+++ b/doc/lispref/numbers.texi
@@ -41,6 +41,8 @@ Integer Basics
 Some functions in Emacs accept only fixnums.  Also, while fixnums can
 always be compared for numeric equality with @code{eq}, bignums
 require more-heavyweight equality predicates like @code{eql}.
+To avoid any concern about fixnum ranges, use @code{eql} or @code{=}
+for comparing numbers.
 
   The range of values for bignums is limited by the amount of main
 memory, by machine characteristics such as the size of the word used
diff --git a/doc/lispref/objects.texi b/doc/lispref/objects.texi
index 4be2eb6918..a0ce7aebd0 100644
--- a/doc/lispref/objects.texi
+++ b/doc/lispref/objects.texi
@@ -270,7 +270,9 @@ Integer Type
 @code{eql} or @code{=}.  To test whether an integer is a fixnum or a
 bignum, you can compare it to @code{most-negative-fixnum} and
 @code{most-positive-fixnum}, or you can use the convenience predicates
-@code{fixnump} and @code{bignump} on any object.
+@code{fixnump} and @code{bignump} on any object.  Most of the time,
+however, it is more convenient to ignore the difference and use
+@code{eql} or @code{=} for comparing any kind of number.
 
   The read syntax for integers is a sequence of (base ten) digits with an
 optional sign at the beginning and an optional period at the end.  The
@@ -2167,19 +2169,20 @@ Equality Predicates
 This function returns @code{t} if @var{object1} and @var{object2} are
 the same object, and @code{nil} otherwise.
 
-If @var{object1} and @var{object2} are fixnums with the same value,
-they are considered to be the same object (i.e., @code{eq} returns
-@code{t}).  If @var{object1} and @var{object2} are symbols with the
+Numbers in general do not have an object identity and therefore cannot
+be compared reliably using @code{eq}.  While fixnums (and characters)
+with the same value are considered to be the same object (i.e.,
+@code{eq} returns @code{t}), this is not true for bignums and floats.
+For maximum portability and robustness, avoid using @code{eq} for
+numbers (@pxref{Comparison of Numbers}).
+
+If @var{object1} and @var{object2} are symbols with the
 same name, they are normally the same object---but see @ref{Creating
 Symbols} for exceptions.  For other types (e.g., lists, vectors,
 strings), two arguments with the same contents or elements are not
 necessarily @code{eq} to each other: they are @code{eq} only if they
 are the same object, meaning that a change in the contents of one will
 be reflected by the same change in the contents of the other.
-For other types of objects whose contents cannot be changed (e.g.,
-bignums and floats), two arguments with the same contents might or might not be
-the same object, and @code{eq} returns @code{t} or @code{nil}
-depending on whether the Lisp interpreter created one object or two.
 
 @example
 @group
@@ -2188,26 +2191,25 @@ Equality Predicates
 @end group
 
 @group
-(eq 456 456)
+(eq ?A ?A)
      @result{} t
 @end group
 
 @group
 (eq 3.0 3.0)
      @result{} t @r{or} nil
-;; @r{The result is implementation-dependent.}
+;; @r{Equal floats may or may not be the same object.}
 @end group
 
 @group
-(eq "asdf" "asdf")
+(eq (make-string 3 ?A) (make-string 3 ?A))
      @result{} nil
 @end group
 
 @group
-(eq "" "")
-     @result{} t
-;; @r{This exception occurs because Emacs Lisp}
-;; @r{makes just one multibyte empty string, to save space.}
+(eq "asdf" "asdf")
+     @result{} t @r{or} nil
+;; @r{Equal string constants may or may not be the same object.}
 @end group
 
 @group
diff --git a/etc/NEWS b/etc/NEWS
index a8c8e2763e..efcd63e35c 100644
--- a/etc/NEWS
+++ b/etc/NEWS
@@ -2879,7 +2879,8 @@ All the arithmetic, comparison, and logical (a.k.a. "bitwise")
 operations where bignums make sense now support both fixnums and
 bignums.  However, note that unlike fixnums, bignums will not compare
 equal with 'eq', you must use 'eql' instead.  (Numerical comparison
-with '=' works on both, of course.)
+with '=' works on both, of course.)  To avoid mistakes, we recommend
+that you do not use 'eq' for comparing numbers at all.
 
 Since large bignums consume a lot of memory, Emacs limits the size of
 the largest bignum a Lisp program is allowed to create.  The
-- 
2.21.0 (Apple Git-122.2)

Re: Bug#38708: eq vs eql in byte-compiled code

[Stefan Monnier]

>> For example, this code will produce t:
>> (defun my-eq (a b) (eq a b))
>> (defun f () (xor (eq 1.0 1.0) (my-eq 1.0 1.0)))
>> (byte-compile 'f)
>> (f)

Such paradoxes are just what you get from using `eq`.
We could eliminate this one in some ad-hoc way, but there'd still be a
million others.  AFAIK people here have decided (to my chagrin) that
`eq` should stay distinct from `eql`, so these paradoxes are considered
as "features".

> How about going a bit further, and globally deduplicating all flonums
> and bignums that result from low-level text-to-number conversion and
> module imports?

I don't see the benefit.  All it would do, AFAICT, is to make it more
difficult to "manually" reproduce/show those eq-paradoxes, so people
will be even more stumped when their code gets nil whereas redoing the
test by hand with M-: returns t (which again, is part of the "fetureset"
of `eq`, but still).

We could/should do hash-consing of bignums, tho.  It won't affect code
that doesn't use bignums, and should have a fairly minor performance
cost for bignums while making their semantics more clean.


        Stefan

Re: Bug#38708: eq vs eql in byte-compiled code

[Paul Eggert]

[-- Attachment #1: Type: text/plain, Size: 1409 bytes --]

On 1/1/20 7:45 AM, Stefan Monnier wrote:
> We could/should do hash-consing of bignums, tho.  It won't affect code
> that doesn't use bignums, and should have a fairly minor performance
> cost for bignums while making their semantics more clean.

I did that, and surprise! it sped up 'make compile-always' by about 7% on the
two platforms I tried it on (Fedora 31 and Ubuntu 18.04.3, both x86-64).

Although hash-consing of bignums slows down computations that do nothing but
generate new bignums (a slowdown of 38% on my microbenchmark) such computations
are reasonably rare, and the benefit having 'eq' be more-compatible with
traditional Emacs (as well as the abovementioned speedup in more-typical code)
seems to make this tradeoff well worthwhile.

Code patch against Emacs master attached. Given the performance boost, at least
this should go into master; not so sure about emacs-27, though (pro: eq is more
compatible; con: it's a last-minute change to emacs-27).

Two or three issues:

* Should we document that eq == eql on bignums, or continue to leave this stuff
unspecified?

* Should we try hash-consing floats too? Maybe it wouldn't be as slow as we
thought, for typical computations anyway....

* The attached patch could probably be sped up a bit by supporting sets as well
as mappings at the low level, since bignum_map is really just a set of bignums.
Not sure it's worth the effort, though.

[-- Attachment #2: 0001-Hash-cons-bignums.txt --]
[-- Type: text/plain, Size: 10506 bytes --]

From 2cc2d34a4f0fe866714f062dde7bfcc485b3b9e4 Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Wed, 1 Jan 2020 23:18:58 -0800
Subject: [PATCH] Hash-cons bignums
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

Suggested by Stefan Monnier in:
https://lists.gnu.org/r/emacs-devel/2020-01/msg00010.html
This improves performance of ‘make compile-always’
by about 7% on my platform (x86-64 Ubuntu 18.04.3).
* src/alloc.c (make_pure_bignum): Remove, as we can’t copy (much
less purecopy) bignums any more.  Caller removed.
* src/bignum.c (make_bignum_bits): Make sure the result is unique.
(make_bignum_str): Let make_bignum do the work.  Also, this
checks against converting a string to a too-big bignum.
* src/fns.c (Fmemql, Feql, internal_equal, hashfn_eql):
Just use eq to compare bignums.
(sxhash_mpz): Rename from sxhash_bignum and change the argument
to mpz_t const *.  Caller changed.
(sxhash): No need to treat bignums specially any more.
(bignum_map): New static variable.
(make_unique_bignum): New function, which uses sxhash_mpz.
(syms_of_fns): Initialize bignum_map.
* src/pdumper.c (dump_hash_table_stable_p):
Bignums are stable keys now.
---
 src/alloc.c   |  31 ----------------
 src/bignum.c  |  14 ++-----
 src/fns.c     | 100 +++++++++++++++++++++++++++++++-------------------
 src/lisp.h    |   1 +
 src/pdumper.c |   5 +--
 5 files changed, 68 insertions(+), 83 deletions(-)

diff --git a/src/alloc.c b/src/alloc.c
index 1c6b664b22..6a2ae6f6d5 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -5279,35 +5279,6 @@ make_pure_float (double num)
   return new;
 }
 
-/* Value is a bignum object with value VALUE allocated from pure
-   space.  */
-
-static Lisp_Object
-make_pure_bignum (Lisp_Object value)
-{
-  mpz_t const *n = xbignum_val (value);
-  size_t i, nlimbs = mpz_size (*n);
-  size_t nbytes = nlimbs * sizeof (mp_limb_t);
-  mp_limb_t *pure_limbs;
-  mp_size_t new_size;
-
-  struct Lisp_Bignum *b = pure_alloc (sizeof *b, Lisp_Vectorlike);
-  XSETPVECTYPESIZE (b, PVEC_BIGNUM, 0, VECSIZE (struct Lisp_Bignum));
-
-  int limb_alignment = alignof (mp_limb_t);
-  pure_limbs = pure_alloc (nbytes, - limb_alignment);
-  for (i = 0; i < nlimbs; ++i)
-    pure_limbs[i] = mpz_getlimbn (*n, i);
-
-  new_size = nlimbs;
-  if (mpz_sgn (*n) < 0)
-    new_size = -new_size;
-
-  mpz_roinit_n (b->value, pure_limbs, new_size);
-
-  return make_lisp_ptr (b, Lisp_Vectorlike);
-}
-
 /* Return a vector with room for LEN Lisp_Objects allocated from
    pure space.  */
 
@@ -5449,8 +5420,6 @@ purecopy (Lisp_Object obj)
       /* Don't hash-cons it.  */
       return obj;
     }
-  else if (BIGNUMP (obj))
-    obj = make_pure_bignum (obj);
   else
     {
       AUTO_STRING (fmt, "Don't know how to purify: %S");
diff --git a/src/bignum.c b/src/bignum.c
index 51d90ffaef..0e3f5db8d9 100644
--- a/src/bignum.c
+++ b/src/bignum.c
@@ -89,12 +89,7 @@ make_bignum_bits (size_t bits)
      timestamps.  */
   if (integer_width < bits && 2 * max (INTMAX_WIDTH, UINTMAX_WIDTH) < bits)
     overflow_error ();
-
-  struct Lisp_Bignum *b = ALLOCATE_PLAIN_PSEUDOVECTOR (struct Lisp_Bignum,
-						       PVEC_BIGNUM);
-  mpz_init (b->value);
-  mpz_swap (b->value, mpz[0]);
-  return make_lisp_ptr (b, Lisp_Vectorlike);
+  return make_unique_bignum ();
 }
 
 /* Return a Lisp integer equal to mpz[0], which must not be in fixnum range.
@@ -424,10 +419,7 @@ bignum_to_string (Lisp_Object num, int base)
 Lisp_Object
 make_bignum_str (char const *num, int base)
 {
-  struct Lisp_Bignum *b = ALLOCATE_PLAIN_PSEUDOVECTOR (struct Lisp_Bignum,
-						       PVEC_BIGNUM);
-  mpz_init (b->value);
-  int check = mpz_set_str (b->value, num, base);
+  int check = mpz_set_str (mpz[0], num, base);
   eassert (check == 0);
-  return make_lisp_ptr (b, Lisp_Vectorlike);
+  return make_bignum ();
 }
diff --git a/src/fns.c b/src/fns.c
index 3b5feace52..80e0eac71c 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -1575,29 +1575,17 @@ DEFUN ("memql", Fmemql, Smemql, 2, 2, 0,
 The value is actually the tail of LIST whose car is ELT.  */)
   (Lisp_Object elt, Lisp_Object list)
 {
+  if (!FLOATP (elt))
+    return Fmemq (elt, list);
+
   Lisp_Object tail = list;
 
-  if (FLOATP (elt))
-    {
-      FOR_EACH_TAIL (tail)
-        {
-          Lisp_Object tem = XCAR (tail);
-          if (FLOATP (tem) && same_float (elt, tem))
-            return tail;
-        }
-    }
-  else if (BIGNUMP (elt))
+  FOR_EACH_TAIL (tail)
     {
-      FOR_EACH_TAIL (tail)
-        {
-          Lisp_Object tem = XCAR (tail);
-          if (BIGNUMP (tem)
-	      && mpz_cmp (*xbignum_val (elt), *xbignum_val (tem)) == 0)
-            return tail;
-        }
+      Lisp_Object tem = XCAR (tail);
+      if (FLOATP (tem) && same_float (elt, tem))
+	return tail;
     }
-  else
-    return Fmemq (elt, list);
 
   CHECK_LIST_END (tail, list);
   return Qnil;
@@ -2300,14 +2288,9 @@ DEFUN ("eql", Feql, Seql, 2, 2, 0,
 \(eql 0.0e+NaN 0.0e+NaN) returns t, whereas `=' does the opposite.  */)
   (Lisp_Object obj1, Lisp_Object obj2)
 {
-  if (FLOATP (obj1))
-    return FLOATP (obj2) && same_float (obj1, obj2) ? Qt : Qnil;
-  else if (BIGNUMP (obj1))
-    return ((BIGNUMP (obj2)
-	     && mpz_cmp (*xbignum_val (obj1), *xbignum_val (obj2)) == 0)
-	    ? Qt : Qnil);
-  else
-    return EQ (obj1, obj2) ? Qt : Qnil;
+  return ((EQ (obj1, obj2)
+	   || (FLOATP (obj1) && FLOATP (obj2) && same_float (obj1, obj2)))
+	  ? Qt : Qnil);
 }
 
 DEFUN ("equal", Fequal, Sequal, 2, 2, 0,
@@ -2433,8 +2416,6 @@ internal_equal (Lisp_Object o1, Lisp_Object o2, enum equal_kind equal_kind,
 	   same size.  */
 	if (ASIZE (o2) != size)
 	  return false;
-	if (BIGNUMP (o1))
-	  return mpz_cmp (*xbignum_val (o1), *xbignum_val (o2)) == 0;
 	if (OVERLAYP (o1))
 	  {
 	    if (!internal_equal (OVERLAY_START (o1), OVERLAY_START (o2),
@@ -4031,7 +4012,7 @@ hashfn_equal (Lisp_Object key, struct Lisp_Hash_Table *h)
 Lisp_Object
 hashfn_eql (Lisp_Object key, struct Lisp_Hash_Table *h)
 {
-  return (FLOATP (key) || BIGNUMP (key) ? hashfn_equal : hashfn_eq) (key, h);
+  return (FLOATP (key) ? hashfn_equal : hashfn_eq) (key, h);
 }
 
 /* Given HT, return a hash code for KEY which uses a user-defined
@@ -4655,16 +4636,15 @@ sxhash_bool_vector (Lisp_Object vec)
   return SXHASH_REDUCE (hash);
 }
 
-/* Return a hash for a bignum.  */
+/* Return a hash for an integer.  */
 
 static EMACS_UINT
-sxhash_bignum (Lisp_Object bignum)
+sxhash_mpz (mpz_t const *n)
 {
-  mpz_t const *n = xbignum_val (bignum);
-  size_t i, nlimbs = mpz_size (*n);
+  size_t nlimbs = mpz_size (*n);
   EMACS_UINT hash = 0;
 
-  for (i = 0; i < nlimbs; ++i)
+  for (size_t i = 0; i < nlimbs; i++)
     hash = sxhash_combine (hash, mpz_getlimbn (*n, i));
 
   return SXHASH_REDUCE (hash);
@@ -4698,9 +4678,7 @@ sxhash (Lisp_Object obj, int depth)
 
       /* This can be everything from a vector to an overlay.  */
     case Lisp_Vectorlike:
-      if (BIGNUMP (obj))
-	hash = sxhash_bignum (obj);
-      else if (VECTORP (obj) || RECORDP (obj))
+      if (VECTORP (obj) || RECORDP (obj))
 	/* According to the CL HyperSpec, two arrays are equal only if
 	   they are `eq', except for strings and bit-vectors.  In
 	   Emacs, this works differently.  We have to compare element
@@ -5066,6 +5044,47 @@ DEFUN ("define-hash-table-test", Fdefine_hash_table_test,
   return Fput (name, Qhash_table_test, list2 (test, hash));
 }
 
+\f
+/***********************************************************************
+			    Hashed bignums
+ ***********************************************************************/
+
+/* Weak hash table of all current bignum objects, to prevent duplicates.  */
+
+static Lisp_Object bignum_map;
+
+/* Return the unique bignum with value equal to mpz[0], which must not
+   be in fixnum range.  Set mpz[0] to a junk value.  */
+
+Lisp_Object
+make_unique_bignum (void)
+{
+  struct Lisp_Hash_Table *h = XHASH_TABLE (bignum_map);
+
+  /* If mpz[0]'s value is already hashed, return the corresponding bignum.
+     This is like hash_lookup, except with special hashing and
+     comparison for bignums.  hash_rehash_if_needed would be redundant
+     since sxhash_mpz is stable.  */
+  EMACS_UINT hash = sxhash_mpz (&mpz[0]);
+  Lisp_Object hash_code = make_ufixnum (hash);
+  ptrdiff_t start_of_bucket = hash % ASIZE (h->index);
+  for (ptrdiff_t i = HASH_INDEX (h, start_of_bucket);
+       0 <= i; i = HASH_NEXT (h, i))
+    if (EQ (hash_code, HASH_HASH (h, i)))
+      {
+	Lisp_Object num = HASH_KEY (h, i);
+	if (mpz_cmp (mpz[0], *xbignum_val (num)) == 0)
+	  return num;
+      }
+
+  struct Lisp_Bignum *b = ALLOCATE_PLAIN_PSEUDOVECTOR (struct Lisp_Bignum,
+						       PVEC_BIGNUM);
+  mpz_init (b->value);
+  mpz_swap (b->value, mpz[0]);
+  Lisp_Object bignum = make_lisp_ptr (b, Lisp_Vectorlike);
+  hash_put (h, bignum, Qnil, hash_code);
+  return bignum;
+}
 
 \f
 /************************************************************************
@@ -5665,4 +5684,9 @@ syms_of_fns (void)
   defsubr (&Ssecure_hash);
   defsubr (&Sbuffer_hash);
   defsubr (&Slocale_info);
+
+  bignum_map = make_hash_table (hashtest_eq, DEFAULT_HASH_SIZE,
+				DEFAULT_REHASH_SIZE, DEFAULT_REHASH_THRESHOLD,
+				Qkey, false);
+  staticpro (&bignum_map);
 }
diff --git a/src/lisp.h b/src/lisp.h
index 8674fe11a6..e066085514 100644
--- a/src/lisp.h
+++ b/src/lisp.h
@@ -3649,6 +3649,7 @@ #define CONS_TO_INTEGER(cons, type, var)				\
 extern EMACS_INT next_almost_prime (EMACS_INT) ATTRIBUTE_CONST;
 extern Lisp_Object larger_vector (Lisp_Object, ptrdiff_t, ptrdiff_t);
 extern bool sweep_weak_table (struct Lisp_Hash_Table *, bool);
+extern Lisp_Object make_unique_bignum (void);
 extern void hexbuf_digest (char *, void const *, int);
 extern char *extract_data_from_object (Lisp_Object, ptrdiff_t *, ptrdiff_t *);
 EMACS_UINT hash_string (char const *, ptrdiff_t);
diff --git a/src/pdumper.c b/src/pdumper.c
index 3ee1146040..ab0461ccb6 100644
--- a/src/pdumper.c
+++ b/src/pdumper.c
@@ -2632,11 +2632,10 @@ dump_hash_table_stable_p (const struct Lisp_Hash_Table *hash)
       if (!EQ (key, Qunbound))
         {
 	  bool key_stable = (dump_builtin_symbol_p (key)
-			     || FIXNUMP (key)
+			     || INTEGERP (key)
 			     || (is_equal
 			         && (STRINGP (key) || BOOL_VECTOR_P (key)))
-			     || ((is_equal || is_eql)
-			         && (FLOATP (key) || BIGNUMP (key))));
+			     || ((is_equal || is_eql) && FLOATP (key)));
           if (!key_stable)
             return false;
         }
-- 
2.17.1

Re: Bug#38708: eq vs eql in byte-compiled code

[Paul Eggert]

[-- Attachment #1: Type: text/plain, Size: 1991 bytes --]

On 1/1/20 4:38 AM, Mattias Engdegård wrote:

> The flonum/bignum deduplication patch is only in master at this point. If you think it emacs-27 would benefit from a version of it that specifically excludes flonums, this could of course be arranged.

This depends on how important we want (eq integer integer) to work in Emacs 27
as it did in Emacs 26. If it's important, then we hash-cons bignums in Emacs 27
(using a patch like the one I just emailed you), and in that case the
flonum/bignum deduplication patch does not matter for bignums. If it's not
important, then I'd say the flonum/bignum deduplication patch is not urgent
enough to put into Emacs 27.

> The standard rule should be not to use 'eq' for numbers of any kind.

The manual already says this:

To test numbers for numerical equality, you should normally use
@code{=} instead of non-numeric comparison predicates like @code{eq},
@code{eql} and @code{equal}.

> Attached is a proposed documentation patch for emacs-27. While not perfect, it should at least be an improvement (and fixes at least one error).

I found that a bit too dogmatic about avoiding eq on numbers, as it's reasonable
to use eq in many cases (I do it in my code, you do it in your code, and as long
as you know what you're doing it's OK). How about the attached patch instead?
(It does not assume the global bignum deduplication patch.)

>> How about going a bit further, and globally deduplicating all flonums and
>> bignums that result from low-level text-to-number conversion and module imports?
>> That conversion is slow and/or rare already, and if we're lucky deduplication
>> wouldn't make things noticeably slower and wouldn't be much work.
> 
> Maybe, but wouldn't that slow down reading .elc files (and still not shorten individual constant vectors)?

Almost surely it would, yes. I don't know how important that would be. Perhaps
we'd get performance back elsewhere. Only one way to find out, I suppose....

[-- Attachment #2: doc.diff --]
[-- Type: text/x-patch, Size: 3852 bytes --]

diff --git a/doc/lispref/numbers.texi b/doc/lispref/numbers.texi
index e952980f26..c8941eab73 100644
--- a/doc/lispref/numbers.texi
+++ b/doc/lispref/numbers.texi
@@ -39,8 +39,8 @@ Integer Basics
   Under the hood, though, there are two kinds of integers: smaller
 ones, called @dfn{fixnums}, and larger ones, called @dfn{bignums}.
 Some functions in Emacs accept only fixnums.  Also, while fixnums can
-always be compared for numeric equality with @code{eq}, bignums
-require more-heavyweight equality predicates like @code{eql}.
+be compared for numeric equality with @code{eq}, bignums require
+more-heavyweight equality predicates like @code{eql} and @code{=}.
 
   The range of values for bignums is limited by the amount of main
 memory, by machine characteristics such as the size of the word used
diff --git a/doc/lispref/objects.texi b/doc/lispref/objects.texi
index 4be2eb6918..1c4e7e4d4e 100644
--- a/doc/lispref/objects.texi
+++ b/doc/lispref/objects.texi
@@ -266,8 +266,8 @@ Integer Type
   Bignums can have arbitrary precision.  Operations that overflow a
 fixnum will return a bignum instead.
 
-  Fixnums can be compared with @code{eq}, but bignums require
-@code{eql} or @code{=}.  To test whether an integer is a fixnum or a
+  All numbers can be compared with @code{eql} or @code{=}; fixnums can
+also be compared with @code{eq}.  To test whether an integer is a fixnum or a
 bignum, you can compare it to @code{most-negative-fixnum} and
 @code{most-positive-fixnum}, or you can use the convenience predicates
 @code{fixnump} and @code{bignump} on any object.
@@ -2167,17 +2167,20 @@ Equality Predicates
 This function returns @code{t} if @var{object1} and @var{object2} are
 the same object, and @code{nil} otherwise.
 
-If @var{object1} and @var{object2} are fixnums with the same value,
-they are considered to be the same object (i.e., @code{eq} returns
-@code{t}).  If @var{object1} and @var{object2} are symbols with the
+If @var{object1} and @var{object2} are symbols with the
 same name, they are normally the same object---but see @ref{Creating
-Symbols} for exceptions.  For other types (e.g., lists, vectors,
+Symbols} for exceptions.  For other non-numeric types (e.g., lists, vectors,
 strings), two arguments with the same contents or elements are not
 necessarily @code{eq} to each other: they are @code{eq} only if they
 are the same object, meaning that a change in the contents of one will
 be reflected by the same change in the contents of the other.
-For other types of objects whose contents cannot be changed (e.g.,
-bignums and floats), two arguments with the same contents might or might not be
+
+If @var{object1} and @var{object2} are numbers with differing types or values,
+then they cannot be the same object and @code{eq} returns @code{nil}.
+If they are fixnums with the same value,
+then they are the same object and @code{eq} returns @code{t}.
+If they were computed separately but happen to have the same value
+and the same non-fixnum numeric type, then they might or might not be
 the same object, and @code{eq} returns @code{t} or @code{nil}
 depending on whether the Lisp interpreter created one object or two.
 
@@ -2188,26 +2191,25 @@ Equality Predicates
 @end group
 
 @group
-(eq 456 456)
+(eq ?A ?A)
      @result{} t
 @end group
 
 @group
 (eq 3.0 3.0)
      @result{} t @r{or} nil
-;; @r{The result is implementation-dependent.}
+;; @r{Equal floats may or may not be the same object.}
 @end group
 
 @group
-(eq "asdf" "asdf")
+(eq (make-string 3 ?A) (make-string 3 ?A))
      @result{} nil
 @end group
 
 @group
-(eq "" "")
-     @result{} t
-;; @r{This exception occurs because Emacs Lisp}
-;; @r{makes just one multibyte empty string, to save space.}
+(eq "asdf" "asdf")
+     @result{} t @r{or} nil
+;; @r{Equal string constants or may not be the same object.}
 @end group
 
 @group

Re: Bug#38708: eq vs eql in byte-compiled code

[Pip Cet]

On Thu, Jan 2, 2020 at 7:52 AM Paul Eggert <eggert@cs.ucla.edu> wrote:
> I did that, and surprise! it sped up 'make compile-always' by about 7% on the
> two platforms I tried it on (Fedora 31 and Ubuntu 18.04.3, both x86-64).

For what it's worth, I'm not seeing that effect, and it seems too
large to me to be easily explicable.

I might be mistaken, but our hash tables never shrink, do they? That
sounds like a potential problem to me, particularly for people who
mess about with gc settings; but I haven't been able to produce a
problem in practice with your patch.

> Two or three issues:
>
> * Should we document that eq == eql on bignums, or continue to leave this stuff
> unspecified?

I don't think we should be making any new promises about eq.

> * Should we try hash-consing floats too? Maybe it wouldn't be as slow as we
> thought, for typical computations anyway....

I think the answer is yes here...

> * The attached patch could probably be sped up a bit by supporting sets as well
> as mappings at the low level, since bignum_map is really just a set of bignums.
> Not sure it's worth the effort, though.

if it's also yes here.

Re: Bug#38708: eq vs eql in byte-compiled code

[Eli Zaretskii]

> From: Paul Eggert <eggert@cs.ucla.edu>
> Date: Wed, 1 Jan 2020 23:52:12 -0800
> Cc: Mattias Engdegård <mattiase@acm.org>,
>  Pip Cet <pipcet@gmail.com>, emacs-devel@gnu.org
> 
> Code patch against Emacs master attached. Given the performance boost, at least
> this should go into master; not so sure about emacs-27, though (pro: eq is more
> compatible; con: it's a last-minute change to emacs-27).

Please, not on emacs-27.  We shouldn't add any more new features, not
even fix any bugs that require non-trivial changes.

Than ks.

Re: Bug#38708: eq vs eql in byte-compiled code

[Mattias Engdegård]

2 jan. 2020 kl. 09.38 skrev Paul Eggert <eggert@cs.ucla.edu>:

> [...] If it's not
> important, then I'd say the flonum/bignum deduplication patch is not urgent
> enough to put into Emacs 27.

Yes, we'd better leave Emacs 27 alone, except for improved documentation.

I'm feeling queasy about hash-consing floats and bignums. Benchmarking is treacherous in several regards: there is currently very little use of bignums for obvious reasons, and Emacs sessions are famously long-lived. The real problem is Emacs's archaic non-generational GC.

Most bignums aren't very big; they tend to obey a power law. Particularly common are full-word integers, just a bit or two larger than fixnums. They crop up in various kind of system interfaces (IDs, handles, addresses etc), FFIs, checksums/hashes, fields in binary files and protocols, and so on. Having bignums, we may see quite a few of these.

In other words, making bignums/flonums slower may seem to have no bad effects, until suddenly it has.

> The manual already says this:
> 
> To test numbers for numerical equality, you should normally use
> @code{=} instead of non-numeric comparison predicates like @code{eq},
> @code{eql} and @code{equal}.

That sentence mentions eq and eql as equally inferior alternatives to =, which isn't necessarily helpful.

> I found that a bit too dogmatic about avoiding eq on numbers, as it's reasonable
> to use eq in many cases (I do it in my code, you do it in your code, and as long
> as you know what you're doing it's OK).

We should be allowed to make recommendations as long as it's made clear that experts (ahem) can do what they please, no? The user may otherwise not realise that using eql instead of eq (1) makes their code more portable, and (2) extends it to a greater range of input data, both of which will make it useful in a wider range of circumstances.

That said, your patch is fine! One sentence, though:

> +If they were computed separately but happen to have the same value
> +and the same non-fixnum numeric type, then they might or might not be
>  the same object, and @code{eq} returns @code{t} or @code{nil}
>  depending on whether the Lisp interpreter created one object or two.


The "computed separately" qualifier is a bit too vague, but the statement also risks becoming too strong. Can't we just say that equal non-fixnum numbers may or may not be eq?

Re: Bug#38708: eq vs eql in byte-compiled code

[Paul Eggert]

On 1/2/20 4:27 AM, Pip Cet wrote:

> For what it's worth, I'm not seeing that effect, and it seems too
> large to me to be easily explicable.

I'm also puzzled. I reproduced the effect on two smallish hosts (Fedora 
31, Ubuntu 18.04.3) running sequentially, but not on a larger one when 
running with 'make -j14' (RHEL 7.7). I'll look into it a bit more. Could 
be a cache-size issue.
> I might be mistaken, but our hash tables never shrink, do they? That
> sounds like a potential problem to me, particularly for people who
> mess about with gc settings; but I haven't been able to produce a
> problem in practice with your patch.

You're right they don't shrink. However, on today's machines I expect 
that the only problem would be that a hash table too large for its 
number of entries would not cache as well.

>> * Should we try hash-consing floats too? Maybe it wouldn't be as slow as we
>> thought, for typical computations anyway....
> 
> I think the answer is yes here...
> 
>> * The attached patch could probably be sped up a bit by supporting sets as well
>> as mappings at the low level, since bignum_map is really just a set of bignums.
>> Not sure it's worth the effort, though.
> 
> if it's also yes here.

More things for me to look into, I suppose...

Re: Bug#38708: eq vs eql in byte-compiled code

[Stefan Monnier]

> * Should we try hash-consing floats too?

A float operation is typically extremely quick (less than 10 CPU
cycles), so the relative overhead of hash-consing them will be very
much higher than the 38% worst case you got on bignums.

IOW, it would be fine for the case where we don't use floats very much,
but it would make float operations too expensive IMO.

> * The attached patch could probably be sped up a bit by supporting
> sets as well as mappings at the low level, since bignum_map is really
> just a set of bignums.  Not sure it's worth the effort, though.

I don't think a "hash-set" would be much smaller than a hash-map, so the
benefit would be fairly small (the ~5 words-per-entry cost of
a hash-table are hash+index+next+key+value, so a set would only save one
of those).

OTOH defining a hash-set as the base structure and then building
hash-table on-top would make it possible to safely export the
"hash-lookup" such that `incf` on a hash-table could perform the lookup
only once.

> From 2cc2d34a4f0fe866714f062dde7bfcc485b3b9e4 Mon Sep 17 00:00:00 2001
> From: Paul Eggert <eggert@cs.ucla.edu>
> Date: Wed, 1 Jan 2020 23:18:58 -0800
> Subject: [PATCH] Hash-cons bignums
> MIME-Version: 1.0
> Content-Type: text/plain; charset=UTF-8
> Content-Transfer-Encoding: 8bit
>
> Suggested by Stefan Monnier in:
> https://lists.gnu.org/r/emacs-devel/2020-01/msg00010.html
> This improves performance of ‘make compile-always’
> by about 7% on my platform (x86-64 Ubuntu 18.04.3).

> * src/alloc.c (make_pure_bignum): Remove, as we can’t copy (much
> less purecopy) bignums any more.

Sounds dangerous: it means that pure objects which point to bignums
could end up with dangling pointers because the GC won't see those
pointers and will then GC the corresponding bignum.

I think we should instead *move* the bignum to pure space.


        Stefan

Re: Bug#38708: eq vs eql in byte-compiled code

[Paul Eggert]

On 1/4/20 10:54 AM, Stefan Monnier wrote:
>> * src/alloc.c (make_pure_bignum): Remove, as we can’t copy (much
>> less purecopy) bignums any more.
> Sounds dangerous: it means that pure objects which point to bignums
> could end up with dangling pointers because the GC won't see those
> pointers and will then GC the corresponding bignum.

That dangerous thing can't happen, as the change causes purecopy to signal an
error when given a bignum. That is, bignums fall into the same category as
markers, overlays and other objects where purecopy signals an error. Since these
objects are not used in the early phase of building that calls purecopy, this
should not be an issue.

Re: Bug#38708: eq vs eql in byte-compiled code

[Stefan Monnier]

>>> * src/alloc.c (make_pure_bignum): Remove, as we can’t copy (much
>>> less purecopy) bignums any more.
>> Sounds dangerous: it means that pure objects which point to bignums
>> could end up with dangling pointers because the GC won't see those
>> pointers and will then GC the corresponding bignum.
>
> That dangerous thing can't happen, as the change causes purecopy to signal an
> error when given a bignum. That is, bignums fall into the same category as
> markers, overlays and other objects where purecopy signals an error. Since these
> objects are not used in the early phase of building that calls purecopy, this
> should not be an issue.

Ah, sorry, I missed that.  It's OK then (and if/when we need to fix it,
then we'll want to do the move I mentioned).


        Stefan

Re: Bug#38708: eq vs eql in byte-compiled code

[Stefan Monnier]

> In other words, making bignums/flonums slower may seem to have no bad
> effects, until suddenly it has.

Agreed for flonums, but not for bignums: the bignum-replacements in
Emacs<27 were pretty inefficient, so I think we can use hash-consed
bignums without incurring a performance cost relative to Emacs-26.

IOW hash-cons'd bignums may be slower than "the best bignums we can
have", but they're still faster than the "the best bignums we used to
have".


        Stefan

Re: Bug#38708: eq vs eql in byte-compiled code

[Mattias Engdegård]

2 jan. 2020 kl. 09.38 skrev Paul Eggert <eggert@cs.ucla.edu>:

> <doc.diff>

That patch is a clear improvement to the manual. What about pushing it to emacs-27, since it pertains to the addition of bignums (and clarification of other eq-related issues)?

Re: Bug#38708: eq vs eql in byte-compiled code

[Paul Eggert]

On 1/22/20 2:56 AM, Mattias Engdegård wrote:
> That patch is a clear improvement to the manual. What about pushing it to emacs-27, since it pertains to the addition of bignums (and clarification of other eq-related issues)?

Sounds good, so I pushed it there.