v1-0002-Use-do-while-loops-instead-of-for-loops.patch

From a9b0f52face6d918738885413da83070ae48a137 Mon Sep 17 00:00:00 2001
From: David Rowley <dgrowley@gmail.com>
Date: Tue, 7 Mar 2023 12:43:26 +1300
Subject: [PATCH v1 2/2] Use do while loops instead of for loops

---
 src/backend/nodes/bitmapset.c | 118 +++++++++++++++++++---------------
 1 file changed, 67 insertions(+), 51 deletions(-)

diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index 14fb100087..aec7392cff 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -8,7 +8,13 @@
  * say at most a few hundred.  By convention, we always represent a set with
  * the minimum possible number of words, i.e, there are never any trailing
  * zero words.  Enforcing this requires that an empty set is represented as
- * NULL.
+ * NULL.  Because an empty Bitmapset is represented as NULL, a non-NULL
+ * Bitmapset always has at least 1 Bitmapword.  We can exploit this fact to
+ * speedup various loops over the Bitmapset's words array by using "do while"
+ * loops instead of "for" loops.  This means the code does not waste time
+ * checking the loop condition before the first iteration.  For Bitmapsets
+ * containing only a single word (likely the majority of them) this reduces
+ * the loop condition tests by half.
  *
  *
  * Copyright (c) 2003-2023, PostgreSQL Global Development Group
@@ -109,11 +115,11 @@ bms_equal(const Bitmapset *a, const Bitmapset *b)
 		return false;
 
 	/* check each word matches */
-	for (i = 0; i < a->nwords; i++)
-	{
+	i = 0;
+	do {
 		if (a->words[i] != b->words[i])
 			return false;
-	}
+	} while (++i < a->nwords);
 
 	return true;
 }
@@ -140,14 +146,14 @@ bms_compare(const Bitmapset *a, const Bitmapset *b)
 	if (a->nwords != b->nwords)
 		return (a->nwords > b->nwords) ? +1 : -1;
 
-	for (i = a->nwords - 1; i >= 0; i--)
-	{
+	i = a->nwords - 1;
+	do {
 		bitmapword	aw = a->words[i];
 		bitmapword	bw = b->words[i];
 
 		if (aw != bw)
 			return (aw > bw) ? +1 : -1;
-	}
+	} while (--i >= 0);
 	return 0;
 }
 
@@ -220,8 +226,10 @@ bms_union(const Bitmapset *a, const Bitmapset *b)
 	}
 	/* And union the shorter input into the result */
 	otherlen = other->nwords;
-	for (i = 0; i < otherlen; i++)
+	i = 0;
+	do {
 		result->words[i] |= other->words[i];
+	} while (++i < otherlen);
 	return result;
 }
 
@@ -254,13 +262,13 @@ bms_intersect(const Bitmapset *a, const Bitmapset *b)
 	/* And intersect the longer input with the result */
 	resultlen = result->nwords;
 	lastnonzero = -1;
-	for (i = 0; i < resultlen; i++)
-	{
+	i = 0;
+	do {
 		result->words[i] &= other->words[i];
 
 		if (result->words[i] != 0)
 			lastnonzero = i;
-	}
+	} while (++i < resultlen);
 	/* If we computed an empty result, we must return NULL */
 	if (lastnonzero == -1)
 	{
@@ -303,13 +311,13 @@ bms_difference(const Bitmapset *a, const Bitmapset *b)
 	/* And remove b's bits from result */
 	shortlen = Min(a->nwords, b->nwords);
 	lastnonzero = -1;
-	for (i = 0; i < shortlen; i++)
-	{
+	i = 0;
+	do {
 		result->words[i] &= ~b->words[i];
 
 		if (result->words[i] != 0)
 			lastnonzero = i;
-	}
+	} while (++i < shortlen);
 
 	/* get rid of trailing zero words */
 	result->nwords = lastnonzero + 1;
@@ -337,11 +345,11 @@ bms_is_subset(const Bitmapset *a, const Bitmapset *b)
 		return false;
 
 	/* Check all 'a' members are set in 'b' */
-	for (i = 0; i < a->nwords; i++)
-	{
+	i = 0;
+	do {
 		if ((a->words[i] & ~b->words[i]) != 0)
 			return false;
-	}
+	} while (++i < a->nwords);
 	return true;
 }
 
