Subject: Re: Popcount optimization using AVX512

From: David Rowley <[email-masked]>
Date: Tue, 19 Mar 2024 10:02:18 +1300

On Tue, 19 Mar 2024 at 06:30, Nathan Bossart <[email-masked]> wrote:
> Here is a more fleshed-out version of what I believe David is proposing.
> On my machine, the gains aren't quite as impressive (~8.8s to ~5.2s for the
> test_popcount benchmark).  I assume this is because this patch turns
> pg_popcount() into a function pointer, which is what the AVX512 patches do,
> too.  I left out the 32-bit section from pg_popcount_fast(), but I'll admit
> that I'm not yet 100% sure that we can assume we're on a 64-bit system
> there.

I looked at your latest patch and tried out the performance on a Zen4
running windows and a Zen2 running on Linux. As follows:

AMD 3990x:

master:
postgres=# select drive_popcount(10000000, 1024);
Time: 11904.078 ms (00:11.904)
Time: 11907.176 ms (00:11.907)
Time: 11927.983 ms (00:11.928)

patched:
postgres=# select drive_popcount(10000000, 1024);
Time: 3641.271 ms (00:03.641)
Time: 3610.934 ms (00:03.611)
Time: 3663.423 ms (00:03.663)

AMD 7945HX Windows

master:
postgres=# select drive_popcount(10000000, 1024);
Time: 9832.845 ms (00:09.833)
Time: 9844.460 ms (00:09.844)
Time: 9858.608 ms (00:09.859)

patched:
postgres=# select drive_popcount(10000000, 1024);
Time: 3427.942 ms (00:03.428)
Time: 3364.262 ms (00:03.364)
Time: 3413.407 ms (00:03.413)

The only thing I'd question in the patch is in pg_popcount_fast(). It
looks like you've opted to not do the 32-bit processing on 32-bit
machines. I think that's likely still worth coding in a similar way to
how pg_popcount_slow() works. i.e. use "#if SIZEOF_VOID_P >= 8".
Probably one day we'll remove that code, but it seems strange to have
pg_popcount_slow() do it and not pg_popcount_fast().

> IMHO this work is arguably a prerequisite for the AVX512 work, as turning
> pg_popcount() into a function pointer will likely regress performance for
> folks on systems without AVX512 otherwise.

I think so too.

David

---

From: Nathan Bossart <[email-masked]>
Date: Mon, 18 Mar 2024 16:08:10 -0500

> running windows and a Zen2 running on Linux. As follows:

Thanks for taking a look.

> pg_popcount_slow() do it and not pg_popcount_fast().

The only reason I left it out was because I couldn't convince myself that
it wasn't dead code, given we assume that popcntq is available in
pg_popcount64_fast() today.  But I don't see any harm in adding that just
in case.

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

---

From: David Rowley <[email-masked]>
Date: Tue, 19 Mar 2024 10:27:58 +1300

> pg_popcount64_fast() today.  But I don't see any harm in adding that just

It's probably more of a case of using native instructions rather than
ones that might be implemented only via microcode.  For the record, I
don't know if that would be the case for popcntq on x86 32-bit and I
don't have the hardware to test it. It just seems less risky just to
do it.

David

---

From: Nathan Bossart <[email-masked]>
Date: Mon, 18 Mar 2024 16:29:19 -0500

> don't have the hardware to test it. It just seems less risky just to

Agreed.  Will send an updated patch shortly.

---

From: Nathan Bossart <[email-masked]>
Date: Mon, 18 Mar 2024 17:08:45 -0500

> Agreed.  Will send an updated patch shortly.

As promised...

>From b673663b1d1344549cbd0912220f96ba1712afc6 Mon Sep 17 00:00:00 2001
From: Nathan Bossart <[email-masked]>
Date: Mon, 18 Mar 2024 12:18:15 -0500
Subject: [PATCH v4 1/1] inline function calls in pg_popcount() when possible

---
 src/include/port/pg_bitutils.h |   5 +-
 src/port/pg_bitutils.c         | 155 +++++++++++++++++++++++++--------
 2 files changed, 121 insertions(+), 39 deletions(-)

diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.h
index 46bf4f0103..53e5239717 100644
--- a/src/include/port/pg_bitutils.h
+++ b/src/include/port/pg_bitutils.h
@@ -302,17 +302,16 @@ pg_ceil_log2_64(uint64 num)
 /* Attempt to use the POPCNT instruction, but perform a runtime check first */
 extern PGDLLIMPORT int (*pg_popcount32) (uint32 word);
 extern PGDLLIMPORT int (*pg_popcount64) (uint64 word);
