Source-Changes-HG archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
[src/trunk]: src/usr.bin/make make: avoid allocating memory for simple variab...
details: https://anonhg.NetBSD.org/src/rev/fb9c9fd62890
branches: trunk
changeset: 961536:fb9c9fd62890
user: rillig <rillig%NetBSD.org@localhost>
date: Sun Apr 11 12:46:54 2021 +0000
description:
make: avoid allocating memory for simple variable names
The main change is in ParseVarname, where a Buffer is replaced with the
newly introduced LazyBuf. LazyBuf is inspired by
https://golang.org/src/path/path.go.
In CanonicalVarname, the pre-comparison of the first letter of the
variable name is no longer necessary. GCC 9 optimizes a fixed-length
memcmp so well that the code can finally be written to target human
readers, leaving the optimization to the compiler.
diffstat:
usr.bin/make/hash.c | 60 +++++++++++++--
usr.bin/make/hash.h | 6 +-
usr.bin/make/var.c | 192 +++++++++++++++++++++++----------------------------
3 files changed, 142 insertions(+), 116 deletions(-)
diffs (truncated from 527 to 300 lines):
diff -r 73260f627b64 -r fb9c9fd62890 usr.bin/make/hash.c
--- a/usr.bin/make/hash.c Sun Apr 11 12:06:53 2021 +0000
+++ b/usr.bin/make/hash.c Sun Apr 11 12:46:54 2021 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: hash.c,v 1.63 2021/04/03 14:39:02 rillig Exp $ */
+/* $NetBSD: hash.c,v 1.64 2021/04/11 12:46:54 rillig Exp $ */
/*
* Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
@@ -74,7 +74,7 @@
#include "make.h"
/* "@(#)hash.c 8.1 (Berkeley) 6/6/93" */
-MAKE_RCSID("$NetBSD: hash.c,v 1.63 2021/04/03 14:39:02 rillig Exp $");
+MAKE_RCSID("$NetBSD: hash.c,v 1.64 2021/04/11 12:46:54 rillig Exp $");
/*
* The ratio of # entries to # buckets at which we rebuild the table to
@@ -84,7 +84,7 @@
/* This hash function matches Gosling's Emacs and java.lang.String. */
static unsigned int
-hash(const char *key, size_t *out_keylen)
+Hash_String(const char *key, size_t *out_keylen)
{
unsigned int h;
const char *p;
@@ -98,10 +98,17 @@
return h;
}
+/* This hash function matches Gosling's Emacs and java.lang.String. */
unsigned int
-Hash_Hash(const char *key)
+Hash_Substring(Substring key)
{
- return hash(key, NULL);
+ unsigned int h;
+ const char *p;
+
+ h = 0;
+ for (p = key.start; p != key.end; p++)
+ h = 31 * h + (unsigned char)*p;
+ return h;
}
static HashEntry *
@@ -126,6 +133,41 @@
return e;
}
+static bool
+HashEntry_KeyEquals(const HashEntry *he, Substring key)
+{
+ const char *heKey, *p;
+
+ heKey = he->key;
+ for (p = key.start; p != key.end; p++, heKey++)
+ if (*p != *heKey || *heKey == '\0')
+ return false;
+ return *heKey == '\0';
+}
+
+static HashEntry *
+HashTable_FindEntryBySubstring(HashTable *t, Substring key, unsigned int h)
+{
+ HashEntry *e;
+ unsigned int chainlen = 0;
+
+#ifdef DEBUG_HASH_LOOKUP
+ DEBUG4(HASH, "%s: %p h=%08x key=%.*s\n", __func__, t, h,
+ (int)Substring_Length(key), key.start);
+#endif
+
+ for (e = t->buckets[h & t->bucketsMask]; e != NULL; e = e->next) {
+ chainlen++;
+ if (e->key_hash == h && HashEntry_KeyEquals(e, key))
+ break;
+ }
+
+ if (chainlen > t->maxchain)
+ t->maxchain = chainlen;
+
+ return e;
+}
+
/* Set up the hash table. */
void
HashTable_Init(HashTable *t)
@@ -171,7 +213,7 @@
HashEntry *
HashTable_FindEntry(HashTable *t, const char *key)
{
- unsigned int h = hash(key, NULL);
+ unsigned int h = Hash_String(key, NULL);
return HashTable_Find(t, h, key);
}
@@ -188,9 +230,9 @@
* or return NULL.
*/
void *
-HashTable_FindValueHash(HashTable *t, const char *key, unsigned int h)
+HashTable_FindValueBySubstringHash(HashTable *t, Substring key, unsigned int h)
{
- HashEntry *he = HashTable_Find(t, h, key);
+ HashEntry *he = HashTable_FindEntryBySubstring(t, key, h);
return he != NULL ? he->value : NULL;
}
@@ -239,7 +281,7 @@
HashTable_CreateEntry(HashTable *t, const char *key, bool *out_isNew)
{
size_t keylen;
- unsigned int h = hash(key, &keylen);
+ unsigned int h = Hash_String(key, &keylen);
HashEntry *he = HashTable_Find(t, h, key);
if (he != NULL) {
diff -r 73260f627b64 -r fb9c9fd62890 usr.bin/make/hash.h
--- a/usr.bin/make/hash.h Sun Apr 11 12:06:53 2021 +0000
+++ b/usr.bin/make/hash.h Sun Apr 11 12:46:54 2021 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: hash.h,v 1.39 2021/04/03 11:08:40 rillig Exp $ */
+/* $NetBSD: hash.h,v 1.40 2021/04/11 12:46:54 rillig Exp $ */
/*
* Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
@@ -124,8 +124,8 @@
void HashTable_Done(HashTable *);
HashEntry *HashTable_FindEntry(HashTable *, const char *);
void *HashTable_FindValue(HashTable *, const char *);
-unsigned int Hash_Hash(const char *);
-void *HashTable_FindValueHash(HashTable *, const char *, unsigned int);
+unsigned int Hash_Substring(Substring);
+void *HashTable_FindValueBySubstringHash(HashTable *, Substring, unsigned int);
HashEntry *HashTable_CreateEntry(HashTable *, const char *, bool *);
HashEntry *HashTable_Set(HashTable *, const char *, void *);
void HashTable_DeleteEntry(HashTable *, HashEntry *);
diff -r 73260f627b64 -r fb9c9fd62890 usr.bin/make/var.c
--- a/usr.bin/make/var.c Sun Apr 11 12:06:53 2021 +0000
+++ b/usr.bin/make/var.c Sun Apr 11 12:46:54 2021 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: var.c,v 1.915 2021/04/10 22:40:34 rillig Exp $ */
+/* $NetBSD: var.c,v 1.916 2021/04/11 12:46:54 rillig Exp $ */
/*
* Copyright (c) 1988, 1989, 1990, 1993
@@ -140,7 +140,7 @@
#include "metachar.h"
/* "@(#)var.c 8.3 (Berkeley) 3/19/94" */
-MAKE_RCSID("$NetBSD: var.c,v 1.915 2021/04/10 22:40:34 rillig Exp $");
+MAKE_RCSID("$NetBSD: var.c,v 1.916 2021/04/11 12:46:54 rillig Exp $");
/*
* Variables are defined using one of the VAR=value assignments. Their
@@ -345,45 +345,30 @@
return var;
}
-static const char *
-CanonicalVarname(const char *name)
+static Substring
+CanonicalVarname(Substring name)
{
- if (*name == '.' && ch_isupper(name[1])) {
- switch (name[1]) {
- case 'A':
- if (strcmp(name, ".ALLSRC") == 0)
- name = ALLSRC;
- if (strcmp(name, ".ARCHIVE") == 0)
- name = ARCHIVE;
- break;
- case 'I':
- if (strcmp(name, ".IMPSRC") == 0)
- name = IMPSRC;
- break;
- case 'M':
- if (strcmp(name, ".MEMBER") == 0)
- name = MEMBER;
- break;
- case 'O':
- if (strcmp(name, ".OODATE") == 0)
- name = OODATE;
- break;
- case 'P':
- if (strcmp(name, ".PREFIX") == 0)
- name = PREFIX;
- break;
- case 'S':
- if (strcmp(name, ".SHELL") == 0) {
- if (shellPath == NULL)
- Shell_Init();
- }
- break;
- case 'T':
- if (strcmp(name, ".TARGET") == 0)
- name = TARGET;
- break;
- }
- }
+
+ if (!(Substring_Length(name) > 0 && name.start[0] == '.'))
+ return name;
+
+ if (Substring_Equals(name, ".ALLSRC"))
+ return Substring_InitStr(ALLSRC);
+ if (Substring_Equals(name, ".ARCHIVE"))
+ return Substring_InitStr(ARCHIVE);
+ if (Substring_Equals(name, ".IMPSRC"))
+ return Substring_InitStr(IMPSRC);
+ if (Substring_Equals(name, ".MEMBER"))
+ return Substring_InitStr(MEMBER);
+ if (Substring_Equals(name, ".OODATE"))
+ return Substring_InitStr(OODATE);
+ if (Substring_Equals(name, ".PREFIX"))
+ return Substring_InitStr(PREFIX);
+ if (Substring_Equals(name, ".TARGET"))
+ return Substring_InitStr(TARGET);
+
+ if (Substring_Equals(name, ".SHELL") && shellPath == NULL)
+ Shell_Init();
/* GNU make has an additional alias $^ == ${.ALLSRC}. */
@@ -391,9 +376,9 @@
}
static Var *
-GNode_FindVar(GNode *scope, const char *varname, unsigned int hash)
+GNode_FindVar(GNode *scope, Substring varname, unsigned int hash)
{
- return HashTable_FindValueHash(&scope->vars, varname, hash);
+ return HashTable_FindValueBySubstringHash(&scope->vars, varname, hash);
}
/*
@@ -410,14 +395,14 @@
* VarFreeEnv after use.
*/
static Var *
-VarFind(const char *name, GNode *scope, bool elsewhere)
+VarFindSubstring(Substring name, GNode *scope, bool elsewhere)
{
Var *var;
unsigned int nameHash;
/* Replace '.TARGET' with '@', likewise for other local variables. */
name = CanonicalVarname(name);
- nameHash = Hash_Hash(name);
+ nameHash = Hash_Substring(name);
var = GNode_FindVar(scope, name, nameHash);
if (!elsewhere)
@@ -435,17 +420,19 @@
}
if (var == NULL) {
- char *env;
+ FStr envName;
+ const char *envValue;
/*
* TODO: try setting an environment variable with the empty
* name, which should be technically possible, just to see
* how make reacts. All .for loops should be broken then.
*/
- if ((env = getenv(name)) != NULL) {
- char *varname = bmake_strdup(name);
- return VarNew(FStr_InitOwn(varname), env, true, false);
- }
+ envName = Substring_Str(name);
+ envValue = getenv(envName.str);
+ if (envValue != NULL)
+ return VarNew(envName, envValue, true, false);
+ FStr_Done(&envName);
if (opts.checkEnvFirst && scope != SCOPE_GLOBAL) {
var = GNode_FindVar(SCOPE_GLOBAL, name, nameHash);
@@ -461,6 +448,13 @@
return var;
}
+/* TODO: Replace these calls with VarFindSubstring, as far as possible. */
+static Var *
+VarFind(const char *name, GNode *scope, bool elsewhere)
+{
+ return VarFindSubstring(Substring_InitStr(name), scope, elsewhere);
+}
+
/* If the variable is an environment variable, free it, including its value. */
static void
VarFreeEnv(Var *v)
@@ -4006,12 +4000,17 @@
}
/*
- * Only four of the local variables are treated specially as they are the
- * only four that will be set when dynamic sources are expanded.
Home |
Main Index |
Thread Index |
Old Index