Subject: RE: Popcount optimization using AVX512

From: "Amonson, Paul D" <[email-masked]>
Date: Mon, 4 Mar 2024 21:39:36 +0000

Hi,

First, apologies on the patch. Find re-attached updated version.
 
Now I have some questions....
#1
 
> -#define LARGE_OFF_T (((off_t) 1 << 62) - 1 + ((off_t) 1 << 62))
> +#define LARGE_OFF_T ((((off_t) 1 << 31) << 31) - 1 + (((off_t) 1 << 31)
> +<< 31))
>
> IME this means that the autoconf you are using has been patched.  A quick search on the mailing lists seems to indicate that it might be specific to Debian [1].
 
I am not sure what the ask is here?  I made changes to the configure.ac and ran autoconf2.69 to get builds to succeed. Do you have a separate feedback here? 
 
#2 
As for the refactoring, this was done to satisfy previous review feedback about applying the AVX512 CFLAGS to the entire pg_bitutils.c file. Mainly to avoid segfault due to the AVX512 flags. If its ok, I would prefer to make a single commit as the change is pretty small and straight forward.
 
#3
I am not sure I understand the comment about the SIZE_VOID_P checks. Aren't they necessary to choose which functions to call based on 32 or 64 bit architectures?
 
#4
Would this change qualify for Workflow A as described in [0] and can be picked up by a committer, given it has been reviewed by multiple committers so far? The scope of the change is pretty contained as well. 
 
[0] https://wiki.postgresql.org/wiki/Submitting_a_Patch

Thanks,
Paul

-----Original Message-----
From: Nathan Bossart <[email-masked]> 
Sent: Friday, March 1, 2024 1:45 PM
To: Amonson, Paul D <[email-masked]>
Cc: Andres Freund <[email-masked]>; Alvaro Herrera <[email-masked]>; Shankaran, Akash <[email-masked]>; Noah Misch <[email-masked]>; Tom Lane <[email-masked]>; Matthias van de Meent <[email-masked]>; [email-masked]
Subject: Re: Popcount optimization using AVX512

Thanks for the new version of the patch.  I didn't see a commitfest entry for this one, and unfortunately I think it's too late to add it for the March commitfest.  I would encourage you to add it to July's commitfest [0] so that we can get some routine cfbot coverage.

On Tue, Feb 27, 2024 at 08:46:06PM +0000, Amonson, Paul D wrote:
> After consulting some Intel internal experts on MSVC the linking issue 
> as it stood was not resolved. Instead, I created a MSVC ONLY work-around.
> This adds one extra functional call on the Windows builds (The linker 
> resolves a real function just fine but not a function pointer of the 
> same name). This extra latency does not exist on any of the other 
> platforms. I also believe I addressed all issues raised in the 
> previous reviews. The new pg_popcnt_x86_64_accel.c file is now the 
> ONLY file compiled with the
> AVX512 compiler flags. I added support for the MSVC compiler flag as 
> well. Both meson and autoconf are updated with the new refactor.
> 
> I am attaching the new patch.

I think this patch might be missing the new files.

-#define LARGE_OFF_T (((off_t) 1 << 62) - 1 + ((off_t) 1 << 62))
+#define LARGE_OFF_T ((((off_t) 1 << 31) << 31) - 1 + (((off_t) 1 << 31) 
+<< 31))

IME this means that the autoconf you are using has been patched.  A quick search on the mailing lists seems to indicate that it might be specific to Debian [1].

-static int	pg_popcount32_slow(uint32 word);
-static int	pg_popcount64_slow(uint64 word);
+int	pg_popcount32_slow(uint32 word);
+int	pg_popcount64_slow(uint64 word);
+uint64 pg_popcount_slow(const char *buf, int bytes);

This patch appears to do a lot of refactoring.  Would it be possible to break out the refactoring parts into a prerequisite patch that could be reviewed and committed independently from the AVX512 stuff?

