public inbox for [email protected]
help / color / mirror / Atom feedFrom: Shankaran, Akash <[email protected]>
To: Nathan Bossart <[email protected]>
Cc: Noah Misch <[email protected]>
Cc: 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: Thu, 25 Jan 2024 05:43:41 +0000
Message-ID: <PH0PR11MB5000C2258BF2804AAF7AAE27F27A2@PH0PR11MB5000.namprd11.prod.outlook.com> (raw)
In-Reply-To: <20231115214853.GC2448045@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>
<PH0PR11MB5000EFC19DD2C07F09871161F2B1A@PH0PR11MB5000.namprd11.prod.outlook.com>
<20231115214853.GC2448045@nathanxps13>
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 protected]>
Sent: Wednesday, November 15, 2023 1:49 PM
To: Shankaran, Akash <[email protected]>
Cc: Noah Misch <[email protected]>; Amonson, Paul D <[email protected]>; Tom Lane <[email protected]>; Matthias van de Meent <[email protected]>; [email protected]
Subject: Re: Popcount optimization using AVX512
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
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
Attachments:
[application/octet-stream] perf-avx512-1.8mrows.svg (154.0K, ../PH0PR11MB5000C2258BF2804AAF7AAE27F27A2@PH0PR11MB5000.namprd11.prod.outlook.com/2-perf-avx512-1.8mrows.svg)
download
[application/octet-stream] perf-with-64bit-1.8m.svg (138.2K, ../PH0PR11MB5000C2258BF2804AAF7AAE27F27A2@PH0PR11MB5000.namprd11.prod.outlook.com/3-perf-with-64bit-1.8m.svg)
download
[application/octet-stream] popcount_avx512.patch (1.9K, ../PH0PR11MB5000C2258BF2804AAF7AAE27F27A2@PH0PR11MB5000.namprd11.prod.outlook.com/4-popcount_avx512.patch)
download | inline diff:
diff --git a/src/port/Makefile b/src/port/Makefile
index dcc8737e68..354ab636da 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 some AVX-512 Capabilities (11/01/2023)
+pg_bitutils.o: CFLAGS+=$(CFLAGS_AVX512)
+pg_bitutils_shlib.o: CFLAGS+=$(CFLAGS_AVX512)
+pg_bitutils_srv.o:CFLAGS+=$(CFLAGS_AVX512)
+
# 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/pg_bitutils.c b/src/port/pg_bitutils.c
index 640a89561a..a0c91273ec 100644
--- a/src/port/pg_bitutils.c
+++ b/src/port/pg_bitutils.c
@@ -19,6 +19,10 @@
#include <intrin.h>
#endif
+#if defined(HAVE__HW_AVX512_POPCNT)
+#include <immintrin.h>
+#endif
+
#include "port/pg_bitutils.h"
@@ -298,6 +302,23 @@ pg_popcount(const char *buf, int bytes)
uint64 popcnt = 0;
#if SIZEOF_VOID_P >= 8
+#if defined(HAVE__HW_AVX512_POPCNT)
+ uint64 tmp[8] __attribute__((aligned(64)));
+ __m512i *pc_result = (__m512i *)tmp;
+ __m512i accumulator = _mm512_setzero_si512();
+ while (bytes >= 64)
+ {
+ const __m512i v = _mm512_loadu_si512((const __m512i *)buf);
+ const __m512i p = _mm512_popcnt_epi64(v);
+ accumulator = _mm512_add_epi64(accumulator, p);
+ bytes -= 64;
+ buf += 64;
+ }
+ _mm512_store_si512(pc_result, accumulator);
+ popcnt = _mm512_reduce_add_epi64(*pc_result);
+ bytes = bytes % 64;
+
+#else // HAVE__HW_AVX512_POPCNT
/* Process in 64-bit chunks if the buffer is aligned. */
if (buf == (const char *) TYPEALIGN(8, buf))
{
@@ -311,6 +332,7 @@ pg_popcount(const char *buf, int bytes)
buf = (const char *) words;
}
+#endif // HAVE__HW_AVX512_POPCNT
#else
/* Process in 32-bit chunks if the buffer is aligned. */
if (buf == (const char *) TYPEALIGN(4, buf))
view thread (37+ 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: <PH0PR11MB5000C2258BF2804AAF7AAE27F27A2@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