[PATCH] datastruct/hash: Simplify hashtorture initial insertion

[PATCH] datastruct/hash: Simplify hashtorture initial insertion

[Kunwu Chan]

From: Kunwu Chan <kunwu.chan@gmail.com>

Commit 1314f0a0 ("datastruct/hash: Speed up hashtorture initial
insertions") replaced random element placement with a linear scan
guarded by:

        if (elperupdater / 2 - j <= elperupdater - i || random() % 2)

The left disjunct is always true along the loop execution.  The loop
maintains the invariant i == j, starting from i == j == 0.  The guard
therefore reduces to elperupdater / 2 <= elperupdater, and each forced
insertion increments both i and j.  Thus random() % 2 is never
evaluated, and the loop has inserted the first elperupdater / 2
elements consecutively since 2020.

Simplify both perftest_updater_init() and zoo_updater_init() to plain
for loops, drop the unused counter j and random.h include, and update
the comment to describe the actual deterministic behavior.

This does not change the test behavior exercised since 2020.  The
randomized initial population was the only stochastic element in this
initialization path, while the concurrent update loop is a deterministic
round-robin over each updater's elements.  The perfbook description of
hashtorture ("RCU-Protected Hash Table Validation") lists invariant
verification, concurrent-corruption detection, resize correctness,
and performance-data collection as the documented coverage; none is
described as depending on the initial key distribution.

Signed-off-by: Kunwu Chan <kunwu.chan@gmail.com>
---
 CodeSamples/datastruct/hash/hashtorture.h | 41 ++++++++---------------
 1 file changed, 14 insertions(+), 27 deletions(-)

diff --git a/CodeSamples/datastruct/hash/hashtorture.h b/CodeSamples/datastruct/hash/hashtorture.h
index 4bd8e247..4fbb7623 100644
--- a/CodeSamples/datastruct/hash/hashtorture.h
+++ b/CodeSamples/datastruct/hash/hashtorture.h
@@ -815,27 +815,20 @@ void *perftest_reader(void *arg)
 	return NULL;
 }
 
-/* Pre-load specified updater's portion of hash table. */
+/* Pre-load the first half of this updater's elements into the hash table. */
 void perftest_updater_init(int mylowkey, struct testhe *thep)
 {
 	long i;
-	long j;
 
-	i = j = 0;
-	while (j < elperupdater / 2) {
+	for (i = 0; i < elperupdater / 2; i++) {
 		thep[i].data = i + mylowkey;
 		thep[i].in_table = 0;
-		if (elperupdater / 2 - j <= elperupdater - i || random() % 2) {
-			perftest_add(&thep[i]);
-			BUG_ON(!perftest_lookup(thep[i].data));
-			j++;
-		}
-		i++;
+		perftest_add(&thep[i]);
+		BUG_ON(!perftest_lookup(thep[i].data));
 	}
-	while (i < elperupdater) {
+	for (i = elperupdater / 2; i < elperupdater; i++) {
 		thep[i].data = i + mylowkey;
 		thep[i].in_table = 0;
-		i++;
 	}
 }
 
@@ -1132,26 +1125,20 @@ void *zoo_reader(void *arg)
 	return NULL;
 }
 
-/* Pre-load specified updater's portion of hash table. */
+/* Pre-load the first half of this updater's elements into the hash table. */
 void zoo_updater_init(int mylowkey, struct zoo_he **zheplist)
 {
 	long i;
-	long j;
 	struct zoo_he *zhep;
 
-	i = j = 0;
-	while (j < elperupdater / 2) {
-		if (elperupdater / 2 - j <= elperupdater - i || random() % 2) {
-			zhep = malloc(sizeof(*zhep));
-			BUG_ON(!zhep);
-			strcpy(zhep->name,
-			       &zoo_names[ZOO_NAMELEN * (i + mylowkey)]);
-			zoo_add(zhep);
-			zheplist[i] = zhep;
-			BUG_ON(!zoo_lookup(zhep->name));
-			j++;
-		}
-		i++;
+	for (i = 0; i < elperupdater / 2; i++) {
+		zhep = malloc(sizeof(*zhep));
+		BUG_ON(!zhep);
+		strcpy(zhep->name,
+		       &zoo_names[ZOO_NAMELEN * (i + mylowkey)]);
+		zoo_add(zhep);
+		zheplist[i] = zhep;
+		BUG_ON(!zoo_lookup(zhep->name));
 	}
 }
 
-- 
2.43.0