-#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))
+	if (buf == (const char *)TYPEALIGN(8, buf))
 	{
-		const uint64 *words = (const uint64 *) buf;
+		const uint64 *words = (const uint64 *)buf;
 
 		while (bytes >= 8)
 		{
@@ -309,9 +213,9 @@ pg_popcount(const char *buf, int bytes)
 			bytes -= 8;
 		}
 
-		buf = (const char *) words;
+		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))
 	{

Most, if not all, of these changes seem extraneous.  Do we actually need to more strictly check SIZEOF_VOID_P?

[0] https://commitfest.postgresql.org/48/
[1] https://postgr.es/m/20230211020042.uthdgj72kp3xlqam%40awork3.anarazel.de

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

---

From: Nathan Bossart <[email-masked]>
Date: Mon, 4 Mar 2024 16:21:18 -0600

(Please don't top-post on the Postgres lists.)

> First, apologies on the patch. Find re-attached updated version.

Thanks for the new version of the patch.

>> IME this means that the autoconf you are using has been patched.  A
>> quick search on the mailing lists seems to indicate that it might be
>> specific to Debian [1].
>  
> I am not sure what the ask is here?  I made changes to the configure.ac
> and ran autoconf2.69 to get builds to succeed. Do you have a separate
> feedback here?

These LARGE_OFF_T changes are unrelated to the patch at hand and should be
removed.  This likely means that you are using a patched autoconf that is
making these extra changes.
 
> As for the refactoring, this was done to satisfy previous review feedback
> about applying the AVX512 CFLAGS to the entire pg_bitutils.c file. Mainly
> to avoid segfault due to the AVX512 flags. If its ok, I would prefer to
> make a single commit as the change is pretty small and straight forward.

Okay.  The only reason I suggest this is to ease review.  For example, if
there is some required refactoring that doesn't involve any functionality
changes, it can be advantageous to get that part reviewed and committed
first so that reviewers can better focus on the code for the new feature.
But, of course, that isn't necessary and/or isn't possible in all cases.

> I am not sure I understand the comment about the SIZE_VOID_P checks.
> Aren't they necessary to choose which functions to call based on 32 or 64
> bit architectures?

Yes.  My comment was that the patch appeared to make unnecessary changes to
this code.  Perhaps I am misunderstanding something here.

> Would this change qualify for Workflow A as described in [0] and can be
> picked up by a committer, given it has been reviewed by multiple
> committers so far? The scope of the change is pretty contained as well.

I think so.  I would still encourage you to create an entry for this so
that it is automatically tested via cfbot [0].

[0] http://commitfest.cputube.org/

---

From: "Amonson, Paul D" <[email-masked]>
Date: Tue, 5 Mar 2024 16:31:15 +0000

Hi,

I am not sure what "top-post" means but I am not doing anything different but using "reply to all" in Outlook. Please enlighten me. 😊

This is the new patch with the hand edit to remove the offending lines from the patch file. I did a basic test to make the patch would apply and build. It succeeded.

Thanks,
Paul

-----Original Message-----
From: Nathan Bossart <[email-masked]> 
Sent: Monday, March 4, 2024 2:21 PM
To: Amonson, Paul D <[email-masked]>
Cc: Andres Freund <[email-masked]>; Alvaro Herrera <[email-masked]>; Shankaran, Akash <[email-masked]>; Noah Misch <[email-masked]>; Tom Lane <[email-masked]>; Matthias van de Meent <[email-masked]>; [email-masked]
Subject: Re: Popcount optimization using AVX512

>> +#define LARGE_OFF_T ((((off_t) 1 << 31) << 31) - 1 + (((off_t) 1 << 
>> +31) << 31))
>>
> I am not sure what the ask is here?  I made changes to the 
> configure.ac and ran autoconf2.69 to get builds to succeed. Do you 
> have a separate feedback here?

These LARGE_OFF_T changes are unrelated to the patch at hand and should be removed.  This likely means that you are using a patched autoconf that is making these extra changes.
 
> As for the refactoring, this was done to satisfy previous review 
> feedback about applying the AVX512 CFLAGS to the entire pg_bitutils.c 
> file. Mainly to avoid segfault due to the AVX512 flags. If its ok, I 
> would prefer to make a single commit as the change is pretty small and straight forward.

Okay.  The only reason I suggest this is to ease review.  For example, if there is some required refactoring that doesn't involve any functionality changes, it can be advantageous to get that part reviewed and committed first so that reviewers can better focus on the code for the new feature.
But, of course, that isn't necessary and/or isn't possible in all cases.