@@ -369,8 +377,8 @@ bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
 	/* Check common words */
 	result = BMS_EQUAL;			/* status so far */
 	shortlen = Min(a->nwords, b->nwords);
-	for (i = 0; i < shortlen; i++)
-	{
+	i = 0;
+	do {
 		bitmapword	aword = a->words[i];
 		bitmapword	bword = b->words[i];
 
@@ -388,7 +396,7 @@ bms_subset_compare(const Bitmapset *a, const Bitmapset *b)
 				return BMS_DIFFERENT;
 			result = BMS_SUBSET1;
 		}
-	}
+	} while (++i < shortlen);
 	/* Check extra words */
 	if (a->nwords > b->nwords)
 	{
@@ -488,11 +496,11 @@ bms_overlap(const Bitmapset *a, const Bitmapset *b)
 		return false;
 	/* Check words in common */
 	shortlen = Min(a->nwords, b->nwords);
-	for (i = 0; i < shortlen; i++)
-	{
+	i = 0;
+	do {
 		if ((a->words[i] & b->words[i]) != 0)
 			return true;
-	}
+	} while (++i < shortlen);
 	return false;
 }
 
@@ -543,11 +551,11 @@ bms_nonempty_difference(const Bitmapset *a, const Bitmapset *b)
 	if (a->nwords > b->nwords)
 		return true;
 	/* Check all 'a' members are set in 'b' */
-	for (i = 0; i < a->nwords; i++)
-	{
+	i  = 0;
+	do {
 		if ((a->words[i] & ~b->words[i]) != 0)
 			return true;
-	}
+	} while (++i < a->nwords);
 	return false;
 }
 
@@ -566,8 +574,8 @@ bms_singleton_member(const Bitmapset *a)
 	if (a == NULL)
 		elog(ERROR, "bitmapset is empty");
 	nwords = a->nwords;
-	for (wordnum = 0; wordnum < nwords; wordnum++)
-	{
+	wordnum = 0;
+	do {
 		bitmapword	w = a->words[wordnum];
 
 		if (w != 0)
@@ -577,7 +585,7 @@ bms_singleton_member(const Bitmapset *a)
 			result = wordnum * BITS_PER_BITMAPWORD;
 			result += bmw_rightmost_one_pos(w);
 		}
-	}
+	} while (++wordnum < nwords);
 	if (result < 0)
 		elog(ERROR, "bitmapset is empty");
 	return result;
@@ -604,8 +612,8 @@ bms_get_singleton_member(const Bitmapset *a, int *member)
 	if (a == NULL)
 		return false;
 	nwords = a->nwords;
-	for (wordnum = 0; wordnum < nwords; wordnum++)
-	{
+	wordnum = 0;
+	do {
 		bitmapword	w = a->words[wordnum];
 
 		if (w != 0)
@@ -615,7 +623,7 @@ bms_get_singleton_member(const Bitmapset *a, int *member)
 			result = wordnum * BITS_PER_BITMAPWORD;
 			result += bmw_rightmost_one_pos(w);
 		}
-	}
+	} while (++wordnum < nwords);
 	if (result < 0)
 		return false;
 	*member = result;
@@ -635,14 +643,14 @@ bms_num_members(const Bitmapset *a)
 	if (a == NULL)
 		return 0;
 	nwords = a->nwords;
-	for (wordnum = 0; wordnum < nwords; wordnum++)
-	{
+	wordnum = 0;
+	do {
 		bitmapword	w = a->words[wordnum];
 
 		/* No need to count the bits in a zero word */
 		if (w != 0)
 			result += bmw_popcount(w);
-	}
+	} while (++wordnum < nwords);
 	return result;
 }
 
@@ -661,8 +669,8 @@ bms_membership(const Bitmapset *a)
 	if (a == NULL)
 		return BMS_EMPTY_SET;
 	nwords = a->nwords;
