[src/trunk]: src/usr.bin/make make(1): reduce amount of string hashing

[rillig <rillig%NetBSD.org@localhost>]

details:   https://anonhg.NetBSD.org/src/rev/2c8fb5532c34
branches:  trunk
changeset: 941637:2c8fb5532c34
user:      rillig <rillig%NetBSD.org@localhost>
date:      Sun Oct 25 17:01:05 2020 +0000

description:
make(1): reduce amount of string hashing

In pkgsrc, running "bmake show-all" in pkgtools/pkglint called the hash
function 249130 times before, and only 115502 times after.

Still, a single call to Var_Set hashes the same string 3 times.

diffstat:

 usr.bin/make/hash.c |  17 +++++++++++++++--
 usr.bin/make/hash.h |  10 ++++++----
 usr.bin/make/var.c  |  18 ++++++++++--------
 3 files changed, 31 insertions(+), 14 deletions(-)

diffs (144 lines):

diff -r 62f99a63da3b -r 2c8fb5532c34 usr.bin/make/hash.c
--- a/usr.bin/make/hash.c       Sun Oct 25 16:59:27 2020 +0000
+++ b/usr.bin/make/hash.c       Sun Oct 25 17:01:05 2020 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: hash.c,v 1.47 2020/10/18 12:47:43 rillig Exp $ */
+/*     $NetBSD: hash.c,v 1.48 2020/10/25 17:01:05 rillig Exp $ */
 
 /*
  * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
@@ -79,7 +79,7 @@
 #include "make.h"
 
 /*     "@(#)hash.c     8.1 (Berkeley) 6/6/93"  */
-MAKE_RCSID("$NetBSD: hash.c,v 1.47 2020/10/18 12:47:43 rillig Exp $");
+MAKE_RCSID("$NetBSD: hash.c,v 1.48 2020/10/25 17:01:05 rillig Exp $");
 
 /*
  * The ratio of # entries to # buckets at which we rebuild the table to
@@ -100,6 +100,12 @@
        return h;
 }
 
+unsigned int
+Hash_Hash(const char *key)
+{
+    return hash(key, NULL);
+}
+
 static HashEntry *
 HashTable_Find(HashTable *t, unsigned int h, const char *key)
 {
@@ -185,6 +191,13 @@
        return he != NULL ? he->value : NULL;
 }
 
+void *
+Hash_FindValueHash(HashTable *t, const char *key, unsigned int h)
+{
+       HashEntry *he = HashTable_Find(t, h, key);
+       return he != NULL ? he->value : NULL;
+}
+
 /* Makes a new hash table that is larger than the old one. The entire hash
  * table is moved, so any bucket numbers from the old table become invalid. */
 static void
diff -r 62f99a63da3b -r 2c8fb5532c34 usr.bin/make/hash.h
--- a/usr.bin/make/hash.h       Sun Oct 25 16:59:27 2020 +0000
+++ b/usr.bin/make/hash.h       Sun Oct 25 17:01:05 2020 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: hash.h,v 1.29 2020/10/18 12:47:43 rillig Exp $ */
+/*     $NetBSD: hash.h,v 1.30 2020/10/25 17:01:05 rillig Exp $ */
 
 /*
  * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
@@ -81,9 +81,9 @@
 typedef struct HashEntry {
     struct HashEntry *next;    /* Used to link together all the entries
                                 * associated with the same bucket. */
-    void             *value;
-    unsigned         key_hash; /* hash value of the key */
-    char             key[1];   /* key string, variable length */
+    void *value;
+    unsigned int key_hash;     /* hash value of the key */
+    char key[1];               /* key string, variable length */
 } HashEntry;
 
 /* The hash table containing the entries. */
@@ -119,6 +119,8 @@
 void Hash_DeleteTable(HashTable *);
 HashEntry *Hash_FindEntry(HashTable *, const char *);
 void *Hash_FindValue(HashTable *, const char *);
+unsigned int Hash_Hash(const char *);
+void *Hash_FindValueHash(HashTable *, const char *, unsigned int);
 HashEntry *Hash_CreateEntry(HashTable *, const char *, Boolean *);
 void Hash_DeleteEntry(HashTable *, HashEntry *);
 
diff -r 62f99a63da3b -r 2c8fb5532c34 usr.bin/make/var.c
--- a/usr.bin/make/var.c        Sun Oct 25 16:59:27 2020 +0000
+++ b/usr.bin/make/var.c        Sun Oct 25 17:01:05 2020 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: var.c,v 1.585 2020/10/25 13:06:12 rillig Exp $ */
+/*     $NetBSD: var.c,v 1.586 2020/10/25 17:01:05 rillig Exp $ */
 
 /*
  * Copyright (c) 1988, 1989, 1990, 1993
@@ -121,7 +121,7 @@
 #include    "metachar.h"
 
 /*     "@(#)var.c      8.3 (Berkeley) 3/19/94" */
-MAKE_RCSID("$NetBSD: var.c,v 1.585 2020/10/25 13:06:12 rillig Exp $");
+MAKE_RCSID("$NetBSD: var.c,v 1.586 2020/10/25 17:01:05 rillig Exp $");
 
 #define VAR_DEBUG1(fmt, arg1) DEBUG1(VAR, fmt, arg1)
 #define VAR_DEBUG2(fmt, arg1, arg2) DEBUG2(VAR, fmt, arg1, arg2)
@@ -353,6 +353,7 @@
 VarFind(const char *name, GNode *ctxt, VarFindFlags flags)
 {
     Var *var;
+    unsigned int nameHash;
 
     /*
      * If the variable name begins with a '.', it could very well be one of
@@ -361,24 +362,25 @@
      * them.
      */
     name = CanonicalVarname(name);
+    nameHash = Hash_Hash(name);
 
     /*
      * First look for the variable in the given context. If it's not there,
      * look for it in VAR_CMD, VAR_GLOBAL and the environment, in that order,
      * depending on the FIND_* flags in 'flags'
      */
-    var = Hash_FindValue(&ctxt->context, name);
+    var = Hash_FindValueHash(&ctxt->context, name, nameHash);
 
     if (var == NULL && (flags & FIND_CMD) && ctxt != VAR_CMD)
-       var = Hash_FindValue(&VAR_CMD->context, name);
+       var = Hash_FindValueHash(&VAR_CMD->context, name, nameHash);
 
     if (!checkEnvFirst && var == NULL && (flags & FIND_GLOBAL) &&
        ctxt != VAR_GLOBAL)
     {
-       var = Hash_FindValue(&VAR_GLOBAL->context, name);
+       var = Hash_FindValueHash(&VAR_GLOBAL->context, name, nameHash);
        if (var == NULL && ctxt != VAR_INTERNAL) {
            /* VAR_INTERNAL is subordinate to VAR_GLOBAL */
-           var = Hash_FindValue(&VAR_INTERNAL->context, name);
+           var = Hash_FindValueHash(&VAR_INTERNAL->context, name, nameHash);
        }
     }
 
@@ -391,9 +393,9 @@
        }
 
        if (checkEnvFirst && (flags & FIND_GLOBAL) && ctxt != VAR_GLOBAL) {
-           var = Hash_FindValue(&VAR_GLOBAL->context, name);
+           var = Hash_FindValueHash(&VAR_GLOBAL->context, name, nameHash);
            if (var == NULL && ctxt != VAR_INTERNAL)
-               var = Hash_FindValue(&VAR_INTERNAL->context, name);
+               var = Hash_FindValueHash(&VAR_INTERNAL->context, name, nameHash);
            return var;
        }