> Aren't they necessary to choose which functions to call based on 32 or 
> 64 bit architectures?

Yes.  My comment was that the patch appeared to make unnecessary changes to this code.  Perhaps I am misunderstanding something here.

> Would this change qualify for Workflow A as described in [0] and can 
> be picked up by a committer, given it has been reviewed by multiple 

I think so.  I would still encourage you to create an entry for this so that it is automatically tested via cfbot [0].

---

From: Nathan Bossart <[email-masked]>
Date: Tue, 5 Mar 2024 10:37:30 -0600

On Tue, Mar 05, 2024 at 04:31:15PM +0000, Amonson, Paul D wrote:
> I am not sure what "top-post" means but I am not doing anything different
> but using "reply to all" in Outlook. Please enlighten me. 😊

The following link provides some more information:

	https://wiki.postgresql.org/wiki/Mailing_Lists#Email_etiquette_mechanics

---

From: "Amonson, Paul D" <[email-masked]>
Date: Tue, 5 Mar 2024 16:52:23 +0000

-----Original Message-----
>Sent: Tuesday, March 5, 2024 8:38 AM
>Cc: Andres Freund <[email-masked]>; Alvaro Herrera <[email-masked]>; Shankaran, Akash <[email-masked]>; Noah Misch <[email-masked]>; Tom Lane <[email-masked]>; Matthias van de Meent <[email-masked]>; >[email-masked]
>> I am not sure what "top-post" means but I am not doing anything 
>> different but using "reply to all" in Outlook. Please enlighten me. 😊
>

Ahhhh.....Ok... guess it's time to thank Microsoft then.  ;) Noted I will try to do the "reduced" bottom-posting. I might slip up occasionally because it's an Intel habit. Is there a way to make Outlook do the leading ">" in a reply for the previous message?

BTW: Created the commit-fest submission.

Paul

---

From: Bruce Momjian <[email-masked]>
Date: Tue, 5 Mar 2024 17:18:32 -0500

> Ahhhh.....Ok... guess it's time to thank Microsoft then.  ;) Noted I will try to do the "reduced" bottom-posting. I might slip up occasionally because it's an Intel habit. Is there a way to make Ou…

Here is a blog post about how complex email posting can be:

	https://momjian.us/main/blogs/pgblog/2023.html#September_8_2023

-- 
  Bruce Momjian  <[email-masked]>        https://momjian.us
  EDB                                      https://enterprisedb.com

  Only you can decide what is important to you.

---

From: Nathan Bossart <[email-masked]>
Date: Thu, 7 Mar 2024 11:33:18 -0600

On Tue, Mar 05, 2024 at 04:52:23PM +0000, Amonson, Paul D wrote:
> Noted I will try to do the "reduced" bottom-posting. I might slip up
> occasionally because it's an Intel habit.

No worries.

> Is there a way to make Outlook do the leading ">" in a reply for the
> previous message?

I do not know, sorry.  I personally use mutt for the lists.

> BTW: Created the commit-fest submission.

Thanks.  I intend to provide a more detailed review shortly, as I am aiming
to get this one committed for v17.

---

From: Alvaro Herrera <[email-masked]>
Date: Thu, 7 Mar 2024 18:53:12 +0100

> have a separate feedback here? 

So what happens here is that autoconf-2.69 as shipped by Debian contains
some patches on top of the one released by GNU.  We use the latter, so
if you run Debian's, then the generated configure script will contain
the differences coming from Debian's version.

Really, I don't think this is very important as a review point, because
if the configure.ac file is changed in the patch, it's best for the
committer to run autoconf on their own, using a pristine GNU autoconf;
the configure file in the submitted patch is not relevant, only
configure.ac matters.

What committers do (or should do) is keep an install of autoconf-2.69
straight from GNU.

-- 
Álvaro Herrera        Breisgau, Deutschland  —  https://www.EnterpriseDB.com/

---

From: Nathan Bossart <[email-masked]>
Date: Thu, 7 Mar 2024 11:59:55 -0600

> the configure file in the submitted patch is not relevant, only

Agreed.  I didn't intend for this to be a major review point, and I
apologize for the extra noise.

---

From: Nathan Bossart <[email-masked]>
Date: Thu, 7 Mar 2024 15:36:00 -0600

As promised...

> +# Check for Intel AVX512 intrinsics to do POPCNT calculations.
> +#
> +PGAC_AVX512_POPCNT_INTRINSICS([])
> +if test x"$pgac_avx512_popcnt_intrinsics" != x"yes"; then
> +  PGAC_AVX512_POPCNT_INTRINSICS([-mavx512vpopcntdq -mavx512f])
> +fi
> +AC_SUBST(CFLAGS_AVX512_POPCNT)

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.

> 13 files changed, 657 insertions(+), 119 deletions(-)

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.

> +#undef HAVE__GET_CPUID_COUNT
> +
> +/* Define to 1 if you have  immintrin. */
> +#undef HAVE__IMMINTRIN

Is this missing HAVE__CPUIDEX?

>  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
>      if (buf == (const char *) TYPEALIGN(8, buf))
>      {
> @@ -311,7 +224,7 @@ pg_popcount(const char *buf, int bytes)
> 
>          buf = (const char *) words;
>      }
> -#else

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.

> +    /* 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?"

> +#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.

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.

[0] https://postgr.es/m/202402071953.5c4z7t6kl7ts%40alvherre.pgsql

---

From: "Amonson, Paul D" <[email-masked]>
Date: Mon, 11 Mar 2024 21:59:53 +0000

> Sent: Thursday, March 7, 2024 1:36 PM

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?

> 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. :)

> > +/* Define to 1 if you have  immintrin. */ #undef HAVE__IMMINTRIN
> 

Yes I missed it, I will include in the second patch (AVX specific) of the 2 patches.

> 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.

> nitpick: Could we call pg_popcount_slow() in a common section for these

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

> 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.

> 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

---

From: Nathan Bossart <[email-masked]>
Date: Mon, 11 Mar 2024 20:34:36 -0500

On Mon, Mar 11, 2024 at 09:59:53PM +0000, Amonson, Paul D wrote:
> 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?

Thanks.  There's no need to wait to post the AVX portion.  I recommend
using "git format-patch" to construct the patch set for the lists.

> 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.

I'm recommending that we don't change any of the code in the pg_popcount()
function (which is renamed to pg_popcount_slow() in your v6 patch).  If
pointers are 8 or more bytes, we'll try to process the buffer in 64-bit
chunks.  Else, we'll try to process it in 32-bit chunks.  Any remaining
bytes will be processed one-by-one.

---

From: Nathan Bossart <[email-masked]>
Date: Wed, 13 Mar 2024 11:39:04 -0500

A couple of thoughts on v7-0001:

+extern int  pg_popcount32_slow(uint32 word);
+extern int  pg_popcount64_slow(uint64 word);

+/* In pg_popcnt_*_accel source file. */
+extern int  pg_popcount32_fast(uint32 word);
+extern int  pg_popcount64_fast(uint64 word);

Can these prototypes be moved to a header file (maybe pg_bitutils.h)?  It
looks like these are defined twice in the patch, and while I'm not positive
that it's against project policy to declare extern function prototypes in
.c files, it appears to be pretty rare.

+  'pg_popcnt_choose.c',
+  'pg_popcnt_x86_64_accel.c',

I think we want these to be architecture-specific, i.e., only built for
x86_64 if the compiler knows how to use the relevant instructions.  There
is a good chance that we'll want to add similar support for other systems.
The CRC32C files are probably a good reference point for how to do this.

+#ifdef TRY_POPCNT_FAST

IIUC this macro can be set if either 1) the popcntq test in the
autoconf/meson scripts passes or 2) we're building with MSVC on x86_64.  I
wonder if it would be better to move the MSVC/x86_64 check to the
autoconf/meson scripts so that we could avoid surrounding large portions of
the popcount code with this macro.  This might even be a necessary step
towards building these files in an architecture-specific fashion.

---

From: "Amonson, Paul D" <[email-masked]>
Date: Wed, 13 Mar 2024 17:52:14 +0000

