pg.ddx.io pgsql-hackers@postgresql.org mailing list archive
help / color / mirror / Atom feedadd AVX2 support to simd.h
48+ messages / 5 participants
[nested] [flat]
Commits from this thread:
2024-03-28 7188a7806d Improve style of pg_lfind32().
2024-03-27 1f42337be5 Fix compiler warning for pg_lfind32().
2024-03-26 7644a7340c Micro-optimize pg_lfind32().
* add AVX2 support to simd.h
@ 2023-11-29 17:15 Nathan Bossart <nathandbossart@gmail.com>
2024-01-01 12:12 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-08 07:01 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-09 14:03 ` Re: add AVX2 support to simd.h Peter Eisentraut <peter@eisentraut.org>
0 siblings, 3 replies; 48+ messages in thread
From: Nathan Bossart @ 2023-11-29 17:15 UTC (permalink / raw)
To: Ants Aasma <ants@cybertec.at>; +Cc: John Naylor <johncnaylorls@gmail.com>; pgsql-hackers
On Wed, Nov 22, 2023 at 12:49:35PM -0600, Nathan Bossart wrote:
> On Wed, Nov 22, 2023 at 02:54:13PM +0200, Ants Aasma wrote:
>> For reference, executing the page checksum 10M times on a AMD 3900X CPU:
>>
>> clang-14 -O2 4.292s (17.8 GiB/s)
>> clang-14 -O2 -msse4.1 2.859s (26.7 GiB/s)
>> clang-14 -O2 -msse4.1 -mavx2 1.378s (55.4 GiB/s)
>
> Nice. I've noticed similar improvements with AVX2 intrinsics in simd.h.
I've alluded to this a few times now, so I figured I'd park the patch and
preliminary benchmarks in a new thread while we iron out how to support
newer instructions (see discussion here [0]).
Using the same benchmark as we did for the SSE2 linear searches in
XidInMVCCSnapshot() (commit 37a6e5d) [1] [2], I see the following:
writers sse2 avx2 %
256 1195 1188 -1
512 928 1054 +14
1024 633 716 +13
2048 332 420 +27
4096 162 203 +25
8192 162 182 +12
It's been a while since I ran these benchmarks, but I vaguely recall also
seeing something like a 50% improvement for a dedicated pg_lfind32()
benchmark on long arrays.
As is, the patch likely won't do anything unless you add -mavx2 or
-march=native to your CFLAGS. I don't intend for this patch to be
seriously considered until we have better support for detecting/compiling
AVX2 instructions and a buildfarm machine that uses them.
I plan to start another thread for AVX2 support for the page checksums.
[0] https://postgr.es/m/20231107024734.GB729644%40nathanxps13
[1] https://postgr.es/m/057a9a95-19d2-05f0-17e2-f46ff20e9b3e@2ndquadrant.com
[2] https://postgr.es/m/20220713170950.GA3116318%40nathanxps13
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
Attachments:
v1-0001-add-avx2-support-in-simd.h.patch (text/x-diff, 4.1K) download
From 5a90f1597fdc64aa6df6b9d0ffd959af7df41abd Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathan@postgresql.org>
Date: Wed, 29 Nov 2023 10:01:32 -0600
Subject: [PATCH v1 1/1] add avx2 support in simd.h
---
src/include/port/simd.h | 50 ++++++++++++++++++++++++++++++++---------
1 file changed, 39 insertions(+), 11 deletions(-)
diff --git a/src/include/port/simd.h b/src/include/port/simd.h
index 1fa6c3bc6c..0e698dcfab 100644
--- a/src/include/port/simd.h
+++ b/src/include/port/simd.h
@@ -18,7 +18,15 @@
#ifndef SIMD_H
#define SIMD_H
-#if (defined(__x86_64__) || defined(_M_AMD64))
+#if defined(__AVX2__)
+
+#include <immintrin.h>
+#define USE_AVX2
+typedef __m256i Vector8;
+typedef __m256i Vector32;
+
+#elif (defined(__x86_64__) || defined(_M_AMD64))
+
/*
* SSE2 instructions are part of the spec for the 64-bit x86 ISA. We assume
* that compilers targeting this architecture understand SSE2 intrinsics.
@@ -105,7 +113,9 @@ static inline Vector32 vector32_eq(const Vector32 v1, const Vector32 v2);
static inline void
vector8_load(Vector8 *v, const uint8 *s)
{
-#if defined(USE_SSE2)
+#if defined(USE_AVX2)
+ *v = _mm256_loadu_si256((const __m256i *) s);
+#elif defined(USE_SSE2)
*v = _mm_loadu_si128((const __m128i *) s);
#elif defined(USE_NEON)
*v = vld1q_u8(s);
@@ -118,7 +128,9 @@ vector8_load(Vector8 *v, const uint8 *s)
static inline void
vector32_load(Vector32 *v, const uint32 *s)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ *v = _mm256_loadu_si256((const __m256i *) s);
+#elif defined(USE_SSE2)
*v = _mm_loadu_si128((const __m128i *) s);
#elif defined(USE_NEON)
*v = vld1q_u32(s);
@@ -132,7 +144,9 @@ vector32_load(Vector32 *v, const uint32 *s)
static inline Vector8
vector8_broadcast(const uint8 c)
{
-#if defined(USE_SSE2)
+#if defined(USE_AVX2)
+ return _mm256_set1_epi8(c);
+#elif defined(USE_SSE2)
return _mm_set1_epi8(c);
#elif defined(USE_NEON)
return vdupq_n_u8(c);
@@ -145,7 +159,9 @@ vector8_broadcast(const uint8 c)
static inline Vector32
vector32_broadcast(const uint32 c)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_set1_epi32(c);
+#elif defined(USE_SSE2)
return _mm_set1_epi32(c);
#elif defined(USE_NEON)
return vdupq_n_u32(c);
@@ -268,7 +284,9 @@ vector8_has_le(const Vector8 v, const uint8 c)
static inline bool
vector8_is_highbit_set(const Vector8 v)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_movemask_epi8(v) != 0;
+#elif defined(USE_SSE2)
return _mm_movemask_epi8(v) != 0;
#elif defined(USE_NEON)
return vmaxvq_u8(v) > 0x7F;
@@ -305,7 +323,9 @@ vector32_is_highbit_set(const Vector32 v)
static inline Vector8
vector8_or(const Vector8 v1, const Vector8 v2)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_or_si256(v1, v2);
+#elif defined(USE_SSE2)
return _mm_or_si128(v1, v2);
#elif defined(USE_NEON)
return vorrq_u8(v1, v2);
@@ -318,7 +338,9 @@ vector8_or(const Vector8 v1, const Vector8 v2)
static inline Vector32
vector32_or(const Vector32 v1, const Vector32 v2)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_or_si256(v1, v2);
+#elif defined(USE_SSE2)
return _mm_or_si128(v1, v2);
#elif defined(USE_NEON)
return vorrq_u32(v1, v2);
@@ -336,7 +358,9 @@ vector32_or(const Vector32 v1, const Vector32 v2)
static inline Vector8
vector8_ssub(const Vector8 v1, const Vector8 v2)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_subs_epu8(v1, v2);
+#elif defined(USE_SSE2)
return _mm_subs_epu8(v1, v2);
#elif defined(USE_NEON)
return vqsubq_u8(v1, v2);
@@ -352,7 +376,9 @@ vector8_ssub(const Vector8 v1, const Vector8 v2)
static inline Vector8
vector8_eq(const Vector8 v1, const Vector8 v2)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_cmpeq_epi8(v1, v2);
+#elif defined(USE_SSE2)
return _mm_cmpeq_epi8(v1, v2);
#elif defined(USE_NEON)
return vceqq_u8(v1, v2);
@@ -364,7 +390,9 @@ vector8_eq(const Vector8 v1, const Vector8 v2)
static inline Vector32
vector32_eq(const Vector32 v1, const Vector32 v2)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_cmpeq_epi32(v1, v2);
+#elif defined(USE_SSE2)
return _mm_cmpeq_epi32(v1, v2);
#elif defined(USE_NEON)
return vceqq_u32(v1, v2);
--
2.25.1
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
@ 2024-01-01 12:12 ` John Naylor <johncnaylorls@gmail.com>
2024-01-02 16:11 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2 siblings, 1 reply; 48+ messages in thread
From: John Naylor @ 2024-01-01 12:12 UTC (permalink / raw)
To: Nathan Bossart <nathandbossart@gmail.com>; +Cc: Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Thu, Nov 30, 2023 at 12:15 AM Nathan Bossart
<nathandbossart@gmail.com> wrote:
> I don't intend for this patch to be
> seriously considered until we have better support for detecting/compiling
> AVX2 instructions and a buildfarm machine that uses them.
That's completely understandable, yet I'm confused why there is a
commitfest entry for it marked "needs review".
^ permalink raw reply [nested|flat] 48+ messages in thread
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-01 12:12 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
@ 2024-01-02 16:11 ` Nathan Bossart <nathandbossart@gmail.com>
2024-01-02 17:50 ` Re: add AVX2 support to simd.h Tom Lane <tgl@sss.pgh.pa.us>
2024-01-03 14:13 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-04 17:48 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
0 siblings, 3 replies; 48+ messages in thread
From: Nathan Bossart @ 2024-01-02 16:11 UTC (permalink / raw)
To: John Naylor <johncnaylorls@gmail.com>; +Cc: Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Mon, Jan 01, 2024 at 07:12:26PM +0700, John Naylor wrote:
> On Thu, Nov 30, 2023 at 12:15 AM Nathan Bossart
> <nathandbossart@gmail.com> wrote:
>> I don't intend for this patch to be
>> seriously considered until we have better support for detecting/compiling
>> AVX2 instructions and a buildfarm machine that uses them.
>
> That's completely understandable, yet I'm confused why there is a
> commitfest entry for it marked "needs review".
Perhaps I was too optimistic about adding support for newer instructions...
I'm tempted to propose that we move forward with this patch as-is after
adding a buildfarm machine that compiles with -mavx2 or -march=x86-64-v3.
There is likely still follow-up work to make these improvements more
accessible, but I'm not sure that is a strict prerequisite here.
(In case it isn't clear, I'm volunteering to set up such a buildfarm
machine.)
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
^ permalink raw reply [nested|flat] 48+ messages in thread
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-01 12:12 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-02 16:11 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
@ 2024-01-02 17:50 ` Tom Lane <tgl@sss.pgh.pa.us>
2024-01-02 22:00 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2 siblings, 1 reply; 48+ messages in thread
From: Tom Lane @ 2024-01-02 17:50 UTC (permalink / raw)
To: Nathan Bossart <nathandbossart@gmail.com>; +Cc: John Naylor <johncnaylorls@gmail.com>; Ants Aasma <ants@cybertec.at>; pgsql-hackers
Nathan Bossart <nathandbossart@gmail.com> writes:
> I'm tempted to propose that we move forward with this patch as-is after
> adding a buildfarm machine that compiles with -mavx2 or -march=x86-64-v3.
> There is likely still follow-up work to make these improvements more
> accessible, but I'm not sure that is a strict prerequisite here.
The patch needs better comments (as in, more than "none whatsoever").
It doesn't need to be much though, perhaps like
+#if defined(__AVX2__)
+
+/*
+ * When compiled with -mavx2 or allied options, we prefer AVX2 instructions.
+ */
+#include <immintrin.h>
+#define USE_AVX2
+typedef __m256i Vector8;
+typedef __m256i Vector32;
Also, do you really want to structure the header so that USE_SSE2
doesn't get defined? In that case you are committing to provide
an AVX2 replacement every single place that there's USE_SSE2, which
doesn't seem like a great thing to require. OTOH, maybe there's
no choice given than we need a different definition for Vector8 and
Vector32?
regards, tom lane
^ permalink raw reply [nested|flat] 48+ messages in thread
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-01 12:12 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-02 16:11 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-02 17:50 ` Re: add AVX2 support to simd.h Tom Lane <tgl@sss.pgh.pa.us>
@ 2024-01-02 22:00 ` Nathan Bossart <nathandbossart@gmail.com>
0 siblings, 0 replies; 48+ messages in thread
From: Nathan Bossart @ 2024-01-02 22:00 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: John Naylor <johncnaylorls@gmail.com>; Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Tue, Jan 02, 2024 at 12:50:04PM -0500, Tom Lane wrote:
> The patch needs better comments (as in, more than "none whatsoever").
Yes, will do.
> Also, do you really want to structure the header so that USE_SSE2
> doesn't get defined? In that case you are committing to provide
> an AVX2 replacement every single place that there's USE_SSE2, which
> doesn't seem like a great thing to require. OTOH, maybe there's
> no choice given than we need a different definition for Vector8 and
> Vector32?
Yeah, the precedent is to use these abstracted types elsewhere so that any
SIMD-related improvements aren't limited to one architecture. There are a
couple of places that do explicitly check for USE_NO_SIMD, though. Maybe
there's an eventual use-case for using SSE2 intrinsics even when you have
AVX2 support, but for now, ensuring we have an AVX2 replacement for
everything doesn't seem particularly burdensome.
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
^ permalink raw reply [nested|flat] 48+ messages in thread
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-01 12:12 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-02 16:11 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
@ 2024-01-03 14:13 ` John Naylor <johncnaylorls@gmail.com>
2024-01-03 15:29 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2 siblings, 1 reply; 48+ messages in thread
From: John Naylor @ 2024-01-03 14:13 UTC (permalink / raw)
To: Nathan Bossart <nathandbossart@gmail.com>; +Cc: Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Tue, Jan 2, 2024 at 11:11 PM Nathan Bossart <nathandbossart@gmail.com> wrote:
>
> Perhaps I was too optimistic about adding support for newer instructions...
>
> I'm tempted to propose that we move forward with this patch as-is after
> adding a buildfarm machine that compiles with -mavx2 or -march=x86-64-v3.
That means that we would be on the hook to fix it if it breaks, even
though nothing uses it yet in a normal build. I have pending patches
that will break, or get broken by, this, so minus-many from me until
there is an availability story.
^ permalink raw reply [nested|flat] 48+ messages in thread
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-01 12:12 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-02 16:11 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-03 14:13 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
@ 2024-01-03 15:29 ` Nathan Bossart <nathandbossart@gmail.com>
2024-01-05 02:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
0 siblings, 1 reply; 48+ messages in thread
From: Nathan Bossart @ 2024-01-03 15:29 UTC (permalink / raw)
To: John Naylor <johncnaylorls@gmail.com>; +Cc: Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Wed, Jan 03, 2024 at 09:13:52PM +0700, John Naylor wrote:
> On Tue, Jan 2, 2024 at 11:11 PM Nathan Bossart <nathandbossart@gmail.com> wrote:
>> I'm tempted to propose that we move forward with this patch as-is after
>> adding a buildfarm machine that compiles with -mavx2 or -march=x86-64-v3.
>
> That means that we would be on the hook to fix it if it breaks, even
> though nothing uses it yet in a normal build. I have pending patches
> that will break, or get broken by, this, so minus-many from me until
> there is an availability story.
How will this break your patches? Is it just a matter of adding more AVX2
support, or something else?
If the requirement is that normal builds use AVX2, then I fear we will be
waiting a long time. IIUC the current proposals (building multiple
binaries or adding a configuration option that maps to compiler flags)
would still be opt-in, and I'm not sure we can mandate AVX2 support for all
x86_64 builds anytime soon.
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
^ permalink raw reply [nested|flat] 48+ messages in thread
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-01 12:12 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-02 16:11 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-03 14:13 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-03 15:29 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
@ 2024-01-05 02:03 ` John Naylor <johncnaylorls@gmail.com>
2024-01-05 17:04 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
0 siblings, 1 reply; 48+ messages in thread
From: John Naylor @ 2024-01-05 02:03 UTC (permalink / raw)
To: Nathan Bossart <nathandbossart@gmail.com>; +Cc: Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Wed, Jan 3, 2024 at 10:29 PM Nathan Bossart <nathandbossart@gmail.com> wrote:
> If the requirement is that normal builds use AVX2, then I fear we will be
> waiting a long time. IIUC the current proposals (building multiple
> binaries or adding a configuration option that maps to compiler flags)
> would still be opt-in,
If and when we get one of those, I would consider that a "normal"
build. Since there are no concrete proposals yet, I'm still waiting
for you to justify imposing an immediate maintenance cost for zero
benefit.
^ permalink raw reply [nested|flat] 48+ messages in thread
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-01 12:12 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-02 16:11 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-03 14:13 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-03 15:29 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-05 02:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
@ 2024-01-05 17:04 ` Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 09:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
0 siblings, 1 reply; 48+ messages in thread
From: Nathan Bossart @ 2024-01-05 17:04 UTC (permalink / raw)
To: John Naylor <johncnaylorls@gmail.com>; +Cc: Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Fri, Jan 05, 2024 at 09:03:39AM +0700, John Naylor wrote:
> On Wed, Jan 3, 2024 at 10:29 PM Nathan Bossart <nathandbossart@gmail.com> wrote:
>> If the requirement is that normal builds use AVX2, then I fear we will be
>> waiting a long time. IIUC the current proposals (building multiple
>> binaries or adding a configuration option that maps to compiler flags)
>> would still be opt-in,
>
> If and when we get one of those, I would consider that a "normal"
> build. Since there are no concrete proposals yet, I'm still waiting
> for you to justify imposing an immediate maintenance cost for zero
> benefit.
I've been thinking about the configuration option approach. ISTM that
would be the most feasible strategy, at least for v17. A couple things
come to mind:
* This option would simply map to existing compiler flags. We already have
ways to provide those (-Dc_args in meson, CFLAGS in autoconf). Perhaps
we'd want to provide our own shorthand for certain platforms (e.g., ARM),
but that will still just be shorthand for compiler flags.
* Such an option would itself generate some maintenance cost. That could
be worth it because it formalizes the Postgres support for those options,
but it's still one more thing to track.
Another related option could be to simply document that we have support for
some newer instructions that can be enabled by setting the aforementioned
compiler flags. That's perhaps a little less user-friendly, but it'd avoid
the duplication and possibly reduce the maintenance cost. I also wonder if
it'd help prevent confusion when CFLAGS and this extra option conflict.
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
^ permalink raw reply [nested|flat] 48+ messages in thread
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-01 12:12 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-02 16:11 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-03 14:13 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-03 15:29 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-05 02:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-05 17:04 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
@ 2024-01-08 09:03 ` John Naylor <johncnaylorls@gmail.com>
0 siblings, 0 replies; 48+ messages in thread
From: John Naylor @ 2024-01-08 09:03 UTC (permalink / raw)
To: Nathan Bossart <nathandbossart@gmail.com>; +Cc: Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Sat, Jan 6, 2024 at 12:04 AM Nathan Bossart <nathandbossart@gmail.com> wrote:
> I've been thinking about the configuration option approach. ISTM that
> would be the most feasible strategy, at least for v17. A couple things
> come to mind:
>
> * This option would simply map to existing compiler flags. We already have
> ways to provide those (-Dc_args in meson, CFLAGS in autoconf). Perhaps
> we'd want to provide our own shorthand for certain platforms (e.g., ARM),
> but that will still just be shorthand for compiler flags.
>
> * Such an option would itself generate some maintenance cost. That could
> be worth it because it formalizes the Postgres support for those options,
> but it's still one more thing to track.
>
> Another related option could be to simply document that we have support for
> some newer instructions that can be enabled by setting the aforementioned
> compiler flags. That's perhaps a little less user-friendly, but it'd avoid
> the duplication and possibly reduce the maintenance cost. I also wonder if
> it'd help prevent confusion when CFLAGS and this extra option conflict.
The last one might offer more graceful forward compatibility if the
multiple-binaries idea gets any traction some day, because at that
point the additional config options are not needed, I think.
Another consideration is which way would touch the fewest places to
work with Windows, which uses the spelling /arch:AVX2 etc.
One small thing I would hope for from the finial version of this is
the ability to inline things where we currently indirect depending on
a run-time check. That seems like "just work" on top of everything
else, and I don't think it makes a case for either of the above.
^ permalink raw reply [nested|flat] 48+ messages in thread
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-01 12:12 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-02 16:11 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
@ 2024-01-04 17:48 ` Nathan Bossart <nathandbossart@gmail.com>
2 siblings, 0 replies; 48+ messages in thread
From: Nathan Bossart @ 2024-01-04 17:48 UTC (permalink / raw)
To: John Naylor <johncnaylorls@gmail.com>; +Cc: Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Tue, Jan 02, 2024 at 10:11:23AM -0600, Nathan Bossart wrote:
> (In case it isn't clear, I'm volunteering to set up such a buildfarm
> machine.)
I set up "akepa" to run with -march=x86-64-v3.
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
^ permalink raw reply [nested|flat] 48+ messages in thread
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
@ 2024-01-08 07:01 ` John Naylor <johncnaylorls@gmail.com>
2024-01-08 17:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2 siblings, 1 reply; 48+ messages in thread
From: John Naylor @ 2024-01-08 07:01 UTC (permalink / raw)
To: Nathan Bossart <nathandbossart@gmail.com>; +Cc: Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Thu, Nov 30, 2023 at 12:15 AM Nathan Bossart
<nathandbossart@gmail.com> wrote:
> Using the same benchmark as we did for the SSE2 linear searches in
> XidInMVCCSnapshot() (commit 37a6e5d) [1] [2], I see the following:
I've been antagonistic towards the patch itself, but it'd be more
productive if I paid some nuanced attention to the problem it's trying
to solve. First, I'd like to understand the benchmark a bit better.
> writers sse2 avx2 %
> 256 1195 1188 -1
> 512 928 1054 +14
> 1024 633 716 +13
> 2048 332 420 +27
> 4096 162 203 +25
> 8192 162 182 +12
There doesn't seem to be any benefit at 256 at all. Is that expected
and/or fine?
> It's been a while since I ran these benchmarks, but I vaguely recall also
> seeing something like a 50% improvement for a dedicated pg_lfind32()
> benchmark on long arrays.
The latest I see in
https://www.postgresql.org/message-id/20220808223254.GA1393216%40nathanxps13
writers head patch
8 672 680
16 639 664
32 701 689
64 705 703
128 628 653
256 576 627
512 530 584
768 450 536
1024 350 494
Here, the peak throughput seems to be around 64 writers with or
without the patch from a couple years ago, but the slope is shallower
after that. It would be good to make sure that it can't regress near
the peak, even with a "long tail" case (see next paragraph). The first
benchmark above starts at 256, so we can't tell where the peak is. It
might be worth it to also have a microbenchmark because the systemic
one has enough noise to obscure what's going on unless there are a
very large number of writers. We know what a systemic benchmark can
tell us on extreme workloads past the peak, and the microbenchmark
would tell us "we need to see X improvement here in order to see Y
improvement in the system benchmark".
I suspect that there could be a regression lurking for some inputs
that the benchmark doesn't look at: pg_lfind32() currently needs to be
able to read 4 vector registers worth of elements before taking the
fast path. There is then a tail of up to 15 elements that are now
checked one-by-one, but AVX2 would increase that to 31. That's getting
big enough to be noticeable, I suspect. It would be good to understand
that case (n*32 + 31), because it may also be relevant now. It's also
easy to improve for SSE2/NEON for v17.
Also, by reading 4 registers per loop iteration, that's 128 bytes on
AVX2. I'm not sure that matters, but we shouldn't assume it doesn't.
Code I've seen elsewhere reads a fixed 64-byte block, and then uses 1,
2, or 4 registers to handle it, depending on architecture. Whether or
not that's worth it in this case, this patch does mean future patches
will have to wonder if they have to do anything differently depending
on vector length, whereas now they don't. That's not a deal-breaker,
but it is a trade-off to keep in mind.
^ permalink raw reply [nested|flat] 48+ messages in thread
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 07:01 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
@ 2024-01-08 17:37 ` Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 02:20 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
0 siblings, 1 reply; 48+ messages in thread
From: Nathan Bossart @ 2024-01-08 17:37 UTC (permalink / raw)
To: John Naylor <johncnaylorls@gmail.com>; +Cc: Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Mon, Jan 08, 2024 at 02:01:39PM +0700, John Naylor wrote:
> On Thu, Nov 30, 2023 at 12:15 AM Nathan Bossart
> <nathandbossart@gmail.com> wrote:
>> writers sse2 avx2 %
>> 256 1195 1188 -1
>> 512 928 1054 +14
>> 1024 633 716 +13
>> 2048 332 420 +27
>> 4096 162 203 +25
>> 8192 162 182 +12
>
> There doesn't seem to be any benefit at 256 at all. Is that expected
> and/or fine?
My unverified assumption is that the linear searches make up much less of
the benchmark at these lower client counts, so any improvements we make
here are unlikely to show up here. IIRC even the hash table approach that
we originally explored for XidInMVCCSnapshot() didn't do much, if anything,
for the benchmark at lower client counts.
> Here, the peak throughput seems to be around 64 writers with or
> without the patch from a couple years ago, but the slope is shallower
> after that. It would be good to make sure that it can't regress near
> the peak, even with a "long tail" case (see next paragraph). The first
> benchmark above starts at 256, so we can't tell where the peak is. It
> might be worth it to also have a microbenchmark because the systemic
> one has enough noise to obscure what's going on unless there are a
> very large number of writers. We know what a systemic benchmark can
> tell us on extreme workloads past the peak, and the microbenchmark
> would tell us "we need to see X improvement here in order to see Y
> improvement in the system benchmark".
Yes, will do.
> I suspect that there could be a regression lurking for some inputs
> that the benchmark doesn't look at: pg_lfind32() currently needs to be
> able to read 4 vector registers worth of elements before taking the
> fast path. There is then a tail of up to 15 elements that are now
> checked one-by-one, but AVX2 would increase that to 31. That's getting
> big enough to be noticeable, I suspect. It would be good to understand
> that case (n*32 + 31), because it may also be relevant now. It's also
> easy to improve for SSE2/NEON for v17.
Good idea. If it is indeed noticeable, we might be able to "fix" it by
processing some of the tail with shorter vectors. But that probably means
finding a way to support multiple vector sizes on the same build, which
would require some work.
> Also, by reading 4 registers per loop iteration, that's 128 bytes on
> AVX2. I'm not sure that matters, but we shouldn't assume it doesn't.
> Code I've seen elsewhere reads a fixed 64-byte block, and then uses 1,
> 2, or 4 registers to handle it, depending on architecture. Whether or
> not that's worth it in this case, this patch does mean future patches
> will have to wonder if they have to do anything differently depending
> on vector length, whereas now they don't. That's not a deal-breaker,
> but it is a trade-off to keep in mind.
Yeah. Presently, this AVX2 patch just kicks the optimization down the road
a bit for the existing use-cases, so you don't start using the vector
registers until there's more data to work with, which might not even be
noticeable. But it's conceivable that vector length could matter at some
point, even if it doesn't matter much now.
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
^ permalink raw reply [nested|flat] 48+ messages in thread
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 07:01 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-08 17:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
@ 2024-01-09 02:20 ` John Naylor <johncnaylorls@gmail.com>
2024-01-09 16:20 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
0 siblings, 1 reply; 48+ messages in thread
From: John Naylor @ 2024-01-09 02:20 UTC (permalink / raw)
To: Nathan Bossart <nathandbossart@gmail.com>; +Cc: Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Tue, Jan 9, 2024 at 12:37 AM Nathan Bossart <nathandbossart@gmail.com> wrote:
>
> > I suspect that there could be a regression lurking for some inputs
> > that the benchmark doesn't look at: pg_lfind32() currently needs to be
> > able to read 4 vector registers worth of elements before taking the
> > fast path. There is then a tail of up to 15 elements that are now
> > checked one-by-one, but AVX2 would increase that to 31. That's getting
> > big enough to be noticeable, I suspect. It would be good to understand
> > that case (n*32 + 31), because it may also be relevant now. It's also
> > easy to improve for SSE2/NEON for v17.
>
> Good idea. If it is indeed noticeable, we might be able to "fix" it by
> processing some of the tail with shorter vectors. But that probably means
> finding a way to support multiple vector sizes on the same build, which
> would require some work.
What I had in mind was an overlapping pattern I've seen in various
places: do one iteration at the beginning, then subtract the
aligned-down length from the end and do all those iterations. And
one-by-one is only used if the total length is small.
^ permalink raw reply [nested|flat] 48+ messages in thread
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 07:01 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-08 17:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 02:20 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
@ 2024-01-09 16:20 ` Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 21:21 ` Re: add AVX2 support to simd.h Ants Aasma <ants.aasma@cybertec.at>
2024-01-10 02:06 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
0 siblings, 2 replies; 48+ messages in thread
From: Nathan Bossart @ 2024-01-09 16:20 UTC (permalink / raw)
To: John Naylor <johncnaylorls@gmail.com>; +Cc: Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Tue, Jan 09, 2024 at 09:20:09AM +0700, John Naylor wrote:
> On Tue, Jan 9, 2024 at 12:37 AM Nathan Bossart <nathandbossart@gmail.com> wrote:
>>
>> > I suspect that there could be a regression lurking for some inputs
>> > that the benchmark doesn't look at: pg_lfind32() currently needs to be
>> > able to read 4 vector registers worth of elements before taking the
>> > fast path. There is then a tail of up to 15 elements that are now
>> > checked one-by-one, but AVX2 would increase that to 31. That's getting
>> > big enough to be noticeable, I suspect. It would be good to understand
>> > that case (n*32 + 31), because it may also be relevant now. It's also
>> > easy to improve for SSE2/NEON for v17.
>>
>> Good idea. If it is indeed noticeable, we might be able to "fix" it by
>> processing some of the tail with shorter vectors. But that probably means
>> finding a way to support multiple vector sizes on the same build, which
>> would require some work.
>
> What I had in mind was an overlapping pattern I've seen in various
> places: do one iteration at the beginning, then subtract the
> aligned-down length from the end and do all those iterations. And
> one-by-one is only used if the total length is small.
Sorry, I'm not sure I understood this. Do you mean processing the first
several elements individually or with SSE2 until the number of remaining
elements can be processed with just the AVX2 instructions (a bit like how
pg_comp_crc32c_armv8() is structured for memory alignment)?
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
^ permalink raw reply [nested|flat] 48+ messages in thread
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 07:01 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-08 17:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 02:20 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-09 16:20 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
@ 2024-01-09 21:21 ` Ants Aasma <ants.aasma@cybertec.at>
1 sibling, 0 replies; 48+ messages in thread
From: Ants Aasma @ 2024-01-09 21:21 UTC (permalink / raw)
To: Nathan Bossart <nathandbossart@gmail.com>; +Cc: John Naylor <johncnaylorls@gmail.com>; pgsql-hackers
On Tue, 9 Jan 2024 at 18:20, Nathan Bossart <nathandbossart@gmail.com> wrote:
>
> On Tue, Jan 09, 2024 at 09:20:09AM +0700, John Naylor wrote:
> > On Tue, Jan 9, 2024 at 12:37 AM Nathan Bossart <nathandbossart@gmail.com> wrote:
> >>
> >> > I suspect that there could be a regression lurking for some inputs
> >> > that the benchmark doesn't look at: pg_lfind32() currently needs to be
> >> > able to read 4 vector registers worth of elements before taking the
> >> > fast path. There is then a tail of up to 15 elements that are now
> >> > checked one-by-one, but AVX2 would increase that to 31. That's getting
> >> > big enough to be noticeable, I suspect. It would be good to understand
> >> > that case (n*32 + 31), because it may also be relevant now. It's also
> >> > easy to improve for SSE2/NEON for v17.
> >>
> >> Good idea. If it is indeed noticeable, we might be able to "fix" it by
> >> processing some of the tail with shorter vectors. But that probably means
> >> finding a way to support multiple vector sizes on the same build, which
> >> would require some work.
> >
> > What I had in mind was an overlapping pattern I've seen in various
> > places: do one iteration at the beginning, then subtract the
> > aligned-down length from the end and do all those iterations. And
> > one-by-one is only used if the total length is small.
>
> Sorry, I'm not sure I understood this. Do you mean processing the first
> several elements individually or with SSE2 until the number of remaining
> elements can be processed with just the AVX2 instructions (a bit like how
> pg_comp_crc32c_armv8() is structured for memory alignment)?
For some operations (min, max, = any) processing the same elements
multiple times doesn't change the result. So the vectors for first
and/or last iterations can overlap with the main loop. In other cases
it's possible to mask out the invalid elements and replace them with
zeroes. Something along the lines of:
static inline Vector8
vector8_mask_right(int num_valid)
{
__m256i seq = _mm256_set_epi8(31, 30, 29, 28, 27, 26, 25, 24,
23, 22, 21, 20, 19, 18, 17, 16,
15, 14, 13, 12, 11, 10, 9, 8,
7, 6, 5, 4, 3, 2, 1, 0);
return _mm256_cmpgt_epi8(_mm256_set1_epi8(num_valid), seq);
}
/* final incomplete iteration */
Vector8 mask = vector8_mask_right(end - cur);
final_vec = vector8_and((Vector8*) (end - sizeof(Vector8), mask);
accum = vector8_add(accum, final_vec);
It helps that on any halfway recent x86 unaligned loads only have a
minor performance penalty and only when straddling cache line
boundaries. Not sure what the state on ARM is. If we don't care about
unaligned loads then we only need to care about the load not crossing
page boundaries which could cause segfaults. Though I'm sure memory
sanitizer tools will have plenty to complain about around such hacks.
^ permalink raw reply [nested|flat] 48+ messages in thread
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 07:01 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-08 17:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 02:20 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-09 16:20 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
@ 2024-01-10 02:06 ` John Naylor <johncnaylorls@gmail.com>
2024-03-15 17:41 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
1 sibling, 1 reply; 48+ messages in thread
From: John Naylor @ 2024-01-10 02:06 UTC (permalink / raw)
To: Nathan Bossart <nathandbossart@gmail.com>; +Cc: Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Tue, Jan 9, 2024 at 11:20 PM Nathan Bossart <nathandbossart@gmail.com> wrote:
>
> On Tue, Jan 09, 2024 at 09:20:09AM +0700, John Naylor wrote:
> > On Tue, Jan 9, 2024 at 12:37 AM Nathan Bossart <nathandbossart@gmail.com> wrote:
> >>
> >> > I suspect that there could be a regression lurking for some inputs
> >> > that the benchmark doesn't look at: pg_lfind32() currently needs to be
> >> > able to read 4 vector registers worth of elements before taking the
> >> > fast path. There is then a tail of up to 15 elements that are now
> >> > checked one-by-one, but AVX2 would increase that to 31. That's getting
> >> > big enough to be noticeable, I suspect. It would be good to understand
> >> > that case (n*32 + 31), because it may also be relevant now. It's also
> >> > easy to improve for SSE2/NEON for v17.
> >>
> >> Good idea. If it is indeed noticeable, we might be able to "fix" it by
> >> processing some of the tail with shorter vectors. But that probably means
> >> finding a way to support multiple vector sizes on the same build, which
> >> would require some work.
> >
> > What I had in mind was an overlapping pattern I've seen in various
> > places: do one iteration at the beginning, then subtract the
> > aligned-down length from the end and do all those iterations. And
> > one-by-one is only used if the total length is small.
>
> Sorry, I'm not sure I understood this. Do you mean processing the first
> several elements individually or with SSE2 until the number of remaining
> elements can be processed with just the AVX2 instructions (a bit like how
> pg_comp_crc32c_armv8() is structured for memory alignment)?
If we have say 25 elements, I mean (for SSE2) check the first 16, then
the last 16. Some will be checked twice, but that's okay.
^ permalink raw reply [nested|flat] 48+ messages in thread
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 07:01 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-08 17:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 02:20 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-09 16:20 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-10 02:06 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
@ 2024-03-15 17:41 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-15 19:40 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
0 siblings, 1 reply; 48+ messages in thread
From: Nathan Bossart @ 2024-03-15 17:41 UTC (permalink / raw)
To: John Naylor <johncnaylorls@gmail.com>; +Cc: Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Wed, Jan 10, 2024 at 09:06:08AM +0700, John Naylor wrote:
> If we have say 25 elements, I mean (for SSE2) check the first 16, then
> the last 16. Some will be checked twice, but that's okay.
I finally got around to trying this. 0001 adds this overlapping logic.
0002 is a rebased version of the AVX2 patch (it needed some updates after
commit 9f225e9). And 0003 is a benchmark for test_lfind32(). It runs
pg_lfind32() on an array of the given size 100M times.
I've also attached the results of running this benchmark on my machine at
HEAD, after applying 0001, and after applying both 0001 and 0002. 0001
appears to work pretty well. When there is a small "tail," it regresses a
small amount, but overall, it seems to improve more cases than it harms.
0002 does regress searches on smaller arrays quite a bit, since it
postpones the SIMD optimizations until the arrays are longer. It might be
possible to mitigate by using 2 registers when the "tail" is long enough,
but I have yet to try that.
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
Attachments: download all (4 files, .tar.gz)
v2-0001-pg_lfind32-process-tail-with-SIMD-intructions.patch (text/x-diff, 1.4K) download
From 3a4d74eeab18d9e8f510e11185109ed910e40268 Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathan@postgresql.org>
Date: Fri, 15 Mar 2024 12:26:26 -0500
Subject: [PATCH v2 1/3] pg_lfind32: process "tail" with SIMD intructions
---
src/include/port/pg_lfind.h | 16 ++++++++++++++--
1 file changed, 14 insertions(+), 2 deletions(-)
diff --git a/src/include/port/pg_lfind.h b/src/include/port/pg_lfind.h
index b8dfa66eef..9d21284724 100644
--- a/src/include/port/pg_lfind.h
+++ b/src/include/port/pg_lfind.h
@@ -103,7 +103,7 @@ pg_lfind32(uint32 key, uint32 *base, uint32 nelem)
const uint32 nelem_per_iteration = 4 * nelem_per_vector;
/* round down to multiple of elements per iteration */
- const uint32 tail_idx = nelem & ~(nelem_per_iteration - 1);
+ uint32 tail_idx = nelem & ~(nelem_per_iteration - 1);
#if defined(USE_ASSERT_CHECKING)
bool assert_result = false;
@@ -117,9 +117,11 @@ pg_lfind32(uint32 key, uint32 *base, uint32 nelem)
break;
}
}
+ i = 0;
#endif
- for (i = 0; i < tail_idx; i += nelem_per_iteration)
+retry:
+ for (; i < tail_idx; i += nelem_per_iteration)
{
Vector32 vals1,
vals2,
@@ -157,6 +159,16 @@ pg_lfind32(uint32 key, uint32 *base, uint32 nelem)
return true;
}
}
+
+ if (i == nelem)
+ return false;
+ else if (tail_idx > 0)
+ {
+ tail_idx = nelem;
+ i = nelem - nelem_per_iteration;
+ goto retry;
+ }
+
#endif /* ! USE_NO_SIMD */
/* Process the remaining elements one at a time. */
--
2.25.1
v2-0002-add-avx2-support-in-simd.h.patch (text/x-diff, 4.7K) download
From 0ac61e17b6ed07116086ded2a6a5142da9afa28f Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathan@postgresql.org>
Date: Fri, 15 Mar 2024 12:26:52 -0500
Subject: [PATCH v2 2/3] add avx2 support in simd.h
---
src/include/port/simd.h | 58 ++++++++++++++++++++++++++++++++---------
1 file changed, 45 insertions(+), 13 deletions(-)
diff --git a/src/include/port/simd.h b/src/include/port/simd.h
index 597496f2fb..767127b85c 100644
--- a/src/include/port/simd.h
+++ b/src/include/port/simd.h
@@ -18,7 +18,15 @@
#ifndef SIMD_H
#define SIMD_H
-#if (defined(__x86_64__) || defined(_M_AMD64))
+#if defined(__AVX2__)
+
+#include <immintrin.h>
+#define USE_AVX2
+typedef __m256i Vector8;
+typedef __m256i Vector32;
+
+#elif (defined(__x86_64__) || defined(_M_AMD64))
+
/*
* SSE2 instructions are part of the spec for the 64-bit x86 ISA. We assume
* that compilers targeting this architecture understand SSE2 intrinsics.
@@ -107,7 +115,9 @@ static inline Vector32 vector32_eq(const Vector32 v1, const Vector32 v2);
static inline void
vector8_load(Vector8 *v, const uint8 *s)
{
-#if defined(USE_SSE2)
+#if defined(USE_AVX2)
+ *v = _mm256_loadu_si256((const __m256i *) s);
+#elif defined(USE_SSE2)
*v = _mm_loadu_si128((const __m128i *) s);
#elif defined(USE_NEON)
*v = vld1q_u8(s);
@@ -120,7 +130,9 @@ vector8_load(Vector8 *v, const uint8 *s)
static inline void
vector32_load(Vector32 *v, const uint32 *s)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ *v = _mm256_loadu_si256((const __m256i *) s);
+#elif defined(USE_SSE2)
*v = _mm_loadu_si128((const __m128i *) s);
#elif defined(USE_NEON)
*v = vld1q_u32(s);
@@ -134,7 +146,9 @@ vector32_load(Vector32 *v, const uint32 *s)
static inline Vector8
vector8_broadcast(const uint8 c)
{
-#if defined(USE_SSE2)
+#if defined(USE_AVX2)
+ return _mm256_set1_epi8(c);
+#elif defined(USE_SSE2)
return _mm_set1_epi8(c);
#elif defined(USE_NEON)
return vdupq_n_u8(c);
@@ -147,7 +161,9 @@ vector8_broadcast(const uint8 c)
static inline Vector32
vector32_broadcast(const uint32 c)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_set1_epi32(c);
+#elif defined(USE_SSE2)
return _mm_set1_epi32(c);
#elif defined(USE_NEON)
return vdupq_n_u32(c);
@@ -270,7 +286,9 @@ vector8_has_le(const Vector8 v, const uint8 c)
static inline bool
vector8_is_highbit_set(const Vector8 v)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_movemask_epi8(v) != 0;
+#elif defined(USE_SSE2)
return _mm_movemask_epi8(v) != 0;
#elif defined(USE_NEON)
return vmaxvq_u8(v) > 0x7F;
@@ -308,7 +326,9 @@ vector32_is_highbit_set(const Vector32 v)
static inline uint32
vector8_highbit_mask(const Vector8 v)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return (uint32) _mm256_movemask_epi8(v);
+#elif defined(USE_SSE2)
return (uint32) _mm_movemask_epi8(v);
#elif defined(USE_NEON)
/*
@@ -337,7 +357,9 @@ vector8_highbit_mask(const Vector8 v)
static inline Vector8
vector8_or(const Vector8 v1, const Vector8 v2)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_or_si256(v1, v2);
+#elif defined(USE_SSE2)
return _mm_or_si128(v1, v2);
#elif defined(USE_NEON)
return vorrq_u8(v1, v2);
@@ -350,7 +372,9 @@ vector8_or(const Vector8 v1, const Vector8 v2)
static inline Vector32
vector32_or(const Vector32 v1, const Vector32 v2)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_or_si256(v1, v2);
+#elif defined(USE_SSE2)
return _mm_or_si128(v1, v2);
#elif defined(USE_NEON)
return vorrq_u32(v1, v2);
@@ -368,7 +392,9 @@ vector32_or(const Vector32 v1, const Vector32 v2)
static inline Vector8
vector8_ssub(const Vector8 v1, const Vector8 v2)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_subs_epu8(v1, v2);
+#elif defined(USE_SSE2)
return _mm_subs_epu8(v1, v2);
#elif defined(USE_NEON)
return vqsubq_u8(v1, v2);
@@ -384,7 +410,9 @@ vector8_ssub(const Vector8 v1, const Vector8 v2)
static inline Vector8
vector8_eq(const Vector8 v1, const Vector8 v2)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_cmpeq_epi8(v1, v2);
+#elif defined(USE_SSE2)
return _mm_cmpeq_epi8(v1, v2);
#elif defined(USE_NEON)
return vceqq_u8(v1, v2);
@@ -396,7 +424,9 @@ vector8_eq(const Vector8 v1, const Vector8 v2)
static inline Vector32
vector32_eq(const Vector32 v1, const Vector32 v2)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_cmpeq_epi32(v1, v2);
+#elif defined(USE_SSE2)
return _mm_cmpeq_epi32(v1, v2);
#elif defined(USE_NEON)
return vceqq_u32(v1, v2);
@@ -411,7 +441,9 @@ vector32_eq(const Vector32 v1, const Vector32 v2)
static inline Vector8
vector8_min(const Vector8 v1, const Vector8 v2)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_min_epu8(v1, v2);
+#elif defined(USE_SSE2)
return _mm_min_epu8(v1, v2);
#elif defined(USE_NEON)
return vminq_u8(v1, v2);
--
2.25.1
v2-0003-test_lfind32-benchmark.patch (text/x-diff, 3.6K) download
From 9b2b61927a8b52637f70659d513ddfeba7c03024 Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathan@postgresql.org>
Date: Fri, 15 Mar 2024 12:28:00 -0500
Subject: [PATCH v2 3/3] test_lfind32() benchmark
---
.../modules/test_lfind/sql/test_lfind.sql | 67 +++++++++++++++++++
.../modules/test_lfind/test_lfind--1.0.sql | 4 ++
src/test/modules/test_lfind/test_lfind.c | 16 +++++
3 files changed, 87 insertions(+)
diff --git a/src/test/modules/test_lfind/sql/test_lfind.sql b/src/test/modules/test_lfind/sql/test_lfind.sql
index 766c640831..d8fa461bfa 100644
--- a/src/test/modules/test_lfind/sql/test_lfind.sql
+++ b/src/test/modules/test_lfind/sql/test_lfind.sql
@@ -8,3 +8,70 @@ CREATE EXTENSION test_lfind;
SELECT test_lfind8();
SELECT test_lfind8_le();
SELECT test_lfind32();
+
+\timing on
+SELECT drive_lfind32(0);
+SELECT drive_lfind32(1);
+SELECT drive_lfind32(2);
+SELECT drive_lfind32(3);
+SELECT drive_lfind32(4);
+SELECT drive_lfind32(5);
+SELECT drive_lfind32(6);
+SELECT drive_lfind32(7);
+SELECT drive_lfind32(8);
+SELECT drive_lfind32(9);
+SELECT drive_lfind32(10);
+SELECT drive_lfind32(11);
+SELECT drive_lfind32(12);
+SELECT drive_lfind32(13);
+SELECT drive_lfind32(14);
+SELECT drive_lfind32(15);
+SELECT drive_lfind32(16);
+SELECT drive_lfind32(17);
+SELECT drive_lfind32(18);
+SELECT drive_lfind32(19);
+SELECT drive_lfind32(20);
+SELECT drive_lfind32(21);
+SELECT drive_lfind32(22);
+SELECT drive_lfind32(23);
+SELECT drive_lfind32(24);
+SELECT drive_lfind32(25);
+SELECT drive_lfind32(26);
+SELECT drive_lfind32(27);
+SELECT drive_lfind32(28);
+SELECT drive_lfind32(29);
+SELECT drive_lfind32(30);
+SELECT drive_lfind32(31);
+SELECT drive_lfind32(32);
+SELECT drive_lfind32(33);
+SELECT drive_lfind32(34);
+SELECT drive_lfind32(35);
+SELECT drive_lfind32(36);
+SELECT drive_lfind32(37);
+SELECT drive_lfind32(38);
+SELECT drive_lfind32(39);
+SELECT drive_lfind32(40);
+SELECT drive_lfind32(41);
+SELECT drive_lfind32(42);
+SELECT drive_lfind32(43);
+SELECT drive_lfind32(44);
+SELECT drive_lfind32(45);
+SELECT drive_lfind32(46);
+SELECT drive_lfind32(47);
+SELECT drive_lfind32(48);
+SELECT drive_lfind32(49);
+SELECT drive_lfind32(50);
+SELECT drive_lfind32(51);
+SELECT drive_lfind32(52);
+SELECT drive_lfind32(53);
+SELECT drive_lfind32(54);
+SELECT drive_lfind32(55);
+SELECT drive_lfind32(56);
+SELECT drive_lfind32(57);
+SELECT drive_lfind32(58);
+SELECT drive_lfind32(59);
+SELECT drive_lfind32(60);
+SELECT drive_lfind32(61);
+SELECT drive_lfind32(62);
+SELECT drive_lfind32(63);
+SELECT drive_lfind32(64);
diff --git a/src/test/modules/test_lfind/test_lfind--1.0.sql b/src/test/modules/test_lfind/test_lfind--1.0.sql
index 81801926ae..6b396dbd58 100644
--- a/src/test/modules/test_lfind/test_lfind--1.0.sql
+++ b/src/test/modules/test_lfind/test_lfind--1.0.sql
@@ -14,3 +14,7 @@ CREATE FUNCTION test_lfind8()
CREATE FUNCTION test_lfind8_le()
RETURNS pg_catalog.void
AS 'MODULE_PATHNAME' LANGUAGE C;
+
+CREATE FUNCTION drive_lfind32(n int)
+ RETURNS pg_catalog.void
+ AS 'MODULE_PATHNAME' LANGUAGE C;
diff --git a/src/test/modules/test_lfind/test_lfind.c b/src/test/modules/test_lfind/test_lfind.c
index c04bc2f6b4..2234f148b6 100644
--- a/src/test/modules/test_lfind/test_lfind.c
+++ b/src/test/modules/test_lfind/test_lfind.c
@@ -146,3 +146,19 @@ test_lfind32(PG_FUNCTION_ARGS)
PG_RETURN_VOID();
}
+
+PG_FUNCTION_INFO_V1(drive_lfind32);
+Datum
+drive_lfind32(PG_FUNCTION_ARGS)
+{
+ int array_size = PG_GETARG_INT32(0);
+ uint32 *test_array = palloc0(array_size * sizeof(uint32));
+
+ for (int i = 0; i < 100000000; i++)
+ {
+ if (pg_lfind32(1, test_array, array_size))
+ elog(ERROR, "pg_lfind32() found nonexistent element");
+ }
+
+ PG_RETURN_VOID();
+}
--
2.25.1
avx2_bench_graph.jpg (image/jpeg, 28.0K) download
view image
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 07:01 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-08 17:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 02:20 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-09 16:20 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-10 02:06 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-15 17:41 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
@ 2024-03-15 19:40 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-17 02:47 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
0 siblings, 1 reply; 48+ messages in thread
From: Nathan Bossart @ 2024-03-15 19:40 UTC (permalink / raw)
To: John Naylor <johncnaylorls@gmail.com>; +Cc: Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Fri, Mar 15, 2024 at 12:41:49PM -0500, Nathan Bossart wrote:
> I've also attached the results of running this benchmark on my machine at
> HEAD, after applying 0001, and after applying both 0001 and 0002. 0001
> appears to work pretty well. When there is a small "tail," it regresses a
> small amount, but overall, it seems to improve more cases than it harms.
> 0002 does regress searches on smaller arrays quite a bit, since it
> postpones the SIMD optimizations until the arrays are longer. It might be
> possible to mitigate by using 2 registers when the "tail" is long enough,
> but I have yet to try that.
The attached 0003 is a sketch of what such mitigation might look like. It
appears to help with the regressions nicely. I omitted the benchmarking
patch in v3 to appease cfbot.
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
Attachments: download all (4 files, .tar.gz)
v3-0001-pg_lfind32-process-tail-with-SIMD-intructions.patch (text/x-diff, 1.4K) download
From 3817435d200af5da954d505ae66245662dea064c Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathan@postgresql.org>
Date: Fri, 15 Mar 2024 12:26:26 -0500
Subject: [PATCH v3 1/3] pg_lfind32: process "tail" with SIMD intructions
---
src/include/port/pg_lfind.h | 16 ++++++++++++++--
1 file changed, 14 insertions(+), 2 deletions(-)
diff --git a/src/include/port/pg_lfind.h b/src/include/port/pg_lfind.h
index b8dfa66eef..9d21284724 100644
--- a/src/include/port/pg_lfind.h
+++ b/src/include/port/pg_lfind.h
@@ -103,7 +103,7 @@ pg_lfind32(uint32 key, uint32 *base, uint32 nelem)
const uint32 nelem_per_iteration = 4 * nelem_per_vector;
/* round down to multiple of elements per iteration */
- const uint32 tail_idx = nelem & ~(nelem_per_iteration - 1);
+ uint32 tail_idx = nelem & ~(nelem_per_iteration - 1);
#if defined(USE_ASSERT_CHECKING)
bool assert_result = false;
@@ -117,9 +117,11 @@ pg_lfind32(uint32 key, uint32 *base, uint32 nelem)
break;
}
}
+ i = 0;
#endif
- for (i = 0; i < tail_idx; i += nelem_per_iteration)
+retry:
+ for (; i < tail_idx; i += nelem_per_iteration)
{
Vector32 vals1,
vals2,
@@ -157,6 +159,16 @@ pg_lfind32(uint32 key, uint32 *base, uint32 nelem)
return true;
}
}
+
+ if (i == nelem)
+ return false;
+ else if (tail_idx > 0)
+ {
+ tail_idx = nelem;
+ i = nelem - nelem_per_iteration;
+ goto retry;
+ }
+
#endif /* ! USE_NO_SIMD */
/* Process the remaining elements one at a time. */
--
2.25.1
v3-0002-add-avx2-support-in-simd.h.patch (text/x-diff, 4.7K) download
From a867e342db08aae501374c75c0d8f17473a6cbc9 Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathan@postgresql.org>
Date: Fri, 15 Mar 2024 12:26:52 -0500
Subject: [PATCH v3 2/3] add avx2 support in simd.h
---
src/include/port/simd.h | 58 ++++++++++++++++++++++++++++++++---------
1 file changed, 45 insertions(+), 13 deletions(-)
diff --git a/src/include/port/simd.h b/src/include/port/simd.h
index 597496f2fb..767127b85c 100644
--- a/src/include/port/simd.h
+++ b/src/include/port/simd.h
@@ -18,7 +18,15 @@
#ifndef SIMD_H
#define SIMD_H
-#if (defined(__x86_64__) || defined(_M_AMD64))
+#if defined(__AVX2__)
+
+#include <immintrin.h>
+#define USE_AVX2
+typedef __m256i Vector8;
+typedef __m256i Vector32;
+
+#elif (defined(__x86_64__) || defined(_M_AMD64))
+
/*
* SSE2 instructions are part of the spec for the 64-bit x86 ISA. We assume
* that compilers targeting this architecture understand SSE2 intrinsics.
@@ -107,7 +115,9 @@ static inline Vector32 vector32_eq(const Vector32 v1, const Vector32 v2);
static inline void
vector8_load(Vector8 *v, const uint8 *s)
{
-#if defined(USE_SSE2)
+#if defined(USE_AVX2)
+ *v = _mm256_loadu_si256((const __m256i *) s);
+#elif defined(USE_SSE2)
*v = _mm_loadu_si128((const __m128i *) s);
#elif defined(USE_NEON)
*v = vld1q_u8(s);
@@ -120,7 +130,9 @@ vector8_load(Vector8 *v, const uint8 *s)
static inline void
vector32_load(Vector32 *v, const uint32 *s)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ *v = _mm256_loadu_si256((const __m256i *) s);
+#elif defined(USE_SSE2)
*v = _mm_loadu_si128((const __m128i *) s);
#elif defined(USE_NEON)
*v = vld1q_u32(s);
@@ -134,7 +146,9 @@ vector32_load(Vector32 *v, const uint32 *s)
static inline Vector8
vector8_broadcast(const uint8 c)
{
-#if defined(USE_SSE2)
+#if defined(USE_AVX2)
+ return _mm256_set1_epi8(c);
+#elif defined(USE_SSE2)
return _mm_set1_epi8(c);
#elif defined(USE_NEON)
return vdupq_n_u8(c);
@@ -147,7 +161,9 @@ vector8_broadcast(const uint8 c)
static inline Vector32
vector32_broadcast(const uint32 c)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_set1_epi32(c);
+#elif defined(USE_SSE2)
return _mm_set1_epi32(c);
#elif defined(USE_NEON)
return vdupq_n_u32(c);
@@ -270,7 +286,9 @@ vector8_has_le(const Vector8 v, const uint8 c)
static inline bool
vector8_is_highbit_set(const Vector8 v)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_movemask_epi8(v) != 0;
+#elif defined(USE_SSE2)
return _mm_movemask_epi8(v) != 0;
#elif defined(USE_NEON)
return vmaxvq_u8(v) > 0x7F;
@@ -308,7 +326,9 @@ vector32_is_highbit_set(const Vector32 v)
static inline uint32
vector8_highbit_mask(const Vector8 v)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return (uint32) _mm256_movemask_epi8(v);
+#elif defined(USE_SSE2)
return (uint32) _mm_movemask_epi8(v);
#elif defined(USE_NEON)
/*
@@ -337,7 +357,9 @@ vector8_highbit_mask(const Vector8 v)
static inline Vector8
vector8_or(const Vector8 v1, const Vector8 v2)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_or_si256(v1, v2);
+#elif defined(USE_SSE2)
return _mm_or_si128(v1, v2);
#elif defined(USE_NEON)
return vorrq_u8(v1, v2);
@@ -350,7 +372,9 @@ vector8_or(const Vector8 v1, const Vector8 v2)
static inline Vector32
vector32_or(const Vector32 v1, const Vector32 v2)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_or_si256(v1, v2);
+#elif defined(USE_SSE2)
return _mm_or_si128(v1, v2);
#elif defined(USE_NEON)
return vorrq_u32(v1, v2);
@@ -368,7 +392,9 @@ vector32_or(const Vector32 v1, const Vector32 v2)
static inline Vector8
vector8_ssub(const Vector8 v1, const Vector8 v2)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_subs_epu8(v1, v2);
+#elif defined(USE_SSE2)
return _mm_subs_epu8(v1, v2);
#elif defined(USE_NEON)
return vqsubq_u8(v1, v2);
@@ -384,7 +410,9 @@ vector8_ssub(const Vector8 v1, const Vector8 v2)
static inline Vector8
vector8_eq(const Vector8 v1, const Vector8 v2)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_cmpeq_epi8(v1, v2);
+#elif defined(USE_SSE2)
return _mm_cmpeq_epi8(v1, v2);
#elif defined(USE_NEON)
return vceqq_u8(v1, v2);
@@ -396,7 +424,9 @@ vector8_eq(const Vector8 v1, const Vector8 v2)
static inline Vector32
vector32_eq(const Vector32 v1, const Vector32 v2)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_cmpeq_epi32(v1, v2);
+#elif defined(USE_SSE2)
return _mm_cmpeq_epi32(v1, v2);
#elif defined(USE_NEON)
return vceqq_u32(v1, v2);
@@ -411,7 +441,9 @@ vector32_eq(const Vector32 v1, const Vector32 v2)
static inline Vector8
vector8_min(const Vector8 v1, const Vector8 v2)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_min_epu8(v1, v2);
+#elif defined(USE_SSE2)
return _mm_min_epu8(v1, v2);
#elif defined(USE_NEON)
return vminq_u8(v1, v2);
--
2.25.1
v3-0003-optimize-pg_lfind32-by-processing-tail-with-fewer.patch (text/x-diff, 1.8K) download
From edd188759e4b937089c5bc2259a401cea1f9331f Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathan@postgresql.org>
Date: Fri, 15 Mar 2024 14:27:52 -0500
Subject: [PATCH v3 3/3] optimize pg_lfind32() by processing "tail" with fewer
vectors
---
src/include/port/pg_lfind.h | 29 +++++++++++++++++++++++++++--
1 file changed, 27 insertions(+), 2 deletions(-)
diff --git a/src/include/port/pg_lfind.h b/src/include/port/pg_lfind.h
index 9d21284724..9c6cce0b69 100644
--- a/src/include/port/pg_lfind.h
+++ b/src/include/port/pg_lfind.h
@@ -100,7 +100,7 @@ pg_lfind32(uint32 key, uint32 *base, uint32 nelem)
*/
const Vector32 keys = vector32_broadcast(key); /* load copies of key */
const uint32 nelem_per_vector = sizeof(Vector32) / sizeof(uint32);
- const uint32 nelem_per_iteration = 4 * nelem_per_vector;
+ uint32 nelem_per_iteration = 4 * nelem_per_vector;
/* round down to multiple of elements per iteration */
uint32 tail_idx = nelem & ~(nelem_per_iteration - 1);
@@ -120,7 +120,6 @@ pg_lfind32(uint32 key, uint32 *base, uint32 nelem)
i = 0;
#endif
-retry:
for (; i < tail_idx; i += nelem_per_iteration)
{
Vector32 vals1,
@@ -160,6 +159,32 @@ retry:
}
}
+retry:
+ nelem_per_iteration = 2 * nelem_per_vector;
+ tail_idx = nelem & ~(nelem_per_iteration - 1);
+ for (; i < tail_idx; i += nelem_per_iteration)
+ {
+ Vector32 vals1,
+ vals2,
+ result1,
+ result2,
+ result;
+
+ vector32_load(&vals1, &base[i]);
+ vector32_load(&vals2, &base[i + nelem_per_vector]);
+
+ result1 = vector32_eq(keys, vals1);
+ result2 = vector32_eq(keys, vals2);
+
+ result = vector32_or(result1, result2);
+
+ if (vector32_is_highbit_set(result))
+ {
+ Assert(assert_result == true);
+ return true;
+ }
+ }
+
if (i == nelem)
return false;
else if (tail_idx > 0)
--
2.25.1
avx2_bench_graph_2.jpg (image/jpeg, 25.2K) download
view image
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 07:01 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-08 17:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 02:20 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-09 16:20 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-10 02:06 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-15 17:41 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-15 19:40 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
@ 2024-03-17 02:47 ` John Naylor <johncnaylorls@gmail.com>
2024-03-19 02:03 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
0 siblings, 1 reply; 48+ messages in thread
From: John Naylor @ 2024-03-17 02:47 UTC (permalink / raw)
To: Nathan Bossart <nathandbossart@gmail.com>; +Cc: Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Sat, Mar 16, 2024 at 2:40 AM Nathan Bossart <nathandbossart@gmail.com> wrote:
>
> On Fri, Mar 15, 2024 at 12:41:49PM -0500, Nathan Bossart wrote:
> > I've also attached the results of running this benchmark on my machine at
> > HEAD, after applying 0001, and after applying both 0001 and 0002. 0001
> > appears to work pretty well. When there is a small "tail," it regresses a
> > small amount, but overall, it seems to improve more cases than it harms.
> > 0002 does regress searches on smaller arrays quite a bit, since it
> > postpones the SIMD optimizations until the arrays are longer. It might be
> > possible to mitigate by using 2 registers when the "tail" is long enough,
> > but I have yet to try that.
>
> The attached 0003 is a sketch of what such mitigation might look like. It
> appears to help with the regressions nicely. I omitted the benchmarking
> patch in v3 to appease cfbot.
I haven't looked at the patches, but the graphs look good.
^ permalink raw reply [nested|flat] 48+ messages in thread
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 07:01 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-08 17:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 02:20 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-09 16:20 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-10 02:06 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-15 17:41 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-15 19:40 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-17 02:47 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
@ 2024-03-19 02:03 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
0 siblings, 1 reply; 48+ messages in thread
From: Nathan Bossart @ 2024-03-19 02:03 UTC (permalink / raw)
To: John Naylor <johncnaylorls@gmail.com>; +Cc: Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Sun, Mar 17, 2024 at 09:47:33AM +0700, John Naylor wrote:
> I haven't looked at the patches, but the graphs look good.
I spent some more time on these patches. Specifically, I reordered them to
demonstrate the effects on systems without AVX2 support. I've also added a
shortcut to jump to the one-by-one approach when there aren't many
elements, as the overhead becomes quite noticeable otherwise. Finally, I
ran the same benchmarks again on x86 and Arm out to 128 elements.
Overall, I think 0001 and 0002 are in decent shape, although I'm wondering
if it's possible to improve the style a bit. 0003 at least needs a big
comment in simd.h, and it might need a note in the documentation, too. If
the approach in this patch set seems reasonable, I'll spend some time on
that.
BTW I did try to add some other optimizations, such as processing remaining
elements with only one vector and trying to use the overlapping strategy
with more registers if we know there are relatively many remaining
elements. These other approaches all added a lot of complexity and began
hurting performance, and I've probably already spent way too much time
optimizing a linear search, so this is where I've decided to stop.
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
Attachments: download all (5 files, .tar.gz)
v4-0001-pg_lfind32-Optimize-processing-remaining-elements.patch (text/x-diff, 2.5K) download
From 2f4a7747025cd3288453fdabd520638e37e3633c Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathan@postgresql.org>
Date: Mon, 18 Mar 2024 10:44:08 -0500
Subject: [PATCH v4 1/3] pg_lfind32(): Optimize processing remaining elements.
Discussion: https://postgr.es/m/20231129171526.GA857928%40nathanxps13
---
src/include/port/pg_lfind.h | 42 +++++++++++++++++++++++++++++++++----
1 file changed, 38 insertions(+), 4 deletions(-)
diff --git a/src/include/port/pg_lfind.h b/src/include/port/pg_lfind.h
index b8dfa66eef..bef0e2d5be 100644
--- a/src/include/port/pg_lfind.h
+++ b/src/include/port/pg_lfind.h
@@ -95,15 +95,16 @@ pg_lfind32(uint32 key, uint32 *base, uint32 nelem)
/*
* For better instruction-level parallelism, each loop iteration operates
- * on a block of four registers. Testing for SSE2 has showed this is ~40%
- * faster than using a block of two registers.
+ * on a block of registers. We first do as much processing as possible
+ * with a block of 4 registers, then we try to process what remains with a
+ * block of 2 registers.
*/
const Vector32 keys = vector32_broadcast(key); /* load copies of key */
const uint32 nelem_per_vector = sizeof(Vector32) / sizeof(uint32);
- const uint32 nelem_per_iteration = 4 * nelem_per_vector;
+ uint32 nelem_per_iteration = 4 * nelem_per_vector;
/* round down to multiple of elements per iteration */
- const uint32 tail_idx = nelem & ~(nelem_per_iteration - 1);
+ uint32 tail_idx = nelem & ~(nelem_per_iteration - 1);
#if defined(USE_ASSERT_CHECKING)
bool assert_result = false;
@@ -157,6 +158,39 @@ pg_lfind32(uint32 key, uint32 *base, uint32 nelem)
return true;
}
}
+
+ /*
+ * Try processing the remaining elements using 2 registers instead of 4.
+ */
+ nelem_per_iteration = 2 * nelem_per_vector;
+ tail_idx = nelem & ~(nelem_per_iteration - 1);
+
+ for (; i < tail_idx; i += nelem_per_iteration)
+ {
+ Vector32 vals1,
+ vals2,
+ result1,
+ result2,
+ result;
+
+ /* load the next block into 2 registers */
+ vector32_load(&vals1, &base[i]);
+ vector32_load(&vals2, &base[i + nelem_per_vector]);
+
+ /* compare each value to the key */
+ result1 = vector32_eq(keys, vals1);
+ result2 = vector32_eq(keys, vals2);
+
+ /* combine the results into a single variable */
+ result = vector32_or(result1, result2);
+
+ /* see if there was a match */
+ if (vector32_is_highbit_set(result))
+ {
+ Assert(assert_result);
+ return true;
+ }
+ }
#endif /* ! USE_NO_SIMD */
/* Process the remaining elements one at a time. */
--
2.25.1
v4-0002-pg_lfind32-Further-optimize-processing-remaining-.patch (text/x-diff, 2.5K) download
From 68ee8bf34c80a0a3df02c2aae8357f664895b4de Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathan@postgresql.org>
Date: Mon, 18 Mar 2024 10:55:50 -0500
Subject: [PATCH v4 2/3] pg_lfind32(): Further optimize processing remaining
elements.
Discussion: https://postgr.es/m/20231129171526.GA857928%40nathanxps13
---
src/include/port/pg_lfind.h | 31 +++++++++++++++++++++++++++++--
1 file changed, 29 insertions(+), 2 deletions(-)
diff --git a/src/include/port/pg_lfind.h b/src/include/port/pg_lfind.h
index bef0e2d5be..83fb8f50d2 100644
--- a/src/include/port/pg_lfind.h
+++ b/src/include/port/pg_lfind.h
@@ -96,8 +96,8 @@ pg_lfind32(uint32 key, uint32 *base, uint32 nelem)
/*
* For better instruction-level parallelism, each loop iteration operates
* on a block of registers. We first do as much processing as possible
- * with a block of 4 registers, then we try to process what remains with a
- * block of 2 registers.
+ * with a block of 4 registers, then we process what remains with a block
+ * of 2 registers.
*/
const Vector32 keys = vector32_broadcast(key); /* load copies of key */
const uint32 nelem_per_vector = sizeof(Vector32) / sizeof(uint32);
@@ -120,6 +120,15 @@ pg_lfind32(uint32 key, uint32 *base, uint32 nelem)
}
#endif
+ /*
+ * If there aren't enough elements for the SIMD optimizations, jump
+ * straight to the standard one-by-one linear search code. Testing has
+ * shown that the gains of skipping to the standard linear search code are
+ * worth the extra check.
+ */
+ if (nelem < nelem_per_vector * 2)
+ goto slow_path;
+
for (i = 0; i < tail_idx; i += nelem_per_iteration)
{
Vector32 vals1,
@@ -165,6 +174,7 @@ pg_lfind32(uint32 key, uint32 *base, uint32 nelem)
nelem_per_iteration = 2 * nelem_per_vector;
tail_idx = nelem & ~(nelem_per_iteration - 1);
+retry:
for (; i < tail_idx; i += nelem_per_iteration)
{
Vector32 vals1,
@@ -191,8 +201,25 @@ pg_lfind32(uint32 key, uint32 *base, uint32 nelem)
return true;
}
}
+
+ /*
+ * Process the remaining elements via the 2-register loop above. This
+ * will cause us to process some elements more than once, but that won't
+ * affect correctness, and testing shows that this approach helps more
+ * than it harms.
+ */
+ if (i != nelem)
+ {
+ tail_idx = nelem;
+ i = tail_idx - nelem_per_iteration;
+ goto retry;
+ }
+
+ Assert(!assert_result);
+ return false;
#endif /* ! USE_NO_SIMD */
+slow_path:
/* Process the remaining elements one at a time. */
for (; i < nelem; i++)
{
--
2.25.1
v4-0003-Add-support-for-AVX2-in-simd.h.patch (text/x-diff, 4.8K) download
From 41882bbf78f2d8a1fe817a0cbac70f221a0debf4 Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathan@postgresql.org>
Date: Mon, 18 Mar 2024 11:02:05 -0500
Subject: [PATCH v4 3/3] Add support for AVX2 in simd.h.
Discussion: https://postgr.es/m/20231129171526.GA857928%40nathanxps13
---
src/include/port/simd.h | 61 ++++++++++++++++++++++++++++++++---------
1 file changed, 48 insertions(+), 13 deletions(-)
diff --git a/src/include/port/simd.h b/src/include/port/simd.h
index 597496f2fb..f06b21876b 100644
--- a/src/include/port/simd.h
+++ b/src/include/port/simd.h
@@ -18,7 +18,18 @@
#ifndef SIMD_H
#define SIMD_H
-#if (defined(__x86_64__) || defined(_M_AMD64))
+#if defined(__AVX2__)
+
+/*
+ * XXX: Need to add a big comment here.
+ */
+#include <immintrin.h>
+#define USE_AVX2
+typedef __m256i Vector8;
+typedef __m256i Vector32;
+
+#elif (defined(__x86_64__) || defined(_M_AMD64))
+
/*
* SSE2 instructions are part of the spec for the 64-bit x86 ISA. We assume
* that compilers targeting this architecture understand SSE2 intrinsics.
@@ -107,7 +118,9 @@ static inline Vector32 vector32_eq(const Vector32 v1, const Vector32 v2);
static inline void
vector8_load(Vector8 *v, const uint8 *s)
{
-#if defined(USE_SSE2)
+#if defined(USE_AVX2)
+ *v = _mm256_loadu_si256((const __m256i *) s);
+#elif defined(USE_SSE2)
*v = _mm_loadu_si128((const __m128i *) s);
#elif defined(USE_NEON)
*v = vld1q_u8(s);
@@ -120,7 +133,9 @@ vector8_load(Vector8 *v, const uint8 *s)
static inline void
vector32_load(Vector32 *v, const uint32 *s)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ *v = _mm256_loadu_si256((const __m256i *) s);
+#elif defined(USE_SSE2)
*v = _mm_loadu_si128((const __m128i *) s);
#elif defined(USE_NEON)
*v = vld1q_u32(s);
@@ -134,7 +149,9 @@ vector32_load(Vector32 *v, const uint32 *s)
static inline Vector8
vector8_broadcast(const uint8 c)
{
-#if defined(USE_SSE2)
+#if defined(USE_AVX2)
+ return _mm256_set1_epi8(c);
+#elif defined(USE_SSE2)
return _mm_set1_epi8(c);
#elif defined(USE_NEON)
return vdupq_n_u8(c);
@@ -147,7 +164,9 @@ vector8_broadcast(const uint8 c)
static inline Vector32
vector32_broadcast(const uint32 c)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_set1_epi32(c);
+#elif defined(USE_SSE2)
return _mm_set1_epi32(c);
#elif defined(USE_NEON)
return vdupq_n_u32(c);
@@ -270,7 +289,9 @@ vector8_has_le(const Vector8 v, const uint8 c)
static inline bool
vector8_is_highbit_set(const Vector8 v)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_movemask_epi8(v) != 0;
+#elif defined(USE_SSE2)
return _mm_movemask_epi8(v) != 0;
#elif defined(USE_NEON)
return vmaxvq_u8(v) > 0x7F;
@@ -308,7 +329,9 @@ vector32_is_highbit_set(const Vector32 v)
static inline uint32
vector8_highbit_mask(const Vector8 v)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return (uint32) _mm256_movemask_epi8(v);
+#elif defined(USE_SSE2)
return (uint32) _mm_movemask_epi8(v);
#elif defined(USE_NEON)
/*
@@ -337,7 +360,9 @@ vector8_highbit_mask(const Vector8 v)
static inline Vector8
vector8_or(const Vector8 v1, const Vector8 v2)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_or_si256(v1, v2);
+#elif defined(USE_SSE2)
return _mm_or_si128(v1, v2);
#elif defined(USE_NEON)
return vorrq_u8(v1, v2);
@@ -350,7 +375,9 @@ vector8_or(const Vector8 v1, const Vector8 v2)
static inline Vector32
vector32_or(const Vector32 v1, const Vector32 v2)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_or_si256(v1, v2);
+#elif defined(USE_SSE2)
return _mm_or_si128(v1, v2);
#elif defined(USE_NEON)
return vorrq_u32(v1, v2);
@@ -368,7 +395,9 @@ vector32_or(const Vector32 v1, const Vector32 v2)
static inline Vector8
vector8_ssub(const Vector8 v1, const Vector8 v2)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_subs_epu8(v1, v2);
+#elif defined(USE_SSE2)
return _mm_subs_epu8(v1, v2);
#elif defined(USE_NEON)
return vqsubq_u8(v1, v2);
@@ -384,7 +413,9 @@ vector8_ssub(const Vector8 v1, const Vector8 v2)
static inline Vector8
vector8_eq(const Vector8 v1, const Vector8 v2)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_cmpeq_epi8(v1, v2);
+#elif defined(USE_SSE2)
return _mm_cmpeq_epi8(v1, v2);
#elif defined(USE_NEON)
return vceqq_u8(v1, v2);
@@ -396,7 +427,9 @@ vector8_eq(const Vector8 v1, const Vector8 v2)
static inline Vector32
vector32_eq(const Vector32 v1, const Vector32 v2)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_cmpeq_epi32(v1, v2);
+#elif defined(USE_SSE2)
return _mm_cmpeq_epi32(v1, v2);
#elif defined(USE_NEON)
return vceqq_u32(v1, v2);
@@ -411,7 +444,9 @@ vector32_eq(const Vector32 v1, const Vector32 v2)
static inline Vector8
vector8_min(const Vector8 v1, const Vector8 v2)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_min_epu8(v1, v2);
+#elif defined(USE_SSE2)
return _mm_min_epu8(v1, v2);
#elif defined(USE_NEON)
return vminq_u8(v1, v2);
--
2.25.1
v4_x86.jpg (image/jpeg, 26.9K) download
view image
v4_arm.jpg (image/jpeg, 29.0K) download
view image
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 07:01 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-08 17:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 02:20 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-09 16:20 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-10 02:06 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-15 17:41 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-15 19:40 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-17 02:47 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 02:03 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
@ 2024-03-19 03:03 ` John Naylor <johncnaylorls@gmail.com>
2024-03-19 03:16 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
0 siblings, 1 reply; 48+ messages in thread
From: John Naylor @ 2024-03-19 03:03 UTC (permalink / raw)
To: Nathan Bossart <nathandbossart@gmail.com>; +Cc: Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Tue, Mar 19, 2024 at 9:03 AM Nathan Bossart <nathandbossart@gmail.com> wrote:
>
> On Sun, Mar 17, 2024 at 09:47:33AM +0700, John Naylor wrote:
> > I haven't looked at the patches, but the graphs look good.
>
> I spent some more time on these patches. Specifically, I reordered them to
> demonstrate the effects on systems without AVX2 support. I've also added a
> shortcut to jump to the one-by-one approach when there aren't many
> elements, as the overhead becomes quite noticeable otherwise. Finally, I
> ran the same benchmarks again on x86 and Arm out to 128 elements.
>
> Overall, I think 0001 and 0002 are in decent shape, although I'm wondering
> if it's possible to improve the style a bit.
I took a brief look, and 0001 isn't quite what I had in mind. I can't
quite tell what it's doing with the additional branches and "goto
retry", but I meant something pretty simple:
- if short, do one element at a time and return
- if long, do one block unconditionally, then round the start pointer
up so that "end - start" is an exact multiple of blocks, and loop over
them
^ permalink raw reply [nested|flat] 48+ messages in thread
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 07:01 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-08 17:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 02:20 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-09 16:20 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-10 02:06 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-15 17:41 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-15 19:40 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-17 02:47 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 02:03 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
@ 2024-03-19 03:16 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 09:53 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
0 siblings, 1 reply; 48+ messages in thread
From: Nathan Bossart @ 2024-03-19 03:16 UTC (permalink / raw)
To: John Naylor <johncnaylorls@gmail.com>; +Cc: Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Tue, Mar 19, 2024 at 10:03:36AM +0700, John Naylor wrote:
> I took a brief look, and 0001 isn't quite what I had in mind. I can't
> quite tell what it's doing with the additional branches and "goto
> retry", but I meant something pretty simple:
Do you mean 0002? 0001 just adds a 2-register loop for remaining elements
once we've exhausted what can be processed with the 4-register loop.
> - if short, do one element at a time and return
0002 does this.
> - if long, do one block unconditionally, then round the start pointer
> up so that "end - start" is an exact multiple of blocks, and loop over
> them
0002 does the opposite of this. That is, after we've completed as many
blocks as possible, we move the iterator variable back to "end -
block_size" and do one final iteration to cover all the remaining elements.
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
^ permalink raw reply [nested|flat] 48+ messages in thread
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 07:01 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-08 17:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 02:20 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-09 16:20 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-10 02:06 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-15 17:41 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-15 19:40 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-17 02:47 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 02:03 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 03:16 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
@ 2024-03-19 09:53 ` John Naylor <johncnaylorls@gmail.com>
2024-03-19 16:30 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
0 siblings, 1 reply; 48+ messages in thread
From: John Naylor @ 2024-03-19 09:53 UTC (permalink / raw)
To: Nathan Bossart <nathandbossart@gmail.com>; +Cc: Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Tue, Mar 19, 2024 at 10:16 AM Nathan Bossart
<nathandbossart@gmail.com> wrote:
>
> On Tue, Mar 19, 2024 at 10:03:36AM +0700, John Naylor wrote:
> > I took a brief look, and 0001 isn't quite what I had in mind. I can't
> > quite tell what it's doing with the additional branches and "goto
> > retry", but I meant something pretty simple:
>
> Do you mean 0002? 0001 just adds a 2-register loop for remaining elements
> once we've exhausted what can be processed with the 4-register loop.
Sorry, I was looking at v2 at the time.
> > - if short, do one element at a time and return
>
> 0002 does this.
That part looks fine.
> > - if long, do one block unconditionally, then round the start pointer
> > up so that "end - start" is an exact multiple of blocks, and loop over
> > them
>
> 0002 does the opposite of this. That is, after we've completed as many
> blocks as possible, we move the iterator variable back to "end -
> block_size" and do one final iteration to cover all the remaining elements.
Sounds similar in principle, but it looks really complicated. I don't
think the additional loops and branches are a good way to go, either
for readability or for branch prediction. My sketch has one branch for
which loop to do, and then performs only one loop. Let's do the
simplest thing that could work. (I think we might need a helper
function to do the block, but the rest should be easy)
^ permalink raw reply [nested|flat] 48+ messages in thread
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 07:01 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-08 17:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 02:20 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-09 16:20 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-10 02:06 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-15 17:41 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-15 19:40 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-17 02:47 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 02:03 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 03:16 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 09:53 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
@ 2024-03-19 16:30 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 06:57 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
0 siblings, 1 reply; 48+ messages in thread
From: Nathan Bossart @ 2024-03-19 16:30 UTC (permalink / raw)
To: John Naylor <johncnaylorls@gmail.com>; +Cc: Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Tue, Mar 19, 2024 at 04:53:04PM +0700, John Naylor wrote:
> On Tue, Mar 19, 2024 at 10:16 AM Nathan Bossart
> <nathandbossart@gmail.com> wrote:
>> 0002 does the opposite of this. That is, after we've completed as many
>> blocks as possible, we move the iterator variable back to "end -
>> block_size" and do one final iteration to cover all the remaining elements.
>
> Sounds similar in principle, but it looks really complicated. I don't
> think the additional loops and branches are a good way to go, either
> for readability or for branch prediction. My sketch has one branch for
> which loop to do, and then performs only one loop. Let's do the
> simplest thing that could work. (I think we might need a helper
> function to do the block, but the rest should be easy)
I tried to trim some of the branches, and came up with the attached patch.
I don't think this is exactly what you were suggesting, but I think it's
relatively close. My testing showed decent benefits from using 2 vectors
when there aren't enough elements for 4, so I've tried to keep that part
intact. This changes pg_lfind32() to something like:
if not many elements
process one by one
while enough elements for 4 registers remain
process with 4 registers
if no elements remain
return false
if more than 2-registers-worth of elements remain
do one iteration with 2 registers
do another iteration on last 2-registers-worth of elements
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
Attachments:
johns_suggestion.patch (text/x-diff, 2.1K) download
diff --git a/src/include/port/pg_lfind.h b/src/include/port/pg_lfind.h
index b8dfa66eef..d154b61555 100644
--- a/src/include/port/pg_lfind.h
+++ b/src/include/port/pg_lfind.h
@@ -80,6 +80,34 @@ pg_lfind8_le(uint8 key, uint8 *base, uint32 nelem)
return false;
}
+static inline bool
+lfind32_2reg_helper(const Vector32 keys, uint32 *base)
+{
+ const uint32 nelem_per_vector = sizeof(Vector32) / sizeof(uint32);
+ Vector32 vals1,
+ vals2,
+ result1,
+ result2,
+ result;
+
+ /* load the next block into 2 registers */
+ vector32_load(&vals1, base);
+ vector32_load(&vals2, &base[nelem_per_vector]);
+
+ /* compare each value to the key */
+ result1 = vector32_eq(keys, vals1);
+ result2 = vector32_eq(keys, vals2);
+
+ /* combine the results into a single variable */
+ result = vector32_or(result1, result2);
+
+ /* see if there was a match */
+ if (vector32_is_highbit_set(result))
+ return true;
+
+ return false;
+}
+
/*
* pg_lfind32
*
@@ -100,7 +128,8 @@ pg_lfind32(uint32 key, uint32 *base, uint32 nelem)
*/
const Vector32 keys = vector32_broadcast(key); /* load copies of key */
const uint32 nelem_per_vector = sizeof(Vector32) / sizeof(uint32);
- const uint32 nelem_per_iteration = 4 * nelem_per_vector;
+ uint32 nelem_per_iteration = 4 * nelem_per_vector;
+ uint32 remaining;
/* round down to multiple of elements per iteration */
const uint32 tail_idx = nelem & ~(nelem_per_iteration - 1);
@@ -119,6 +148,9 @@ pg_lfind32(uint32 key, uint32 *base, uint32 nelem)
}
#endif
+ if (nelem < nelem_per_vector * 2)
+ goto slow_path;
+
for (i = 0; i < tail_idx; i += nelem_per_iteration)
{
Vector32 vals1,
@@ -157,8 +189,21 @@ pg_lfind32(uint32 key, uint32 *base, uint32 nelem)
return true;
}
}
+
+ nelem_per_iteration = 2 * nelem_per_vector;
+ remaining = nelem - i;
+
+ if (remaining == 0)
+ return false;
+
+ if (remaining > nelem_per_iteration &&
+ lfind32_2reg_helper(keys, &base[i]))
+ return true;
+
+ return lfind32_2reg_helper(keys, &base[nelem - nelem_per_iteration]);
#endif /* ! USE_NO_SIMD */
+slow_path:
/* Process the remaining elements one at a time. */
for (; i < nelem; i++)
{
reduce_branches.jpg (image/jpeg, 19.7K) download
view image
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 07:01 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-08 17:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 02:20 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-09 16:20 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-10 02:06 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-15 17:41 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-15 19:40 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-17 02:47 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 02:03 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 03:16 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 09:53 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 16:30 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
@ 2024-03-20 06:57 ` John Naylor <johncnaylorls@gmail.com>
2024-03-20 14:31 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
0 siblings, 1 reply; 48+ messages in thread
From: John Naylor @ 2024-03-20 06:57 UTC (permalink / raw)
To: Nathan Bossart <nathandbossart@gmail.com>; +Cc: Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Tue, Mar 19, 2024 at 11:30 PM Nathan Bossart
<nathandbossart@gmail.com> wrote:
> > Sounds similar in principle, but it looks really complicated. I don't
> > think the additional loops and branches are a good way to go, either
> > for readability or for branch prediction. My sketch has one branch for
> > which loop to do, and then performs only one loop. Let's do the
> > simplest thing that could work. (I think we might need a helper
> > function to do the block, but the rest should be easy)
>
> I tried to trim some of the branches, and came up with the attached patch.
> I don't think this is exactly what you were suggesting, but I think it's
> relatively close. My testing showed decent benefits from using 2 vectors
> when there aren't enough elements for 4, so I've tried to keep that part
> intact.
I would caution against that if the benchmark is repeatedly running
against a static number of elements, because the branch predictor will
be right all the time (except maybe when it exits a loop, not sure).
We probably don't need to go to the trouble to construct a benchmark
with some added randomness, but we have be careful not to overfit what
the test is actually measuring.
^ permalink raw reply [nested|flat] 48+ messages in thread
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 07:01 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-08 17:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 02:20 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-09 16:20 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-10 02:06 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-15 17:41 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-15 19:40 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-17 02:47 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 02:03 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 03:16 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 09:53 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 16:30 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 06:57 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
@ 2024-03-20 14:31 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 19:55 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
0 siblings, 1 reply; 48+ messages in thread
From: Nathan Bossart @ 2024-03-20 14:31 UTC (permalink / raw)
To: John Naylor <johncnaylorls@gmail.com>; +Cc: Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Wed, Mar 20, 2024 at 01:57:54PM +0700, John Naylor wrote:
> On Tue, Mar 19, 2024 at 11:30 PM Nathan Bossart
> <nathandbossart@gmail.com> wrote:
>> I tried to trim some of the branches, and came up with the attached patch.
>> I don't think this is exactly what you were suggesting, but I think it's
>> relatively close. My testing showed decent benefits from using 2 vectors
>> when there aren't enough elements for 4, so I've tried to keep that part
>> intact.
>
> I would caution against that if the benchmark is repeatedly running
> against a static number of elements, because the branch predictor will
> be right all the time (except maybe when it exits a loop, not sure).
> We probably don't need to go to the trouble to construct a benchmark
> with some added randomness, but we have be careful not to overfit what
> the test is actually measuring.
I don't mind removing the 2-register stuff if that's what you think we
should do. I'm cautiously optimistic that it'd help more than the extra
branch prediction might hurt, and it'd at least help avoid regressing the
lower end for the larger AVX2 registers, but I probably won't be able to
prove that without constructing another benchmark. And TBH I'm not sure
it'll significantly impact any real-world workload, anyway.
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
^ permalink raw reply [nested|flat] 48+ messages in thread
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 07:01 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-08 17:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 02:20 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-09 16:20 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-10 02:06 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-15 17:41 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-15 19:40 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-17 02:47 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 02:03 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 03:16 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 09:53 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 16:30 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 06:57 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-20 14:31 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
@ 2024-03-20 19:55 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-21 04:30 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
0 siblings, 1 reply; 48+ messages in thread
From: Nathan Bossart @ 2024-03-20 19:55 UTC (permalink / raw)
To: John Naylor <johncnaylorls@gmail.com>; +Cc: Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Wed, Mar 20, 2024 at 09:31:16AM -0500, Nathan Bossart wrote:
> On Wed, Mar 20, 2024 at 01:57:54PM +0700, John Naylor wrote:
>> On Tue, Mar 19, 2024 at 11:30 PM Nathan Bossart
>> <nathandbossart@gmail.com> wrote:
>>> I tried to trim some of the branches, and came up with the attached patch.
>>> I don't think this is exactly what you were suggesting, but I think it's
>>> relatively close. My testing showed decent benefits from using 2 vectors
>>> when there aren't enough elements for 4, so I've tried to keep that part
>>> intact.
>>
>> I would caution against that if the benchmark is repeatedly running
>> against a static number of elements, because the branch predictor will
>> be right all the time (except maybe when it exits a loop, not sure).
>> We probably don't need to go to the trouble to construct a benchmark
>> with some added randomness, but we have be careful not to overfit what
>> the test is actually measuring.
>
> I don't mind removing the 2-register stuff if that's what you think we
> should do. I'm cautiously optimistic that it'd help more than the extra
> branch prediction might hurt, and it'd at least help avoid regressing the
> lower end for the larger AVX2 registers, but I probably won't be able to
> prove that without constructing another benchmark. And TBH I'm not sure
> it'll significantly impact any real-world workload, anyway.
Here's a new version of the patch set with the 2-register stuff removed,
plus a fresh run of the benchmark. The weird spike for AVX2 is what led me
down the 2-register path earlier.
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
Attachments: download all (3 files, .tar.gz)
v5-0001-pg_lfind32-add-overlap-code-for-remaining-element.patch (text/x-diff, 3.7K) download
From d47b3219fd1b803a5dedff9babaa5134c07e6947 Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathan@postgresql.org>
Date: Wed, 20 Mar 2024 14:20:24 -0500
Subject: [PATCH v5 1/2] pg_lfind32(): add "overlap" code for remaining
elements
---
src/include/port/pg_lfind.h | 102 +++++++++++++++++++++++++-----------
1 file changed, 71 insertions(+), 31 deletions(-)
diff --git a/src/include/port/pg_lfind.h b/src/include/port/pg_lfind.h
index b8dfa66eef..21af399dc4 100644
--- a/src/include/port/pg_lfind.h
+++ b/src/include/port/pg_lfind.h
@@ -80,6 +80,49 @@ pg_lfind8_le(uint8 key, uint8 *base, uint32 nelem)
return false;
}
+/*
+ * pg_lfind32_helper
+ *
+ * Searches one 4-register-block of integers. The caller is responsible for
+ * ensuring that there are at least 4-registers-worth of integers remaining.
+ */
+static inline bool
+pg_lfind32_helper(const Vector32 keys, uint32 *base)
+{
+ const uint32 nelem_per_vector = sizeof(Vector32) / sizeof(uint32);
+ Vector32 vals1,
+ vals2,
+ vals3,
+ vals4,
+ result1,
+ result2,
+ result3,
+ result4,
+ tmp1,
+ tmp2,
+ result;
+
+ /* load the next block into 4 registers */
+ vector32_load(&vals1, base);
+ vector32_load(&vals2, &base[nelem_per_vector]);
+ vector32_load(&vals3, &base[nelem_per_vector * 2]);
+ vector32_load(&vals4, &base[nelem_per_vector * 3]);
+
+ /* compare each value to the key */
+ result1 = vector32_eq(keys, vals1);
+ result2 = vector32_eq(keys, vals2);
+ result3 = vector32_eq(keys, vals3);
+ result4 = vector32_eq(keys, vals4);
+
+ /* combine the results into a single variable */
+ tmp1 = vector32_or(result1, result2);
+ tmp2 = vector32_or(result3, result4);
+ result = vector32_or(tmp1, tmp2);
+
+ /* return whether there was a match */
+ return vector32_is_highbit_set(result);
+}
+
/*
* pg_lfind32
*
@@ -119,46 +162,43 @@ pg_lfind32(uint32 key, uint32 *base, uint32 nelem)
}
#endif
+ /*
+ * If there aren't enough elements for the SIMD code, jump to the standard
+ * one-by-one linear search code.
+ */
+ if (nelem < nelem_per_iteration)
+ goto one_by_one;
+
+ /*
+ * Process as many elements as possible with a block of 4 registers.
+ */
for (i = 0; i < tail_idx; i += nelem_per_iteration)
{
- Vector32 vals1,
- vals2,
- vals3,
- vals4,
- result1,
- result2,
- result3,
- result4,
- tmp1,
- tmp2,
- result;
-
- /* load the next block into 4 registers */
- vector32_load(&vals1, &base[i]);
- vector32_load(&vals2, &base[i + nelem_per_vector]);
- vector32_load(&vals3, &base[i + nelem_per_vector * 2]);
- vector32_load(&vals4, &base[i + nelem_per_vector * 3]);
-
- /* compare each value to the key */
- result1 = vector32_eq(keys, vals1);
- result2 = vector32_eq(keys, vals2);
- result3 = vector32_eq(keys, vals3);
- result4 = vector32_eq(keys, vals4);
-
- /* combine the results into a single variable */
- tmp1 = vector32_or(result1, result2);
- tmp2 = vector32_or(result3, result4);
- result = vector32_or(tmp1, tmp2);
-
- /* see if there was a match */
- if (vector32_is_highbit_set(result))
+ if (pg_lfind32_helper(keys, &base[i]))
{
Assert(assert_result == true);
return true;
}
}
+
+ /*
+ * If any elements remain, process the last 'nelem_per_iteration' elements
+ * in the array with a 4-register block. This will cause us to check some
+ * elements more than once, but that won't affect correctness, and testing
+ * has demonstrated that this helps more cases than it harms.
+ */
+ if (i != nelem &&
+ pg_lfind32_helper(keys, &base[nelem - nelem_per_iteration]))
+ {
+ Assert(assert_result);
+ return true;
+ }
+
+ Assert(!assert_result);
+ return false;
#endif /* ! USE_NO_SIMD */
+one_by_one:
/* Process the remaining elements one at a time. */
for (; i < nelem; i++)
{
--
2.25.1
v5-0002-Add-support-for-AVX2-in-simd.h.patch (text/x-diff, 4.8K) download
From e8337b123d828671d5c547d2a96485ef15f4ddfe Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathan@postgresql.org>
Date: Mon, 18 Mar 2024 11:02:05 -0500
Subject: [PATCH v5 2/2] Add support for AVX2 in simd.h.
Discussion: https://postgr.es/m/20231129171526.GA857928%40nathanxps13
---
src/include/port/simd.h | 61 ++++++++++++++++++++++++++++++++---------
1 file changed, 48 insertions(+), 13 deletions(-)
diff --git a/src/include/port/simd.h b/src/include/port/simd.h
index 597496f2fb..f06b21876b 100644
--- a/src/include/port/simd.h
+++ b/src/include/port/simd.h
@@ -18,7 +18,18 @@
#ifndef SIMD_H
#define SIMD_H
-#if (defined(__x86_64__) || defined(_M_AMD64))
+#if defined(__AVX2__)
+
+/*
+ * XXX: Need to add a big comment here.
+ */
+#include <immintrin.h>
+#define USE_AVX2
+typedef __m256i Vector8;
+typedef __m256i Vector32;
+
+#elif (defined(__x86_64__) || defined(_M_AMD64))
+
/*
* SSE2 instructions are part of the spec for the 64-bit x86 ISA. We assume
* that compilers targeting this architecture understand SSE2 intrinsics.
@@ -107,7 +118,9 @@ static inline Vector32 vector32_eq(const Vector32 v1, const Vector32 v2);
static inline void
vector8_load(Vector8 *v, const uint8 *s)
{
-#if defined(USE_SSE2)
+#if defined(USE_AVX2)
+ *v = _mm256_loadu_si256((const __m256i *) s);
+#elif defined(USE_SSE2)
*v = _mm_loadu_si128((const __m128i *) s);
#elif defined(USE_NEON)
*v = vld1q_u8(s);
@@ -120,7 +133,9 @@ vector8_load(Vector8 *v, const uint8 *s)
static inline void
vector32_load(Vector32 *v, const uint32 *s)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ *v = _mm256_loadu_si256((const __m256i *) s);
+#elif defined(USE_SSE2)
*v = _mm_loadu_si128((const __m128i *) s);
#elif defined(USE_NEON)
*v = vld1q_u32(s);
@@ -134,7 +149,9 @@ vector32_load(Vector32 *v, const uint32 *s)
static inline Vector8
vector8_broadcast(const uint8 c)
{
-#if defined(USE_SSE2)
+#if defined(USE_AVX2)
+ return _mm256_set1_epi8(c);
+#elif defined(USE_SSE2)
return _mm_set1_epi8(c);
#elif defined(USE_NEON)
return vdupq_n_u8(c);
@@ -147,7 +164,9 @@ vector8_broadcast(const uint8 c)
static inline Vector32
vector32_broadcast(const uint32 c)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_set1_epi32(c);
+#elif defined(USE_SSE2)
return _mm_set1_epi32(c);
#elif defined(USE_NEON)
return vdupq_n_u32(c);
@@ -270,7 +289,9 @@ vector8_has_le(const Vector8 v, const uint8 c)
static inline bool
vector8_is_highbit_set(const Vector8 v)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_movemask_epi8(v) != 0;
+#elif defined(USE_SSE2)
return _mm_movemask_epi8(v) != 0;
#elif defined(USE_NEON)
return vmaxvq_u8(v) > 0x7F;
@@ -308,7 +329,9 @@ vector32_is_highbit_set(const Vector32 v)
static inline uint32
vector8_highbit_mask(const Vector8 v)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return (uint32) _mm256_movemask_epi8(v);
+#elif defined(USE_SSE2)
return (uint32) _mm_movemask_epi8(v);
#elif defined(USE_NEON)
/*
@@ -337,7 +360,9 @@ vector8_highbit_mask(const Vector8 v)
static inline Vector8
vector8_or(const Vector8 v1, const Vector8 v2)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_or_si256(v1, v2);
+#elif defined(USE_SSE2)
return _mm_or_si128(v1, v2);
#elif defined(USE_NEON)
return vorrq_u8(v1, v2);
@@ -350,7 +375,9 @@ vector8_or(const Vector8 v1, const Vector8 v2)
static inline Vector32
vector32_or(const Vector32 v1, const Vector32 v2)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_or_si256(v1, v2);
+#elif defined(USE_SSE2)
return _mm_or_si128(v1, v2);
#elif defined(USE_NEON)
return vorrq_u32(v1, v2);
@@ -368,7 +395,9 @@ vector32_or(const Vector32 v1, const Vector32 v2)
static inline Vector8
vector8_ssub(const Vector8 v1, const Vector8 v2)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_subs_epu8(v1, v2);
+#elif defined(USE_SSE2)
return _mm_subs_epu8(v1, v2);
#elif defined(USE_NEON)
return vqsubq_u8(v1, v2);
@@ -384,7 +413,9 @@ vector8_ssub(const Vector8 v1, const Vector8 v2)
static inline Vector8
vector8_eq(const Vector8 v1, const Vector8 v2)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_cmpeq_epi8(v1, v2);
+#elif defined(USE_SSE2)
return _mm_cmpeq_epi8(v1, v2);
#elif defined(USE_NEON)
return vceqq_u8(v1, v2);
@@ -396,7 +427,9 @@ vector8_eq(const Vector8 v1, const Vector8 v2)
static inline Vector32
vector32_eq(const Vector32 v1, const Vector32 v2)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_cmpeq_epi32(v1, v2);
+#elif defined(USE_SSE2)
return _mm_cmpeq_epi32(v1, v2);
#elif defined(USE_NEON)
return vceqq_u32(v1, v2);
@@ -411,7 +444,9 @@ vector32_eq(const Vector32 v1, const Vector32 v2)
static inline Vector8
vector8_min(const Vector8 v1, const Vector8 v2)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_min_epu8(v1, v2);
+#elif defined(USE_SSE2)
return _mm_min_epu8(v1, v2);
#elif defined(USE_NEON)
return vminq_u8(v1, v2);
--
2.25.1
v5_x86.jpg (image/jpeg, 26.0K) download
view image
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 07:01 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-08 17:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 02:20 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-09 16:20 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-10 02:06 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-15 17:41 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-15 19:40 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-17 02:47 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 02:03 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 03:16 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 09:53 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 16:30 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 06:57 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-20 14:31 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 19:55 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
@ 2024-03-21 04:30 ` John Naylor <johncnaylorls@gmail.com>
2024-03-21 17:09 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
0 siblings, 1 reply; 48+ messages in thread
From: John Naylor @ 2024-03-21 04:30 UTC (permalink / raw)
To: Nathan Bossart <nathandbossart@gmail.com>; +Cc: Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Thu, Mar 21, 2024 at 2:55 AM Nathan Bossart <nathandbossart@gmail.com> wrote:
>
> On Wed, Mar 20, 2024 at 09:31:16AM -0500, Nathan Bossart wrote:
> > I don't mind removing the 2-register stuff if that's what you think we
> > should do. I'm cautiously optimistic that it'd help more than the extra
> > branch prediction might hurt, and it'd at least help avoid regressing the
> > lower end for the larger AVX2 registers, but I probably won't be able to
> > prove that without constructing another benchmark. And TBH I'm not sure
> > it'll significantly impact any real-world workload, anyway.
>
> Here's a new version of the patch set with the 2-register stuff removed,
I'm much happier about v5-0001. With a small tweak it would match what
I had in mind:
+ if (nelem < nelem_per_iteration)
+ goto one_by_one;
If this were "<=" then the for long arrays we could assume there is
always more than one block, and wouldn't need to check if any elements
remain -- first block, then a single loop and it's done.
The loop could also then be a "do while" since it doesn't have to
check the exit condition up front.
> plus a fresh run of the benchmark. The weird spike for AVX2 is what led me
> down the 2-register path earlier.
Yes, that spike is weird, because it seems super-linear. However, the
more interesting question for me is: AVX2 isn't really buying much for
the numbers covered in this test. Between 32 and 48 elements, and
between 64 and 80, it's indistinguishable from SSE2. The jumps to the
next shelf are postponed, but the jumps are just as high. From earlier
system benchmarks, I recall it eventually wins out with hundreds of
elements, right? Is that still true?
Further, now that the algorithm is more SIMD-appropriate, I wonder
what doing 4 registers at a time is actually buying us for either SSE2
or AVX2. It might just be a matter of scale, but that would be good to
understand.
^ permalink raw reply [nested|flat] 48+ messages in thread
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 07:01 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-08 17:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 02:20 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-09 16:20 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-10 02:06 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-15 17:41 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-15 19:40 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-17 02:47 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 02:03 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 03:16 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 09:53 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 16:30 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 06:57 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-20 14:31 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 19:55 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-21 04:30 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
@ 2024-03-21 17:09 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-21 17:12 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-21 18:38 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-25 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
0 siblings, 3 replies; 48+ messages in thread
From: Nathan Bossart @ 2024-03-21 17:09 UTC (permalink / raw)
To: John Naylor <johncnaylorls@gmail.com>; +Cc: Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Thu, Mar 21, 2024 at 11:30:30AM +0700, John Naylor wrote:
> I'm much happier about v5-0001. With a small tweak it would match what
> I had in mind:
>
> + if (nelem < nelem_per_iteration)
> + goto one_by_one;
>
> If this were "<=" then the for long arrays we could assume there is
> always more than one block, and wouldn't need to check if any elements
> remain -- first block, then a single loop and it's done.
>
> The loop could also then be a "do while" since it doesn't have to
> check the exit condition up front.
Good idea. That causes us to re-check all of the tail elements when the
number of elements is evenly divisible by nelem_per_iteration, but that
might be worth the trade-off.
> Yes, that spike is weird, because it seems super-linear. However, the
> more interesting question for me is: AVX2 isn't really buying much for
> the numbers covered in this test. Between 32 and 48 elements, and
> between 64 and 80, it's indistinguishable from SSE2. The jumps to the
> next shelf are postponed, but the jumps are just as high. From earlier
> system benchmarks, I recall it eventually wins out with hundreds of
> elements, right? Is that still true?
It does still eventually win, although not nearly to the same extent as
before. I extended the benchmark a bit to show this. I wouldn't be
devastated if we only got 0001 committed for v17, given these results.
> Further, now that the algorithm is more SIMD-appropriate, I wonder
> what doing 4 registers at a time is actually buying us for either SSE2
> or AVX2. It might just be a matter of scale, but that would be good to
> understand.
I'll follow up with these numbers shortly.
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
Attachments: download all (4 files, .tar.gz)
v6-0001-pg_lfind32-add-overlap-code-for-remaining-element.patch (text/x-diff, 3.8K) download
From 5d4d91d169b973838c99e8d4fdadcb09df36a6ea Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathan@postgresql.org>
Date: Wed, 20 Mar 2024 14:20:24 -0500
Subject: [PATCH v6 1/2] pg_lfind32(): add "overlap" code for remaining
elements
---
src/include/port/pg_lfind.h | 103 ++++++++++++++++++++++++------------
1 file changed, 70 insertions(+), 33 deletions(-)
diff --git a/src/include/port/pg_lfind.h b/src/include/port/pg_lfind.h
index b8dfa66eef..22a3711ab5 100644
--- a/src/include/port/pg_lfind.h
+++ b/src/include/port/pg_lfind.h
@@ -80,6 +80,49 @@ pg_lfind8_le(uint8 key, uint8 *base, uint32 nelem)
return false;
}
+/*
+ * pg_lfind32_helper
+ *
+ * Searches one 4-register-block of integers. The caller is responsible for
+ * ensuring that there are at least 4-registers-worth of integers remaining.
+ */
+static inline bool
+pg_lfind32_helper(const Vector32 keys, uint32 *base)
+{
+ const uint32 nelem_per_vector = sizeof(Vector32) / sizeof(uint32);
+ Vector32 vals1,
+ vals2,
+ vals3,
+ vals4,
+ result1,
+ result2,
+ result3,
+ result4,
+ tmp1,
+ tmp2,
+ result;
+
+ /* load the next block into 4 registers */
+ vector32_load(&vals1, base);
+ vector32_load(&vals2, &base[nelem_per_vector]);
+ vector32_load(&vals3, &base[nelem_per_vector * 2]);
+ vector32_load(&vals4, &base[nelem_per_vector * 3]);
+
+ /* compare each value to the key */
+ result1 = vector32_eq(keys, vals1);
+ result2 = vector32_eq(keys, vals2);
+ result3 = vector32_eq(keys, vals3);
+ result4 = vector32_eq(keys, vals4);
+
+ /* combine the results into a single variable */
+ tmp1 = vector32_or(result1, result2);
+ tmp2 = vector32_or(result3, result4);
+ result = vector32_or(tmp1, tmp2);
+
+ /* return whether there was a match */
+ return vector32_is_highbit_set(result);
+}
+
/*
* pg_lfind32
*
@@ -119,46 +162,40 @@ pg_lfind32(uint32 key, uint32 *base, uint32 nelem)
}
#endif
- for (i = 0; i < tail_idx; i += nelem_per_iteration)
+ /*
+ * If there aren't enough elements for the SIMD code, jump to the standard
+ * one-by-one linear search code.
+ */
+ if (nelem <= nelem_per_iteration)
+ goto one_by_one;
+
+ /*
+ * Process as many elements as possible with a block of 4 registers.
+ */
+ do
{
- Vector32 vals1,
- vals2,
- vals3,
- vals4,
- result1,
- result2,
- result3,
- result4,
- tmp1,
- tmp2,
- result;
-
- /* load the next block into 4 registers */
- vector32_load(&vals1, &base[i]);
- vector32_load(&vals2, &base[i + nelem_per_vector]);
- vector32_load(&vals3, &base[i + nelem_per_vector * 2]);
- vector32_load(&vals4, &base[i + nelem_per_vector * 3]);
-
- /* compare each value to the key */
- result1 = vector32_eq(keys, vals1);
- result2 = vector32_eq(keys, vals2);
- result3 = vector32_eq(keys, vals3);
- result4 = vector32_eq(keys, vals4);
-
- /* combine the results into a single variable */
- tmp1 = vector32_or(result1, result2);
- tmp2 = vector32_or(result3, result4);
- result = vector32_or(tmp1, tmp2);
-
- /* see if there was a match */
- if (vector32_is_highbit_set(result))
+ if (pg_lfind32_helper(keys, &base[i]))
{
Assert(assert_result == true);
return true;
}
- }
+
+ i += nelem_per_iteration;
+
+ } while (i < tail_idx);
+
+ /*
+ * Process the last 'nelem_per_iteration' elements in the array with a
+ * 4-register block. This will cause us to check some of the elements
+ * more than once, but that won't affect correctness, and testing has
+ * demonstrated that this helps more cases than it harms.
+ */
+ Assert(assert_result == pg_lfind32_helper(keys, &base[nelem - nelem_per_iteration]));
+ return pg_lfind32_helper(keys, &base[nelem - nelem_per_iteration]);
+
#endif /* ! USE_NO_SIMD */
+one_by_one:
/* Process the remaining elements one at a time. */
for (; i < nelem; i++)
{
--
2.25.1
v6-0002-Add-support-for-AVX2-in-simd.h.patch (text/x-diff, 4.8K) download
From 7e7781454646992218a990cf75f0654c67ce2dab Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathan@postgresql.org>
Date: Mon, 18 Mar 2024 11:02:05 -0500
Subject: [PATCH v6 2/2] Add support for AVX2 in simd.h.
Discussion: https://postgr.es/m/20231129171526.GA857928%40nathanxps13
---
src/include/port/simd.h | 61 ++++++++++++++++++++++++++++++++---------
1 file changed, 48 insertions(+), 13 deletions(-)
diff --git a/src/include/port/simd.h b/src/include/port/simd.h
index 597496f2fb..f06b21876b 100644
--- a/src/include/port/simd.h
+++ b/src/include/port/simd.h
@@ -18,7 +18,18 @@
#ifndef SIMD_H
#define SIMD_H
-#if (defined(__x86_64__) || defined(_M_AMD64))
+#if defined(__AVX2__)
+
+/*
+ * XXX: Need to add a big comment here.
+ */
+#include <immintrin.h>
+#define USE_AVX2
+typedef __m256i Vector8;
+typedef __m256i Vector32;
+
+#elif (defined(__x86_64__) || defined(_M_AMD64))
+
/*
* SSE2 instructions are part of the spec for the 64-bit x86 ISA. We assume
* that compilers targeting this architecture understand SSE2 intrinsics.
@@ -107,7 +118,9 @@ static inline Vector32 vector32_eq(const Vector32 v1, const Vector32 v2);
static inline void
vector8_load(Vector8 *v, const uint8 *s)
{
-#if defined(USE_SSE2)
+#if defined(USE_AVX2)
+ *v = _mm256_loadu_si256((const __m256i *) s);
+#elif defined(USE_SSE2)
*v = _mm_loadu_si128((const __m128i *) s);
#elif defined(USE_NEON)
*v = vld1q_u8(s);
@@ -120,7 +133,9 @@ vector8_load(Vector8 *v, const uint8 *s)
static inline void
vector32_load(Vector32 *v, const uint32 *s)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ *v = _mm256_loadu_si256((const __m256i *) s);
+#elif defined(USE_SSE2)
*v = _mm_loadu_si128((const __m128i *) s);
#elif defined(USE_NEON)
*v = vld1q_u32(s);
@@ -134,7 +149,9 @@ vector32_load(Vector32 *v, const uint32 *s)
static inline Vector8
vector8_broadcast(const uint8 c)
{
-#if defined(USE_SSE2)
+#if defined(USE_AVX2)
+ return _mm256_set1_epi8(c);
+#elif defined(USE_SSE2)
return _mm_set1_epi8(c);
#elif defined(USE_NEON)
return vdupq_n_u8(c);
@@ -147,7 +164,9 @@ vector8_broadcast(const uint8 c)
static inline Vector32
vector32_broadcast(const uint32 c)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_set1_epi32(c);
+#elif defined(USE_SSE2)
return _mm_set1_epi32(c);
#elif defined(USE_NEON)
return vdupq_n_u32(c);
@@ -270,7 +289,9 @@ vector8_has_le(const Vector8 v, const uint8 c)
static inline bool
vector8_is_highbit_set(const Vector8 v)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_movemask_epi8(v) != 0;
+#elif defined(USE_SSE2)
return _mm_movemask_epi8(v) != 0;
#elif defined(USE_NEON)
return vmaxvq_u8(v) > 0x7F;
@@ -308,7 +329,9 @@ vector32_is_highbit_set(const Vector32 v)
static inline uint32
vector8_highbit_mask(const Vector8 v)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return (uint32) _mm256_movemask_epi8(v);
+#elif defined(USE_SSE2)
return (uint32) _mm_movemask_epi8(v);
#elif defined(USE_NEON)
/*
@@ -337,7 +360,9 @@ vector8_highbit_mask(const Vector8 v)
static inline Vector8
vector8_or(const Vector8 v1, const Vector8 v2)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_or_si256(v1, v2);
+#elif defined(USE_SSE2)
return _mm_or_si128(v1, v2);
#elif defined(USE_NEON)
return vorrq_u8(v1, v2);
@@ -350,7 +375,9 @@ vector8_or(const Vector8 v1, const Vector8 v2)
static inline Vector32
vector32_or(const Vector32 v1, const Vector32 v2)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_or_si256(v1, v2);
+#elif defined(USE_SSE2)
return _mm_or_si128(v1, v2);
#elif defined(USE_NEON)
return vorrq_u32(v1, v2);
@@ -368,7 +395,9 @@ vector32_or(const Vector32 v1, const Vector32 v2)
static inline Vector8
vector8_ssub(const Vector8 v1, const Vector8 v2)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_subs_epu8(v1, v2);
+#elif defined(USE_SSE2)
return _mm_subs_epu8(v1, v2);
#elif defined(USE_NEON)
return vqsubq_u8(v1, v2);
@@ -384,7 +413,9 @@ vector8_ssub(const Vector8 v1, const Vector8 v2)
static inline Vector8
vector8_eq(const Vector8 v1, const Vector8 v2)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_cmpeq_epi8(v1, v2);
+#elif defined(USE_SSE2)
return _mm_cmpeq_epi8(v1, v2);
#elif defined(USE_NEON)
return vceqq_u8(v1, v2);
@@ -396,7 +427,9 @@ vector8_eq(const Vector8 v1, const Vector8 v2)
static inline Vector32
vector32_eq(const Vector32 v1, const Vector32 v2)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_cmpeq_epi32(v1, v2);
+#elif defined(USE_SSE2)
return _mm_cmpeq_epi32(v1, v2);
#elif defined(USE_NEON)
return vceqq_u32(v1, v2);
@@ -411,7 +444,9 @@ vector32_eq(const Vector32 v1, const Vector32 v2)
static inline Vector8
vector8_min(const Vector8 v1, const Vector8 v2)
{
-#ifdef USE_SSE2
+#if defined(USE_AVX2)
+ return _mm256_min_epu8(v1, v2);
+#elif defined(USE_SSE2)
return _mm_min_epu8(v1, v2);
#elif defined(USE_NEON)
return vminq_u8(v1, v2);
--
2.25.1
v6_x86.jpg (image/jpeg, 23.3K) download
view image
v6_x86_extended.jpg (image/jpeg, 20.0K) download
view image
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 07:01 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-08 17:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 02:20 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-09 16:20 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-10 02:06 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-15 17:41 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-15 19:40 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-17 02:47 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 02:03 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 03:16 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 09:53 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 16:30 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 06:57 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-20 14:31 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 19:55 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-21 04:30 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-21 17:09 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
@ 2024-03-21 17:12 ` Nathan Bossart <nathandbossart@gmail.com>
2 siblings, 0 replies; 48+ messages in thread
From: Nathan Bossart @ 2024-03-21 17:12 UTC (permalink / raw)
To: John Naylor <johncnaylorls@gmail.com>; +Cc: Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Thu, Mar 21, 2024 at 12:09:44PM -0500, Nathan Bossart wrote:
> It does still eventually win, although not nearly to the same extent as
> before. I extended the benchmark a bit to show this. I wouldn't be
> devastated if we only got 0001 committed for v17, given these results.
(In case it isn't clear from the graph, after 128 elements, I only tested
at 200, 300, 400, etc. elements.)
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
^ permalink raw reply [nested|flat] 48+ messages in thread
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 07:01 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-08 17:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 02:20 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-09 16:20 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-10 02:06 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-15 17:41 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-15 19:40 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-17 02:47 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 02:03 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 03:16 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 09:53 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 16:30 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 06:57 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-20 14:31 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 19:55 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-21 04:30 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-21 17:09 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
@ 2024-03-21 18:38 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-24 20:53 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2 siblings, 1 reply; 48+ messages in thread
From: Nathan Bossart @ 2024-03-21 18:38 UTC (permalink / raw)
To: John Naylor <johncnaylorls@gmail.com>; +Cc: Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Thu, Mar 21, 2024 at 12:09:44PM -0500, Nathan Bossart wrote:
> On Thu, Mar 21, 2024 at 11:30:30AM +0700, John Naylor wrote:
>> Further, now that the algorithm is more SIMD-appropriate, I wonder
>> what doing 4 registers at a time is actually buying us for either SSE2
>> or AVX2. It might just be a matter of scale, but that would be good to
>> understand.
>
> I'll follow up with these numbers shortly.
It looks like the 4-register code still outperforms the 2-register code,
except for a handful of cases where there aren't many elements.
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
Attachments:
2reg.jpg (image/jpeg, 30.0K) download
view image
2reg_extended.jpg (image/jpeg, 23.8K) download
view image
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 07:01 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-08 17:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 02:20 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-09 16:20 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-10 02:06 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-15 17:41 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-15 19:40 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-17 02:47 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 02:03 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 03:16 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 09:53 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 16:30 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 06:57 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-20 14:31 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 19:55 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-21 04:30 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-21 17:09 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-21 18:38 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
@ 2024-03-24 20:53 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-24 22:09 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
0 siblings, 1 reply; 48+ messages in thread
From: Nathan Bossart @ 2024-03-24 20:53 UTC (permalink / raw)
To: John Naylor <johncnaylorls@gmail.com>; +Cc: Ants Aasma <ants@cybertec.at>; pgsql-hackers
Here's a new version of 0001 with some added #ifdefs that cfbot revealed
were missing.
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
Attachments:
v7-0001-pg_lfind32-add-overlap-code-for-remaining-element.patch (text/x-diff, 3.8K) download
From cc2bc5ca5b49cd8641af8b2231a34a1aa5091bb9 Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathan@postgresql.org>
Date: Wed, 20 Mar 2024 14:20:24 -0500
Subject: [PATCH v7 1/1] pg_lfind32(): add "overlap" code for remaining
elements
---
src/include/port/pg_lfind.h | 105 ++++++++++++++++++++++++------------
1 file changed, 72 insertions(+), 33 deletions(-)
diff --git a/src/include/port/pg_lfind.h b/src/include/port/pg_lfind.h
index b8dfa66eef..5830cc7cb3 100644
--- a/src/include/port/pg_lfind.h
+++ b/src/include/port/pg_lfind.h
@@ -80,6 +80,51 @@ pg_lfind8_le(uint8 key, uint8 *base, uint32 nelem)
return false;
}
+#ifndef USE_NO_SIMD
+/*
+ * pg_lfind32_helper
+ *
+ * Searches one 4-register-block of integers. The caller is responsible for
+ * ensuring that there are at least 4-registers-worth of integers remaining.
+ */
+static inline bool
+pg_lfind32_helper(const Vector32 keys, uint32 *base)
+{
+ const uint32 nelem_per_vector = sizeof(Vector32) / sizeof(uint32);
+ Vector32 vals1,
+ vals2,
+ vals3,
+ vals4,
+ result1,
+ result2,
+ result3,
+ result4,
+ tmp1,
+ tmp2,
+ result;
+
+ /* load the next block into 4 registers */
+ vector32_load(&vals1, base);
+ vector32_load(&vals2, &base[nelem_per_vector]);
+ vector32_load(&vals3, &base[nelem_per_vector * 2]);
+ vector32_load(&vals4, &base[nelem_per_vector * 3]);
+
+ /* compare each value to the key */
+ result1 = vector32_eq(keys, vals1);
+ result2 = vector32_eq(keys, vals2);
+ result3 = vector32_eq(keys, vals3);
+ result4 = vector32_eq(keys, vals4);
+
+ /* combine the results into a single variable */
+ tmp1 = vector32_or(result1, result2);
+ tmp2 = vector32_or(result3, result4);
+ result = vector32_or(tmp1, tmp2);
+
+ /* return whether there was a match */
+ return vector32_is_highbit_set(result);
+}
+#endif /* ! USE_NO_SIMD */
+
/*
* pg_lfind32
*
@@ -119,46 +164,40 @@ pg_lfind32(uint32 key, uint32 *base, uint32 nelem)
}
#endif
- for (i = 0; i < tail_idx; i += nelem_per_iteration)
+ /*
+ * If there aren't enough elements for the SIMD code, jump to the standard
+ * one-by-one linear search code.
+ */
+ if (nelem <= nelem_per_iteration)
+ goto one_by_one;
+
+ /*
+ * Process as many elements as possible with a block of 4 registers.
+ */
+ do
{
- Vector32 vals1,
- vals2,
- vals3,
- vals4,
- result1,
- result2,
- result3,
- result4,
- tmp1,
- tmp2,
- result;
-
- /* load the next block into 4 registers */
- vector32_load(&vals1, &base[i]);
- vector32_load(&vals2, &base[i + nelem_per_vector]);
- vector32_load(&vals3, &base[i + nelem_per_vector * 2]);
- vector32_load(&vals4, &base[i + nelem_per_vector * 3]);
-
- /* compare each value to the key */
- result1 = vector32_eq(keys, vals1);
- result2 = vector32_eq(keys, vals2);
- result3 = vector32_eq(keys, vals3);
- result4 = vector32_eq(keys, vals4);
-
- /* combine the results into a single variable */
- tmp1 = vector32_or(result1, result2);
- tmp2 = vector32_or(result3, result4);
- result = vector32_or(tmp1, tmp2);
-
- /* see if there was a match */
- if (vector32_is_highbit_set(result))
+ if (pg_lfind32_helper(keys, &base[i]))
{
Assert(assert_result == true);
return true;
}
- }
+
+ i += nelem_per_iteration;
+
+ } while (i < tail_idx);
+
+ /*
+ * Process the last 'nelem_per_iteration' elements in the array with a
+ * 4-register block. This will cause us to check some of the elements
+ * more than once, but that won't affect correctness, and testing has
+ * demonstrated that this helps more cases than it harms.
+ */
+ Assert(assert_result == pg_lfind32_helper(keys, &base[nelem - nelem_per_iteration]));
+ return pg_lfind32_helper(keys, &base[nelem - nelem_per_iteration]);
+
#endif /* ! USE_NO_SIMD */
+one_by_one:
/* Process the remaining elements one at a time. */
for (; i < nelem; i++)
{
--
2.25.1
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 07:01 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-08 17:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 02:20 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-09 16:20 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-10 02:06 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-15 17:41 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-15 19:40 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-17 02:47 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 02:03 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 03:16 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 09:53 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 16:30 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 06:57 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-20 14:31 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 19:55 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-21 04:30 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-21 17:09 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-21 18:38 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-24 20:53 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
@ 2024-03-24 22:09 ` Nathan Bossart <nathandbossart@gmail.com>
0 siblings, 0 replies; 48+ messages in thread
From: Nathan Bossart @ 2024-03-24 22:09 UTC (permalink / raw)
To: John Naylor <johncnaylorls@gmail.com>; +Cc: Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Sun, Mar 24, 2024 at 03:53:17PM -0500, Nathan Bossart wrote:
> Here's a new version of 0001 with some added #ifdefs that cfbot revealed
> were missing.
Sorry for the noise. cfbot revealed another silly mistake (forgetting to
reset the "i" variable in the assertion path). That should be fixed in v8.
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
Attachments:
v8-0001-pg_lfind32-add-overlap-code-for-remaining-element.patch (text/x-diff, 4.1K) download
From f15d85844370aef8505559fc0f2db629b135a9e8 Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathan@postgresql.org>
Date: Wed, 20 Mar 2024 14:20:24 -0500
Subject: [PATCH v8 1/1] pg_lfind32(): add "overlap" code for remaining
elements
---
src/include/port/pg_lfind.h | 109 ++++++++++++++++++++++++------------
1 file changed, 74 insertions(+), 35 deletions(-)
diff --git a/src/include/port/pg_lfind.h b/src/include/port/pg_lfind.h
index b8dfa66eef..f746aabbf9 100644
--- a/src/include/port/pg_lfind.h
+++ b/src/include/port/pg_lfind.h
@@ -80,6 +80,51 @@ pg_lfind8_le(uint8 key, uint8 *base, uint32 nelem)
return false;
}
+#ifndef USE_NO_SIMD
+/*
+ * pg_lfind32_helper
+ *
+ * Searches one 4-register-block of integers. The caller is responsible for
+ * ensuring that there are at least 4-registers-worth of integers remaining.
+ */
+static inline bool
+pg_lfind32_helper(const Vector32 keys, uint32 *base)
+{
+ const uint32 nelem_per_vector = sizeof(Vector32) / sizeof(uint32);
+ Vector32 vals1,
+ vals2,
+ vals3,
+ vals4,
+ result1,
+ result2,
+ result3,
+ result4,
+ tmp1,
+ tmp2,
+ result;
+
+ /* load the next block into 4 registers */
+ vector32_load(&vals1, base);
+ vector32_load(&vals2, &base[nelem_per_vector]);
+ vector32_load(&vals3, &base[nelem_per_vector * 2]);
+ vector32_load(&vals4, &base[nelem_per_vector * 3]);
+
+ /* compare each value to the key */
+ result1 = vector32_eq(keys, vals1);
+ result2 = vector32_eq(keys, vals2);
+ result3 = vector32_eq(keys, vals3);
+ result4 = vector32_eq(keys, vals4);
+
+ /* combine the results into a single variable */
+ tmp1 = vector32_or(result1, result2);
+ tmp2 = vector32_or(result3, result4);
+ result = vector32_or(tmp1, tmp2);
+
+ /* return whether there was a match */
+ return vector32_is_highbit_set(result);
+}
+#endif /* ! USE_NO_SIMD */
+
/*
* pg_lfind32
*
@@ -109,9 +154,9 @@ pg_lfind32(uint32 key, uint32 *base, uint32 nelem)
bool assert_result = false;
/* pre-compute the result for assert checking */
- for (i = 0; i < nelem; i++)
+ for (int j = 0; j < nelem; j++)
{
- if (key == base[i])
+ if (key == base[j])
{
assert_result = true;
break;
@@ -119,46 +164,40 @@ pg_lfind32(uint32 key, uint32 *base, uint32 nelem)
}
#endif
- for (i = 0; i < tail_idx; i += nelem_per_iteration)
+ /*
+ * If there aren't enough elements for the SIMD code, jump to the standard
+ * one-by-one linear search code.
+ */
+ if (nelem <= nelem_per_iteration)
+ goto one_by_one;
+
+ /*
+ * Process as many elements as possible with a block of 4 registers.
+ */
+ do
{
- Vector32 vals1,
- vals2,
- vals3,
- vals4,
- result1,
- result2,
- result3,
- result4,
- tmp1,
- tmp2,
- result;
-
- /* load the next block into 4 registers */
- vector32_load(&vals1, &base[i]);
- vector32_load(&vals2, &base[i + nelem_per_vector]);
- vector32_load(&vals3, &base[i + nelem_per_vector * 2]);
- vector32_load(&vals4, &base[i + nelem_per_vector * 3]);
-
- /* compare each value to the key */
- result1 = vector32_eq(keys, vals1);
- result2 = vector32_eq(keys, vals2);
- result3 = vector32_eq(keys, vals3);
- result4 = vector32_eq(keys, vals4);
-
- /* combine the results into a single variable */
- tmp1 = vector32_or(result1, result2);
- tmp2 = vector32_or(result3, result4);
- result = vector32_or(tmp1, tmp2);
-
- /* see if there was a match */
- if (vector32_is_highbit_set(result))
+ if (pg_lfind32_helper(keys, &base[i]))
{
Assert(assert_result == true);
return true;
}
- }
+
+ i += nelem_per_iteration;
+
+ } while (i < tail_idx);
+
+ /*
+ * Process the last 'nelem_per_iteration' elements in the array with a
+ * 4-register block. This will cause us to check some of the elements
+ * more than once, but that won't affect correctness, and testing has
+ * demonstrated that this helps more cases than it harms.
+ */
+ Assert(assert_result == pg_lfind32_helper(keys, &base[nelem - nelem_per_iteration]));
+ return pg_lfind32_helper(keys, &base[nelem - nelem_per_iteration]);
+
#endif /* ! USE_NO_SIMD */
+one_by_one:
/* Process the remaining elements one at a time. */
for (; i < nelem; i++)
{
--
2.25.1
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 07:01 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-08 17:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 02:20 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-09 16:20 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-10 02:06 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-15 17:41 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-15 19:40 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-17 02:47 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 02:03 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 03:16 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 09:53 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 16:30 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 06:57 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-20 14:31 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 19:55 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-21 04:30 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-21 17:09 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
@ 2024-03-25 03:03 ` John Naylor <johncnaylorls@gmail.com>
2024-03-25 15:21 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2 siblings, 1 reply; 48+ messages in thread
From: John Naylor @ 2024-03-25 03:03 UTC (permalink / raw)
To: Nathan Bossart <nathandbossart@gmail.com>; +Cc: Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Fri, Mar 22, 2024 at 12:09 AM Nathan Bossart
<nathandbossart@gmail.com> wrote:
>
> On Thu, Mar 21, 2024 at 11:30:30AM +0700, John Naylor wrote:
> > If this were "<=" then the for long arrays we could assume there is
> > always more than one block, and wouldn't need to check if any elements
> > remain -- first block, then a single loop and it's done.
> >
> > The loop could also then be a "do while" since it doesn't have to
> > check the exit condition up front.
>
> Good idea. That causes us to re-check all of the tail elements when the
> number of elements is evenly divisible by nelem_per_iteration, but that
> might be worth the trade-off.
Yeah, if there's no easy way to avoid that it's probably fine. I
wonder if we can subtract one first to force even multiples to round
down, although I admit I haven't thought through the consequences of
that.
> [v8]
Seems pretty good. It'd be good to see the results of 2- vs.
4-register before committing, because that might lead to some
restructuring, but maybe it won't, and v8 is already an improvement
over HEAD.
/* Process the remaining elements one at a time. */
This now does all of them if that path is taken, so "remaining" can be removed.
^ permalink raw reply [nested|flat] 48+ messages in thread
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 07:01 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-08 17:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 02:20 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-09 16:20 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-10 02:06 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-15 17:41 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-15 19:40 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-17 02:47 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 02:03 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 03:16 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 09:53 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 16:30 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 06:57 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-20 14:31 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 19:55 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-21 04:30 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-21 17:09 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-25 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
@ 2024-03-25 15:21 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-25 21:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
0 siblings, 1 reply; 48+ messages in thread
From: Nathan Bossart @ 2024-03-25 15:21 UTC (permalink / raw)
To: John Naylor <johncnaylorls@gmail.com>; +Cc: Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Mon, Mar 25, 2024 at 10:03:27AM +0700, John Naylor wrote:
> Seems pretty good. It'd be good to see the results of 2- vs.
> 4-register before committing, because that might lead to some
> restructuring, but maybe it won't, and v8 is already an improvement
> over HEAD.
I tested this the other day [0] (only for x86). The results seemed to
indicate that the 4-register approach was still quite a bit better.
> /* Process the remaining elements one at a time. */
>
> This now does all of them if that path is taken, so "remaining" can be removed.
Right, will do.
[0] https://postgr.es/m/20240321183823.GA1800896%40nathanxps13
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
^ permalink raw reply [nested|flat] 48+ messages in thread
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 07:01 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-08 17:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 02:20 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-09 16:20 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-10 02:06 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-15 17:41 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-15 19:40 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-17 02:47 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 02:03 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 03:16 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 09:53 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 16:30 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 06:57 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-20 14:31 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 19:55 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-21 04:30 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-21 17:09 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-25 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-25 15:21 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
@ 2024-03-25 21:37 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-26 19:09 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
0 siblings, 1 reply; 48+ messages in thread
From: Nathan Bossart @ 2024-03-25 21:37 UTC (permalink / raw)
To: John Naylor <johncnaylorls@gmail.com>; +Cc: Ants Aasma <ants@cybertec.at>; pgsql-hackers
Here is what I have staged for commit. One notable difference in this
version of the patch is that I've changed
+ if (nelem <= nelem_per_iteration)
+ goto one_by_one;
to
+ if (nelem < nelem_per_iteration)
+ goto one_by_one;
I realized that there's no reason to jump to the one-by-one linear search
code when nelem == nelem_per_iteration, as the worst thing that will happen
is that we'll process all the elements twice if the value isn't present in
the array. My benchmark that I've been using also shows a significant
speedup for this case with this change (on the order of 75%), which I
imagine might be due to a combination of branch prediction, caching, fewer
instructions, etc.
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
Attachments:
v9-0001-Micro-optimize-pg_lfind32.patch (text/x-diff, 5.4K) download
From 1dd970248efd3c5ae1736c0dd1d61fbabbb6c101 Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathan@postgresql.org>
Date: Mon, 25 Mar 2024 16:21:45 -0500
Subject: [PATCH v9 1/1] Micro-optimize pg_lfind32().
This commit improves the performance of pg_lfind32() in many cases
by modifying it to process the remaining "tail" of elements with
SIMD instructions instead of processing them one-by-one. Since the
SIMD code processes a large block of elements, this means that we
will process a subset of elements more than once, but that won't
affect the correctness of the result, and testing has shown that
this helps more cases than it regresses. With this change, the
standard one-by-one linear search code is only used for small
arrays and for platforms without SIMD support.
Furthermore, this commit restructures pg_lfind32() to minimize
branching, which should also improve performance.
Suggested-by: John Naylor
Reviewed-by: John Naylor
Discussion: https://postgr.es/m/20231129171526.GA857928%40nathanxps13
---
src/include/port/pg_lfind.h | 114 ++++++++++++++++++++++++------------
1 file changed, 76 insertions(+), 38 deletions(-)
diff --git a/src/include/port/pg_lfind.h b/src/include/port/pg_lfind.h
index b8dfa66eef..dbc3e9fc6a 100644
--- a/src/include/port/pg_lfind.h
+++ b/src/include/port/pg_lfind.h
@@ -80,6 +80,51 @@ pg_lfind8_le(uint8 key, uint8 *base, uint32 nelem)
return false;
}
+#ifndef USE_NO_SIMD
+/*
+ * pg_lfind32_simd_helper
+ *
+ * Searches one 4-register-block of integers. The caller is responsible for
+ * ensuring that there are at least 4-registers-worth of integers remaining.
+ */
+static inline bool
+pg_lfind32_simd_helper(const Vector32 keys, uint32 *base)
+{
+ const uint32 nelem_per_vector = sizeof(Vector32) / sizeof(uint32);
+ Vector32 vals1,
+ vals2,
+ vals3,
+ vals4,
+ result1,
+ result2,
+ result3,
+ result4,
+ tmp1,
+ tmp2,
+ result;
+
+ /* load the next block into 4 registers */
+ vector32_load(&vals1, base);
+ vector32_load(&vals2, &base[nelem_per_vector]);
+ vector32_load(&vals3, &base[nelem_per_vector * 2]);
+ vector32_load(&vals4, &base[nelem_per_vector * 3]);
+
+ /* compare each value to the key */
+ result1 = vector32_eq(keys, vals1);
+ result2 = vector32_eq(keys, vals2);
+ result3 = vector32_eq(keys, vals3);
+ result4 = vector32_eq(keys, vals4);
+
+ /* combine the results into a single variable */
+ tmp1 = vector32_or(result1, result2);
+ tmp2 = vector32_or(result3, result4);
+ result = vector32_or(tmp1, tmp2);
+
+ /* return whether there was a match */
+ return vector32_is_highbit_set(result);
+}
+#endif /* ! USE_NO_SIMD */
+
/*
* pg_lfind32
*
@@ -95,8 +140,7 @@ pg_lfind32(uint32 key, uint32 *base, uint32 nelem)
/*
* For better instruction-level parallelism, each loop iteration operates
- * on a block of four registers. Testing for SSE2 has showed this is ~40%
- * faster than using a block of two registers.
+ * on a block of four registers.
*/
const Vector32 keys = vector32_broadcast(key); /* load copies of key */
const uint32 nelem_per_vector = sizeof(Vector32) / sizeof(uint32);
@@ -109,9 +153,9 @@ pg_lfind32(uint32 key, uint32 *base, uint32 nelem)
bool assert_result = false;
/* pre-compute the result for assert checking */
- for (i = 0; i < nelem; i++)
+ for (int j = 0; j < nelem; j++)
{
- if (key == base[i])
+ if (key == base[j])
{
assert_result = true;
break;
@@ -119,47 +163,41 @@ pg_lfind32(uint32 key, uint32 *base, uint32 nelem)
}
#endif
- for (i = 0; i < tail_idx; i += nelem_per_iteration)
+ /*
+ * If there aren't enough elements for the SIMD code, jump to the standard
+ * one-by-one linear search code.
+ */
+ if (nelem < nelem_per_iteration)
+ goto one_by_one;
+
+ /*
+ * Process as many elements as possible with a block of 4 registers.
+ */
+ do
{
- Vector32 vals1,
- vals2,
- vals3,
- vals4,
- result1,
- result2,
- result3,
- result4,
- tmp1,
- tmp2,
- result;
-
- /* load the next block into 4 registers */
- vector32_load(&vals1, &base[i]);
- vector32_load(&vals2, &base[i + nelem_per_vector]);
- vector32_load(&vals3, &base[i + nelem_per_vector * 2]);
- vector32_load(&vals4, &base[i + nelem_per_vector * 3]);
-
- /* compare each value to the key */
- result1 = vector32_eq(keys, vals1);
- result2 = vector32_eq(keys, vals2);
- result3 = vector32_eq(keys, vals3);
- result4 = vector32_eq(keys, vals4);
-
- /* combine the results into a single variable */
- tmp1 = vector32_or(result1, result2);
- tmp2 = vector32_or(result3, result4);
- result = vector32_or(tmp1, tmp2);
-
- /* see if there was a match */
- if (vector32_is_highbit_set(result))
+ if (pg_lfind32_simd_helper(keys, &base[i]))
{
Assert(assert_result == true);
return true;
}
- }
+
+ i += nelem_per_iteration;
+
+ } while (i < tail_idx);
+
+ /*
+ * Process the last 'nelem_per_iteration' elements in the array with a
+ * 4-register block. This will cause us to check a subset of the elements
+ * more than once, but that won't affect correctness, and testing has
+ * demonstrated that this helps more cases than it harms.
+ */
+ Assert(assert_result == pg_lfind32_simd_helper(keys, &base[nelem - nelem_per_iteration]));
+ return pg_lfind32_simd_helper(keys, &base[nelem - nelem_per_iteration]);
+
#endif /* ! USE_NO_SIMD */
- /* Process the remaining elements one at a time. */
+one_by_one:
+ /* Process the elements one at a time. */
for (; i < nelem; i++)
{
if (key == base[i])
--
2.25.1
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 07:01 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-08 17:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 02:20 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-09 16:20 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-10 02:06 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-15 17:41 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-15 19:40 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-17 02:47 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 02:03 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 03:16 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 09:53 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 16:30 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 06:57 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-20 14:31 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 19:55 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-21 04:30 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-21 17:09 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-25 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-25 15:21 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-25 21:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
@ 2024-03-26 19:09 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-26 23:28 ` Re: add AVX2 support to simd.h Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 1 reply; 48+ messages in thread
From: Nathan Bossart @ 2024-03-26 19:09 UTC (permalink / raw)
To: John Naylor <johncnaylorls@gmail.com>; +Cc: Ants Aasma <ants@cybertec.at>; pgsql-hackers
I've committed v9, and I've marked the commitfest entry as "Committed,"
although we may want to revisit AVX2, etc. in the future.
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
^ permalink raw reply [nested|flat] 48+ messages in thread
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 07:01 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-08 17:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 02:20 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-09 16:20 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-10 02:06 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-15 17:41 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-15 19:40 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-17 02:47 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 02:03 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 03:16 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 09:53 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 16:30 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 06:57 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-20 14:31 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 19:55 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-21 04:30 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-21 17:09 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-25 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-25 15:21 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-25 21:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-26 19:09 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
@ 2024-03-26 23:28 ` Tom Lane <tgl@sss.pgh.pa.us>
2024-03-26 23:55 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
0 siblings, 1 reply; 48+ messages in thread
From: Tom Lane @ 2024-03-26 23:28 UTC (permalink / raw)
To: Nathan Bossart <nathandbossart@gmail.com>; +Cc: John Naylor <johncnaylorls@gmail.com>; Ants Aasma <ants@cybertec.at>; pgsql-hackers
Nathan Bossart <nathandbossart@gmail.com> writes:
> I've committed v9, and I've marked the commitfest entry as "Committed,"
> although we may want to revisit AVX2, etc. in the future.
A significant fraction of the buildfarm is issuing warnings about
this.
adder | 2024-03-26 21:04:33 | ../pgsql/src/include/port/pg_lfind.h:199:1: warning: label 'one_by_one' defined but not used [-Wunused-label]
buri | 2024-03-26 21:16:09 | ../../src/include/port/pg_lfind.h:199:1: warning: label 'one_by_one' defined but not used [-Wunused-label]
cavefish | 2024-03-26 22:53:23 | ../../src/include/port/pg_lfind.h:199:1: warning: label 'one_by_one' defined but not used [-Wunused-label]
cisticola | 2024-03-26 22:20:07 | ../../../../src/include/port/pg_lfind.h:199:1: warning: label 'one_by_one' defined but not used [-Wunused-label]
lancehead | 2024-03-26 21:48:17 | ../../src/include/port/pg_lfind.h:199:1: warning: unused label 'one_by_one' [-Wunused-label]
nicator | 2024-03-26 21:08:14 | ../../src/include/port/pg_lfind.h:199:1: warning: label 'one_by_one' defined but not used [-Wunused-label]
nuthatch | 2024-03-26 22:00:04 | ../../src/include/port/pg_lfind.h:199:1: warning: label 'one_by_one' defined but not used [-Wunused-label]
rinkhals | 2024-03-26 19:51:32 | ../../src/include/port/pg_lfind.h:199:1: warning: unused label 'one_by_one' [-Wunused-label]
siskin | 2024-03-26 19:59:29 | ../../src/include/port/pg_lfind.h:199:1: warning: label 'one_by_one' defined but not used [-Wunused-label]
regards, tom lane
^ permalink raw reply [nested|flat] 48+ messages in thread
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 07:01 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-08 17:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 02:20 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-09 16:20 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-10 02:06 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-15 17:41 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-15 19:40 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-17 02:47 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 02:03 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 03:16 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 09:53 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 16:30 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 06:57 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-20 14:31 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 19:55 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-21 04:30 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-21 17:09 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-25 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-25 15:21 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-25 21:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-26 19:09 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-26 23:28 ` Re: add AVX2 support to simd.h Tom Lane <tgl@sss.pgh.pa.us>
@ 2024-03-26 23:55 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-27 01:36 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
0 siblings, 1 reply; 48+ messages in thread
From: Nathan Bossart @ 2024-03-26 23:55 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: John Naylor <johncnaylorls@gmail.com>; Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Tue, Mar 26, 2024 at 07:28:24PM -0400, Tom Lane wrote:
> Nathan Bossart <nathandbossart@gmail.com> writes:
>> I've committed v9, and I've marked the commitfest entry as "Committed,"
>> although we may want to revisit AVX2, etc. in the future.
>
> A significant fraction of the buildfarm is issuing warnings about
> this.
Thanks for the heads-up. Will fix.
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
^ permalink raw reply [nested|flat] 48+ messages in thread
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 07:01 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-08 17:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 02:20 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-09 16:20 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-10 02:06 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-15 17:41 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-15 19:40 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-17 02:47 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 02:03 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 03:16 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 09:53 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 16:30 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 06:57 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-20 14:31 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 19:55 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-21 04:30 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-21 17:09 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-25 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-25 15:21 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-25 21:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-26 19:09 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-26 23:28 ` Re: add AVX2 support to simd.h Tom Lane <tgl@sss.pgh.pa.us>
2024-03-26 23:55 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
@ 2024-03-27 01:36 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-27 01:48 ` Re: add AVX2 support to simd.h Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 1 reply; 48+ messages in thread
From: Nathan Bossart @ 2024-03-27 01:36 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: John Naylor <johncnaylorls@gmail.com>; Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Tue, Mar 26, 2024 at 06:55:54PM -0500, Nathan Bossart wrote:
> On Tue, Mar 26, 2024 at 07:28:24PM -0400, Tom Lane wrote:
>> A significant fraction of the buildfarm is issuing warnings about
>> this.
>
> Thanks for the heads-up. Will fix.
Done. I'll keep an eye on the farm.
I just did the minimal fix for now, i.e., I moved the new label into the
SIMD section of the function. I think it would be better stylistically to
move the one-by-one logic to an inline helper function, but I didn't do
that just in case it might negatively impact performance. I'll look into
this and will follow up with another patch if it looks good.
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
^ permalink raw reply [nested|flat] 48+ messages in thread
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 07:01 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-08 17:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 02:20 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-09 16:20 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-10 02:06 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-15 17:41 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-15 19:40 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-17 02:47 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 02:03 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 03:16 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 09:53 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 16:30 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 06:57 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-20 14:31 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 19:55 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-21 04:30 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-21 17:09 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-25 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-25 15:21 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-25 21:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-26 19:09 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-26 23:28 ` Re: add AVX2 support to simd.h Tom Lane <tgl@sss.pgh.pa.us>
2024-03-26 23:55 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-27 01:36 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
@ 2024-03-27 01:48 ` Tom Lane <tgl@sss.pgh.pa.us>
2024-03-27 18:57 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
0 siblings, 1 reply; 48+ messages in thread
From: Tom Lane @ 2024-03-27 01:48 UTC (permalink / raw)
To: Nathan Bossart <nathandbossart@gmail.com>; +Cc: John Naylor <johncnaylorls@gmail.com>; Ants Aasma <ants@cybertec.at>; pgsql-hackers
Nathan Bossart <nathandbossart@gmail.com> writes:
> On Tue, Mar 26, 2024 at 06:55:54PM -0500, Nathan Bossart wrote:
>> On Tue, Mar 26, 2024 at 07:28:24PM -0400, Tom Lane wrote:
>>> A significant fraction of the buildfarm is issuing warnings about
>>> this.
> Done. I'll keep an eye on the farm.
Thanks.
> I just did the minimal fix for now, i.e., I moved the new label into the
> SIMD section of the function. I think it would be better stylistically to
> move the one-by-one logic to an inline helper function, but I didn't do
> that just in case it might negatively impact performance. I'll look into
> this and will follow up with another patch if it looks good.
Sounds like a plan.
regards, tom lane
^ permalink raw reply [nested|flat] 48+ messages in thread
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 07:01 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-08 17:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 02:20 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-09 16:20 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-10 02:06 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-15 17:41 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-15 19:40 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-17 02:47 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 02:03 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 03:16 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 09:53 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 16:30 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 06:57 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-20 14:31 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 19:55 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-21 04:30 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-21 17:09 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-25 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-25 15:21 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-25 21:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-26 19:09 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-26 23:28 ` Re: add AVX2 support to simd.h Tom Lane <tgl@sss.pgh.pa.us>
2024-03-26 23:55 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-27 01:36 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-27 01:48 ` Re: add AVX2 support to simd.h Tom Lane <tgl@sss.pgh.pa.us>
@ 2024-03-27 18:57 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-27 21:10 ` Re: add AVX2 support to simd.h Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 1 reply; 48+ messages in thread
From: Nathan Bossart @ 2024-03-27 18:57 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: John Naylor <johncnaylorls@gmail.com>; Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Tue, Mar 26, 2024 at 09:48:57PM -0400, Tom Lane wrote:
> Nathan Bossart <nathandbossart@gmail.com> writes:
>> I just did the minimal fix for now, i.e., I moved the new label into the
>> SIMD section of the function. I think it would be better stylistically to
>> move the one-by-one logic to an inline helper function, but I didn't do
>> that just in case it might negatively impact performance. I'll look into
>> this and will follow up with another patch if it looks good.
>
> Sounds like a plan.
Here's what I had in mind. My usual benchmark seems to indicate that this
shouldn't impact performance.
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
Attachments:
v1-0001-improve-style-of-pg_lfind32.patch (text/x-diff, 2.8K) download
From c3f163753246c5ec82dd8c5dba70232cbeebbf2a Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathan@postgresql.org>
Date: Wed, 27 Mar 2024 13:50:17 -0500
Subject: [PATCH v1 1/1] improve style of pg_lfind32()
---
src/include/port/pg_lfind.h | 58 +++++++++++++++----------------------
1 file changed, 24 insertions(+), 34 deletions(-)
diff --git a/src/include/port/pg_lfind.h b/src/include/port/pg_lfind.h
index 33e8471b03..5b76cc8937 100644
--- a/src/include/port/pg_lfind.h
+++ b/src/include/port/pg_lfind.h
@@ -80,6 +80,24 @@ pg_lfind8_le(uint8 key, uint8 *base, uint32 nelem)
return false;
}
+/*
+ * pg_lfind32_one_by_one_helper
+ *
+ * Searches the array of integers one-by-one. The caller is responsible for
+ * ensuring that there are at least "nelem" integers in the array.
+ */
+static inline bool
+pg_lfind32_one_by_one_helper(uint32 key, uint32 *base, uint32 nelem)
+{
+ for (int i = 0; i < nelem; i++)
+ {
+ if (key == base[i])
+ return true;
+ }
+
+ return false;
+}
+
#ifndef USE_NO_SIMD
/*
* pg_lfind32_simd_helper
@@ -134,9 +152,8 @@ pg_lfind32_simd_helper(const Vector32 keys, uint32 *base)
static inline bool
pg_lfind32(uint32 key, uint32 *base, uint32 nelem)
{
- uint32 i = 0;
-
#ifndef USE_NO_SIMD
+ uint32 i = 0;
/*
* For better instruction-level parallelism, each loop iteration operates
@@ -150,25 +167,15 @@ pg_lfind32(uint32 key, uint32 *base, uint32 nelem)
const uint32 tail_idx = nelem & ~(nelem_per_iteration - 1);
#if defined(USE_ASSERT_CHECKING)
- bool assert_result = false;
-
- /* pre-compute the result for assert checking */
- for (int j = 0; j < nelem; j++)
- {
- if (key == base[j])
- {
- assert_result = true;
- break;
- }
- }
+ bool assert_result = pg_lfind32_one_by_one_helper(key, base, nelem);
#endif
/*
- * If there aren't enough elements for the SIMD code, jump to the standard
+ * If there aren't enough elements for the SIMD code, use the standard
* one-by-one linear search code.
*/
if (nelem < nelem_per_iteration)
- goto one_by_one;
+ return pg_lfind32_one_by_one_helper(key, base, nelem);
/*
* Process as many elements as possible with a block of 4 registers.
@@ -193,27 +200,10 @@ pg_lfind32(uint32 key, uint32 *base, uint32 nelem)
*/
Assert(assert_result == pg_lfind32_simd_helper(keys, &base[nelem - nelem_per_iteration]));
return pg_lfind32_simd_helper(keys, &base[nelem - nelem_per_iteration]);
-
-one_by_one:
-
-#endif /* ! USE_NO_SIMD */
-
+#else
/* Process the elements one at a time. */
- for (; i < nelem; i++)
- {
- if (key == base[i])
- {
-#ifndef USE_NO_SIMD
- Assert(assert_result == true);
+ return pg_lfind32_one_by_one_helper(key, base, nelem);
#endif
- return true;
- }
- }
-
-#ifndef USE_NO_SIMD
- Assert(assert_result == false);
-#endif
- return false;
}
#endif /* PG_LFIND_H */
--
2.25.1
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 07:01 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-08 17:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 02:20 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-09 16:20 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-10 02:06 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-15 17:41 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-15 19:40 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-17 02:47 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 02:03 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 03:16 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 09:53 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 16:30 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 06:57 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-20 14:31 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 19:55 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-21 04:30 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-21 17:09 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-25 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-25 15:21 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-25 21:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-26 19:09 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-26 23:28 ` Re: add AVX2 support to simd.h Tom Lane <tgl@sss.pgh.pa.us>
2024-03-26 23:55 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-27 01:36 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-27 01:48 ` Re: add AVX2 support to simd.h Tom Lane <tgl@sss.pgh.pa.us>
2024-03-27 18:57 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
@ 2024-03-27 21:10 ` Tom Lane <tgl@sss.pgh.pa.us>
2024-03-27 21:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
0 siblings, 1 reply; 48+ messages in thread
From: Tom Lane @ 2024-03-27 21:10 UTC (permalink / raw)
To: Nathan Bossart <nathandbossart@gmail.com>; +Cc: John Naylor <johncnaylorls@gmail.com>; Ants Aasma <ants@cybertec.at>; pgsql-hackers
Nathan Bossart <nathandbossart@gmail.com> writes:
> Here's what I had in mind. My usual benchmark seems to indicate that this
> shouldn't impact performance.
Shouldn't "i" be declared uint32, since nelem is?
BTW, I wonder why these functions don't declare their array
arguments like "const uint32 *base".
LGTM otherwise, and I like the fact that the #if structure
gets a lot less messy.
regards, tom lane
^ permalink raw reply [nested|flat] 48+ messages in thread
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 07:01 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-08 17:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 02:20 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-09 16:20 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-10 02:06 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-15 17:41 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-15 19:40 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-17 02:47 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 02:03 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 03:16 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 09:53 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 16:30 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 06:57 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-20 14:31 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 19:55 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-21 04:30 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-21 17:09 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-25 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-25 15:21 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-25 21:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-26 19:09 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-26 23:28 ` Re: add AVX2 support to simd.h Tom Lane <tgl@sss.pgh.pa.us>
2024-03-26 23:55 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-27 01:36 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-27 01:48 ` Re: add AVX2 support to simd.h Tom Lane <tgl@sss.pgh.pa.us>
2024-03-27 18:57 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-27 21:10 ` Re: add AVX2 support to simd.h Tom Lane <tgl@sss.pgh.pa.us>
@ 2024-03-27 21:37 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-28 01:32 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
0 siblings, 1 reply; 48+ messages in thread
From: Nathan Bossart @ 2024-03-27 21:37 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: John Naylor <johncnaylorls@gmail.com>; Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Wed, Mar 27, 2024 at 05:10:13PM -0400, Tom Lane wrote:
> Shouldn't "i" be declared uint32, since nelem is?
Yes, that's a mistake.
> BTW, I wonder why these functions don't declare their array
> arguments like "const uint32 *base".
They probably should. I don't see any reason not to, and my compiler
doesn't complain, either.
> LGTM otherwise, and I like the fact that the #if structure
> gets a lot less messy.
Thanks for reviewing. I've attached a v2 that I intend to commit when I
get a chance.
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
Attachments:
v2-0001-improve-style-of-pg_lfind32.patch (text/x-diff, 3.3K) download
From 6f2577779917230bf70284f0ec1186bed17d9b4a Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathan@postgresql.org>
Date: Wed, 27 Mar 2024 13:50:17 -0500
Subject: [PATCH v2 1/1] improve style of pg_lfind32()
---
src/include/port/pg_lfind.h | 62 ++++++++++++++++---------------------
1 file changed, 26 insertions(+), 36 deletions(-)
diff --git a/src/include/port/pg_lfind.h b/src/include/port/pg_lfind.h
index 33e8471b03..4b1431ed00 100644
--- a/src/include/port/pg_lfind.h
+++ b/src/include/port/pg_lfind.h
@@ -80,6 +80,24 @@ pg_lfind8_le(uint8 key, uint8 *base, uint32 nelem)
return false;
}
+/*
+ * pg_lfind32_one_by_one_helper
+ *
+ * Searches the array of integers one-by-one. The caller is responsible for
+ * ensuring that there are at least "nelem" integers in the array.
+ */
+static inline bool
+pg_lfind32_one_by_one_helper(uint32 key, const uint32 *base, uint32 nelem)
+{
+ for (uint32 i = 0; i < nelem; i++)
+ {
+ if (key == base[i])
+ return true;
+ }
+
+ return false;
+}
+
#ifndef USE_NO_SIMD
/*
* pg_lfind32_simd_helper
@@ -88,7 +106,7 @@ pg_lfind8_le(uint8 key, uint8 *base, uint32 nelem)
* ensuring that there are at least 4-registers-worth of integers remaining.
*/
static inline bool
-pg_lfind32_simd_helper(const Vector32 keys, uint32 *base)
+pg_lfind32_simd_helper(const Vector32 keys, const uint32 *base)
{
const uint32 nelem_per_vector = sizeof(Vector32) / sizeof(uint32);
Vector32 vals1,
@@ -132,11 +150,10 @@ pg_lfind32_simd_helper(const Vector32 keys, uint32 *base)
* return false.
*/
static inline bool
-pg_lfind32(uint32 key, uint32 *base, uint32 nelem)
+pg_lfind32(uint32 key, const uint32 *base, uint32 nelem)
{
- uint32 i = 0;
-
#ifndef USE_NO_SIMD
+ uint32 i = 0;
/*
* For better instruction-level parallelism, each loop iteration operates
@@ -150,25 +167,15 @@ pg_lfind32(uint32 key, uint32 *base, uint32 nelem)
const uint32 tail_idx = nelem & ~(nelem_per_iteration - 1);
#if defined(USE_ASSERT_CHECKING)
- bool assert_result = false;
-
- /* pre-compute the result for assert checking */
- for (int j = 0; j < nelem; j++)
- {
- if (key == base[j])
- {
- assert_result = true;
- break;
- }
- }
+ bool assert_result = pg_lfind32_one_by_one_helper(key, base, nelem);
#endif
/*
- * If there aren't enough elements for the SIMD code, jump to the standard
+ * If there aren't enough elements for the SIMD code, use the standard
* one-by-one linear search code.
*/
if (nelem < nelem_per_iteration)
- goto one_by_one;
+ return pg_lfind32_one_by_one_helper(key, base, nelem);
/*
* Process as many elements as possible with a block of 4 registers.
@@ -193,27 +200,10 @@ pg_lfind32(uint32 key, uint32 *base, uint32 nelem)
*/
Assert(assert_result == pg_lfind32_simd_helper(keys, &base[nelem - nelem_per_iteration]));
return pg_lfind32_simd_helper(keys, &base[nelem - nelem_per_iteration]);
-
-one_by_one:
-
-#endif /* ! USE_NO_SIMD */
-
+#else
/* Process the elements one at a time. */
- for (; i < nelem; i++)
- {
- if (key == base[i])
- {
-#ifndef USE_NO_SIMD
- Assert(assert_result == true);
+ return pg_lfind32_one_by_one_helper(key, base, nelem);
#endif
- return true;
- }
- }
-
-#ifndef USE_NO_SIMD
- Assert(assert_result == false);
-#endif
- return false;
}
#endif /* PG_LFIND_H */
--
2.25.1
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 07:01 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-08 17:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 02:20 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-01-09 16:20 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-10 02:06 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-15 17:41 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-15 19:40 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-17 02:47 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 02:03 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 03:16 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 09:53 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-19 16:30 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 06:57 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-20 14:31 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 19:55 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-21 04:30 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-21 17:09 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-25 03:03 ` Re: add AVX2 support to simd.h John Naylor <johncnaylorls@gmail.com>
2024-03-25 15:21 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-25 21:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-26 19:09 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-26 23:28 ` Re: add AVX2 support to simd.h Tom Lane <tgl@sss.pgh.pa.us>
2024-03-26 23:55 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-27 01:36 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-27 01:48 ` Re: add AVX2 support to simd.h Tom Lane <tgl@sss.pgh.pa.us>
2024-03-27 18:57 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-03-27 21:10 ` Re: add AVX2 support to simd.h Tom Lane <tgl@sss.pgh.pa.us>
2024-03-27 21:37 ` Re: add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
@ 2024-03-28 01:32 ` Nathan Bossart <nathandbossart@gmail.com>
0 siblings, 0 replies; 48+ messages in thread
From: Nathan Bossart @ 2024-03-28 01:32 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: John Naylor <johncnaylorls@gmail.com>; Ants Aasma <ants@cybertec.at>; pgsql-hackers
On Wed, Mar 27, 2024 at 04:37:35PM -0500, Nathan Bossart wrote:
> On Wed, Mar 27, 2024 at 05:10:13PM -0400, Tom Lane wrote:
>> LGTM otherwise, and I like the fact that the #if structure
>> gets a lot less messy.
>
> Thanks for reviewing. I've attached a v2 that I intend to commit when I
> get a chance.
Committed.
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.com
^ permalink raw reply [nested|flat] 48+ messages in thread
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
@ 2024-01-09 14:03 ` Peter Eisentraut <peter@eisentraut.org>
2024-01-09 15:25 ` Re: add AVX2 support to simd.h Ants Aasma <ants.aasma@cybertec.at>
2 siblings, 1 reply; 48+ messages in thread
From: Peter Eisentraut @ 2024-01-09 14:03 UTC (permalink / raw)
To: Nathan Bossart <nathandbossart@gmail.com>; Ants Aasma <ants@cybertec.at>; +Cc: John Naylor <johncnaylorls@gmail.com>; pgsql-hackers
On 29.11.23 18:15, Nathan Bossart wrote:
> Using the same benchmark as we did for the SSE2 linear searches in
> XidInMVCCSnapshot() (commit 37a6e5d) [1] [2], I see the following:
>
> writers sse2 avx2 %
> 256 1195 1188 -1
> 512 928 1054 +14
> 1024 633 716 +13
> 2048 332 420 +27
> 4096 162 203 +25
> 8192 162 182 +12
AFAICT, your patch merely provides an alternative AVX2 implementation
for where currently SSE2 is supported, but it doesn't provide any new
API calls or new functionality. One might naively expect that these are
just two different ways to call the underlying primitives in the CPU, so
these performance improvements are surprising to me. Or do the CPUs
actually have completely separate machinery for SSE2 and AVX2, and just
using the latter to do the same thing is faster?
^ permalink raw reply [nested|flat] 48+ messages in thread
* Re: add AVX2 support to simd.h
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 14:03 ` Re: add AVX2 support to simd.h Peter Eisentraut <peter@eisentraut.org>
@ 2024-01-09 15:25 ` Ants Aasma <ants.aasma@cybertec.at>
0 siblings, 0 replies; 48+ messages in thread
From: Ants Aasma @ 2024-01-09 15:25 UTC (permalink / raw)
To: Peter Eisentraut <peter@eisentraut.org>; +Cc: Nathan Bossart <nathandbossart@gmail.com>; John Naylor <johncnaylorls@gmail.com>; pgsql-hackers
On Tue, 9 Jan 2024 at 16:03, Peter Eisentraut <peter@eisentraut.org> wrote:
> On 29.11.23 18:15, Nathan Bossart wrote:
> > Using the same benchmark as we did for the SSE2 linear searches in
> > XidInMVCCSnapshot() (commit 37a6e5d) [1] [2], I see the following:
> >
> > writers sse2 avx2 %
> > 256 1195 1188 -1
> > 512 928 1054 +14
> > 1024 633 716 +13
> > 2048 332 420 +27
> > 4096 162 203 +25
> > 8192 162 182 +12
>
> AFAICT, your patch merely provides an alternative AVX2 implementation
> for where currently SSE2 is supported, but it doesn't provide any new
> API calls or new functionality. One might naively expect that these are
> just two different ways to call the underlying primitives in the CPU, so
> these performance improvements are surprising to me. Or do the CPUs
> actually have completely separate machinery for SSE2 and AVX2, and just
> using the latter to do the same thing is faster?
The AVX2 implementation uses a wider vector register. On most current
processors the throughput of the instructions in question is the same
on 256bit vectors as on 128bit vectors. Basically, the chip has AVX2
worth of machinery and using SSE2 leaves half of it unused. Notable
exceptions are efficiency cores on recent Intel desktop CPUs and AMD
CPUs pre Zen 2 where AVX2 instructions are internally split up into
two 128bit wide instructions.
For AVX512 the picture is much more complicated. Some instructions run
at half rate, some at full rate, but not on all ALU ports, some
instructions cause aggressive clock rate reduction on some
microarchitectures. AVX-512 adds mask registers and masked vector
instructions that enable quite a bit simpler code in many cases.
Interestingly I have seen Clang make quite effective use of these
masked instructions even when using AVX2 intrinsics, but targeting an
AVX-512 capable platform.
The vector width independent approach used in the patch is nice for
simple cases by not needing a separate implementation for each vector
width. However for more complicated cases where "horizontal"
operations are needed it's going to be much less useful. But these
cases can easily just drop down to using intrinsics directly.
^ permalink raw reply [nested|flat] 48+ messages in thread
end of thread, other threads:[~2024-03-28 01:32 UTC | newest]
Thread overview: 48+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2023-11-29 17:15 add AVX2 support to simd.h Nathan Bossart <nathandbossart@gmail.com>
2024-01-01 12:12 ` John Naylor <johncnaylorls@gmail.com>
2024-01-02 16:11 ` Nathan Bossart <nathandbossart@gmail.com>
2024-01-02 17:50 ` Tom Lane <tgl@sss.pgh.pa.us>
2024-01-02 22:00 ` Nathan Bossart <nathandbossart@gmail.com>
2024-01-03 14:13 ` John Naylor <johncnaylorls@gmail.com>
2024-01-03 15:29 ` Nathan Bossart <nathandbossart@gmail.com>
2024-01-05 02:03 ` John Naylor <johncnaylorls@gmail.com>
2024-01-05 17:04 ` Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 09:03 ` John Naylor <johncnaylorls@gmail.com>
2024-01-04 17:48 ` Nathan Bossart <nathandbossart@gmail.com>
2024-01-08 07:01 ` John Naylor <johncnaylorls@gmail.com>
2024-01-08 17:37 ` Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 02:20 ` John Naylor <johncnaylorls@gmail.com>
2024-01-09 16:20 ` Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 21:21 ` Ants Aasma <ants.aasma@cybertec.at>
2024-01-10 02:06 ` John Naylor <johncnaylorls@gmail.com>
2024-03-15 17:41 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-15 19:40 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-17 02:47 ` John Naylor <johncnaylorls@gmail.com>
2024-03-19 02:03 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 03:03 ` John Naylor <johncnaylorls@gmail.com>
2024-03-19 03:16 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-19 09:53 ` John Naylor <johncnaylorls@gmail.com>
2024-03-19 16:30 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 06:57 ` John Naylor <johncnaylorls@gmail.com>
2024-03-20 14:31 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-20 19:55 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-21 04:30 ` John Naylor <johncnaylorls@gmail.com>
2024-03-21 17:09 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-21 17:12 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-21 18:38 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-24 20:53 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-24 22:09 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-25 03:03 ` John Naylor <johncnaylorls@gmail.com>
2024-03-25 15:21 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-25 21:37 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-26 19:09 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-26 23:28 ` Tom Lane <tgl@sss.pgh.pa.us>
2024-03-26 23:55 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-27 01:36 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-27 01:48 ` Tom Lane <tgl@sss.pgh.pa.us>
2024-03-27 18:57 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-27 21:10 ` Tom Lane <tgl@sss.pgh.pa.us>
2024-03-27 21:37 ` Nathan Bossart <nathandbossart@gmail.com>
2024-03-28 01:32 ` Nathan Bossart <nathandbossart@gmail.com>
2024-01-09 14:03 ` Peter Eisentraut <peter@eisentraut.org>
2024-01-09 15:25 ` Ants Aasma <ants.aasma@cybertec.at>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox