Subject: Re: Popcount optimization using AVX512

From: Tom Lane <[email-masked]>
Date: Mon, 06 Nov 2023 21:52:58 -0500

Nathan Bossart <[email-masked]> writes:
> Like I said, I don't have any proposals yet, but assuming we do want to
> support newer intrinsics, either open-coded or via auto-vectorization, I
> suspect we'll need to gather consensus for a new policy/strategy.

Yeah.  The function-pointer solution kind of sucks, because for the
sort of operation we're considering here, adding a call and return
is probably order-of-100% overhead.  Worse, it adds similar overhead
for everyone who doesn't get the benefit of the optimization.  (One
of the key things you want to be able to say, when trying to sell
a maybe-it-helps-or-maybe-it-doesnt optimization to the PG community,
is "it doesn't hurt anyone who's not able to benefit".)  And you
can't argue that that overhead is negligible either, because if it
is then we're all wasting our time even discussing this.  So we need
a better technology, and I fear I have no good ideas about what.

Your comment about vectorization hints at one answer: if you can
amortize the overhead across multiple applications of the operation,
then it doesn't hurt so much.  But I'm not sure how often we can
make that answer work.

			regards, tom lane

---

From: Noah Misch <[email-masked]>
Date: Mon, 6 Nov 2023 19:15:01 -0800

On Mon, Nov 06, 2023 at 09:52:58PM -0500, Tom Lane wrote:
> for everyone who doesn't get the benefit of the optimization.

The glibc/gcc "ifunc" mechanism was designed to solve this problem of choosing
a function implementation based on the runtime CPU, without incurring function
pointer overhead.  I would not attempt to use AVX512 on non-glibc systems, and
I would use ifunc to select the desired popcount implementation on glibc:
https://gcc.gnu.org/onlinedocs/gcc-4.8.5/gcc/Function-Attributes.html

---

From: Nathan Bossart <[email-masked]>
Date: Mon, 6 Nov 2023 21:59:26 -0600

> https://gcc.gnu.org/onlinedocs/gcc-4.8.5/gcc/Function-Attributes.html

Thanks, that seems promising for the function pointer cases.  I'll plan on
trying to convert one of the existing ones to use it.  BTW it looks like
LLVM has something similar [0].

IIUC this unfortunately wouldn't help for cases where we wanted to keep
stuff inlined, such as is_valid_ascii() and the functions in pg_lfind.h,
unless we applied it to the calling functions, but that doesn't ѕound
particularly maintainable.

[0] https://llvm.org/docs/LangRef.html#ifuncs

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

---

From: Noah Misch <[email-masked]>
Date: Mon, 6 Nov 2023 21:53:15 -0800

> particularly maintainable.

Agreed, it doesn't solve inline cases.  If the gains are big enough, we should
move toward packages containing N CPU-specialized copies of the postgres
binary, with bin/postgres just exec'ing the right one.

---

From: Nathan Bossart <[email-masked]>
Date: Tue, 7 Nov 2023 14:14:41 -0600

> binary, with bin/postgres just exec'ing the right one.

I performed a quick test with ifunc on my x86 machine that ordinarily uses
the runtime checks for the CRC32C code, and I actually see a consistent
3.5% regression for pg_waldump -z on 100M 65-byte records.  I've attached
the patch used for testing.

The multiple-copies-of-the-postgres-binary idea seems interesting.  That's
probably not something that could be enabled by default, but perhaps we
could add support for a build option.

