Subject: Re: Popcount optimization using AVX512

From: Andres Freund <[email-masked]>
Date: Fri, 9 Feb 2024 10:34:50 -0800

Hi,

On 2024-02-09 17:39:46 +0000, Amonson, Paul D wrote:

> diff --git a/meson.build b/meson.build
> index 8ed51b6aae..1e7a4dc942 100644
> --- a/meson.build
> +++ b/meson.build
> @@ -1773,6 +1773,45 @@ elif cc.links('''
>  endif
>  
>  
> +# XXX: The configure.ac check for __cpuidex() is broken, we don't copy that
> +# here. To prevent problems due to two detection methods working, stop
> +# checking after one.

This seems like a bogus copy-paste.

> +if cc.links('''
> +    #include <cpuid.h>
> +    int main(int arg, char **argv)
> +    {
> +        unsigned int exx[4] = {0, 0, 0, 0};
> +        __get_cpuid_count(7, 0, &exx[0], &exx[1], &exx[2], &exx[3]);
> +    }
> +    ''', name: '__get_cpuid_count',
> +    args: test_c_args)
> +  cdata.set('HAVE__GET_CPUID_COUNT', 1)
> +elif cc.links('''
> +    #include <intrin.h>
> +    int main(int arg, char **argv)
> +    {
> +        unsigned int exx[4] = {0, 0, 0, 0};
> +        __cpuidex(exx, 7, 0);
> +    }
> +    ''', name: '__cpuidex',
> +    args: test_c_args)
> +  cdata.set('HAVE__CPUIDEX', 1)
> +endif
> +
> +
> +# Check for header immintrin.h
> +if cc.links('''
> +    #include <immintrin.h>
> +    int main(int arg, char **argv)
> +    {
> +      return 1701;
> +    }
> +    ''', name: '__immintrin',
> +    args: test_c_args)
> +  cdata.set('HAVE__IMMINTRIN', 1)
> +endif

Do these all actually have to link?  Invoking the linker is slow.

I think you might be able to just use cc.has_header_symbol().

> +###############################################################
> +# AVX 512 POPCNT Intrinsic check
> +###############################################################
> +have_avx512_popcnt = false
> +cflags_avx512_popcnt = []
> +if host_cpu == 'x86_64'
> +  prog = '''
> +      #include <immintrin.h>
> +      #include <stdint.h>
> +      void main(void)
> +      {
> +        __m512i tmp __attribute__((aligned(64)));
> +        __m512i input = _mm512_setzero_si512();
> +        __m512i output = _mm512_popcnt_epi64(input);
> +        uint64_t cnt = 999;
> +        _mm512_store_si512(&tmp, output);
> +        cnt = _mm512_reduce_add_epi64(tmp);
> +        /* return computed value, to prevent the above being optimized away */
> +        return cnt == 0;
> +      }'''

Does this work with msvc?

> +    if cc.links(prog, name: '_mm512_setzero_si512, _mm512_popcnt_epi64, _mm512_store_si512, and _mm512_reduce_add_epi64 with -mavx512vpopcntdq -mavx512f',

That's a very long line in the output, how about using the avx feature name or
something?

> diff --git a/src/port/Makefile b/src/port/Makefile
> index dcc8737e68..6a01a7d89a 100644
> --- a/src/port/Makefile
> +++ b/src/port/Makefile
> @@ -87,6 +87,11 @@ pg_crc32c_sse42.o: CFLAGS+=$(CFLAGS_CRC)
>  pg_crc32c_sse42_shlib.o: CFLAGS+=$(CFLAGS_CRC)
>  pg_crc32c_sse42_srv.o: CFLAGS+=$(CFLAGS_CRC)
>  
> +# Newer Intel processors can use AVX-512 POPCNT Capabilities (01/30/2024)
> +pg_bitutils.o: CFLAGS+=$(CFLAGS_AVX512_POPCNT)
> +pg_bitutils_shlib.o: CFLAGS+=$(CFLAGS_AVX512_POPCNT)
> +pg_bitutils_srv.o:CFLAGS+=$(CFLAGS_AVX512_POPCNT)
> +
>  # all versions of pg_crc32c_armv8.o need CFLAGS_CRC
>  pg_crc32c_armv8.o: CFLAGS+=$(CFLAGS_CRC)
>  pg_crc32c_armv8_shlib.o: CFLAGS+=$(CFLAGS_CRC)
> diff --git a/src/port/meson.build b/src/port/meson.build
> index 69b30ab21b..1c48a3b07e 100644
> --- a/src/port/meson.build
> +++ b/src/port/meson.build
> @@ -184,6 +184,7 @@ foreach name, opts : pgport_variants
>        link_with: cflag_libs,
>        c_pch: pch_c_h,
>        kwargs: opts + {
> +        'c_args': opts.get('c_args', []) + cflags_avx512_popcnt,
>          'dependencies': opts['dependencies'] + [ssl],
>        }
>      )

This will build all of pgport with the avx flags, which wouldn't be correct, I
think? The compiler might inject automatic uses of avx512 in places, which
would cause problems, no?

While you don't do the same for make, isn't even just using the avx512 for all
of pg_bitutils.c broken for exactly that reson? That's why the existing code
builds the files for various crc variants as their own file.

Greetings,

Andres Freund

---

From: "Amonson, Paul D" <[email-masked]>
Date: Mon, 12 Feb 2024 20:14:06 +0000

My responses with questions,

> > +# XXX: The configure.ac check for __cpuidex() is broken, we don't 
> > +copy that # here. To prevent problems due to two detection methods 
> > +working, stop # checking after one.
>

My bad. Will remove the offending comment.  :)

> ...

I took this to mean the last of the 3 new blocks. I changed this one to the cc_has_header method. I think I do want the first 2 checking the link as well. If the don't link here they won't link in the actual build.

> Does this work with msvc?

I think it will work but I have no way to validate it. I propose we remove the AVX-512 popcount feature from MSVC builds. Sound ok?

> That's a very long line in the output, how about using the avx feature name or something?

Agree, will fix.

> This will build all of pgport with the avx flags, which wouldn't be correct, I think? The compiler might inject automatic uses of avx512 in places, which would cause problems, no?

This will take me some time to learn how to do this in meson. Any pointers here would be helpful. 

> While you don't do the same for make, isn't even just using the avx512 for all of pg_bitutils.c broken for exactly that reson? That's why the existing code builds the files for various crc variants as their own file.

I don't think its broken, nothing else in pg_bitutils.c will make use of AVX-512, so I am not sure what dividing this up into multiple files will yield benefits beyond code readability as they will all be needed during compile time. I prefer to not split if the community agrees to it.
 
If splitting still makes sense, I propose splitting into 3 files:  pg_bitutils.c (entry point +sw popcnt implementation), pg_popcnt_choose.c (CPUID and xgetbv check) and pg_popcnt_x86_64_accel.c (64/512bit x86 implementations). 
I'm not an expert in meson, but splitting might add complexity to meson.build. 

Could you elaborate if there are other benefits to the split file approach?

Paul

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

Hi,

On 2024-02-09 17:39:46 +0000, Amonson, Paul D wrote:

> diff --git a/meson.build b/meson.build index 8ed51b6aae..1e7a4dc942 
> 100644
> --- a/meson.build
> +++ b/meson.build
> +# XXX: The configure.ac check for __cpuidex() is broken, we don't 
> +copy that # here. To prevent problems due to two detection methods 
> +working, stop # checking after one.

> +  cdata.set('HAVE__GET_CPUID_COUNT', 1) elif cc.links('''
> +    #include <intrin.h>

> +    if cc.links(prog, name: '_mm512_setzero_si512, 
> + _mm512_popcnt_epi64, _mm512_store_si512, and _mm512_reduce_add_epi64 
> + with -mavx512vpopcntdq -mavx512f',

That's a very long line in the output, how about using the avx feature name or something?

> diff --git a/src/port/Makefile b/src/port/Makefile index 
> dcc8737e68..6a01a7d89a 100644
> --- a/src/port/Makefile
> +++ b/src/port/Makefile
> +# Newer Intel processors can use AVX-512 POPCNT Capabilities 
> +(01/30/2024)
>  pg_crc32c_armv8_shlib.o: CFLAGS+=$(CFLAGS_CRC) diff --git 
> a/src/port/meson.build b/src/port/meson.build index 
> 69b30ab21b..1c48a3b07e 100644

This will build all of pgport with the avx flags, which wouldn't be correct, I think? The compiler might inject automatic uses of avx512 in places, which would cause problems, no?

While you don't do the same for make, isn't even just using the avx512 for all of pg_bitutils.c broken for exactly that reson? That's why the existing code builds the files for various crc variants as their own file.

Greetings,

Andres Freund

---

From: Andres Freund <[email-masked]>
Date: Mon, 12 Feb 2024 12:37:14 -0800

Hi,

On 2024-02-12 20:14:06 +0000, Amonson, Paul D wrote:
> I took this to mean the last of the 3 new blocks.

Yep.

> I think it will work but I have no way to validate it. I propose we remove the AVX-512 popcount feature from MSVC builds. Sound ok?

CI [1], whould be able to test at least building. Including via cfbot,
automatically run for each commitfest entry - you can see prior runs at
[2].  They run on Zen 3 epyc instances, so unfortunately runtime won't be
tested.  If you look at [3], you can see that currently it doesn't seem to be
considered supported at configure time:

...
[00:23:48.480] Checking if "__get_cpuid" : links: NO
[00:23:48.480] Checking if "__cpuid" : links: YES
...
[00:23:48.492] Checking if "x86_64: popcntq instruction" compiles: NO
...

Unfortunately CI currently is configured to not upload the build logs if the
build succeeds, so we don't have enough details to see why.

> This will take me some time to learn how to do this in meson. Any pointers

Should be fairly simple, add it to the replace_funcs_pos and add the relevant
cflags to pgport_cflags, similar to how it's done for crc.

> I don't think its broken, nothing else in pg_bitutils.c will make use of
> AVX-512

You can't really guarantee that compiler auto-vectorization won't decide to do
so, no? I wouldn't call it likely, but it's also hard to be sure it won't
happen at some point.

> Could you elaborate if there are other benefits to the split file approach?

It won't lead to SIGILLs ;)

Greetings,

Andres Freund

[1] https://github.com/postgres/postgres/blob/master/src/tools/ci/README
[2] https://cirrus-ci.com/github/postgresql-cfbot/postgresql/commitfest%2F47%2F4675
[3] https://cirrus-ci.com/task/5645112189911040

---

From: "Amonson, Paul D" <[email-masked]>
Date: Wed, 21 Feb 2024 17:35:57 +0000

Hi,

I am encountering a problem that I don't think I understand. I cannot get the MSVC build to link in CI. I added 2 files to the build, but the linker is complaining about the original pg_bitutils.c file is missing (specifically symbol 'pg_popcount'). To my knowledge my changes did not change linking for the offending file and I see the compiles for pg_bitutils.c in all 3 libs in the build. All other builds are compiling.

Any help on this issue would be greatly appreciated.

My fork is at https://github.com/paul-amonson/postgresql/tree/popcnt_patch and the CI build is at https://cirrus-ci.com/task/4927666021728256.

Thanks,
Paul

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

Hi,

Yep.

> I think it will work but I have no way to validate it. I propose we remove the AVX-512 popcount feature from MSVC builds. Sound ok?

CI [1], whould be able to test at least building. Including via cfbot, automatically run for each commitfest entry - you can see prior runs at [2].  They run on Zen 3 epyc instances, so unfortunately runtime won't be tested.  If you look at [3], you can see that currently it doesn't seem to be considered supported at configure time:

...
[00:23:48.480] Checking if "__get_cpuid" : links: NO [00:23:48.480] Checking if "__cpuid" : links: YES ...
[00:23:48.492] Checking if "x86_64: popcntq instruction" compiles: NO ...

Unfortunately CI currently is configured to not upload the build logs if the build succeeds, so we don't have enough details to see why.

> pointers here would be helpful.

Should be fairly simple, add it to the replace_funcs_pos and add the relevant cflags to pgport_cflags, similar to how it's done for crc.

> I don't think its broken, nothing else in pg_bitutils.c will make use 

You can't really guarantee that compiler auto-vectorization won't decide to do so, no? I wouldn't call it likely, but it's also hard to be sure it won't happen at some point.

Greetings,

Andres Freund

---

From: "Amonson, Paul D" <[email-masked]>
Date: Mon, 26 Feb 2024 17:56:50 +0000

Hello again,

This is now a blocking issue. I can find no reason for the failing behavior of the MSVC build. All other languages build fine in CI including the Mac. Since the master branch builds, I assume I changed something critical to linking, but I can't figure out what that would be. Can someone with Windows/MSVC experience help me?

* Code: https://github.com/paul-amonson/postgresql/tree/popcnt_patch
* CI build: https://cirrus-ci.com/task/4927666021728256

Thanks,
Paul

-----Original Message-----
From: Amonson, Paul D <[email-masked]> 
Sent: Wednesday, February 21, 2024 9:36 AM
To: Andres Freund <[email-masked]>
Cc: Alvaro Herrera <[email-masked]>; Shankaran, Akash <[email-masked]>; Nathan Bossart <[email-masked]>; Noah Misch <[email-masked]>; Tom Lane <[email-masked]>; Matthias van de Meent <[email-masked]>; [email-masked]
Subject: RE: Popcount optimization using AVX512

Hi,

Thanks,
Paul

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

Hi,

Yep.

...

Greetings,

Andres Freund

---

From: "Amonson, Paul D" <[email-masked]>
Date: Tue, 27 Feb 2024 20:46:06 +0000

Andres,

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.

Paul

-----Original Message-----
From: Amonson, Paul D <[email-masked]> 
Sent: Monday, February 26, 2024 9:57 AM
To: Amonson, Paul D <[email-masked]>; Andres Freund <[email-masked]>
Cc: Alvaro Herrera <[email-masked]>; Shankaran, Akash <[email-masked]>; Nathan Bossart <[email-masked]>; Noah Misch <[email-masked]>; Tom Lane <[email-masked]>; Matthias van de Meent <[email-masked]>; [email-masked]
Subject: RE: Popcount optimization using AVX512

Hello again,

Thanks,
Paul

-----Original Message-----
From: Amonson, Paul D <[email-masked]>
Sent: Wednesday, February 21, 2024 9:36 AM
To: Andres Freund <[email-masked]>
Cc: Alvaro Herrera <[email-masked]>; Shankaran, Akash <[email-masked]>; Nathan Bossart <[email-masked]>; Noah Misch <[email-masked]>; Tom Lane <[email-masked]>; Matthias van de Meent <[email-masked]>; [email-masked]
Subject: RE: Popcount optimization using AVX512

Hi,

Thanks,
Paul

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

Hi,

Yep.

...

Greetings,

Andres Freund

---

From: Nathan Bossart <[email-masked]>
Date: Fri, 1 Mar 2024 15:44:57 -0600

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