> Sent: Wednesday, March 13, 2024 9:39 AM

> +extern int  pg_popcount32_slow(uint32 word); extern int
> +pg_popcount64_slow(uint64 word);
> 
> +/* In pg_popcnt_*_accel source file. */ extern int
> +pg_popcount32_fast(uint32 word); extern int  pg_popcount64_fast(uint64
> +word);
> 
> looks like these are defined twice in the patch, and while I'm not positive that
> it's against project policy to declare extern function prototypes in .c files, it
> appears to be pretty rare.

Originally, I intentionally did not put these in the header file as I want them to be private, but they are not defined in this .c file hence extern. Now I realize the "extern" part is not needed to accomplish my goal. Will fix by removing the "extern" keyword.

> x86_64 if the compiler knows how to use the relevant instructions.  There is a
> good chance that we'll want to add similar support for other systems.

I will look at this for the 'pg_popcnt_x86_64_accel.c' file but the 'pg_popcnt_choose.c' file is intended to be for any platform that may need accelerators including a possible future ARM accelerator.
 
> +#ifdef TRY_POPCNT_FAST
> 
> IIUC this macro can be set if either 1) the popcntq test in the autoconf/meson
> scripts passes or 2) we're building with MSVC on x86_64.  I wonder if it would
> be better to move the MSVC/x86_64 check to the autoconf/meson scripts so
> that we could avoid surrounding large portions of the popcount code with this
> macro.  This might even be a necessary step towards building these files in an
> architecture-specific fashion.

I see the point here; however, this will take some time to get right especially since I don't have a Windows box to do compiles on. Should I attempt to do this in this patch?

Thanks,
Paul

---

From: Nathan Bossart <[email-masked]>
Date: Wed, 13 Mar 2024 13:38:11 -0500

On Wed, Mar 13, 2024 at 05:52:14PM +0000, Amonson, Paul D wrote:
> I will look at this for the 'pg_popcnt_x86_64_accel.c' file but the
> 'pg_popcnt_choose.c' file is intended to be for any platform that may
> need accelerators including a possible future ARM accelerator.

I worry that using the same file for *_choose.c for all architectures would
become rather #ifdef heavy.  Since we are already separating out this code
into new files, IMO we might as well try to avoid too many #ifdefs, too.
But this is admittedly less important right now because there's almost no
chance of any new architecture support here for v17.

> I see the point here; however, this will take some time to get right
> especially since I don't have a Windows box to do compiles on. Should I
> attempt to do this in this patch?

This might also be less important given the absence of any imminent new
architecture support in this area.  I'm okay with it, given we are just
maintaining the status quo.

---

From: "Amonson, Paul D" <[email-masked]>
Date: Thu, 14 Mar 2024 19:50:46 +0000

> Sent: Monday, March 11, 2024 6:35 PM

> Thanks.  There's no need to wait to post the AVX portion.  I recommend using
> "git format-patch" to construct the patch set for the lists.

After exploring git format-patch command I think I understand what you need. Attached.
 
> > pg_popcount32() or pg_popcount64() with the understanding that it may
> > not be optimal, but I do need to know which to use.
> 
> pointers are 8 or more bytes, we'll try to process the buffer in 64-bit chunks.
> Else, we'll try to process it in 32-bit chunks.  Any remaining bytes will be
> processed one-by-one.

Ok, we are on the same page now. :)  It is already fixed that way in the refactor patch #1.

As for new performance numbers: I just ran a full suite like I did earlier in the process. My latest results an equivalent to a pgbench scale factor 10 DB with the target column having varying column widths and appropriate random data are 1.2% improvement with a 2.2% Margin of Error at a 98% confidence level. Still seeing improvement and no regressions.

As stated in the previous separate chain I updated the code removing the extra "extern" keywords.

Thanks,
Paul

---

From: Nathan Bossart <[email-masked]>
Date: Fri, 15 Mar 2024 10:06:11 -0500

On Thu, Mar 14, 2024 at 07:50:46PM +0000, Amonson, Paul D wrote:
> As for new performance numbers: I just ran a full suite like I did
> earlier in the process. My latest results an equivalent to a pgbench
> scale factor 10 DB with the target column having varying column widths
> and appropriate random data are 1.2% improvement with a 2.2% Margin of
> Error at a 98% confidence level. Still seeing improvement and no
> regressions.