+extern PGDLLIMPORT uint64 (*pg_popcount) (const char *buf, int bytes);
 
 #else
 /* Use a portable implementation -- no need for a function pointer. */
 extern int	pg_popcount32(uint32 word);
 extern int	pg_popcount64(uint64 word);
+extern uint64 pg_popcount(const char *buf, int bytes);
 
 #endif							/* TRY_POPCNT_FAST */
 
-/* Count the number of one-bits in a byte array */
-extern uint64 pg_popcount(const char *buf, int bytes);
-
 /*
  * Rotate the bits of "word" to the right/left by n bits.
  */
diff --git a/src/port/pg_bitutils.c b/src/port/pg_bitutils.c
index 640a89561a..1197696e97 100644
--- a/src/port/pg_bitutils.c
+++ b/src/port/pg_bitutils.c
@@ -103,18 +103,22 @@ const uint8 pg_number_of_ones[256] = {
 	4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
 };
 
-static int	pg_popcount32_slow(uint32 word);
-static int	pg_popcount64_slow(uint64 word);
+static inline int pg_popcount32_slow(uint32 word);
+static inline int pg_popcount64_slow(uint64 word);
+static uint64 pg_popcount_slow(const char *buf, int bytes);
 
 #ifdef TRY_POPCNT_FAST
 static bool pg_popcount_available(void);
 static int	pg_popcount32_choose(uint32 word);
 static int	pg_popcount64_choose(uint64 word);
-static int	pg_popcount32_fast(uint32 word);
-static int	pg_popcount64_fast(uint64 word);
+static uint64 pg_popcount_choose(const char *buf, int bytes);
+static inline int pg_popcount32_fast(uint32 word);
+static inline int pg_popcount64_fast(uint64 word);
+static uint64 pg_popcount_fast(const char *buf, int bytes);
 
 int			(*pg_popcount32) (uint32 word) = pg_popcount32_choose;
 int			(*pg_popcount64) (uint64 word) = pg_popcount64_choose;
+uint64		(*pg_popcount) (const char *buf, int bytes) = pg_popcount_choose;
 #endif							/* TRY_POPCNT_FAST */
 
 #ifdef TRY_POPCNT_FAST
@@ -151,11 +155,13 @@ pg_popcount32_choose(uint32 word)
 	{
 		pg_popcount32 = pg_popcount32_fast;
 		pg_popcount64 = pg_popcount64_fast;
+		pg_popcount = pg_popcount_fast;
 	}
 	else
 	{
 		pg_popcount32 = pg_popcount32_slow;
 		pg_popcount64 = pg_popcount64_slow;
+		pg_popcount = pg_popcount_slow;
 	}
 
 	return pg_popcount32(word);
@@ -168,21 +174,42 @@ pg_popcount64_choose(uint64 word)
 	{
 		pg_popcount32 = pg_popcount32_fast;
 		pg_popcount64 = pg_popcount64_fast;
+		pg_popcount = pg_popcount_fast;
 	}
 	else
 	{
 		pg_popcount32 = pg_popcount32_slow;
 		pg_popcount64 = pg_popcount64_slow;
+		pg_popcount = pg_popcount_slow;
 	}
 
 	return pg_popcount64(word);
 }
 
+static uint64
+pg_popcount_choose(const char *buf, int bytes)
+{
+	if (pg_popcount_available())
+	{
+		pg_popcount32 = pg_popcount32_fast;
+		pg_popcount64 = pg_popcount64_fast;
+		pg_popcount = pg_popcount_fast;
+	}
+	else
+	{
+		pg_popcount32 = pg_popcount32_slow;
+		pg_popcount64 = pg_popcount64_slow;
+		pg_popcount = pg_popcount_slow;
+	}
+
+	return pg_popcount(buf, bytes);
+}
+
 /*
  * pg_popcount32_fast
  *		Return the number of 1 bits set in word
  */
