From: Nathan Bossart <nathandbossart@gmail.com>
To: Amonson, Paul D <paul.d.amonson@intel.com>
Cc: David Rowley <dgrowleyml@gmail.com>
Cc: Andres Freund <andres@anarazel.de>
Cc: Alvaro Herrera <alvherre@alvh.no-ip.org>
Cc: Shankaran, Akash <akash.shankaran@intel.com>
Cc: Noah Misch <noah@leadboat.com>
Cc: Tom Lane <tgl@sss.pgh.pa.us>
Cc: Matthias van de Meent <boekewurm+postgres@gmail.com>
Cc: pgsql-hackers@lists.postgresql.org <pgsql-hackers@lists.postgresql.org>
Subject: Re: Popcount optimization using AVX512
Date: Mon, 18 Mar 2024 12:30:04 -0500
Message-ID: <20240318173004.GA361138@nathanxps13> (raw)
In-Reply-To: <20240318162018.GA204772@nathanxps13>
References: <20240307173318.GA455851@nathanxps13>
<20240307213600.GA563369@nathanxps13>
<BL1PR11MB5304165E7A81E0107E70B069DC242@BL1PR11MB5304.namprd11.prod.outlook.com>
<20240312013436.GA1787866@nathanxps13>
<BL1PR11MB53042473B7B53B96E43648A7DC292@BL1PR11MB5304.namprd11.prod.outlook.com>
<20240315150611.GA3495582@nathanxps13>
<CAApHDvrb7MJRB6JuKLDEY2x_LKdFHwVbogpjZBCX547i5+rXOQ@mail.gmail.com>
<20240318152902.GA2850@nathanxps13>
<BL1PR11MB5304070E33F7DD0520445B77DC2D2@BL1PR11MB5304.namprd11.prod.outlook.com>
<20240318162018.GA204772@nathanxps13>
On Mon, Mar 18, 2024 at 11:20:18AM -0500, Nathan Bossart wrote:
> I don't think David was suggesting that we need to remove the runtime
> checks for AVX512. IIUC he was pointing out that most of the performance
> gain is from removing the function call overhead, which your v8-0002 patch
> already does for the proposed AVX512 code. We can apply a similar
> optimization for systems without AVX512 by inlining the code for
> pg_popcount64() and pg_popcount32().
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.
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.comAttachments:0001-inline-function-calls-in-pg_popcount-when-possible.patch (text/x-diff, 6.0K) download
From 1d33c803feb7428f798b13fd643a16c73628f8a9 Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathan@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 | 123 +++++++++++++++++++++++++--------
2 files changed, 97 insertions(+), 31 deletions(-)
diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.hindex 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.cindex 640a89561a..e374e753d7 100644--- a/src/port/pg_bitutils.c+++ b/src/port/pg_bitutils.c@@ -105,16 +105,20 @@ const uint8 pg_number_of_ones[256] = {
static int pg_popcount32_slow(uint32 word);
static 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 */
@@ -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;
@@ -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
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: nathandbossart@gmail.com, paul.d.amonson@intel.com, dgrowleyml@gmail.com, andres@anarazel.de, alvherre@alvh.no-ip.org, akash.shankaran@intel.com, noah@leadboat.com, tgl@sss.pgh.pa.us, boekewurm+postgres@gmail.com, pgsql-hackers@lists.postgresql.org
Subject: Re: Popcount optimization using AVX512
In-Reply-To: <20240318173004.GA361138@nathanxps13>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox