[Emacs-diffs] master f378ed1: Avoid overexposing fixnums for hash codes

[Paul Eggert]

branch: master
commit f378ed1a0b1ca2ceed5afabcf5f303ae339039ba
Author: Paul Eggert <address@hidden>
Commit: Paul Eggert <address@hidden>

    Avoid overexposing fixnums for hash codes
    
    Following a suggestion by Stefan Monnier in:
    https://lists.gnu.org/r/emacs-devel/2019-07/msg00530.html
    * doc/lispref/hash.texi (Creating Hash, Defining Hash):
    * src/fns.c (Fsxhash_eq, Fsxhash_eql, Fsxhash_equal, Fmake_hash_table):
    Don’t insist that hash codes be fixnums, reverting
    the recent doc changes to the contrary.
    * src/bytecode.c (exec_byte_code): Special-case only the eq case,
    as the others aren’t worth tuning now that we treat bignum hashes
    like fixnums.
    * src/fns.c (hashfn_user_defined): If the hash code is a bignum,
    reduce its hash down to a fixnum.
---
 doc/lispref/hash.texi | 16 ++++++++--------
 src/bytecode.c        | 14 ++++----------
 src/fns.c             | 12 +++++++-----
 3 files changed, 19 insertions(+), 23 deletions(-)

diff --git a/doc/lispref/hash.texi b/doc/lispref/hash.texi
index 0515314..50d4c57 100644
--- a/doc/lispref/hash.texi
+++ b/doc/lispref/hash.texi
@@ -132,7 +132,7 @@ When you add an association to a hash table and the table 
is full,
 it grows automatically.  This value specifies how to make the hash table
 larger, at that time.
 
-If @var{rehash-size} is a fixnum, it should be positive and the hash
+If @var{rehash-size} is an integer, it should be positive, and the hash
 table grows by adding approximately that much to the nominal size.  If
 @var{rehash-size} is floating point, it had better be greater
 than 1, and the hash table grows by multiplying the old size by
@@ -239,8 +239,8 @@ to understand how hash tables work, and what a @dfn{hash 
code} means.
 
   You can think of a hash table conceptually as a large array of many
 slots, each capable of holding one association.  To look up a key,
-@code{gethash} first computes a fixnum, the hash code, from the key.
-It reduces this fixnum modulo the length of the array, to produce an
+@code{gethash} first computes an integer, the hash code, from the key.
+It can reduce this integer modulo the length of the array, to produce an
 index in the array.  Then it looks in that slot, and if necessary in
 other nearby slots, to see if it has found the key being sought.
 
@@ -265,7 +265,7 @@ The function @var{test-fn} should accept two arguments, two 
keys, and
 return non-@code{nil} if they are considered the same.
 
 The function @var{hash-fn} should accept one argument, a key, and return
-a fixnum that is the hash code of that key.  For good results, the
+an integer that is the hash code of that key.  For good results, the
 function should use the whole range of fixnums for hash codes,
 including negative fixnums.
 
@@ -276,12 +276,12 @@ under the property @code{hash-table-test}; the property 
value's form is
 
 @defun sxhash-equal obj
 This function returns a hash code for Lisp object @var{obj}.
-This is a fixnum that reflects the contents of @var{obj}
+This is an integer that reflects the contents of @var{obj}
 and the other Lisp objects it points to.
 
 If two objects @var{obj1} and @var{obj2} are @code{equal}, then
 @code{(sxhash-equal @var{obj1})} and @code{(sxhash-equal @var{obj2})}
-are the same fixnum.
+are the same integer.
 
 If the two objects are not @code{equal}, the values returned by
 @code{sxhash-equal} are usually different, but not always; once in a
@@ -299,7 +299,7 @@ result reflects identity of @var{obj}, but not its contents.
 
 If two objects @var{obj1} and @var{obj2} are @code{eq}, then
 @code{(sxhash-eq @var{obj1})} and @code{(sxhash-eq @var{obj2})} are
-the same fixnum.
+the same integer.
 @end defun
 
 @defun sxhash-eql obj
@@ -310,7 +310,7 @@ in which case a hash code is generated for the value.
 
 If two objects @var{obj1} and @var{obj2} are @code{eql}, then
 @code{(sxhash-eql @var{obj1})} and @code{(sxhash-eql @var{obj2})} are
-the same fixnum.
+the same integer.
 @end defun
 
   This example creates a hash table whose keys are strings that are
diff --git a/src/bytecode.c b/src/bytecode.c
index d668a9a..9aad1eb 100644
--- a/src/bytecode.c
+++ b/src/bytecode.c
@@ -1406,18 +1406,12 @@ exec_byte_code (Lisp_Object bytestr, Lisp_Object 
vector, Lisp_Object maxdepth,
 
             /* h->count is a faster approximation for HASH_TABLE_SIZE (h)
                here. */
-            if (h->count <= 5)
+            if (h->count <= 5 && !h->test.cmpfn)
               { /* Do a linear search if there are not many cases
                    FIXME: 5 is arbitrarily chosen.  */
-               Lisp_Object hash_code
-                 = h->test.cmpfn ? h->test.hashfn (v1, h) : Qnil;
-
-                for (i = h->count; 0 <= --i; )
-                  if (EQ (v1, HASH_KEY (h, i))
-                      || (h->test.cmpfn
-                          && EQ (hash_code, HASH_HASH (h, i))
-                         && !NILP (h->test.cmpfn (v1, HASH_KEY (h, i), h))))
-                    break;
+               for (i = h->count; 0 <= --i; )
+                 if (EQ (v1, HASH_KEY (h, i)))
+                   break;
               }
             else
               i = hash_lookup (h, v1, NULL);
diff --git a/src/fns.c b/src/fns.c
index 734a2e2..d28d437 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -47,6 +47,7 @@ static void sort_vector_copy (Lisp_Object, ptrdiff_t,
 enum equal_kind { EQUAL_NO_QUIT, EQUAL_PLAIN, EQUAL_INCLUDING_PROPERTIES };
 static bool internal_equal (Lisp_Object, Lisp_Object,
                            enum equal_kind, int, Lisp_Object);
+static EMACS_UINT sxhash_bignum (struct Lisp_Bignum *);
 
 DEFUN ("identity", Fidentity, Sidentity, 1, 1, 0,
        doc: /* Return the argument unchanged.  */
@@ -4021,7 +4022,8 @@ Lisp_Object
 hashfn_user_defined (Lisp_Object key, struct Lisp_Hash_Table *h)
 {
   Lisp_Object args[] = { h->test.user_hash_function, key };
-  return hash_table_user_defined_call (ARRAYELTS (args), args, h);
+  Lisp_Object hash = hash_table_user_defined_call (ARRAYELTS (args), args, h);
+  return BIGNUMP (hash) ? make_fixnum (sxhash_bignum (XBIGNUM (hash))) : hash;
 }
 
 struct hash_table_test const
@@ -4707,7 +4709,7 @@ sxhash (Lisp_Object obj, int depth)
  ***********************************************************************/
 
 DEFUN ("sxhash-eq", Fsxhash_eq, Ssxhash_eq, 1, 1, 0,
-       doc: /* Return a fixnum hash code for OBJ suitable for `eq'.
+       doc: /* Return an integer hash code for OBJ suitable for `eq'.
 If (eq A B), then (= (sxhash-eq A) (sxhash-eq B)).
 
 Hash codes are not guaranteed to be preserved across Emacs sessions.  */)
@@ -4717,7 +4719,7 @@ Hash codes are not guaranteed to be preserved across 
Emacs sessions.  */)
 }
 
 DEFUN ("sxhash-eql", Fsxhash_eql, Ssxhash_eql, 1, 1, 0,
-       doc: /* Return a fixnum hash code for OBJ suitable for `eql'.
+       doc: /* Return an integer hash code for OBJ suitable for `eql'.
 If (eql A B), then (= (sxhash-eql A) (sxhash-eql B)).
 
 Hash codes are not guaranteed to be preserved across Emacs sessions.  */)
@@ -4727,7 +4729,7 @@ Hash codes are not guaranteed to be preserved across 
Emacs sessions.  */)
 }
 
 DEFUN ("sxhash-equal", Fsxhash_equal, Ssxhash_equal, 1, 1, 0,
-       doc: /* Return a fixnum hash code for OBJ suitable for `equal'.
+       doc: /* Return an integer hash code for OBJ suitable for `equal'.
 If (equal A B), then (= (sxhash-equal A) (sxhash-equal B)).
 
 Hash codes are not guaranteed to be preserved across Emacs sessions.  */)
@@ -4751,7 +4753,7 @@ keys.  Default is `eql'.  Predefined are the tests `eq', 
`eql', and
 Default is 65.
 
 :rehash-size REHASH-SIZE - Indicates how to expand the table when it
-fills up.  If REHASH-SIZE is a fixnum, increase the size by that
+fills up.  If REHASH-SIZE is an integer, increase the size by that
 amount.  If it is a float, it must be > 1.0, and the new size is the
 old size multiplied by that factor.  Default is 1.5.