-static int
+static inline int
 pg_popcount32_fast(uint32 word)
 {
 #ifdef _MSC_VER
@@ -199,7 +226,7 @@ __asm__ __volatile__(" popcntl %1,%0\n":"=q"(res):"rm"(word):"cc");
  * pg_popcount64_fast
  *		Return the number of 1 bits set in word
  */
-static int
+static inline int
 pg_popcount64_fast(uint64 word)
 {
 #ifdef _MSC_VER
@@ -212,6 +239,52 @@ __asm__ __volatile__(" popcntq %1,%0\n":"=q"(res):"rm"(word):"cc");
 #endif
 }
 
+/*
+ * pg_popcount_fast
+ *		Returns the number of 1-bits in buf
+ */
+static uint64
+pg_popcount_fast(const char *buf, int bytes)
+{
+	uint64		popcnt = 0;
+
+#if SIZEOF_VOID_P >= 8
+	/* Process in 64-bit chunks if the buffer is aligned. */
+	if (buf == (const char *) TYPEALIGN(8, buf))
+	{
+		const uint64 *words = (const uint64 *) buf;
+
+		while (bytes >= 8)
+		{
+			popcnt += pg_popcount64_fast(*words++);
+			bytes -= 8;
+		}
+
+		buf = (const char *) words;
+	}
+#else
+	/* Process in 32-bit chunks if the buffer is aligned. */
+	if (buf == (const char *) TYPEALIGN(4, buf))
+	{
+		const uint32 *words = (const uint32 *) buf;
+
+		while (bytes >= 4)
+		{
+			popcnt += pg_popcount32_fast(*words++);
+			bytes -= 4;
+		}
+
+		buf = (const char *) words;
+	}
+#endif
+
+	/* Process any remaining bytes */
+	while (bytes--)
+		popcnt += pg_number_of_ones[(unsigned char) *buf++];
+
+	return popcnt;
+}
+
 #endif							/* TRY_POPCNT_FAST */

@@ -219,7 +292,7 @@ __asm__ __volatile__(" popcntq %1,%0\n":"=q"(res):"rm"(word):"cc");
  * pg_popcount32_slow
  *		Return the number of 1 bits set in word
  */
-static int
+static inline int
 pg_popcount32_slow(uint32 word)
 {
 #ifdef HAVE__BUILTIN_POPCOUNT
@@ -241,7 +314,7 @@ pg_popcount32_slow(uint32 word)
  * pg_popcount64_slow
  *		Return the number of 1 bits set in word
  */
-static int
+static inline int
 pg_popcount64_slow(uint64 word)
 {
 #ifdef HAVE__BUILTIN_POPCOUNT
@@ -265,35 +338,12 @@ pg_popcount64_slow(uint64 word)
 #endif							/* HAVE__BUILTIN_POPCOUNT */
 }
 
-#ifndef TRY_POPCNT_FAST
-
 /*
- * When the POPCNT instruction is not available, there's no point in using
- * function pointers to vary the implementation between the fast and slow
- * method.  We instead just make these actual external functions when
- * TRY_POPCNT_FAST is not defined.  The compiler should be able to inline
- * the slow versions here.
- */
-int
-pg_popcount32(uint32 word)
-{
-	return pg_popcount32_slow(word);
-}
-
-int
-pg_popcount64(uint64 word)
-{
-	return pg_popcount64_slow(word);
-}
-
-#endif							/* !TRY_POPCNT_FAST */
-
-/*
- * pg_popcount
+ * pg_popcount_slow
  *		Returns the number of 1-bits in buf
  */
-uint64
-pg_popcount(const char *buf, int bytes)
+static uint64
+pg_popcount_slow(const char *buf, int bytes)
 {
 	uint64		popcnt = 0;
 
@@ -305,7 +355,7 @@ pg_popcount(const char *buf, int bytes)
 
 		while (bytes >= 8)
 		{
-			popcnt += pg_popcount64(*words++);
+			popcnt += pg_popcount64_slow(*words++);
 			bytes -= 8;
 		}
 
@@ -319,7 +369,7 @@ pg_popcount(const char *buf, int bytes)
 
 		while (bytes >= 4)
 		{
-			popcnt += pg_popcount32(*words++);
+			popcnt += pg_popcount32_slow(*words++);
 			bytes -= 4;
 		}
 
@@ -333,3 +383,36 @@ pg_popcount(const char *buf, int bytes)
 
 	return popcnt;
 }
+
+#ifndef TRY_POPCNT_FAST
+
+/*
+ * When the POPCNT instruction is not available, there's no point in using
+ * function pointers to vary the implementation between the fast and slow
+ * method.  We instead just make these actual external functions when
+ * TRY_POPCNT_FAST is not defined.  The compiler should be able to inline
+ * the slow versions here.
+ */
+int
+pg_popcount32(uint32 word)
+{
+	return pg_popcount32_slow(word);
+}
+
+int
+pg_popcount64(uint64 word)
+{
+	return pg_popcount64_slow(word);
+}
+
+/*
+ * pg_popcount
+ *		Returns the number of 1-bits in buf
+ */
+uint64
+pg_popcount(const char *buf, int bytes)
+{
+	return pg_popcount_slow(buf, bytes);
+}
+
+#endif							/* !TRY_POPCNT_FAST */
-- 
2.25.1