[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
master 3b00255a4c7 10/20: Inlined and specialised hash table look-up
From: |
Mattias Engdegård |
Subject: |
master 3b00255a4c7 10/20: Inlined and specialised hash table look-up |
Date: |
Sat, 13 Jan 2024 14:54:01 -0500 (EST) |
branch: master
commit 3b00255a4c70bc1075446c94a8ff65c987ac143f
Author: Mattias Engdegård <mattiase@acm.org>
Commit: Mattias Engdegård <mattiase@acm.org>
Inlined and specialised hash table look-up
This improves performance in several ways. Separate functions are
used depending on whether the caller has a hash value computed or not.
* src/fns.c (hash_lookup_with_hash, hash_lookup_get_hash): New.
(hash_lookup): Remove hash return argument.
All callers adapted.
hash_lookup_with_hash hash_hash_t arg
---
src/bytecode.c | 2 +-
src/category.c | 2 +-
src/ccl.c | 4 ++--
src/charset.c | 4 ++--
src/charset.h | 2 +-
src/coding.h | 2 +-
src/composite.c | 4 ++--
src/emacs-module.c | 4 ++--
src/fns.c | 59 +++++++++++++++++++++++++++++++++++-------------------
src/image.c | 4 ++--
src/json.c | 2 +-
src/lisp.h | 4 +++-
src/lread.c | 13 ++++++------
src/macfont.m | 4 ++--
src/minibuf.c | 2 +-
15 files changed, 66 insertions(+), 46 deletions(-)
diff --git a/src/bytecode.c b/src/bytecode.c
index e989e5fadf0..a0f02d518b7 100644
--- a/src/bytecode.c
+++ b/src/bytecode.c
@@ -1751,7 +1751,7 @@ exec_byte_code (Lisp_Object fun, ptrdiff_t args_template,
break;
}
else
- i = hash_lookup (h, v1, NULL);
+ i = hash_lookup (h, v1);
if (i >= 0)
{
diff --git a/src/category.c b/src/category.c
index e7fbf1ff500..3a406a567a1 100644
--- a/src/category.c
+++ b/src/category.c
@@ -54,7 +54,7 @@ hash_get_category_set (Lisp_Object table, Lisp_Object
category_set)
make_hash_table (hashtest_equal, DEFAULT_HASH_SIZE, Weak_None, false));
struct Lisp_Hash_Table *h = XHASH_TABLE (XCHAR_TABLE (table)->extras[1]);
hash_hash_t hash;
- ptrdiff_t i = hash_lookup (h, category_set, &hash);
+ ptrdiff_t i = hash_lookup_get_hash (h, category_set, &hash);
if (i >= 0)
return HASH_KEY (h, i);
hash_put (h, category_set, Qnil, hash);
diff --git a/src/ccl.c b/src/ccl.c
index b4dda404b95..7df50ba7022 100644
--- a/src/ccl.c
+++ b/src/ccl.c
@@ -1380,7 +1380,7 @@ ccl_driver (struct ccl_program *ccl, int *source, int
*destination, int src_size
eop = (FIXNUM_OVERFLOW_P (reg[RRR])
? -1
- : hash_lookup (h, make_fixnum (reg[RRR]), NULL));
+ : hash_lookup (h, make_fixnum (reg[RRR])));
if (eop >= 0)
{
Lisp_Object opl;
@@ -1409,7 +1409,7 @@ ccl_driver (struct ccl_program *ccl, int *source, int
*destination, int src_size
eop = (FIXNUM_OVERFLOW_P (i)
? -1
- : hash_lookup (h, make_fixnum (i), NULL));
+ : hash_lookup (h, make_fixnum (i)));
if (eop >= 0)
{
Lisp_Object opl;
diff --git a/src/charset.c b/src/charset.c
index add3bf846f8..6a74f294ad8 100644
--- a/src/charset.c
+++ b/src/charset.c
@@ -1108,8 +1108,8 @@ usage: (define-charset-internal ...) */)
ASET (attrs, charset_plist, args[charset_arg_plist]);
hash_hash_t hash_code;
- charset.hash_index = hash_lookup (hash_table, args[charset_arg_name],
- &hash_code);
+ charset.hash_index = hash_lookup_get_hash (hash_table,
args[charset_arg_name],
+ &hash_code);
if (charset.hash_index >= 0)
{
new_definition_p = 0;
diff --git a/src/charset.h b/src/charset.h
index 1743eb4c909..91454d3d73e 100644
--- a/src/charset.h
+++ b/src/charset.h
@@ -286,7 +286,7 @@ extern int emacs_mule_charset[256];
/* Return an index to Vcharset_hash_table of the charset whose symbol
is SYMBOL. */
#define CHARSET_SYMBOL_HASH_INDEX(symbol) \
- hash_lookup (XHASH_TABLE (Vcharset_hash_table), symbol, NULL)
+ hash_lookup (XHASH_TABLE (Vcharset_hash_table), symbol)
/* Return the attribute vector of CHARSET. */
#define CHARSET_ATTRIBUTES(charset) \
diff --git a/src/coding.h b/src/coding.h
index e9b72403c6b..9beb4350bbf 100644
--- a/src/coding.h
+++ b/src/coding.h
@@ -194,7 +194,7 @@ enum coding_attr_index
#define CODING_SYSTEM_ID(coding_system_symbol) \
hash_lookup (XHASH_TABLE (Vcoding_system_hash_table), \
- coding_system_symbol, NULL)
+ coding_system_symbol)
/* Return true if CODING_SYSTEM_SYMBOL is a coding system. */
diff --git a/src/composite.c b/src/composite.c
index bd69a953e3f..78c884dd72d 100644
--- a/src/composite.c
+++ b/src/composite.c
@@ -241,7 +241,7 @@ get_composition_id (ptrdiff_t charpos, ptrdiff_t bytepos,
ptrdiff_t nchars,
goto invalid_composition;
hash_hash_t hash_code;
- hash_index = hash_lookup (hash_table, key, &hash_code);
+ hash_index = hash_lookup_get_hash (hash_table, key, &hash_code);
if (hash_index >= 0)
{
/* We have already registered the same composition. Change PROP
@@ -644,7 +644,7 @@ Lisp_Object
composition_gstring_lookup_cache (Lisp_Object header)
{
struct Lisp_Hash_Table *h = XHASH_TABLE (gstring_hash_table);
- ptrdiff_t i = hash_lookup (h, header, NULL);
+ ptrdiff_t i = hash_lookup (h, header);
return (i >= 0 ? HASH_VALUE (h, i) : Qnil);
}
diff --git a/src/emacs-module.c b/src/emacs-module.c
index 728da8c2882..e78391b3a71 100644
--- a/src/emacs-module.c
+++ b/src/emacs-module.c
@@ -429,7 +429,7 @@ module_make_global_ref (emacs_env *env, emacs_value value)
struct Lisp_Hash_Table *h = XHASH_TABLE (Vmodule_refs_hash);
Lisp_Object new_obj = value_to_lisp (value);
hash_hash_t hashcode;
- ptrdiff_t i = hash_lookup (h, new_obj, &hashcode);
+ ptrdiff_t i = hash_lookup_get_hash (h, new_obj, &hashcode);
/* Note: This approach requires the garbage collector to never move
objects. */
@@ -468,7 +468,7 @@ module_free_global_ref (emacs_env *env, emacs_value
global_value)
MODULE_FUNCTION_BEGIN ();
struct Lisp_Hash_Table *h = XHASH_TABLE (Vmodule_refs_hash);
Lisp_Object obj = value_to_lisp (global_value);
- ptrdiff_t i = hash_lookup (h, obj, NULL);
+ ptrdiff_t i = hash_lookup (h, obj);
if (module_assertions)
{
diff --git a/src/fns.c b/src/fns.c
index 5a3c51c8412..9d802bba0e2 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -2731,6 +2731,10 @@ equal_no_quit (Lisp_Object o1, Lisp_Object o2)
return internal_equal (o1, o2, EQUAL_NO_QUIT, 0, Qnil);
}
+static ptrdiff_t hash_lookup_with_hash (struct Lisp_Hash_Table *h,
+ Lisp_Object key, hash_hash_t hash);
+
+
/* Return true if O1 and O2 are equal. EQUAL_KIND specifies what kind
of equality test to use: if it is EQUAL_NO_QUIT, do not check for
cycles or large arguments or quits; if EQUAL_PLAIN, do ordinary
@@ -2759,8 +2763,8 @@ internal_equal (Lisp_Object o1, Lisp_Object o2, enum
equal_kind equal_kind,
case Lisp_Cons: case Lisp_Vectorlike:
{
struct Lisp_Hash_Table *h = XHASH_TABLE (ht);
- hash_hash_t hash;
- ptrdiff_t i = hash_lookup (h, o1, &hash);
+ hash_hash_t hash = hash_from_key (h, o1);
+ ptrdiff_t i = hash_lookup_with_hash (h, o1, hash);
if (i >= 0)
{ /* `o1' was seen already. */
Lisp_Object o2s = HASH_VALUE (h, i);
@@ -4791,27 +4795,40 @@ hash_table_thaw (Lisp_Object hash_table)
}
}
-/* Lookup KEY in hash table H. If HASH is non-null, return in *HASH
- the hash code of KEY. Value is the index of the entry in H
- matching KEY, or -1 if not found. */
-
-ptrdiff_t
-hash_lookup (struct Lisp_Hash_Table *h, Lisp_Object key, hash_hash_t *hash)
+/* Look up KEY with hash HASH in table H.
+ Return entry index or -1 if none. */
+static ptrdiff_t
+hash_lookup_with_hash (struct Lisp_Hash_Table *h,
+ Lisp_Object key, hash_hash_t hash)
{
- hash_hash_t hash_code = hash_from_key (h, key);
- if (hash)
- *hash = hash_code;
-
- ptrdiff_t start_of_bucket = hash_index_index (h, hash_code);
- ptrdiff_t i;
- for (i = HASH_INDEX (h, start_of_bucket); 0 <= i; i = HASH_NEXT (h, i))
+ ptrdiff_t start_of_bucket = hash_index_index (h, hash);
+ for (ptrdiff_t i = HASH_INDEX (h, start_of_bucket);
+ 0 <= i; i = HASH_NEXT (h, i))
if (EQ (key, HASH_KEY (h, i))
|| (h->test.cmpfn
- && hash_code == HASH_HASH (h, i)
+ && hash == HASH_HASH (h, i)
&& !NILP (h->test.cmpfn (key, HASH_KEY (h, i), h))))
- break;
+ return i;
- return i;
+ return -1;
+}
+
+/* Look up KEY in table H. Return entry index or -1 if none. */
+ptrdiff_t
+hash_lookup (struct Lisp_Hash_Table *h, Lisp_Object key)
+{
+ return hash_lookup_with_hash (h, key, hash_from_key (h, key));
+}
+
+/* Look up KEY in hash table H. Return its hash value in *PHASH.
+ Value is the index of the entry in H matching KEY, or -1 if not found. */
+ptrdiff_t
+hash_lookup_get_hash (struct Lisp_Hash_Table *h, Lisp_Object key,
+ hash_hash_t *phash)
+{
+ EMACS_UINT hash = hash_from_key (h, key);
+ *phash = hash;
+ return hash_lookup_with_hash (h, key, hash);
}
static void
@@ -5539,7 +5556,7 @@ If KEY is not found, return DFLT which defaults to nil.
*/)
(Lisp_Object key, Lisp_Object table, Lisp_Object dflt)
{
struct Lisp_Hash_Table *h = check_hash_table (table);
- ptrdiff_t i = hash_lookup (h, key, NULL);
+ ptrdiff_t i = hash_lookup_with_hash (h, key, hash_from_key (h, key));
return i >= 0 ? HASH_VALUE (h, i) : dflt;
}
@@ -5553,8 +5570,8 @@ VALUE. In any case, return VALUE. */)
struct Lisp_Hash_Table *h = check_hash_table (table);
check_mutable_hash_table (table, h);
- EMACS_UINT hash;
- ptrdiff_t i = hash_lookup (h, key, &hash);
+ EMACS_UINT hash = hash_from_key (h, key);
+ ptrdiff_t i = hash_lookup_with_hash (h, key, hash);
if (i >= 0)
set_hash_value_slot (h, i, value);
else
diff --git a/src/image.c b/src/image.c
index 55b027d568b..74d4b6c0bfe 100644
--- a/src/image.c
+++ b/src/image.c
@@ -6082,7 +6082,7 @@ xpm_put_color_table_h (Lisp_Object color_table,
Lisp_Object chars = make_unibyte_string (chars_start, chars_len);
hash_hash_t hash_code;
- hash_lookup (table, chars, &hash_code);
+ hash_lookup_get_hash (table, chars, &hash_code);
hash_put (table, chars, color, hash_code);
}
@@ -6093,7 +6093,7 @@ xpm_get_color_table_h (Lisp_Object color_table,
{
struct Lisp_Hash_Table *table = XHASH_TABLE (color_table);
ptrdiff_t i =
- hash_lookup (table, make_unibyte_string (chars_start, chars_len), NULL);
+ hash_lookup (table, make_unibyte_string (chars_start, chars_len));
return i >= 0 ? HASH_VALUE (table, i) : Qnil;
}
diff --git a/src/json.c b/src/json.c
index 1bea4baa8ba..266905f1c34 100644
--- a/src/json.c
+++ b/src/json.c
@@ -881,7 +881,7 @@ json_to_lisp (json_t *json, const struct json_configuration
*conf)
{
Lisp_Object key = build_string_from_utf8 (key_str);
hash_hash_t hash;
- ptrdiff_t i = hash_lookup (h, key, &hash);
+ ptrdiff_t i = hash_lookup_get_hash (h, key, &hash);
/* Keys in JSON objects are unique, so the key can't
be present yet. */
eassert (i < 0);
diff --git a/src/lisp.h b/src/lisp.h
index 474498094c9..02d9c98da22 100644
--- a/src/lisp.h
+++ b/src/lisp.h
@@ -4063,7 +4063,9 @@ EMACS_UINT sxhash (Lisp_Object);
Lisp_Object make_hash_table (struct hash_table_test, EMACS_INT,
hash_table_weakness_t, bool);
Lisp_Object hash_table_weakness_symbol (hash_table_weakness_t weak);
-ptrdiff_t hash_lookup (struct Lisp_Hash_Table *, Lisp_Object, hash_hash_t *);
+ptrdiff_t hash_lookup (struct Lisp_Hash_Table *, Lisp_Object);
+ptrdiff_t hash_lookup_get_hash (struct Lisp_Hash_Table *h, Lisp_Object key,
+ hash_hash_t *phash);
ptrdiff_t hash_put (struct Lisp_Hash_Table *, Lisp_Object, Lisp_Object,
hash_hash_t);
void hash_remove_from_table (struct Lisp_Hash_Table *, Lisp_Object);
diff --git a/src/lread.c b/src/lread.c
index 9ad4d35c0c2..b76fde3f266 100644
--- a/src/lread.c
+++ b/src/lread.c
@@ -4256,7 +4256,7 @@ read0 (Lisp_Object readcharfun, bool locate_syms)
= XHASH_TABLE (read_objects_map);
Lisp_Object number = make_fixnum (n);
hash_hash_t hash;
- ptrdiff_t i = hash_lookup (h, number, &hash);
+ ptrdiff_t i = hash_lookup_get_hash (h, number, &hash);
if (i >= 0)
/* Not normal, but input could be malformed. */
set_hash_value_slot (h, i, placeholder);
@@ -4274,7 +4274,7 @@ read0 (Lisp_Object readcharfun, bool locate_syms)
/* #N# -- reference to numbered object */
struct Lisp_Hash_Table *h
= XHASH_TABLE (read_objects_map);
- ptrdiff_t i = hash_lookup (h, make_fixnum (n), NULL);
+ ptrdiff_t i = hash_lookup (h, make_fixnum (n));
if (i < 0)
invalid_syntax ("#", readcharfun);
obj = HASH_VALUE (h, i);
@@ -4572,7 +4572,7 @@ read0 (Lisp_Object readcharfun, bool locate_syms)
struct Lisp_Hash_Table *h2
= XHASH_TABLE (read_objects_completed);
hash_hash_t hash;
- ptrdiff_t i = hash_lookup (h2, placeholder, &hash);
+ ptrdiff_t i = hash_lookup_get_hash (h2, placeholder, &hash);
eassert (i < 0);
hash_put (h2, placeholder, Qnil, hash);
obj = placeholder;
@@ -4587,7 +4587,7 @@ read0 (Lisp_Object readcharfun, bool locate_syms)
struct Lisp_Hash_Table *h2
= XHASH_TABLE (read_objects_completed);
hash_hash_t hash;
- ptrdiff_t i = hash_lookup (h2, obj, &hash);
+ ptrdiff_t i = hash_lookup_get_hash (h2, obj, &hash);
eassert (i < 0);
hash_put (h2, obj, Qnil, hash);
}
@@ -4599,7 +4599,8 @@ read0 (Lisp_Object readcharfun, bool locate_syms)
/* ...and #n# will use the real value from now on. */
struct Lisp_Hash_Table *h = XHASH_TABLE (read_objects_map);
hash_hash_t hash;
- ptrdiff_t i = hash_lookup (h, e->u.numbered.number, &hash);
+ ptrdiff_t i = hash_lookup_get_hash (h, e->u.numbered.number,
+ &hash);
eassert (i >= 0);
set_hash_value_slot (h, i, obj);
}
@@ -4653,7 +4654,7 @@ substitute_object_recurse (struct subst *subst,
Lisp_Object subtree)
by #n=, which means that we can find it as a value in
COMPLETED. */
if (EQ (subst->completed, Qt)
- || hash_lookup (XHASH_TABLE (subst->completed), subtree, NULL) >= 0)
+ || hash_lookup (XHASH_TABLE (subst->completed), subtree) >= 0)
subst->seen = Fcons (subtree, subst->seen);
/* Recurse according to subtree's type.
diff --git a/src/macfont.m b/src/macfont.m
index dcaa85bea05..48502c2ec00 100644
--- a/src/macfont.m
+++ b/src/macfont.m
@@ -997,7 +997,7 @@ macfont_get_family_cache_if_present (Lisp_Object symbol,
CFStringRef *string)
if (HASH_TABLE_P (macfont_family_cache))
{
struct Lisp_Hash_Table *h = XHASH_TABLE (macfont_family_cache);
- ptrdiff_t i = hash_lookup (h, symbol, NULL);
+ ptrdiff_t i = hash_lookup (h, symbol);
if (i >= 0)
{
@@ -1024,7 +1024,7 @@ macfont_set_family_cache (Lisp_Object symbol, CFStringRef
string)
h = XHASH_TABLE (macfont_family_cache);
hash_hash_t hash;
- i = hash_lookup (h, symbol, &hash);
+ i = hash_lookup_get_hash (h, symbol, &hash);
value = string ? make_mint_ptr ((void *) CFRetain (string)) : Qnil;
if (i >= 0)
{
diff --git a/src/minibuf.c b/src/minibuf.c
index 22bb8fa1d75..8198dc0f360 100644
--- a/src/minibuf.c
+++ b/src/minibuf.c
@@ -2107,7 +2107,7 @@ the values STRING, PREDICATE and `lambda'. */)
else if (HASH_TABLE_P (collection))
{
struct Lisp_Hash_Table *h = XHASH_TABLE (collection);
- i = hash_lookup (h, string, NULL);
+ i = hash_lookup (h, string);
if (i >= 0)
{
tem = HASH_KEY (h, i);
- master c3d0cc50faf 05/20: Remove rehash-threshold and rehash-size struct members, (continued)
- master c3d0cc50faf 05/20: Remove rehash-threshold and rehash-size struct members, Mattias Engdegård, 2024/01/13
- master a3ae5653cfe 09/20: Store hash values as integers instead of Lisp_Object, Mattias Engdegård, 2024/01/13
- master ed06de52a53 14/20: Faster hash table growth, starting at zero size, Mattias Engdegård, 2024/01/13
- master fa5c07fc87d 08/20: Use non-Lisp allocation for internal hash-table vectors, Mattias Engdegård, 2024/01/13
- master 7ad5d427730 16/20: Don't dump Qunbound, Mattias Engdegård, 2024/01/13
- master d2c3a983146 20/20: Hash-table documentation updates (bug#68244), Mattias Engdegård, 2024/01/13
- master a09619f2598 02/20: * src/print.c (print_object): Don't print empty hash-table data, Mattias Engdegård, 2024/01/13
- master 3f9c81a87f7 03/20: Don't print or read the hash table size parameter, Mattias Engdegård, 2024/01/13
- master d3cefd3e983 06/20: Leaner hash table dumping and thawing, Mattias Engdegård, 2024/01/13
- master 519c7ca7356 19/20: Don't pretend that hash-table-size is useful, Mattias Engdegård, 2024/01/13
- master 3b00255a4c7 10/20: Inlined and specialised hash table look-up,
Mattias Engdegård <=
- master 1998039f7a8 18/20: Change hash_hash_t to uint32_t, Mattias Engdegård, 2024/01/13
- master 7d93a0147a1 12/20: Share hash table test structs, Mattias Engdegård, 2024/01/13
- master 47502c55b0c 13/20: ; Reorder struct Lisp_Hash_Table and struct hash_table_test, Mattias Engdegård, 2024/01/13
- master c6bdc1ea1dc 04/20: Represent hash table weakness as an enum internally, Mattias Engdegård, 2024/01/13
- master 68f8bc31114 15/20: Change hash_idx_t to int32_t on all platforms, Mattias Engdegård, 2024/01/13
- master 0a998938ca1 11/20: Use hash_idx_t for storing hash indices, Mattias Engdegård, 2024/01/13
- master 11e467eb600 17/20: Use key Qunbound instead of hash value hash_unused for free entries, Mattias Engdegård, 2024/01/13