public inbox for [email protected]
help / color / mirror / Atom feedFrom: Amonson, Paul D <[email protected]>
To: Nathan Bossart <[email protected]>
Cc: Andres Freund <[email protected]>
Cc: Alvaro Herrera <[email protected]>
Cc: Shankaran, Akash <[email protected]>
Cc: Noah Misch <[email protected]>
Cc: Tom Lane <[email protected]>
Cc: Matthias van de Meent <[email protected]>
Cc: [email protected] <[email protected]>
Subject: RE: Popcount optimization using AVX512
Date: Mon, 11 Mar 2024 21:59:53 +0000
Message-ID: <BL1PR11MB5304165E7A81E0107E70B069DC242@BL1PR11MB5304.namprd11.prod.outlook.com> (raw)
In-Reply-To: <20240307213600.GA563369@nathanxps13>
References: <BL1PR11MB5304F0889AB4EB200AF44565DC572@BL1PR11MB5304.namprd11.prod.outlook.com>
<BL1PR11MB5304C768A3002CD2C6EF672FDC5A2@BL1PR11MB5304.namprd11.prod.outlook.com>
<BL1PR11MB53046A243932039BD545EBF4DC592@BL1PR11MB5304.namprd11.prod.outlook.com>
<20240301214457.GA3024365@nathanxps13>
<BL1PR11MB5304BFE26BAC25624508CFD2DC232@BL1PR11MB5304.namprd11.prod.outlook.com>
<20240304222118.GB3367383@nathanxps13>
<BL1PR11MB53047C28DDBA6A2E77B9420ADC222@BL1PR11MB5304.namprd11.prod.outlook.com>
<20240305163730.GA3479896@nathanxps13>
<BL1PR11MB530444AEE08A91242ABA1915DC222@BL1PR11MB5304.namprd11.prod.outlook.com>
<20240307173318.GA455851@nathanxps13>
<20240307213600.GA563369@nathanxps13>
> -----Original Message-----
> From: Nathan Bossart <[email protected]>
> Sent: Thursday, March 7, 2024 1:36 PM
> Subject: Re: Popcount optimization using AVX512
I will be splitting the request into 2 patches. I am attaching the first patch (refactoring only) and I updated the commitfest entry to match this patch. I have a question however:
Do I need to wait for the refactor patch to be merged before I post the AVX portion of this feature in this thread?
> > + PGAC_AVX512_POPCNT_INTRINSICS([-mavx512vpopcntdq -mavx512f])
>
> I'm curious why we need both -mavx512vpopcntdq and -mavx512f. On my
> machine, -mavx512vpopcntdq alone is enough to pass this test, so if there are
> other instructions required that need -mavx512f, then we might need to
> expand the test.
First, nice catch on the required flags to build! When I changed my algorithm, dependence on the -mavx512f flag was no longer needed, In the second patch (AVX specific) I will fix this.
> I still think it's worth breaking this change into at least 2 patches. In particular,
> I think there's an opportunity to do the refactoring into pg_popcnt_choose.c
> and pg_popcnt_x86_64_accel.c prior to adding the AVX512 stuff. These
> changes are likely straightforward, and getting them out of the way early
> would make it easier to focus on the more interesting changes. IMHO there
> are a lot of moving parts in this patch.
As stated above I am doing this in 2 patches. :)
> > +#undef HAVE__GET_CPUID_COUNT
> > +
> > +/* Define to 1 if you have immintrin. */ #undef HAVE__IMMINTRIN
>
> Is this missing HAVE__CPUIDEX?
Yes I missed it, I will include in the second patch (AVX specific) of the 2 patches.
> > uint64
> > -pg_popcount(const char *buf, int bytes)
> > +pg_popcount_slow(const char *buf, int bytes)
> > {
> > uint64 popcnt = 0;
> >
> > -#if SIZEOF_VOID_P >= 8
> > +#if SIZEOF_VOID_P == 8
> > /* Process in 64-bit chunks if the buffer is aligned. */
> > if (buf == (const char *) TYPEALIGN(8, buf))
> > {
> > @@ -311,7 +224,7 @@ pg_popcount(const char *buf, int bytes)
> >
> > buf = (const char *) words;
> > }
> > -#else
> > +#elif SIZEOF_VOID_P == 4
> > /* Process in 32-bit chunks if the buffer is aligned. */
> > if (buf == (const char *) TYPEALIGN(4, buf))
> > {
>
> Apologies for harping on this, but I'm still not seeing the need for these
> SIZEOF_VOID_P changes. While it's unlikely that this makes any practical
> difference, I see no reason to more strictly check SIZEOF_VOID_P here.
I got rid of the second occurrence as I agree it is not needed but unless you see something I don't how to know which function to call between a 32-bit and 64-bit architecture? Maybe I am missing something obvious? What exactly do you suggest here? I am happy to always call either pg_popcount32() or pg_popcount64() with the understanding that it may not be optimal, but I do need to know which to use.
> > + /* Process any remaining bytes */
> > + while (bytes--)
> > + popcnt += pg_number_of_ones[(unsigned char) *buf++];
> > + return popcnt;
> > +#else
> > + return pg_popcount_slow(buf, bytes);
> > +#endif /* USE_AVX512_CODE */
>
> nitpick: Could we call pg_popcount_slow() in a common section for these
> "remaining bytes?"
Agreed, will fix in the second patch as well.
> > +#if defined(_MSC_VER)
> > + pg_popcount_indirect = pg_popcount512_fast; #else
> > + pg_popcount = pg_popcount512_fast; #endif
> These _MSC_VER sections are interesting. I'm assuming this is the
> workaround for the MSVC linking issue you mentioned above. I haven't
> looked too closely, but I wonder if the CRC32C code (see
> src/include/port/pg_crc32c.h) is doing something different to avoid this issue.
Using the latest master branch, I see what the needed changes are, I will implement using PGDLLIMPORT macro in the second patch.
> Upthread, Alvaro suggested a benchmark [0] that might be useful. I scanned
> through this thread and didn't see any recent benchmark results for the latest
> form of the patch. I think it's worth verifying that we are still seeing the
> expected improvements.
I will get new benchmarks using the same process I used before (from Akash) so I get apples to apples. These are pending completion of the second patch which is still in progress.
Just a reminder, I asked questions above about 1) multi-part dependent patches and, 2) What specifically to do about the SIZE_VOID_P checks. :)
Thanks,
Paul
Attachments:
[application/octet-stream] v7-0001-Refactor-POPCNT.patch (7.7K, ../BL1PR11MB5304165E7A81E0107E70B069DC242@BL1PR11MB5304.namprd11.prod.outlook.com/2-v7-0001-Refactor-POPCNT.patch)
download | inline diff:
diff --git a/src/port/Makefile b/src/port/Makefile
index dcc8737e68..12c56b0ba7 100644
--- a/src/port/Makefile
+++ b/src/port/Makefile
@@ -44,6 +44,8 @@ OBJS = \
noblock.o \
path.o \
pg_bitutils.o \
+ pg_popcnt_choose.o \
+ pg_popcnt_x86_64_accel.o \
pg_strong_random.o \
pgcheckdir.o \
pgmkdirp.o \
diff --git a/src/port/meson.build b/src/port/meson.build
index 92b593e6ef..ed8828c739 100644
--- a/src/port/meson.build
+++ b/src/port/meson.build
@@ -7,6 +7,8 @@ pgport_sources = [
'noblock.c',
'path.c',
'pg_bitutils.c',
+ 'pg_popcnt_choose.c',
+ 'pg_popcnt_x86_64_accel.c',
'pg_strong_random.c',
'pgcheckdir.c',
'pgmkdirp.c',
diff --git a/src/port/pg_bitutils.c b/src/port/pg_bitutils.c
index 640a89561a..5ace0a5b13 100644
--- a/src/port/pg_bitutils.c
+++ b/src/port/pg_bitutils.c
@@ -12,13 +12,6 @@
*/
#include "c.h"
-#ifdef HAVE__GET_CPUID
-#include <cpuid.h>
-#endif
-#ifdef HAVE__CPUID
-#include <intrin.h>
-#endif
-
#include "port/pg_bitutils.h"
@@ -103,123 +96,14 @@ 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);
-
-#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);
-
-int (*pg_popcount32) (uint32 word) = pg_popcount32_choose;
-int (*pg_popcount64) (uint64 word) = pg_popcount64_choose;
-#endif /* TRY_POPCNT_FAST */
-
-#ifdef TRY_POPCNT_FAST
-
-/*
- * Return true if CPUID indicates that the POPCNT instruction is available.
- */
-static bool
-pg_popcount_available(void)
-{
- unsigned int exx[4] = {0, 0, 0, 0};
-
-#if defined(HAVE__GET_CPUID)
- __get_cpuid(1, &exx[0], &exx[1], &exx[2], &exx[3]);
-#elif defined(HAVE__CPUID)
- __cpuid(exx, 1);
-#else
-#error cpuid instruction not available
-#endif
-
- return (exx[2] & (1 << 23)) != 0; /* POPCNT */
-}
-
-/*
- * These functions get called on the first call to pg_popcount32 etc.
- * They detect whether we can use the asm implementations, and replace
- * the function pointers so that subsequent calls are routed directly to
- * the chosen implementation.
- */
-static int
-pg_popcount32_choose(uint32 word)
-{
- if (pg_popcount_available())
- {
- pg_popcount32 = pg_popcount32_fast;
- pg_popcount64 = pg_popcount64_fast;
- }
- else
- {
- pg_popcount32 = pg_popcount32_slow;
- pg_popcount64 = pg_popcount64_slow;
- }
-
- return pg_popcount32(word);
-}
-
-static int
-pg_popcount64_choose(uint64 word)
-{
- if (pg_popcount_available())
- {
- pg_popcount32 = pg_popcount32_fast;
- pg_popcount64 = pg_popcount64_fast;
- }
- else
- {
- pg_popcount32 = pg_popcount32_slow;
- pg_popcount64 = pg_popcount64_slow;
- }
-
- return pg_popcount64(word);
-}
-
-/*
- * pg_popcount32_fast
- * Return the number of 1 bits set in word
- */
-static int
-pg_popcount32_fast(uint32 word)
-{
-#ifdef _MSC_VER
- return __popcnt(word);
-#else
- uint32 res;
-
-__asm__ __volatile__(" popcntl %1,%0\n":"=q"(res):"rm"(word):"cc");
- return (int) res;
-#endif
-}
-
-/*
- * pg_popcount64_fast
- * Return the number of 1 bits set in word
- */
-static int
-pg_popcount64_fast(uint64 word)
-{
-#ifdef _MSC_VER
- return __popcnt64(word);
-#else
- uint64 res;
-
-__asm__ __volatile__(" popcntq %1,%0\n":"=q"(res):"rm"(word):"cc");
- return (int) res;
-#endif
-}
-
-#endif /* TRY_POPCNT_FAST */
-
+extern int pg_popcount32_slow(uint32 word);
+extern int pg_popcount64_slow(uint64 word);
/*
* pg_popcount32_slow
* Return the number of 1 bits set in word
*/
-static int
+int
pg_popcount32_slow(uint32 word)
{
#ifdef HAVE__BUILTIN_POPCOUNT
@@ -241,7 +125,7 @@ pg_popcount32_slow(uint32 word)
* pg_popcount64_slow
* Return the number of 1 bits set in word
*/
-static int
+int
pg_popcount64_slow(uint64 word)
{
#ifdef HAVE__BUILTIN_POPCOUNT
diff --git a/src/port/pg_popcnt_choose.c b/src/port/pg_popcnt_choose.c
new file mode 100644
index 0000000000..70c70f5742
--- /dev/null
+++ b/src/port/pg_popcnt_choose.c
@@ -0,0 +1,97 @@
+/*-------------------------------------------------------------------------
+ *
+ * pg_popcnt_choose.c
+ * For FAST operations, these methods do runtime checks and set the
+ * appropriate function pointers.
+ *
+ * Copyright (c) 2019-2024, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ * src/port/pg_popcnt_choose.c
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "c.h"
+
+#ifdef HAVE__GET_CPUID
+#include <cpuid.h>
+#endif
+#ifdef HAVE__CPUID
+#include <intrin.h>
+#endif
+
+#include "port/pg_bitutils.h"
+
+
+/* In pg_bitutils.c file */
+extern int pg_popcount32_slow(uint32 word);
+extern int pg_popcount64_slow(uint64 word);
+
+#ifdef TRY_POPCNT_FAST
+static bool pg_popcount_available(void);
+static int pg_popcount32_choose(uint32 word);
+static int pg_popcount64_choose(uint64 word);
+
+/* In pg_popcnt_*_accel source file. */
+extern int pg_popcount32_fast(uint32 word);
+extern int pg_popcount64_fast(uint64 word);
+
+int (*pg_popcount32) (uint32 word) = pg_popcount32_choose;
+int (*pg_popcount64) (uint64 word) = pg_popcount64_choose;
+#endif /* TRY_POPCNT_FAST */
+
+#ifdef TRY_POPCNT_FAST
+
+/*
+ * Return true if CPUID indicates that the POPCNT instruction is available.
+ */
+static bool
+pg_popcount_available(void)
+{
+ unsigned int exx[4] = {0, 0, 0, 0};
+
+#if defined(HAVE__GET_CPUID)
+ __get_cpuid(1, &exx[0], &exx[1], &exx[2], &exx[3]);
+#elif defined(HAVE__CPUID)
+ __cpuid(exx, 1);
+#else
+#error cpuid instruction not available
+#endif
+
+ return (exx[2] & (1 << 23)) != 0; /* POPCNT */
+}
+
+/*
+ * These functions get called on the first call to pg_popcount32 etc.
+ * They detect whether we can use the asm implementations, and replace
+ * the function pointers so that subsequent calls are routed directly to
+ * the chosen implementation.
+ */
+static void setup_function_pointers()
+{
+ if (pg_popcount_available())
+ {
+ pg_popcount32 = pg_popcount32_fast;
+ pg_popcount64 = pg_popcount64_fast;
+ }
+ else
+ {
+ pg_popcount32 = pg_popcount32_slow;
+ pg_popcount64 = pg_popcount64_slow;
+ }
+}
+
+static int
+pg_popcount32_choose(uint32 word)
+{
+ setup_function_pointers();
+ return pg_popcount32(word);
+}
+
+static int
+pg_popcount64_choose(uint64 word)
+{
+ setup_function_pointers();
+ return pg_popcount64(word);
+}
+#endif /* TRY_POPCNT_FAST */
diff --git a/src/port/pg_popcnt_x86_64_accel.c b/src/port/pg_popcnt_x86_64_accel.c
new file mode 100644
index 0000000000..6e36e90e16
--- /dev/null
+++ b/src/port/pg_popcnt_x86_64_accel.c
@@ -0,0 +1,55 @@
+/*-------------------------------------------------------------------------
+ *
+ * pg_popcnt_x86_64_accel.c
+ * Fast POPCNT methods for x86_64.
+ *
+ * Copyright (c) 2019-2024, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ * src/port/pg_popcnt_x86_64_accel.c
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "c.h"
+
+#include "port/pg_bitutils.h"
+
+extern int pg_popcount32_fast(uint32 word);
+extern int pg_popcount64_fast(uint64 word);
+
+#ifdef TRY_POPCNT_FAST
+/*
+ * pg_popcount32_fast
+ * Return the number of 1 bits set in word
+ */
+int
+pg_popcount32_fast(uint32 word)
+{
+#ifdef _MSC_VER
+ return __popcnt(word);
+#else
+ uint32 res;
+
+__asm__ __volatile__(" popcntl %1,%0\n":"=q"(res):"rm"(word):"cc");
+ return (int) res;
+#endif
+}
+
+/*
+ * pg_popcount64_fast
+ * Return the number of 1 bits set in word
+ */
+int
+pg_popcount64_fast(uint64 word)
+{
+#ifdef _MSC_VER
+ return __popcnt64(word);
+#else
+ uint64 res;
+
+__asm__ __volatile__(" popcntq %1,%0\n":"=q"(res):"rm"(word):"cc");
+ return (int) res;
+#endif
+}
+
+#endif /* TRY_POPCNT_FAST */
view thread (26+ messages) latest in thread
reply
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: [email protected]
Cc: [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected]
Subject: RE: Popcount optimization using AVX512
In-Reply-To: <BL1PR11MB5304165E7A81E0107E70B069DC242@BL1PR11MB5304.namprd11.prod.outlook.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox