datastruct/hash: Simplify hashtorture initial insertion
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
@@ -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
Paul E. McKenney
AppliedQuoted 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()andzoo_updater_init()to plain for loops, drop the unused counter j andrandom.hinclude, 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
Signed-off-by Kunwu Chan <[email protected]>
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@@ -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
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()andzoo_updater_init()to plain for loops, drop the unused counter j andrandom.hinclude, 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
Signed-off-by Kunwu Chan <[email protected]>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@@ -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