Which test suite did you run?  Those numbers seem potentially
indistinguishable from noise, which probably isn't great for such a large
patch set.

I ran John Naylor's test_popcount module [0] with the following command on
an i7-1195G7:

	time psql postgres -c 'select drive_popcount(10000000, 1024)'

Without your patches, this seems to take somewhere around 8.8 seconds.
With your patches, it takes 0.6 seconds.  (I re-compiled and re-ran the
tests a couple of times because I had a difficult time believing the amount
of improvement.)

[0] https://postgr.es/m/CAFBsxsE7otwnfA36Ly44zZO%2Bb7AEWHRFANxR1h1kxveEV%3DghLQ%40mail.gmail.com

---

From: "Amonson, Paul D" <[email-masked]>
Date: Fri, 15 Mar 2024 15:31:17 +0000

> Sent: Friday, March 15, 2024 8:06 AM
> Cc: Andres Freund <[email-masked]>; Alvaro Herrera <[email-masked]
> ip.org>; Shankaran, Akash <[email-masked]>; Noah Misch
> <[email-masked]>; Tom Lane <[email-masked]>; Matthias van de
> Meent <[email-masked]>; pgsql-
> [email-masked]
> indistinguishable from noise, which probably isn't great for such a large patch
> set.

I ran...
	psql -c "select bitcount(column) from table;"
...in a loop with "column" widths of 84, 4096, 8192, and 16384 containing random data. There DB has 1 million rows.  In the loop before calling the select I have code to clear all system caches. If I omit the code to clear system caches the margin of error remains the same but the improvement percent changes from 1.2% to 14.6% (much less I/O when cached data is available).

> With your patches, it takes 0.6 seconds.  (I re-compiled and re-ran the tests a
> couple of times because I had a difficult time believing the amount of
> improvement.)

When I tested the code outside postgres in a micro benchmark I got 200-300% improvements. Your results are interesting, as it implies more than 300% improvement. Let me do some research on the benchmark you referenced. However, in all cases it seems that there is no regression so should we move forward on merging while I run some more local tests?

Thanks,
Paul

---

From: "Amonson, Paul D" <[email-masked]>
Date: Fri, 15 Mar 2024 17:43:39 +0000

> From: Amonson, Paul D <[email-masked]>
> Sent: Friday, March 15, 2024 8:31 AM
> To: Nathan Bossart <[email-masked]>
...
> When I tested the code outside postgres in a micro benchmark I got 200-
> 300% improvements. Your results are interesting, as it implies more than
> 300% improvement. Let me do some research on the benchmark you
> referenced. However, in all cases it seems that there is no regression so should
> we move forward on merging while I run some more local tests?

When running quick test with small buffers (1 to 32K) I see up to about a 740% improvement. This was using my stand-alone micro benchmark outside of PG. My original 200-300% numbers were averaged including sizes up to 512MB which seems to not run as well on large buffers.  I will try the referenced micro benchmark on Monday. None of my benchmark testing used the command line "time" command. For Postgres is set "\timing" before the run and for the stand-alone benchmark is took timestamps in the code. In all cases I used -O2 for optimization.

Thanks,
Paul

---

From: David Rowley <[email-masked]>
Date: Mon, 18 Mar 2024 09:56:32 +1300

> [0] https://postgr.es/m/CAFBsxsE7otwnfA36Ly44zZO%2Bb7AEWHRFANxR1h1kxveEV%3DghLQ%40mail.gmail.com

I think most of that will come from getting rid of the indirect
function that currently exists in pg_popcount().

Using the attached quick hack, the performance using John's test
module goes from:

-- 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)

-- with attached hacky and untested patch
postgres=# select drive_popcount(10000000, 1024);
Time: 2539.029 ms (00:02.539)
Time: 2598.223 ms (00:02.598)
Time: 2611.435 ms (00:02.611)

--- and with the avx512 patch on an AMD 7945HX CPU:
postgres=# select drive_popcount(10000000, 1024);
Time: 564.982 ms
Time: 556.540 ms
Time: 554.032 ms

