On Mon, Mar 18, 2024 at 12:30:04PM -0500, Nathan Bossart 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.
>
> 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.
Apologies for the noise. I noticed that we could (and probably should)
inline the pg_popcount32/64 calls in the "slow" version, too.
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
>From 3047674f0950435b7fa30746be7f8e5cc7249e6d Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nat...@postgresql.org>
Date: Mon, 18 Mar 2024 12:18:15 -0500
Subject: [PATCH 1/1] inline function calls in pg_popcount() when possible
---
src/include/port/pg_bitutils.h | 5 +-
src/port/pg_bitutils.c | 135 ++++++++++++++++++++++++---------
2 files changed, 103 insertions(+), 37 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..d0c93dafcb 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 uint64 pg_popcount_choose(const char *buf, int bytes);
static int pg_popcount32_fast(uint32 word);
-static int pg_popcount64_fast(uint64 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,16 +174,37 @@ 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
@@ -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,36 @@ __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;
+
+ /* 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;
+ }
+
+ /* Process any remaining bytes */
+ while (bytes--)
+ popcnt += pg_number_of_ones[(unsigned char) *buf++];
+
+ return popcnt;
+}
+
#endif /* TRY_POPCNT_FAST */
@@ -219,7 +276,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 +298,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 +322,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 +339,7 @@ pg_popcount(const char *buf, int bytes)
while (bytes >= 8)
{
- popcnt += pg_popcount64(*words++);
+ popcnt += pg_popcount64_slow(*words++);
bytes -= 8;
}
@@ -319,7 +353,7 @@ pg_popcount(const char *buf, int bytes)
while (bytes >= 4)
{
- popcnt += pg_popcount32(*words++);
+ popcnt += pg_popcount32_slow(*words++);
bytes -= 4;
}
@@ -333,3 +367,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
