From: Nathan Bossart <nathandbossart@gmail.com>
To: Andres Freund <andres@anarazel.de>
Cc: John Naylor <john.naylor@enterprisedb.com>
Cc: John Naylor <jcnaylor@gmail.com>
Cc: pgsql-hackers <pgsql-hackers@postgresql.org>
Subject: Re: optimize lookups in snapshot [sub]xip arrays
Date: Sat, 6 Aug 2022 14:25:22 -0700
Message-ID: <20220806212522.GA1221353@nathanxps13> (raw)
In-Reply-To: <20220806181326.GA1216305@nathanxps13>
References: <20220802225539.nm7bgkwvkpzgib5x@awork3.anarazel.de>
<20220802234357.GA802740@nathanxps13>
<20220803180658.3ofq6v34wxchg4wc@awork3.anarazel.de>
<20220803202540.GA1088968@nathanxps13>
<CAFBsxsH51bBtyr3rf13x7YMNkFfuzZPSQxxbfUepBj8m4=ck=Q@mail.gmail.com>
<20220804221551.GA1090071@nathanxps13>
<CAFBsxsGmNefB-LAo8hNXLDAwWN0vHXc6H2A+NfFUQrj=rn50DQ@mail.gmail.com>
<20220805202510.GA1208450@nathanxps13>
<20220805220434.6h2aa7eww5rxird6@awork3.anarazel.de>
<20220806181326.GA1216305@nathanxps13>
On Sat, Aug 06, 2022 at 11:13:26AM -0700, Nathan Bossart wrote:
> On Fri, Aug 05, 2022 at 03:04:34PM -0700, Andres Freund wrote:
>> But mainly I'd expect to find a difference if the SIMD code were optimized a
>> further on the basis of not needing to return the offset. E.g. by
>> replacing _mm_packs_epi32 with _mm_or_si128, that's cheaper.
>
> I haven't been able to find a significant difference between the two. If
> anything, the _mm_packs_epi* approach actually seems to be slightly faster
> in some cases. For something marginally more concrete, I compared the two
> in perf-top and saw the following for the relevant instructions:
Nevermind, I'm wrong. When compiled with -O2, it uses more than just the
xmm0 and xmm1 registers, and the _mm_or_si128 approach consistently shows a
speedup of slightly more than 5%. Patches attached.
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.comAttachments:
[text/x-diff] v8-0001-Introduce-optimized-routine-for-linear-searches-t.patch (3.0K, ../20220806212522.GA1221353@nathanxps13/2-v8-0001-Introduce-optimized-routine-for-linear-searches-t.patch)
download | inline diff:
From bdfab91f1f2fa647d1b8a888dd6f8ad61ab80523 Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathandbossart@gmail.com>
Date: Wed, 3 Aug 2022 09:49:04 -0700
Subject: [PATCH v8 1/2] Introduce optimized routine for linear searches
through an array of integers.
If SSE2 is available, this function uses it to speed up the search. Otherwise,
it uses a simple 'for' loop. This is a prerequisite for a follow-up commit
that will use this function to optimize [sub]xip lookups in
XidInMVCCSnapshot(), but it can be used anywhere that might benefit from such
an optimization.
It might be worthwhile to add an ARM-specific code path to this function in the
future.
Author: Nathan Bossart
Reviewed by: Andres Freund, John Naylor
Discussion: https://postgr.es/m/20220713170950.GA3116318%40nathanxps13
---
src/include/port/pg_lfind.h | 70 +++++++++++++++++++++++++++++++++++++
1 file changed, 70 insertions(+)
create mode 100644 src/include/port/pg_lfind.h
diff --git a/src/include/port/pg_lfind.h b/src/include/port/pg_lfind.hnew file mode 100644index 0000000000..8a212cc06b--- /dev/null+++ b/src/include/port/pg_lfind.h@@ -0,0 +1,70 @@+/*-------------------------------------------------------------------------+ *+ * pg_lfind.h+ * Optimized linear search routines.+ *+ * Copyright (c) 2022, PostgreSQL Global Development Group+ *+ *+ * IDENTIFICATION+ * src/port/pg_lfind.h+ *+ *-------------------------------------------------------------------------+ */+#ifndef PG_LFIND_H+#define PG_LFIND_H++#include "port/simd.h"++/*+ * pg_lfind32+ *+ * Returns true if there is an element in 'base' that equals 'key'. Otherwise,+ * returns false.+ */+static inline bool+pg_lfind32(uint32 key, uint32 *base, uint32 nelem)+{+ uint32 i = 0;++ /* If possible, use SSE2 intrinsics to speed up the search. */+#ifdef USE_SSE2+ __m128i keys = _mm_set1_epi32(key); /* load 4 copies of key */+ uint32 iterations = nelem & ~0xF; /* round down to multiple of 16 */++ for (; i < iterations; i += 16)+ {+ /* load the next 16 values into __m128i variables */+ __m128i vals1 = _mm_loadu_si128((__m128i *) &base[i]);+ __m128i vals2 = _mm_loadu_si128((__m128i *) &base[i + 4]);+ __m128i vals3 = _mm_loadu_si128((__m128i *) &base[i + 8]);+ __m128i vals4 = _mm_loadu_si128((__m128i *) &base[i + 12]);++ /* perform the comparisons */+ __m128i result1 = _mm_cmpeq_epi32(keys, vals1);+ __m128i result2 = _mm_cmpeq_epi32(keys, vals2);+ __m128i result3 = _mm_cmpeq_epi32(keys, vals3);+ __m128i result4 = _mm_cmpeq_epi32(keys, vals4);++ /* shrink the results into a single variable */+ __m128i tmp1 = _mm_or_si128(result1, result2);+ __m128i tmp2 = _mm_or_si128(result3, result4);+ __m128i result = _mm_or_si128(tmp1, tmp2);++ /* see if there was a match */+ if (_mm_movemask_epi8(result) != 0)+ return true;+ }+#endif++ /* Process the remaining elements the slow way. */+ for (; i < nelem; i++)+ {+ if (key == base[i])+ return true;+ }++ return false;+}++#endif /* PG_LFIND_H */--
2.25.1
[text/x-diff] v8-0002-Optimize-linear-searches-in-XidInMVCCSnapshot.patch (2.8K, ../20220806212522.GA1221353@nathanxps13/3-v8-0002-Optimize-linear-searches-in-XidInMVCCSnapshot.patch)
download | inline diff:
From 826cc190c9ad76558adc41f1cbee76fc47e78c15 Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathandbossart@gmail.com>
Date: Wed, 3 Aug 2022 09:59:28 -0700
Subject: [PATCH v8 2/2] Optimize linear searches in XidInMVCCSnapshot().
This change makes use of the recently-introduced optimized linear search
routine to speed up searches through the [sub]xip arrays when possible, which
should improve performance significantly when the arrays are large.
Author: Nathan Bossart
Reviewed by: Andres Freund, John Naylor
Discussion: https://postgr.es/m/20220713170950.GA3116318%40nathanxps13
---
src/backend/utils/time/snapmgr.c | 28 +++++++---------------------
1 file changed, 7 insertions(+), 21 deletions(-)
diff --git a/src/backend/utils/time/snapmgr.c b/src/backend/utils/time/snapmgr.cindex 5bc2a15160..9b504c9745 100644--- a/src/backend/utils/time/snapmgr.c+++ b/src/backend/utils/time/snapmgr.c@@ -56,6 +56,7 @@
#include "datatype/timestamp.h"
#include "lib/pairingheap.h"
#include "miscadmin.h"
+#include "port/pg_lfind.h"
#include "storage/predicate.h"
#include "storage/proc.h"
#include "storage/procarray.h"
@@ -2284,8 +2285,6 @@ RestoreTransactionSnapshot(Snapshot snapshot, void *source_pgproc)
bool
XidInMVCCSnapshot(TransactionId xid, Snapshot snapshot)
{
- uint32 i;-
/*
* Make a quick range check to eliminate most XIDs without looking at the
* xip arrays. Note that this is OK even if we convert a subxact XID to
@@ -2317,13 +2316,8 @@ XidInMVCCSnapshot(TransactionId xid, Snapshot snapshot)
if (!snapshot->suboverflowed)
{
/* we have full data, so search subxip */
- int32 j;-- for (j = 0; j < snapshot->subxcnt; j++)- {- if (TransactionIdEquals(xid, snapshot->subxip[j]))- return true;- }+ if (pg_lfind32(xid, snapshot->subxip, snapshot->subxcnt))+ return true;
/* not there, fall through to search xip[] */
}
@@ -2344,16 +2338,11 @@ XidInMVCCSnapshot(TransactionId xid, Snapshot snapshot)
return false;
}
- for (i = 0; i < snapshot->xcnt; i++)- {- if (TransactionIdEquals(xid, snapshot->xip[i]))- return true;- }+ if (pg_lfind32(xid, snapshot->xip, snapshot->xcnt))+ return true;
}
else
{
- int32 j;-
/*
* In recovery we store all xids in the subxact array because it is by
* far the bigger array, and we mostly don't know which xids are
@@ -2383,11 +2372,8 @@ XidInMVCCSnapshot(TransactionId xid, Snapshot snapshot)
* indeterminate xid. We don't know whether it's top level or subxact
* but it doesn't matter. If it's present, the xid is visible.
*/
- for (j = 0; j < snapshot->subxcnt; j++)- {- if (TransactionIdEquals(xid, snapshot->subxip[j]))- return true;- }+ if (pg_lfind32(xid, snapshot->subxip, snapshot->subxcnt))+ return true;
}
return false;
--
2.25.1
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: nathandbossart@gmail.com, andres@anarazel.de, john.naylor@enterprisedb.com, jcnaylor@gmail.com
Subject: Re: optimize lookups in snapshot [sub]xip arrays
In-Reply-To: <20220806212522.GA1221353@nathanxps13>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
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