The following comment seems like it could do with some improvements.

 * Use AVX-512 Intrinsics for supported Intel CPUs or fall back the the software
 * loop in pg_bunutils.c and use the best 32 or 64 bit fast methods. If no fast
 * methods are used this will fall back to __builtin_* or pure software.

There's nothing much specific to Intel here.  AMD Zen4 has AVX512.
Plus "pg_bunutils.c" should be "pg_bitutils.c" and "the the"

How about just:

 * Use AVX-512 Intrinsics on supported CPUs. Fall back the software loop in
 * pg_popcount_slow() when AVX-512 is unavailable.

Maybe it's worth exploring something along the lines of the attached
before doing the AVX512 stuff.  It seems like a pretty good speed-up
and will apply for CPUs without AVX512 support.

David
diff --git a/src/port/pg_bitutils.c b/src/port/pg_bitutils.c
index 640a89561a..85e45cee9b 100644
--- a/src/port/pg_bitutils.c
+++ b/src/port/pg_bitutils.c
@@ -305,7 +305,18 @@ pg_popcount(const char *buf, int bytes)
 
 		while (bytes >= 8)
 		{
-			popcnt += pg_popcount64(*words++);
+#ifdef _MSC_VER
+			popcnt += __popcnt64(*words++);
+#else
+			uint64 res;
+
+			__asm__ __volatile__(" popcntq %1,%0\n"
+								 : "=q"(res)
+								 : "rm"(word)
+								 : "cc");
+			popcnt += (int) res;
+			words++;
+#endif
 			bytes -= 8;
 		}
 
diff --git a/src/test/modules/meson.build b/src/test/modules/meson.build
index f1d18a1b29..ae880db64c 100644
--- a/src/test/modules/meson.build
+++ b/src/test/modules/meson.build
@@ -26,6 +26,7 @@ subdir('test_misc')
 subdir('test_oat_hooks')
 subdir('test_parser')
 subdir('test_pg_dump')
+subdir('test_popcount')
 subdir('test_predtest')
 subdir('test_radixtree')
 subdir('test_rbtree')

---

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

> and will apply for CPUs without AVX512 support.

+1

---

From: "Amonson, Paul D" <[email-masked]>
Date: Mon, 18 Mar 2024 16:07:40 +0000

Won't I still need the runtime checks? If I compile with a compiler supporting the HW "feature" but run on HW without that feature,  I will want to avoid faults due to illegal operations. Won't that also affect performance?

Paul

> Sent: Monday, March 18, 2024 8:29 AM
> To: David Rowley <[email-masked]>
> Cc: Amonson, Paul D <[email-masked]>; Andres Freund
> <[email-masked]>; Alvaro Herrera <[email-masked]>; Shankaran,
> Akash <[email-masked]>; Noah Misch <[email-masked]>;
> Tom Lane <[email-masked]>; Matthias van de Meent
> <[email-masked]>; [email-masked]

---

From: Nathan Bossart <[email-masked]>
Date: Mon, 18 Mar 2024 11:20:18 -0500

On Mon, Mar 18, 2024 at 04:07:40PM +0000, Amonson, Paul D wrote:
> Won't I still need the runtime checks? If I compile with a compiler
> supporting the HW "feature" but run on HW without that feature,  I will
> want to avoid faults due to illegal operations. Won't that also affect
> performance?

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().

---

From: "Amonson, Paul D" <[email-masked]>
Date: Mon, 18 Mar 2024 17:28:32 +0000

> Sent: Monday, March 18, 2024 9:20 AM
> ...
> 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

Ok, got you.

Question: I applied the patch for the drive_popcount* functions and rebuilt.  The resultant server complains that the function is missing. What is the trick to make this work?

Another Question: Is there a reason "time psql" is used over the Postgres "\timing" command?

Thanks,
Paul

---

From: Nathan Bossart <[email-masked]>
Date: Mon, 18 Mar 2024 12:30:04 -0500

> 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.

>From 1d33c803feb7428f798b13fd643a16c73628f8a9 Mon Sep 17 00:00:00 2001
From: Nathan Bossart <[email-masked]>
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.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..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