Module Name: src
Committed By: rillig
Date: Sun Oct 25 17:01:05 UTC 2020
Modified Files:
src/usr.bin/make: hash.c hash.h var.c
Log Message:
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.
To generate a diff of this commit:
cvs rdiff -u -r1.47 -r1.48 src/usr.bin/make/hash.c
cvs rdiff -u -r1.29 -r1.30 src/usr.bin/make/hash.h
cvs rdiff -u -r1.585 -r1.586 src/usr.bin/make/var.c
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/usr.bin/make/hash.c
diff -u src/usr.bin/make/hash.c:1.47 src/usr.bin/make/hash.c:1.48
--- src/usr.bin/make/hash.c:1.47 Sun Oct 18 12:47:43 2020
+++ src/usr.bin/make/hash.c Sun Oct 25 17:01:05 2020
@@ -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 @@ hash(const char *key, size_t *out_keylen
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 @@ Hash_FindValue(HashTable *t, const char
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
Index: src/usr.bin/make/hash.h
diff -u src/usr.bin/make/hash.h:1.29 src/usr.bin/make/hash.h:1.30
--- src/usr.bin/make/hash.h:1.29 Sun Oct 18 12:47:43 2020
+++ src/usr.bin/make/hash.h Sun Oct 25 17:01:05 2020
@@ -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_InitTable(HashTable *);
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 *);
Index: src/usr.bin/make/var.c
diff -u src/usr.bin/make/var.c:1.585 src/usr.bin/make/var.c:1.586
--- src/usr.bin/make/var.c:1.585 Sun Oct 25 13:06:12 2020
+++ src/usr.bin/make/var.c Sun Oct 25 17:01:05 2020
@@ -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 @@ static Var *
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 @@ VarFind(const char *name, GNode *ctxt, V
* 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 @@ VarFind(const char *name, GNode *ctxt, V
}
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;
}