-- 
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
diff --git a/src/include/port/pg_crc32c.h b/src/include/port/pg_crc32c.h
index d085f1dc00..6db411ee29 100644
--- a/src/include/port/pg_crc32c.h
+++ b/src/include/port/pg_crc32c.h
@@ -78,7 +78,7 @@ extern pg_crc32c pg_comp_crc32c_loongarch(pg_crc32c crc, const void *data, size_
 #define FIN_CRC32C(crc) ((crc) ^= 0xFFFFFFFF)
 
 extern pg_crc32c pg_comp_crc32c_sb8(pg_crc32c crc, const void *data, size_t len);
-extern pg_crc32c (*pg_comp_crc32c) (pg_crc32c crc, const void *data, size_t len);
+extern pg_crc32c pg_comp_crc32c(pg_crc32c crc, const void *data, size_t len);
 
 #ifdef USE_SSE42_CRC32C_WITH_RUNTIME_CHECK
 extern pg_crc32c pg_comp_crc32c_sse42(pg_crc32c crc, const void *data, size_t len);
diff --git a/src/port/pg_crc32c_sse42_choose.c b/src/port/pg_crc32c_sse42_choose.c
index 41ff4a35ad..62bb981ee8 100644
--- a/src/port/pg_crc32c_sse42_choose.c
+++ b/src/port/pg_crc32c_sse42_choose.c
@@ -51,14 +51,14 @@ pg_crc32c_sse42_available(void)
  * so that subsequent calls are routed directly to the chosen implementation.
  */
 static pg_crc32c
-pg_comp_crc32c_choose(pg_crc32c crc, const void *data, size_t len)
+(*pg_comp_crc32c_choose (void))(pg_crc32c crc, const void *data, size_t len)
 {
 	if (pg_crc32c_sse42_available())
-		pg_comp_crc32c = pg_comp_crc32c_sse42;
+		return pg_comp_crc32c_sse42;
 	else
-		pg_comp_crc32c = pg_comp_crc32c_sb8;
-
-	return pg_comp_crc32c(crc, data, len);
+		return pg_comp_crc32c_sb8;
 }
 
-pg_crc32c	(*pg_comp_crc32c) (pg_crc32c crc, const void *data, size_t len) = pg_comp_crc32c_choose;
+pg_crc32c
+pg_comp_crc32c(pg_crc32c crc, const void *data, size_t len)
+	__attribute__ ((ifunc ("pg_comp_crc32c_choose")));

---

From: "Shankaran, Akash" <[email-masked]>
Date: Wed, 15 Nov 2023 20:27:57 +0000

Sorry for the late response here. We spent some time researching and measuring the frequency impact of AVX512 instructions used here.

>How does this compare to older CPUs, and more mixed workloads? IIRC,
the use of AVX512 (which I believe this instruction to be included in)
has significant implications for core clock frequency when those
instructions are being executed, reducing overall performance if
they're not a large part of the workload.

AVX512 has light and heavy instructions. While the heavy AVX512 instructions have clock frequency implications, the light instructions not so much. See [0] for more details. We captured EMON data for the benchmark used in this work, and see that the instructions are using the licensing level not meant for heavy AVX512 operations. This means the instructions for popcount : _mm512_popcnt_epi64(), _mm512_reduce_add_epi64() are not going to have any significant impact on CPU clock frequency. 
Clock frequency impact aside, we measured the same benchmark for gains on older Intel hardware and observe up to 18% better performance on Intel Icelake. On older intel hardware, the popcntdq 512 instruction is not present so it won’t work. If clock frequency is not affected, rest of workload should not be impacted in the case of mixed workloads. 

>Apart from the two type functions bytea_bit_count and bit_bit_count
(which are not accessed in postgres' own systems, but which could want
to cover bytestreams of >BLCKSZ) the only popcount usages I could find
were on objects that fit on a page, i.e. <8KiB in size. How does
performance compare for bitstreams of such sizes, especially after any
CPU clock implications are taken into account?

Testing this on smaller block sizes < 8KiB shows that AVX512 compared to the current 64bit behavior shows slightly lower performance, but with a large variance. We cannot conclude much from it. The testing with ANALYZE benchmark by Nathan also points to no visible impact as a result of using AVX512. The gains on larger dataset is easily evident, with less variance. 
What are your thoughts if we introduce AVX512 popcount for smaller sizes as an optional feature initially, and then test it more thoroughly over time on this particular use case? 

Regarding enablement, following the other responses related to function inlining, using ifunc and enabling future intrinsic support, it seems a concrete solution would require further discussion. We’re attaching a patch to enable AVX512, which can use AVX512 flags during build. For example:
  >make -E CFLAGS_AVX512="-mavx -mavx512dq -mavx512vpopcntdq -mavx512vl -march=icelake-server -DAVX512_POPCNT=1"

Thoughts or feedback on the approach in the patch? This solution should not impact anyone who doesn’t use the feature i.e. AVX512. Open to additional ideas if this doesn’t seem like the right approach here.  

[0] https://lemire.me/blog/2018/09/07/avx-512-when-and-how-to-use-these-new-instructions/

-----Original Message-----
From: Nathan Bossart <[email-masked]> 
Sent: Tuesday, November 7, 2023 12:15 PM
To: Noah Misch <[email-masked]>
Cc: Tom Lane <[email-masked]>; Matthias van de Meent <[email-masked]>; Amonson, Paul D <[email-masked]>; [email-masked]; Shankaran, Akash <[email-masked]>
Subject: Re: Popcount optimization using AVX512

On Mon, Nov 06, 2023 at 09:53:15PM -0800, Noah Misch wrote:
>> > The glibc/gcc "ifunc" mechanism was designed to solve this problem 
>> > of choosing a function implementation based on the runtime CPU, 
>> > without incurring function pointer overhead.  I would not attempt 
>> > to use AVX512 on non-glibc systems, and I would use ifunc to select the desired popcount implementation on glibc:
>> Thanks, that seems promising for the function pointer cases.  I'll 
>> plan on trying to convert one of the existing ones to use it.  BTW it 
>> looks like LLVM has something similar [0].
>> 
>> IIUC this unfortunately wouldn't help for cases where we wanted to 
>> keep stuff inlined, such as is_valid_ascii() and the functions in 
>> pg_lfind.h, unless we applied it to the calling functions, but that 
>> doesn't ѕound particularly maintainable.
> 
> Agreed, it doesn't solve inline cases.  If the gains are big enough, 
> we should move toward packages containing N CPU-specialized copies of 
> the postgres binary, with bin/postgres just exec'ing the right one.

I performed a quick test with ifunc on my x86 machine that ordinarily uses the runtime checks for the CRC32C code, and I actually see a consistent 3.5% regression for pg_waldump -z on 100M 65-byte records.  I've attached the patch used for testing.

The multiple-copies-of-the-postgres-binary idea seems interesting.  That's probably not something that could be enabled by default, but perhaps we could add support for a build option.

---

From: Nathan Bossart <[email-masked]>
Date: Wed, 15 Nov 2023 15:48:53 -0600

On Wed, Nov 15, 2023 at 08:27:57PM +0000, Shankaran, Akash wrote:
> AVX512 has light and heavy instructions. While the heavy AVX512
> instructions have clock frequency implications, the light instructions
> not so much. See [0] for more details. We captured EMON data for the
> benchmark used in this work, and see that the instructions are using the
> licensing level not meant for heavy AVX512 operations. This means the
> instructions for popcount : _mm512_popcnt_epi64(),
> _mm512_reduce_add_epi64() are not going to have any significant impact on
> CPU clock frequency.
>
> Clock frequency impact aside, we measured the same benchmark for gains on
> older Intel hardware and observe up to 18% better performance on Intel
> Icelake. On older intel hardware, the popcntdq 512 instruction is not
> present so it won’t work. If clock frequency is not affected, rest of
> workload should not be impacted in the case of mixed workloads. 

Thanks for sharing your analysis.

> Testing this on smaller block sizes < 8KiB shows that AVX512 compared to
> the current 64bit behavior shows slightly lower performance, but with a
> large variance. We cannot conclude much from it. The testing with ANALYZE
> benchmark by Nathan also points to no visible impact as a result of using
> AVX512. The gains on larger dataset is easily evident, with less
> variance.
>
> What are your thoughts if we introduce AVX512 popcount for smaller sizes
> as an optional feature initially, and then test it more thoroughly over
> time on this particular use case? 

I don't see any need to rush this.  At the very earliest, this feature
would go into v17, which doesn't enter feature freeze until April 2024.
That seems like enough time to complete any additional testing you'd like
to do.  However, if you are seeing worse performance with this patch, then
it seems unlikely that we'd want to proceed.

> Thoughts or feedback on the approach in the patch? This solution should
> not impact anyone who doesn’t use the feature i.e. AVX512. Open to
> additional ideas if this doesn’t seem like the right approach here.  

It's true that it wouldn't impact anyone not using the feature, but there's
also a decent chance that this code goes virtually untested.  As I've
stated elsewhere [0], I think we should ensure there's buildfarm coverage
for this kind of architecture-specific stuff.

[0] https://postgr.es/m/20230726043707.GB3211130%40nathanxps13

---

From: "Shankaran, Akash" <[email-masked]>
Date: Thu, 25 Jan 2024 05:43:41 +0000

Sorry for the late response. We did some further testing and research on our end, and ended up modifying the AVX512 based algorithm for popcount. We removed a scalar dependency and accumulate the results of popcnt instruction in a zmm register, only performing the reduce add at the very end, similar to [0].

With the updated patch, we observed significant improvements and handily beat the previous popcount algorithm performance. No regressions in any scenario are observed:
Platform: Intel Xeon Platinum 8360Y (Icelake) for data sizes 1kb - 64kb.
Microbenchmark: 2x - 3x gains presently vs 19% previously, on the same microbenchmark described initially in this thread. 

PG testing: 
SQL bit_count() calls popcount. Using a Postgres benchmark calling "select bit_count(bytea(col1)) from mytable" on a table with ~2M text rows, each row 1-12kb in size, we observe (only comparing with 64bit PG implementation, which is the fastest): 

1. Entire benchmark using AVX512 implementation vs PG 64-bit impl runs 6-13% faster. 
2. Reduce time spent on pg_popcount() method in postgres server during the benchmark: 
	o	64bit (current PG):           29.5% 
	o	AVX512:             		 3.3%
3. Reduce number of samples processed by popcount: 
	o	64bit (current PG):          2.4B samples
	o	AVX512:                	285M samples

Compile above patch (on a machine supporting AVX512 vpopcntdq) using: make all CFLAGS_AVX512="-DHAVE__HW_AVX512_POPCNT -mavx -mavx512vpopcntdq -mavx512f -march=native
Attaching flamegraphs and patch for above observations. 

[0] https://github.com/WojciechMula/sse-popcount/blob/master/popcnt-avx512-vpopcnt.cpp

Thanks,
Akash Shankaran 

-----Original Message-----
From: Nathan Bossart <[email-masked]> 
Sent: Wednesday, November 15, 2023 1:49 PM
To: Shankaran, Akash <[email-masked]>
Cc: Noah Misch <[email-masked]>; Amonson, Paul D <[email-masked]>; Tom Lane <[email-masked]>; Matthias van de Meent <[email-masked]>; [email-masked]
Subject: Re: Popcount optimization using AVX512

On Wed, Nov 15, 2023 at 08:27:57PM +0000, Shankaran, Akash wrote:
> benchmark used in this work, and see that the instructions are using 
> the licensing level not meant for heavy AVX512 operations. This means 
> the instructions for popcount : _mm512_popcnt_epi64(),
> _mm512_reduce_add_epi64() are not going to have any significant impact 
> on CPU clock frequency.
>
> Clock frequency impact aside, we measured the same benchmark for gains 
> on older Intel hardware and observe up to 18% better performance on 
> Intel Icelake. On older intel hardware, the popcntdq 512 instruction 
> is not present so it won’t work. If clock frequency is not affected, 
> rest of workload should not be impacted in the case of mixed workloads.

> Testing this on smaller block sizes < 8KiB shows that AVX512 compared 
> to the current 64bit behavior shows slightly lower performance, but 
> with a large variance. We cannot conclude much from it. The testing 
> with ANALYZE benchmark by Nathan also points to no visible impact as a 
> result of using AVX512. The gains on larger dataset is easily evident, 
> with less variance.
>
> What are your thoughts if we introduce AVX512 popcount for smaller 
> sizes as an optional feature initially, and then test it more 
> thoroughly over time on this particular use case?

I don't see any need to rush this.  At the very earliest, this feature would go into v17, which doesn't enter feature freeze until April 2024.
That seems like enough time to complete any additional testing you'd like to do.  However, if you are seeing worse performance with this patch, then it seems unlikely that we'd want to proceed.

> Thoughts or feedback on the approach in the patch? This solution 
> should not impact anyone who doesn’t use the feature i.e. AVX512. Open 
> to additional ideas if this doesn’t seem like the right approach here.

It's true that it wouldn't impact anyone not using the feature, but there's also a decent chance that this code goes virtually untested.  As I've stated elsewhere [0], I think we should ensure there's buildfarm coverage for this kind of architecture-specific stuff.

---

From: Alvaro Herrera <[email-masked]>
Date: Thu, 25 Jan 2024 10:49:09 +0100

On 2024-Jan-25, Shankaran, Akash wrote:

> With the updated patch, we observed significant improvements and
> handily beat the previous popcount algorithm performance. No
> regressions in any scenario are observed:
> Microbenchmark: 2x - 3x gains presently vs 19% previously, on the same
> microbenchmark described initially in this thread. 

These are great results.

However, it would be much better if the improved code were available for
all relevant builds and activated if a CPUID test determines that the
relevant instructions are available, instead of requiring a compile-time
flag -- which most builds are not going to use, thus wasting the
opportunity for running the optimized code.

I suppose this would require patching pg_popcount64_choose() to be more
specific.  Looking at the existing code, I would also consider renaming
the "_fast" variants to something like pg_popcount32_asml/
pg_popcount64_asmq so that you can name the new one pg_popcount64_asmdq
or such.  (Or maybe leave the 32-bit version alone as "fast/slow", since
there's no third option for that one -- or do I misread?)

I also think this needs to move the CFLAGS-decision-making elsewhere;
asking the user to get it right is too much of a burden.  Is it workable
to simply verify compiler support for the additional flags needed, and
if so add them to a new CFLAGS_BITUTILS variable or such?  We already
have the CFLAGS_CRC model that should be easy to follow.  Should be easy
enough to mostly copy what's in configure.ac and meson.build, right?

Finally, the matter of using ifunc as proposed by Noah seems to be still
in the air, with no patches offered for the popcount family.  Given that
Nathan reports [1] a performance decrease, maybe we should set that
thought aside for now and continue to use function pointers.  It's worth
keeping in mind that popcount is already using function pointers (at
least in the case where we try to use POPCNT directly), so patching to
select between three options instead of between two wouldn't be a
regression.

[1] https://postgr.es/m/20231107201441.GA898662@nathanxps13

-- 
Álvaro Herrera               48°01'N 7°57'E  —  https://www.EnterpriseDB.com/
"Nunca se desea ardientemente lo que solo se desea por razón" (F. Alexandre)

---

From: Alvaro Herrera <[email-masked]>
Date: Fri, 26 Jan 2024 07:42:33 +0100

On 2024-Jan-25, Alvaro Herrera wrote:

> in the air, with no patches offered for the popcount family.

Oh, I just realized that the patch as currently proposed is placing the
optimized popcount code in the path that does not require going through
a function pointer.  So the performance increase is probably coming from
both avoiding jumping through the pointer as well as from the improved
instruction.

This suggests that finding a way to make the ifunc stuff work (with good
performance) is critical to this work.

-- 
Álvaro Herrera        Breisgau, Deutschland  —  https://www.EnterpriseDB.com/
"The ability of users to misuse tools is, of course, legendary" (David Steele)
https://postgr.es/m/[email-masked]