scratch/hash-table-perf 8335891387a 22/37: Inlined and specialised hash table look-up

[Mattias Engdegård]

branch: scratch/hash-table-perf
commit 8335891387ad5c4db361aa93cb4a6038e0ecf1a5
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.
---
 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 c53ef678edd..38b70fed43f 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 855db5cd86c..3230844fce6 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]);
   EMACS_UINT 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 67f2a275841..f2c6cba5e67 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 e3e3b8e8757..d68c30353c1 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]);
 
   EMACS_UINT 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 6d115fa3596..697a185488c 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 08c29c884a5..09c32dfb2c1 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 035607c73ff..fb1d607e3d6 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;
 
   EMACS_UINT 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 a29c2c62155..17e7829b32d 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);
   EMACS_UINT 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 56798e009d5..fe446e81a7a 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, EMACS_UINT 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);
-           EMACS_UINT hash;
-           ptrdiff_t i = hash_lookup (h, o1, &hash);
+           EMACS_UINT 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);
@@ -4774,27 +4778,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, EMACS_UINT *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, EMACS_UINT hash)
 {
-  EMACS_UINT 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,
+                     EMACS_UINT *phash)
+{
+  EMACS_UINT hash = hash_from_key (h, key);
+  *phash = hash;
+  return hash_lookup_with_hash (h, key, hash);
 }
 
 static void
@@ -5522,7 +5539,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;
 }
 
@@ -5536,8 +5553,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 4fb5a9e6ccc..cd5f1c4a6b7 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);
 
   EMACS_UINT 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 53add86bfc1..9a6d25335bb 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);
                  EMACS_UINT 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 e842a1a5b29..f1a650b1424 100644
--- a/src/lisp.h
+++ b/src/lisp.h
@@ -4001,7 +4001,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, EMACS_UINT *);
+ptrdiff_t hash_lookup (struct Lisp_Hash_Table *, Lisp_Object);
+ptrdiff_t hash_lookup_get_hash (struct Lisp_Hash_Table *h, Lisp_Object key,
+                               EMACS_UINT *phash);
 ptrdiff_t hash_put (struct Lisp_Hash_Table *, Lisp_Object, Lisp_Object,
                    EMACS_UINT);
 void hash_remove_from_table (struct Lisp_Hash_Table *, Lisp_Object);
diff --git a/src/lread.c b/src/lread.c
index b03b7575552..039b700e169 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);
                        EMACS_UINT 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);
                EMACS_UINT 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);
                    EMACS_UINT 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);
                EMACS_UINT 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 1f050b16805..32083a7b0db 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);
   EMACS_UINT 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 a3a534f5738..0f32c786605 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);