public inbox for [email protected]
help / color / mirror / Atom feedFrom: Shankaran, Akash <[email protected]>
To: Nathan Bossart <[email protected]>
To: Noah Misch <[email protected]>
To: Amonson, Paul D <[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: Wed, 15 Nov 2023 20:27:57 +0000
Message-ID: <PH0PR11MB5000EFC19DD2C07F09871161F2B1A@PH0PR11MB5000.namprd11.prod.outlook.com> (raw)
In-Reply-To: <20231107201441.GA898662@nathanxps13>
References: <BL1PR11MB5304097DF7EA81D04C33F3D1DCA6A@BL1PR11MB5304.namprd11.prod.outlook.com>
<CAEze2WjaFLhp7=Eo-mbSaHsoeq7ZEs00yZ2+FpSpijH+KN_hbA@mail.gmail.com>
<20231107022240.GA729644@nathanxps13>
<[email protected]>
<[email protected]>
<20231107035926.GD729644@nathanxps13>
<[email protected]>
<20231107201441.GA898662@nathanxps13>
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 protected]>
Sent: Tuesday, November 7, 2023 12:15 PM
To: Noah Misch <[email protected]>
Cc: Tom Lane <[email protected]>; Matthias van de Meent <[email protected]>; Amonson, Paul D <[email protected]>; [email protected]; Shankaran, Akash <[email protected]>
Subject: Re: Popcount optimization using AVX512
On Mon, Nov 06, 2023 at 09:53:15PM -0800, Noah Misch wrote:
> On Mon, Nov 06, 2023 at 09:59:26PM -0600, Nathan Bossart wrote:
>> On Mon, Nov 06, 2023 at 07:15:01PM -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:
>> > https://gcc.gnu.org/onlinedocs/gcc-4.8.5/gcc/Function-Attributes.ht
>> > ml
>>
>> 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.
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
Attachments:
[application/octet-stream] proposed_popcnt.patch (4.2K, ../PH0PR11MB5000EFC19DD2C07F09871161F2B1A@PH0PR11MB5000.namprd11.prod.outlook.com/2-proposed_popcnt.patch)
download | inline diff:
diff --git a/src/port/Makefile b/src/port/Makefile
index 4320dee0d1..1f6cbe362f 100644
--- a/src/port/Makefile
+++ b/src/port/Makefile
@@ -93,6 +93,7 @@ pg_crc32c_sse42_srv.o: CFLAGS+=$(CFLAGS_CRC)
pg_crc32c_armv8.o: CFLAGS+=$(CFLAGS_CRC)
pg_crc32c_armv8_shlib.o: CFLAGS+=$(CFLAGS_CRC)
pg_crc32c_armv8_srv.o: CFLAGS+=$(CFLAGS_CRC)
+pg_bitutils.o: CFLAGS+=$(CFLAGS_AVX512)
#
# Shared library versions of object files
diff --git a/src/port/pg_bitutils.c b/src/port/pg_bitutils.c
index 1f3dea2d4b..443b8b63ce 100644
--- a/src/port/pg_bitutils.c
+++ b/src/port/pg_bitutils.c
@@ -21,6 +21,21 @@
#include "port/pg_bitutils.h"
+#if (defined(__linux__) || defined(__linux) || defined(linux))
+#if defined(__x86_64) && defined(AVX512_POPCNT)
+/* Set macro for AVX-512 inclusion in the binary. */
+#define NEED_AVX512_POPCNTDQ 1
+
+#include <immintrin.h>
+
+/* Forward ref for AVX-512 private implementation */
+uint64 popcount_512_impl_unaligned(const char *buf, int bytes);
+#endif /* Platform and Flag for AVX-512 */
+#endif /* Linux */
+
+/* Forward refs for private refactor of 64-bit implementation */
+uint64 popcount_64_impl(const char *buf, int bytes);
+uint64 popcount_impl(const char *buf, int bytes);
/*
* Array giving the position of the left-most set bit for each possible
@@ -288,48 +303,99 @@ pg_popcount64(uint64 word)
#endif /* !TRY_POPCNT_FAST */
+inline uint64
+pg_popcnt_software(const char *buf, int bytes)
+{
+ uint64 popcnt = 0;
+ while (bytes--)
+ popcnt += pg_number_of_ones[(unsigned char)*buf++];
+ return popcnt;
+}
+
/*
* pg_popcount
* Returns the number of 1-bits in buf
*/
-uint64
+inline uint64
pg_popcount(const char *buf, int bytes)
-{
- uint64 popcnt = 0;
-
+{ /* Refatored for reuse in AVX-512 implementaitons. */
#if SIZEOF_VOID_P >= 8
/* Process in 64-bit chunks if the buffer is aligned. */
if (buf == (const char *) TYPEALIGN(8, buf))
- {
- const uint64 *words = (const uint64 *) buf;
+ return popcount_impl(buf, bytes);
+ else /* If not aligned use software only */
+ return pg_popcnt_software(buf, bytes);
+#else
+ return pg_popcnt_software(buf, bytes);
+#endif
+}
- while (bytes >= 8)
- {
- popcnt += pg_popcount64(*words++);
- bytes -= 8;
- }
+/*
+ * Refatored 64-bit algorithm using the refactored software
+ * algorithm for trailing bytes.
+ */
+inline uint64
+popcount_64_impl(const char *buf, int bytes)
+{
+ uint64 popcnt = 0;
- buf = (const char *) words;
- }
-#else
- /* Process in 32-bit chunks if the buffer is aligned. */
- if (buf == (const char *) TYPEALIGN(4, buf))
+ while (bytes >= sizeof(uint64))
{
- const uint32 *words = (const uint32 *) buf;
+ popcnt += pg_popcount64(*((const uint64 *)buf));
+ buf += sizeof(uint64);
+ bytes -= sizeof(uint64);
+ }
+
+ /* Process remaining bytes... */
+ popcnt += pg_popcnt_software(buf, bytes);
+ return popcnt;
+}
- while (bytes >= 4)
- {
- popcnt += pg_popcount32(*words++);
- bytes -= 4;
- }
+#if defined(NEED_AVX512_POPCNTDQ)
- buf = (const char *) words;
+#define LINE_SIZE_LOCAL 8192
+/*
+ * AVX-512 implementation for popcount using 64-bit algorithm
+ * for 512-bit unaligned leading and trailing portions.
+ */
+inline uint64
+popcount_512_impl_unaligned(const char *buf, int bytes)
+{
+ uint64 popcnt = 0;
+ uint64 remainder = ((uint64)buf) % 64;
+ popcnt += popcount_64_impl(buf, remainder);
+ bytes -= remainder;
+ buf += remainder;
+
+ __m512i *vectors = (__m512i *)buf;
+ while (bytes >= 64) {
+ popcnt += (uint64)_mm512_reduce_add_epi64(
+ _mm512_popcnt_epi64(*(vectors++)));
+ bytes -= 64;
}
-#endif
-
- /* Process any remaining bytes */
- while (bytes--)
- popcnt += pg_number_of_ones[(unsigned char) *buf++];
+ buf = (const char *)vectors;
+ popcnt += popcount_64_impl(buf, bytes);
return popcnt;
}
+#endif
+
+/*
+ * Called by pg_popcount when architecture is 64-bit and aligned.
+ * Will default to the original 64-bit algorithm if conditions for AVX-512
+ * are not met.
+ */
+inline uint64
+popcount_impl(const char *buf, int bytes)
+{
+#if defined(NEED_AVX512_POPCNTDQ)
+ if(bytes >= 25165824) /* 24MiB */
+ /* After testing, this is the threshhold where benefits for AVX-512
+ starts. */
+ return popcount_512_impl_unaligned(buf, bytes);
+ else
+ return popcount_64_impl(buf, bytes);
+#else
+ return popcount_64_impl(buf, bytes);
+#endif
+}
view thread (11+ 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]
Subject: RE: Popcount optimization using AVX512
In-Reply-To: <PH0PR11MB5000EFC19DD2C07F09871161F2B1A@PH0PR11MB5000.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