Module Name: src
Committed By: rillig
Date: Sun Jul 7 09:37:00 UTC 2024
Modified Files:
src/usr.bin/make: hash.c hash.h
src/usr.bin/make/unit-tests: Makefile opt-debug-hash.exp
Log Message:
make: don't track hash table chain lengths during lookup
The chain lengths are only used for debugging purposes, so avoid the
extra cost at each lookup. Instead, calculate the maximum chain length
only when it is actually requested in -dh mode.
The reported number changes slightly: Before, it was the length of the
chain that was actually traversed to find an entry, up to that entry,
now it is the length of the largest chain in the table, no matter if it
was actually accessed or not.
To generate a diff of this commit:
cvs rdiff -u -r1.78 -r1.79 src/usr.bin/make/hash.c
cvs rdiff -u -r1.50 -r1.51 src/usr.bin/make/hash.h
cvs rdiff -u -r1.349 -r1.350 src/usr.bin/make/unit-tests/Makefile
cvs rdiff -u -r1.6 -r1.7 src/usr.bin/make/unit-tests/opt-debug-hash.exp
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.78 src/usr.bin/make/hash.c:1.79
--- src/usr.bin/make/hash.c:1.78 Wed Jun 5 22:06:53 2024
+++ src/usr.bin/make/hash.c Sun Jul 7 09:37:00 2024
@@ -1,4 +1,4 @@
-/* $NetBSD: hash.c,v 1.78 2024/06/05 22:06:53 rillig Exp $ */
+/* $NetBSD: hash.c,v 1.79 2024/07/07 09:37:00 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.78 2024/06/05 22:06:53 rillig Exp $");
+MAKE_RCSID("$NetBSD: hash.c,v 1.79 2024/07/07 09:37:00 rillig Exp $");
/*
* The ratio of # entries to # buckets at which we rebuild the table to
@@ -114,7 +114,6 @@ static HashEntry *
HashTable_Find(HashTable *t, Substring key, unsigned int h)
{
HashEntry *he;
- unsigned int chainlen = 0;
size_t keyLen = Substring_Length(key);
#ifdef DEBUG_HASH_LOOKUP
@@ -123,16 +122,12 @@ HashTable_Find(HashTable *t, Substring k
#endif
for (he = t->buckets[h & t->bucketsMask]; he != NULL; he = he->next) {
- chainlen++;
if (he->hash == h &&
strncmp(he->key, key.start, keyLen) == 0 &&
he->key[keyLen] == '\0')
break;
}
- if (chainlen > t->maxchain)
- t->maxchain = chainlen;
-
return he;
}
@@ -149,7 +144,6 @@ HashTable_Init(HashTable *t)
t->bucketsSize = n;
t->numEntries = 0;
t->bucketsMask = n - 1;
- t->maxchain = 0;
}
/*
@@ -205,6 +199,20 @@ HashTable_FindValueBySubstringHash(HashT
return he != NULL ? he->value : NULL;
}
+static unsigned
+HashTable_MaxChain(const HashTable *t)
+{
+ unsigned b, cl, max_cl = 0;
+ for (b = 0; b < t->bucketsSize; b++) {
+ const HashEntry *he = t->buckets[b];
+ for (cl = 0; he != NULL; he = he->next)
+ cl++;
+ if (cl > max_cl)
+ max_cl = cl;
+ }
+ return max_cl;
+}
+
/*
* Make the hash table larger. Any bucket numbers from the old table become
* invalid; the hash values stay valid though.
@@ -238,8 +246,7 @@ HashTable_Enlarge(HashTable *t)
t->bucketsMask = newMask;
t->buckets = newBuckets;
DEBUG4(HASH, "HashTable_Enlarge: %p size=%d entries=%d maxchain=%d\n",
- (void *)t, t->bucketsSize, t->numEntries, t->maxchain);
- t->maxchain = 0;
+ (void *)t, t->bucketsSize, t->numEntries, HashTable_MaxChain(t));
}
/*
@@ -321,8 +328,8 @@ HashIter_Next(HashIter *hi)
}
void
-HashTable_DebugStats(HashTable *t, const char *name)
+HashTable_DebugStats(const HashTable *t, const char *name)
{
- DEBUG4(HASH, "HashTable %s: size=%u numEntries=%u maxchain=%u\n",
- name, t->bucketsSize, t->numEntries, t->maxchain);
+ DEBUG4(HASH, "HashTable \"%s\": size=%u entries=%u maxchain=%u\n",
+ name, t->bucketsSize, t->numEntries, HashTable_MaxChain(t));
}
Index: src/usr.bin/make/hash.h
diff -u src/usr.bin/make/hash.h:1.50 src/usr.bin/make/hash.h:1.51
--- src/usr.bin/make/hash.h:1.50 Sat Jun 1 10:10:50 2024
+++ src/usr.bin/make/hash.h Sun Jul 7 09:37:00 2024
@@ -1,4 +1,4 @@
-/* $NetBSD: hash.h,v 1.50 2024/06/01 10:10:50 rillig Exp $ */
+/* $NetBSD: hash.h,v 1.51 2024/07/07 09:37:00 rillig Exp $ */
/*
* Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
@@ -92,7 +92,6 @@ typedef struct HashTable {
unsigned int bucketsSize;
unsigned int numEntries;
unsigned int bucketsMask; /* Used to select the bucket for a hash. */
- unsigned int maxchain; /* Maximum length of chain seen. */
} HashTable;
/* State of an iteration over all entries in a table. */
@@ -138,7 +137,7 @@ void *HashTable_FindValueBySubstringHash
HashEntry *HashTable_CreateEntry(HashTable *, const char *, bool *);
void HashTable_Set(HashTable *, const char *, void *);
void HashTable_DeleteEntry(HashTable *, HashEntry *);
-void HashTable_DebugStats(HashTable *, const char *);
+void HashTable_DebugStats(const HashTable *, const char *);
bool HashIter_Next(HashIter *) MAKE_ATTR_USE;
Index: src/usr.bin/make/unit-tests/Makefile
diff -u src/usr.bin/make/unit-tests/Makefile:1.349 src/usr.bin/make/unit-tests/Makefile:1.350
--- src/usr.bin/make/unit-tests/Makefile:1.349 Thu Jul 4 20:18:40 2024
+++ src/usr.bin/make/unit-tests/Makefile Sun Jul 7 09:37:00 2024
@@ -1,4 +1,4 @@
-# $NetBSD: Makefile,v 1.349 2024/07/04 20:18:40 rillig Exp $
+# $NetBSD: Makefile,v 1.350 2024/07/07 09:37:00 rillig Exp $
#
# Unit tests for make(1)
#
@@ -534,7 +534,7 @@ SED_CMDS.opt-chdir= -e 's,\(nonexistent
SED_CMDS.opt-debug-graph1= ${STD_SED_CMDS.dg1}
SED_CMDS.opt-debug-graph2= ${STD_SED_CMDS.dg2}
SED_CMDS.opt-debug-graph3= ${STD_SED_CMDS.dg3}
-SED_CMDS.opt-debug-hash= -e 's,\(numEntries\)=[1-9][0-9],\1=<entries>,'
+SED_CMDS.opt-debug-hash= -e 's,\(entries\)=[1-9][0-9],\1=<entries>,'
SED_CMDS.opt-debug-jobs= -e 's,([0-9][0-9]*),(<pid>),'
SED_CMDS.opt-debug-jobs+= -e 's,pid [0-9][0-9]*,pid <pid>,'
SED_CMDS.opt-debug-jobs+= -e 's,Process [0-9][0-9]*,Process <pid>,'
Index: src/usr.bin/make/unit-tests/opt-debug-hash.exp
diff -u src/usr.bin/make/unit-tests/opt-debug-hash.exp:1.6 src/usr.bin/make/unit-tests/opt-debug-hash.exp:1.7
--- src/usr.bin/make/unit-tests/opt-debug-hash.exp:1.6 Fri May 31 07:13:12 2024
+++ src/usr.bin/make/unit-tests/opt-debug-hash.exp Sun Jul 7 09:37:00 2024
@@ -1,6 +1,6 @@
make: "opt-debug-hash.mk" line 13: Missing argument for ".error"
make: Fatal errors encountered -- cannot continue
-HashTable targets: size=16 numEntries=0 maxchain=0
-HashTable Global variables: size=16 numEntries=<entries> maxchain=3
+HashTable "targets": size=16 entries=0 maxchain=0
+HashTable "Global variables": size=16 entries=<entries> maxchain=4
make: stopped in unit-tests
exit status 1