-	for (wordnum = 0; wordnum < nwords; wordnum++)
-	{
+	wordnum = 0;
+	do {
 		bitmapword	w = a->words[wordnum];
 
 		if (w != 0)
@@ -671,7 +679,7 @@ bms_membership(const Bitmapset *a)
 				return BMS_MULTIPLE;
 			result = BMS_SINGLETON;
 		}
-	}
+	} while (++wordnum < nwords);
 	return result;
 }
 
@@ -689,13 +697,13 @@ bms_is_empty_internal(const Bitmapset *a)
 	int			wordnum;
 
 	nwords = a->nwords;
-	for (wordnum = 0; wordnum < nwords; wordnum++)
-	{
+	wordnum = 0;
+	do {
 		bitmapword	w = a->words[wordnum];
 
 		if (w != 0)
 			return false;
-	}
+	} while (++wordnum < nwords);
 	return true;
 }
 
@@ -737,8 +745,10 @@ bms_add_member(Bitmapset *a, int x)
 		a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(wordnum + 1));
 		a->nwords = wordnum + 1;
 		/* zero out the enlarged portion */
-		for (i = oldnwords; i < a->nwords; i++)
+		i = oldnwords;
+		do {
 			a->words[i] = 0;
+		} while (++i < a->nwords);
 	}
 
 	a->words[wordnum] |= ((bitmapword) 1 << bitnum);
@@ -804,8 +814,10 @@ bms_add_members(Bitmapset *a, const Bitmapset *b)
 	}
 	/* And union the shorter input into the result */
 	otherlen = other->nwords;
-	for (i = 0; i < otherlen; i++)
+	i = 0;
+	do {
 		result->words[i] |= other->words[i];
+	} while (++i < otherlen);
 	if (result != a)
 		pfree(a);
 	return result;
@@ -851,8 +863,10 @@ bms_add_range(Bitmapset *a, int lower, int upper)
 		a = (Bitmapset *) repalloc(a, BITMAPSET_SIZE(uwordnum + 1));
 		a->nwords = uwordnum + 1;
 		/* zero out the enlarged portion */
-		for (i = oldnwords; i < a->nwords; i++)
+		i = oldnwords;
+		do {
 			a->words[i] = 0;
+		} while (++i < a->nwords);
 	}
 
 	wordnum = lwordnum = WORDNUM(lower);
@@ -906,13 +920,13 @@ bms_int_members(Bitmapset *a, const Bitmapset *b)
 	/* Intersect b into a; we need never copy */
 	shortlen = Min(a->nwords, b->nwords);
 	lastnonzero = -1;
-	for (i = 0; i < shortlen; i++)
-	{
+	i = 0;
+	do {
 		a->words[i] &= b->words[i];
 
 		if (a->words[i] != 0)
 			lastnonzero = i;
-	}
+	} while (++i < shortlen);
 
 	/* If we computed an empty result, we must return NULL */
 	if (lastnonzero == -1)
@@ -944,13 +958,13 @@ bms_del_members(Bitmapset *a, const Bitmapset *b)
 	/* Remove b's bits from a; we need never copy */
 	shortlen = Min(a->nwords, b->nwords);
 	lastnonzero = -1;
-	for (i = 0; i < shortlen; i++)
-	{
+	i = 0;
+	do {
 		a->words[i] &= ~b->words[i];
 
 		if (a->words[i] != 0)
 			lastnonzero = i;
-	}
+	} while (++i < shortlen);
 
 	/* If we computed an empty result, we must return NULL */
 	if (lastnonzero == -1)
@@ -994,8 +1008,10 @@ bms_join(Bitmapset *a, Bitmapset *b)
 	}
 	/* And union the shorter input into the result */
 	otherlen = other->nwords;
-	for (i = 0; i < otherlen; i++)
+	i = 0;
+	do {
 		result->words[i] |= other->words[i];
+	} while (++i < otherlen);
 	if (other != result)		/* pure paranoia */
 		pfree(other);
 	return result;
-- 
2.37.2