Date: Wed, 27 Mar 2024 16:37:35 -0500
From: Nathan Bossart <nathandbossart@gmail.com>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: John Naylor <johncnaylorls@gmail.com>, Ants Aasma <ants@cybertec.at>,
	pgsql-hackers@postgresql.org
Subject: Re: add AVX2 support to simd.h
Message-ID: <20240327213735.GA95234@nathanxps13>
References: 
 <CANWCAZb7TGEk6ib12Rr6pbGMy9pqofT0dS=8Dkm+=MwJQZAEww@mail.gmail.com>
 <20240325152121.GB2662364@nathanxps13>
 <20240325213754.GA3094030@nathanxps13>
 <20240326190904.GA3700674@nathanxps13>
 <3189995.1711495704@sss.pgh.pa.us>
 <20240326235554.GA3766883@nathanxps13>
 <20240327013616.GA3940109@nathanxps13>
 <3206056.1711504137@sss.pgh.pa.us>
 <20240327185716.GA4188857@nathanxps13>
 <3442907.1711573813@sss.pgh.pa.us>
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="r5Pyd7+fXNt84Ff3"
Content-Disposition: inline
In-Reply-To: <3442907.1711573813@sss.pgh.pa.us>
Archived-At: 
 <https://www.postgresql.org/message-id/20240327213735.GA95234%40nathanxps13>
Precedence: bulk


--r5Pyd7+fXNt84Ff3
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline

On Wed, Mar 27, 2024 at 05:10:13PM -0400, Tom Lane wrote:
> Shouldn't "i" be declared uint32, since nelem is?

Yes, that's a mistake.

> BTW, I wonder why these functions don't declare their array
> arguments like "const uint32 *base".

They probably should.  I don't see any reason not to, and my compiler
doesn't complain, either.
 
> LGTM otherwise, and I like the fact that the #if structure
> gets a lot less messy.

Thanks for reviewing.  I've attached a v2 that I intend to commit when I
get a chance.

-- 
Nathan Bossart
Amazon Web Services: https://aws.amazon.com

--r5Pyd7+fXNt84Ff3
Content-Type: text/x-diff; charset=us-ascii
Content-Disposition: attachment;
	filename="v2-0001-improve-style-of-pg_lfind32.patch"

From 6f2577779917230bf70284f0ec1186bed17d9b4a Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathan@postgresql.org>
Date: Wed, 27 Mar 2024 13:50:17 -0500
Subject: [PATCH v2 1/1] improve style of pg_lfind32()

---
 src/include/port/pg_lfind.h | 62 ++++++++++++++++---------------------
 1 file changed, 26 insertions(+), 36 deletions(-)

diff --git a/src/include/port/pg_lfind.h b/src/include/port/pg_lfind.h
index 33e8471b03..4b1431ed00 100644
--- a/src/include/port/pg_lfind.h
+++ b/src/include/port/pg_lfind.h
@@ -80,6 +80,24 @@ pg_lfind8_le(uint8 key, uint8 *base, uint32 nelem)
 	return false;
 }
 
+/*
+ * pg_lfind32_one_by_one_helper
+ *
+ * Searches the array of integers one-by-one.  The caller is responsible for
+ * ensuring that there are at least "nelem" integers in the array.
+ */
+static inline bool
+pg_lfind32_one_by_one_helper(uint32 key, const uint32 *base, uint32 nelem)
+{
+	for (uint32 i = 0; i < nelem; i++)
+	{
+		if (key == base[i])
+			return true;
+	}
+
+	return false;
+}
+
 #ifndef USE_NO_SIMD
 /*
  * pg_lfind32_simd_helper
@@ -88,7 +106,7 @@ pg_lfind8_le(uint8 key, uint8 *base, uint32 nelem)
  * ensuring that there are at least 4-registers-worth of integers remaining.
  */
 static inline bool
-pg_lfind32_simd_helper(const Vector32 keys, uint32 *base)
+pg_lfind32_simd_helper(const Vector32 keys, const uint32 *base)
 {
 	const uint32 nelem_per_vector = sizeof(Vector32) / sizeof(uint32);
 	Vector32	vals1,
@@ -132,11 +150,10 @@ pg_lfind32_simd_helper(const Vector32 keys, uint32 *base)
  * return false.
  */
 static inline bool
-pg_lfind32(uint32 key, uint32 *base, uint32 nelem)
+pg_lfind32(uint32 key, const uint32 *base, uint32 nelem)
 {
-	uint32		i = 0;
-
 #ifndef USE_NO_SIMD
+	uint32		i = 0;
 
 	/*
 	 * For better instruction-level parallelism, each loop iteration operates
@@ -150,25 +167,15 @@ pg_lfind32(uint32 key, uint32 *base, uint32 nelem)
 	const uint32 tail_idx = nelem & ~(nelem_per_iteration - 1);
 
 #if defined(USE_ASSERT_CHECKING)
-	bool		assert_result = false;
-
-	/* pre-compute the result for assert checking */
-	for (int j = 0; j < nelem; j++)
-	{
-		if (key == base[j])
-		{
-			assert_result = true;
-			break;
-		}
-	}
+	bool		assert_result = pg_lfind32_one_by_one_helper(key, base, nelem);
 #endif
 
 	/*
-	 * If there aren't enough elements for the SIMD code, jump to the standard
+	 * If there aren't enough elements for the SIMD code, use the standard
 	 * one-by-one linear search code.
 	 */
 	if (nelem < nelem_per_iteration)
-		goto one_by_one;
+		return pg_lfind32_one_by_one_helper(key, base, nelem);
 
 	/*
 	 * Process as many elements as possible with a block of 4 registers.
@@ -193,27 +200,10 @@ pg_lfind32(uint32 key, uint32 *base, uint32 nelem)
 	 */
 	Assert(assert_result == pg_lfind32_simd_helper(keys, &base[nelem - nelem_per_iteration]));
 	return pg_lfind32_simd_helper(keys, &base[nelem - nelem_per_iteration]);
-
-one_by_one:
-
-#endif							/* ! USE_NO_SIMD */
-
+#else
 	/* Process the elements one at a time. */
-	for (; i < nelem; i++)
-	{
-		if (key == base[i])
-		{
-#ifndef USE_NO_SIMD
-			Assert(assert_result == true);
+	return pg_lfind32_one_by_one_helper(key, base, nelem);
 #endif
-			return true;
-		}
-	}
-
-#ifndef USE_NO_SIMD
-	Assert(assert_result == false);
-#endif
-	return false;
 }
 
 #endif							/* PG_LFIND_H */
-- 
2.25.1


--r5Pyd7+fXNt84Ff3--