Skip to contentSkip to conversation

datastruct/hash: Simplify hashtorture initial insertion

PATCH Applied Kunwu Chan 2 participants 3 messages Aug 19 – Oct 2

lore
Share & tools
lore

Kunwu Chan

author
#0 lore raw

PATCH 1/1 datastruct/hash: Simplify hashtorture initial insertion

From: Kunwu Chan <[email protected]>

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.

---
 CodeSamples/datastruct/hash/hashtorture.h | 41 ++++++++---------------
 1 file changed, 14 insertions(+), 27 deletions(-)
CodeSamples/datastruct/hash/hashtorture.h +14 -27
index 4bd8e247..4fbb7623 100644
@@ -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));
 	}
 }
 
Signature · 1 line
2.43.0
#1 lore raw
Quoted 28 lines · Kunwu Chan

From: Kunwu Chan <[email protected]>

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.

Quoted 1 line

Queued and pushed, thank you!!! And please accept my apologies for the delay, hopefully better late than never.

Thanx, Paul

Quoted 80 lines
---
 CodeSamples/datastruct/hash/hashtorture.h | 41 ++++++++---------------
 1 file changed, 14 insertions(+), 27 deletions(-)
CodeSamples/datastruct/hash/hashtorture.h +14 -27
index 4bd8e247..4fbb7623 100644
@@ -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));
 	}
 }
 
Signature · 1 line
2.43.0
author
#2 lore raw
Quoted 30 lines · Paul E. McKenney
Quoted 28 lines · Kunwu Chan

From: Kunwu Chan <[email protected]>

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.

Quoted 4 lines
Quoted 1 line

Queued and pushed, thank you!!! And please accept my apologies for the delay, hopefully better late than never.

No worries at all, Paul! I just happened to notice this while looking through the code.
Thanks for picking it up, and better late than never indeed! :-)

Thanks,
Kunwu

Quoted 83 lines

Thanx, Paul

Quoted 80 lines
---
 CodeSamples/datastruct/hash/hashtorture.h | 41 ++++++++---------------
 1 file changed, 14 insertions(+), 27 deletions(-)
CodeSamples/datastruct/hash/hashtorture.h +14 -28
index 4bd8e247..4fbb7623 100644
@@ -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