[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
scratch/hash-table-perf 05297736aa6 33/37: Adapt hash functions to produ
From: |
Mattias Engdegård |
Subject: |
scratch/hash-table-perf 05297736aa6 33/37: Adapt hash functions to produce a hash_hash_t eventually |
Date: |
Sun, 7 Jan 2024 12:41:23 -0500 (EST) |
branch: scratch/hash-table-perf
commit 05297736aa69828eacaafbf1d37457a93ade2311
Author: Mattias Engdegård <mattiase@acm.org>
Commit: Mattias Engdegård <mattiase@acm.org>
Adapt hash functions to produce a hash_hash_t eventually
This eliminates some useless and information-destroying intermediate
hash reduction steps.
We still use EMACS_UINT for most of the actual hashing steps before
producing the final value; this may be slightly wasteful on 32-bit
platforms with 64-bit EMACS_UINT.
* src/fns.c (reduce_emacs_uint_to_hash_hash): New.
(hashfn_eq, hashfn_equal, hashfn_user_defined): Reduce return values
to hash_hash_t.
(sxhash_string): Remove. Caller changed to hash_string.
(sxhash_float, sxhash_list, sxhash_vector, sxhash_bool_vector)
(sxhash_bignum): Remove wasteful calls to SXHASH_REDUCE.
(hash_hash_to_fixnum): New.
(Fsxhash_eq, Fsxhash_eql, Fsxhash_equal)
(Fsxhash_equal_including_properties): Convert return values to fixnum.
---
src/fns.c | 77 ++++++++++++++++++++++++++++++++++-----------------------------
1 file changed, 42 insertions(+), 35 deletions(-)
diff --git a/src/fns.c b/src/fns.c
index d19b704839c..6253e1d64f5 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -4452,6 +4452,16 @@ cmpfn_user_defined (Lisp_Object key1, Lisp_Object key2,
return hash_table_user_defined_call (ARRAYELTS (args), args, h);
}
+/* Reduce an EMACS_UINT hash value to hash_hash_t. */
+static inline hash_hash_t
+reduce_emacs_uint_to_hash_hash (EMACS_UINT x)
+{
+ verify (sizeof x <= 2 * sizeof (hash_hash_t));
+ return (sizeof x == sizeof (hash_hash_t)
+ ? x
+ : x ^ (x >> (8 * (sizeof x - sizeof (hash_hash_t)))));
+}
+
/* Ignore H and return a hash code for KEY which uses 'eq' to compare keys. */
static hash_hash_t
@@ -4459,21 +4469,18 @@ hashfn_eq (Lisp_Object key, struct Lisp_Hash_Table *h)
{
if (symbols_with_pos_enabled && SYMBOL_WITH_POS_P (key))
key = SYMBOL_WITH_POS_SYM (key);
- return XHASH (key) ^ XTYPE (key);
+ return reduce_emacs_uint_to_hash_hash (XHASH (key) ^ XTYPE (key));
}
-/* Ignore H and return a hash code for KEY which uses 'equal' to compare keys.
- The hash code is at most INTMASK. */
-
+/* Ignore H and return a hash code for KEY which uses 'equal' to
+ compare keys. */
static hash_hash_t
hashfn_equal (Lisp_Object key, struct Lisp_Hash_Table *h)
{
- return sxhash (key);
+ return reduce_emacs_uint_to_hash_hash (sxhash (key));
}
-/* Ignore H and return a hash code for KEY which uses 'eql' to compare keys.
- The hash code is at most INTMASK. */
-
+/* Ignore H and return a hash code for KEY which uses 'eql' to compare keys.
*/
static hash_hash_t
hashfn_eql (Lisp_Object key, struct Lisp_Hash_Table *h)
{
@@ -4489,7 +4496,8 @@ hashfn_user_defined (Lisp_Object key, struct
Lisp_Hash_Table *h)
{
Lisp_Object args[] = { h->test->user_hash_function, key };
Lisp_Object hash = hash_table_user_defined_call (ARRAYELTS (args), args, h);
- return FIXNUMP (hash) ? XUFIXNUM(hash) : sxhash (hash);
+ return reduce_emacs_uint_to_hash_hash (FIXNUMP (hash)
+ ? XUFIXNUM(hash) : sxhash (hash));
}
struct hash_table_test const
@@ -5042,16 +5050,6 @@ hash_string (char const *ptr, ptrdiff_t len)
return hash;
}
-/* Return a hash for string PTR which has length LEN. The hash
- code returned is at most INTMASK. */
-
-static EMACS_UINT
-sxhash_string (char const *ptr, ptrdiff_t len)
-{
- EMACS_UINT hash = hash_string (ptr, len);
- return SXHASH_REDUCE (hash);
-}
-
/* Return a hash for the floating point value VAL. */
static EMACS_UINT
@@ -5061,7 +5059,7 @@ sxhash_float (double val)
union double_and_words u = { .val = val };
for (int i = 0; i < WORDS_PER_DOUBLE; i++)
hash = sxhash_combine (hash, u.word[i]);
- return SXHASH_REDUCE (hash);
+ return hash;
}
/* Return a hash for list LIST. DEPTH is the current depth in the
@@ -5088,7 +5086,7 @@ sxhash_list (Lisp_Object list, int depth)
hash = sxhash_combine (hash, hash2);
}
- return SXHASH_REDUCE (hash);
+ return hash;
}
@@ -5108,7 +5106,7 @@ sxhash_vector (Lisp_Object vec, int depth)
hash = sxhash_combine (hash, hash2);
}
- return SXHASH_REDUCE (hash);
+ return hash;
}
/* Return a hash for bool-vector VECTOR. */
@@ -5124,7 +5122,7 @@ sxhash_bool_vector (Lisp_Object vec)
for (i = 0; i < n; ++i)
hash = sxhash_combine (hash, bool_vector_data (vec)[i]);
- return SXHASH_REDUCE (hash);
+ return hash;
}
/* Return a hash for a bignum. */
@@ -5139,19 +5137,18 @@ sxhash_bignum (Lisp_Object bignum)
for (i = 0; i < nlimbs; ++i)
hash = sxhash_combine (hash, mpz_getlimbn (*n, i));
- return SXHASH_REDUCE (hash);
+ return hash;
}
-
-/* Return a hash code for OBJ. DEPTH is the current depth in the Lisp
- structure. Value is an unsigned integer clipped to INTMASK. */
-
EMACS_UINT
sxhash (Lisp_Object obj)
{
return sxhash_obj (obj, 0);
}
+/* Return a hash code for OBJ. DEPTH is the current depth in the Lisp
+ structure. */
+
static EMACS_UINT
sxhash_obj (Lisp_Object obj, int depth)
{
@@ -5167,7 +5164,7 @@ sxhash_obj (Lisp_Object obj, int depth)
return XHASH (obj);
case Lisp_String:
- return sxhash_string (SSDATA (obj), SBYTES (obj));
+ return hash_string (SSDATA (obj), SBYTES (obj));
case Lisp_Vectorlike:
{
@@ -5194,7 +5191,7 @@ sxhash_obj (Lisp_Object obj, int depth)
= XMARKER (obj)->buffer ? XMARKER (obj)->bytepos : 0;
EMACS_UINT hash
= sxhash_combine ((intptr_t) XMARKER (obj)->buffer, bytepos);
- return SXHASH_REDUCE (hash);
+ return hash;
}
else if (pvec_type == PVEC_BOOL_VECTOR)
return sxhash_bool_vector (obj);
@@ -5203,7 +5200,7 @@ sxhash_obj (Lisp_Object obj, int depth)
EMACS_UINT hash = OVERLAY_START (obj);
hash = sxhash_combine (hash, OVERLAY_END (obj));
hash = sxhash_combine (hash, sxhash_obj (XOVERLAY (obj)->plist,
depth));
- return SXHASH_REDUCE (hash);
+ return hash;
}
else if (symbols_with_pos_enabled && pvec_type == PVEC_SYMBOL_WITH_POS)
return sxhash_obj (XSYMBOL_WITH_POS (obj)->sym, depth + 1);
@@ -5239,6 +5236,15 @@ collect_interval (INTERVAL interval, Lisp_Object
collector)
Lisp Interface
***********************************************************************/
+/* Reduce X to a Lisp fixnum. */
+static inline Lisp_Object
+hash_hash_to_fixnum (hash_hash_t x)
+{
+ return make_ufixnum (FIXNUM_BITS < 8 * sizeof x
+ ? (x ^ x >> (8 * sizeof x - FIXNUM_BITS)) & INTMASK
+ : x);
+}
+
DEFUN ("sxhash-eq", Fsxhash_eq, Ssxhash_eq, 1, 1, 0,
doc: /* Return an integer hash code for OBJ suitable for `eq'.
If (eq A B), then (= (sxhash-eq A) (sxhash-eq B)).
@@ -5246,7 +5252,7 @@ If (eq A B), then (= (sxhash-eq A) (sxhash-eq B)).
Hash codes are not guaranteed to be preserved across Emacs sessions. */)
(Lisp_Object obj)
{
- return make_ufixnum (hashfn_eq (obj, NULL));
+ return hash_hash_to_fixnum (hashfn_eq (obj, NULL));
}
DEFUN ("sxhash-eql", Fsxhash_eql, Ssxhash_eql, 1, 1, 0,
@@ -5257,7 +5263,7 @@ isn't necessarily true.
Hash codes are not guaranteed to be preserved across Emacs sessions. */)
(Lisp_Object obj)
{
- return make_ufixnum (hashfn_eql (obj, NULL));
+ return hash_hash_to_fixnum (hashfn_eql (obj, NULL));
}
DEFUN ("sxhash-equal", Fsxhash_equal, Ssxhash_equal, 1, 1, 0,
@@ -5268,7 +5274,7 @@ opposite isn't necessarily true.
Hash codes are not guaranteed to be preserved across Emacs sessions. */)
(Lisp_Object obj)
{
- return make_ufixnum (hashfn_equal (obj, NULL));
+ return hash_hash_to_fixnum (hashfn_equal (obj, NULL));
}
DEFUN ("sxhash-equal-including-properties", Fsxhash_equal_including_properties,
@@ -5283,6 +5289,7 @@ Hash codes are not guaranteed to be preserved across
Emacs sessions. */)
{
if (STRINGP (obj))
{
+ /* FIXME: This is very wasteful. We needn't cons at all. */
Lisp_Object collector = Fcons (Qnil, Qnil);
traverse_intervals (string_intervals (obj), 0, collect_interval,
collector);
@@ -5292,7 +5299,7 @@ Hash codes are not guaranteed to be preserved across
Emacs sessions. */)
sxhash (CDR (collector)))));
}
- return make_ufixnum (hashfn_equal (obj, NULL));
+ return hash_hash_to_fixnum (hashfn_equal (obj, NULL));
}
- scratch/hash-table-perf 1ebd00f6d0a 21/37: Retype hash interfaces to use EMACS_UINT instead of Lisp fixnum, (continued)
- scratch/hash-table-perf 1ebd00f6d0a 21/37: Retype hash interfaces to use EMACS_UINT instead of Lisp fixnum, Mattias Engdegård, 2024/01/07
- scratch/hash-table-perf 8335891387a 22/37: Inlined and specialised hash table look-up, Mattias Engdegård, 2024/01/07
- scratch/hash-table-perf ad3d2f8ed88 25/37: Share hash table test structs, Mattias Engdegård, 2024/01/07
- scratch/hash-table-perf e53398ab698 26/37: ; Reorder structs (hash and test), Mattias Engdegård, 2024/01/07
- scratch/hash-table-perf 1672d880e0c 29/37: Change hash_idx_t to int32_t on all platforms, Mattias Engdegård, 2024/01/07
- scratch/hash-table-perf e6defe82569 27/37: Change default hash table size to 8 (from 65), Mattias Engdegård, 2024/01/07
- scratch/hash-table-perf 41e37c978e6 28/37: Rework index size and resize factor computations, Mattias Engdegård, 2024/01/07
- scratch/hash-table-perf 5cf627d70e1 30/37: Don't dump Qunbound, Mattias Engdegård, 2024/01/07
- scratch/hash-table-perf 8b1b140bed9 32/37: * src/lisp.h (hash_hash_t): Change to uint32_t., Mattias Engdegård, 2024/01/07
- scratch/hash-table-perf 830838eb5f3 31/37: Use KEY=Qunbound instead of HASH=hash_unused for unused entries, Mattias Engdegård, 2024/01/07
- scratch/hash-table-perf 05297736aa6 33/37: Adapt hash functions to produce a hash_hash_t eventually,
Mattias Engdegård <=
- scratch/hash-table-perf 8cd35079f4c 34/37: Don't pretend that hash-table-size is useful, Mattias Engdegård, 2024/01/07
- scratch/hash-table-perf e366ae38cd5 36/37: Improved hash-table allocation accounting, Mattias Engdegård, 2024/01/07
- scratch/hash-table-perf b9c9539db96 37/37: Change hash range reduction from remainder to multiplication, Mattias Engdegård, 2024/01/07
- scratch/hash-table-perf 681a2877cc2 35/37: Hash-table documentation updates, Mattias Engdegård, 2024/01/07