From: Nathan Bossart <nathandbossart@gmail.com>
To: John Naylor <john.naylor@enterprisedb.com>
Cc: Andres Freund <andres@anarazel.de>
Cc: John Naylor <jcnaylor@gmail.com>
Cc: pgsql-hackers <pgsql-hackers@postgresql.org>
Subject: Re: optimize lookups in snapshot [sub]xip arrays
Date: Tue, 2 Aug 2022 15:13:01 -0700
Message-ID: <20220802221301.GA742739@nathanxps13> (raw)
In-Reply-To: <20220730053811.GA417958@nathanxps13>
References: <20220713170950.GA3116318@nathanxps13>
<20220715200857.nm2gc4weixwlwbnx@awork3.anarazel.de>
<20220717035957.GA3631071@nathanxps13>
<20220725190419.GA4095199@nathanxps13>
<20220726181906.7l4ulzjdblnanclm@alap3.anarazel.de>
<20220728213423.GA408719@nathanxps13>
<CAFBsxsE14aHKR6gr+rEeFJKaBq8sgXctonwpWw3G7twaePHkVA@mail.gmail.com>
<20220730053811.GA417958@nathanxps13>
On Fri, Jul 29, 2022 at 10:38:11PM -0700, Nathan Bossart wrote:
> On Sat, Jul 30, 2022 at 12:02:02PM +0700, John Naylor wrote:
>> I'll be the first to say it's not committable and needs some thought. Since
>> there are several recently proposed patches that take advantage of SSE2, it
>> seems time for me to open a new thread and get that prerequisite settled.
>> I'll do that next week.
>
> Awesome. I will help test and review.
While this prerequisite is worked out [0], here is a new patch set. I've
added an 0002 in which I've made use of the proposed SSE2 linear search
function in several other areas. I haven't done any additional performance
analysis, and it's likely I'm missing some eligible code locations, but at
the very least, this demonstrates the reusability of the new function.
[0] https://postgr.es/m/CAFBsxsE2G_H_5Wbw%2BNOPm70-BK4xxKf86-mRzY%3DL2sLoQqM%2B-Q%40mail.gmail.com
--
Nathan Bossart
Amazon Web Services: https://aws.amazon.comAttachments:
[text/x-diff] v4-0001-Use-SSE2-intrinsics-for-XidInMVCCSnapshot.patch (5.5K, ../20220802221301.GA742739@nathanxps13/2-v4-0001-Use-SSE2-intrinsics-for-XidInMVCCSnapshot.patch)
download | inline diff:
From a2b2ab3777f689775c2e731822aefe2ab500e8ee Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathandbossart@gmail.com>
Date: Thu, 28 Jul 2022 12:15:47 -0700
Subject: [PATCH v4 1/2] Use SSE2 intrinsics for XidInMVCCSnapshot().
This optimizes the linear searches through the [sub]xip arrays when
possible, which should improve performance significantly when the
arrays are large.
---
src/backend/utils/time/snapmgr.c | 28 +++---------
src/include/c.h | 8 ++++
src/include/utils/linearsearch.h | 78 ++++++++++++++++++++++++++++++++
3 files changed, 93 insertions(+), 21 deletions(-)
create mode 100644 src/include/utils/linearsearch.h
diff --git a/src/backend/utils/time/snapmgr.c b/src/backend/utils/time/snapmgr.cindex 5bc2a15160..834c8867d4 100644--- a/src/backend/utils/time/snapmgr.c+++ b/src/backend/utils/time/snapmgr.c@@ -63,6 +63,7 @@
#include "storage/sinvaladt.h"
#include "storage/spin.h"
#include "utils/builtins.h"
+#include "utils/linearsearch.h"
#include "utils/memutils.h"
#include "utils/old_snapshot.h"
#include "utils/rel.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_linearsearch_uint32(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_linearsearch_uint32(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_linearsearch_uint32(xid, snapshot->subxip, snapshot->subxcnt))+ return true;
}
return false;
diff --git a/src/include/c.h b/src/include/c.hindex d35405f191..2c1a47bc28 100644--- a/src/include/c.h+++ b/src/include/c.h@@ -371,6 +371,14 @@ typedef void (*pg_funcptr_t) (void);
#endif
#endif
+/*+ * Are SSE2 intrinsics available?+ */+#if (defined(__x86_64__) || defined(_M_AMD64))+#include <emmintrin.h>+#define USE_SSE2+#endif+
/* ----------------------------------------------------------------
* Section 2: bool, true, false
diff --git a/src/include/utils/linearsearch.h b/src/include/utils/linearsearch.hnew file mode 100644index 0000000000..65b0092a65--- /dev/null+++ b/src/include/utils/linearsearch.h@@ -0,0 +1,78 @@+/*-------------------------------------------------------------------------+ *+ * linearsearch.h+ * Optimized linear search routines.+ *+ * Copyright (c) 2022, PostgreSQL Global Development Group+ *+ *+ * IDENTIFICATION+ * src/include/utils/linearsearch.h+ *+ *-------------------------------------------------------------------------+ */+#ifndef LINEARSEARCH_H+#define LINEARSEARCH_H++#include "c.h"++#ifdef USE_SSE2+#include "port/pg_bitutils.h"+#endif++/*+ * pg_linearsearch_uint32+ *+ * Returns the address of the first element in 'base' that equals 'key', or+ * NULL if no match is found.+ */+#ifdef USE_SSE2+pg_attribute_no_sanitize_alignment()+#endif+static inline uint32 *+pg_linearsearch_uint32(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 its = nelem & ~0xF; /* round down to multiple of 16 */++ for (; i < its; 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 an integer */+ __m128i tmp1 = _mm_packs_epi32(result1, result2);+ __m128i tmp2 = _mm_packs_epi32(result3, result4);+ __m128i tmp3 = _mm_packs_epi16(tmp1, tmp2);+ uint32 result = _mm_movemask_epi8(tmp3);++ /* if found, return a pointer to the matching element */+ if (result != 0)+ return &base[i + pg_rightmost_one_pos32(result)];+ }+#endif++ /* Process the remaining elements the slow way. */+ for (; i < nelem; i++)+ {+ if (key == base[i])+ return &base[i];+ }++ return NULL;+}++#endif /* LINEARSEARCH_H */--
2.25.1
[text/x-diff] v4-0002-SIMD-ify-various-linear-searches-through-arrays-o.patch (10.6K, ../20220802221301.GA742739@nathanxps13/3-v4-0002-SIMD-ify-various-linear-searches-through-arrays-o.patch)
download | inline diff:
From 571f831fc1d55660afb1531c17572847ec57b446 Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathandbossart@gmail.com>
Date: Tue, 2 Aug 2022 14:56:53 -0700
Subject: [PATCH v4 2/2] SIMD-ify various linear searches through arrays of
integers.
---
src/backend/access/transam/slru.c | 15 ++++++---------
src/backend/commands/extension.c | 25 +++++++------------------
src/backend/commands/tsearchcmds.c | 13 +++++--------
src/backend/executor/execParallel.c | 23 +++++++++++++++--------
src/backend/parser/parse_coerce.c | 11 ++++++-----
src/backend/storage/ipc/procarray.c | 8 +++-----
src/backend/storage/lmgr/predicate.c | 9 +++------
src/backend/utils/adt/lockfuncs.c | 27 ++++++++++++---------------
8 files changed, 57 insertions(+), 74 deletions(-)
diff --git a/src/backend/access/transam/slru.c b/src/backend/access/transam/slru.cindex b65cb49d7f..84b0487f4d 100644--- a/src/backend/access/transam/slru.c+++ b/src/backend/access/transam/slru.c@@ -59,6 +59,7 @@
#include "pgstat.h"
#include "storage/fd.h"
#include "storage/shmem.h"
+#include "utils/linearsearch.h"
#define SlruFileName(ctl, path, seg) \
snprintf(path, MAXPGPATH, "%s/%04X", (ctl)->Dir, seg)
@@ -812,16 +813,12 @@ SlruPhysicalWritePage(SlruCtl ctl, int pageno, int slotno, SlruWriteAll fdata)
*/
if (fdata)
{
- int i;+ int *match;- for (i = 0; i < fdata->num_files; i++)- {- if (fdata->segno[i] == segno)- {- fd = fdata->fd[i];- break;- }- }+ if ((match = (int *) pg_linearsearch_uint32(segno,+ (uint32 *) fdata->segno,+ fdata->num_files)))+ fd = fdata->fd[match - fdata->segno];
}
if (fd < 0)
diff --git a/src/backend/commands/extension.c b/src/backend/commands/extension.cindex 6b6720c690..06e045c0e0 100644--- a/src/backend/commands/extension.c+++ b/src/backend/commands/extension.c@@ -60,6 +60,7 @@
#include "utils/acl.h"
#include "utils/builtins.h"
#include "utils/fmgroids.h"
+#include "utils/linearsearch.h"
#include "utils/lsyscache.h"
#include "utils/memutils.h"
#include "utils/rel.h"
@@ -2446,7 +2447,7 @@ pg_extension_config_dump(PG_FUNCTION_ARGS)
{
/* Modify or extend existing extconfig array */
Oid *arrayData;
- int i;+ Oid *match;
a = DatumGetArrayTypeP(arrayDatum);
@@ -2461,14 +2462,8 @@ pg_extension_config_dump(PG_FUNCTION_ARGS)
arrayIndex = arrayLength + 1; /* set up to add after end */
- for (i = 0; i < arrayLength; i++)- {- if (arrayData[i] == tableoid)- {- arrayIndex = i + 1; /* replace this element instead */- break;- }- }+ if ((match = pg_linearsearch_uint32(tableoid, arrayData, arrayLength)))+ arrayIndex = (match - arrayData) + 1; /* replace this element instead */
a = array_set(a, 1, &arrayIndex,
elementDatum,
@@ -2582,7 +2577,7 @@ extension_config_remove(Oid extensionoid, Oid tableoid)
else
{
Oid *arrayData;
- int i;+ Oid *match;
a = DatumGetArrayTypeP(arrayDatum);
@@ -2597,14 +2592,8 @@ extension_config_remove(Oid extensionoid, Oid tableoid)
arrayIndex = -1; /* flag for no deletion needed */
- for (i = 0; i < arrayLength; i++)- {- if (arrayData[i] == tableoid)- {- arrayIndex = i; /* index to remove */- break;- }- }+ if ((match = pg_linearsearch_uint32(tableoid, arrayData, arrayLength)))+ arrayIndex = match - arrayData; /* index to remove */
}
/* If tableoid is not in extconfig, nothing to do */
diff --git a/src/backend/commands/tsearchcmds.c b/src/backend/commands/tsearchcmds.cindex 4cc4e3c00f..6ae41bdd56 100644--- a/src/backend/commands/tsearchcmds.c+++ b/src/backend/commands/tsearchcmds.c@@ -44,6 +44,7 @@
#include "tsearch/ts_utils.h"
#include "utils/builtins.h"
#include "utils/fmgroids.h"
+#include "utils/linearsearch.h"
#include "utils/lsyscache.h"
#include "utils/rel.h"
#include "utils/syscache.h"
@@ -1302,14 +1303,10 @@ MakeConfigurationMapping(AlterTSConfigurationStmt *stmt,
{
bool tokmatch = false;
- for (j = 0; j < ntoken; j++)- {- if (cfgmap->maptokentype == tokens[j])- {- tokmatch = true;- break;- }- }+ if (pg_linearsearch_uint32(cfgmap->maptokentype,+ (uint32 *) tokens, ntoken))+ tokmatch = true;+
if (!tokmatch)
continue;
}
diff --git a/src/backend/executor/execParallel.c b/src/backend/executor/execParallel.cindex f1fd7f7e8b..2c9cbe6d52 100644--- a/src/backend/executor/execParallel.c+++ b/src/backend/executor/execParallel.c@@ -47,6 +47,7 @@
#include "tcop/tcopprot.h"
#include "utils/datum.h"
#include "utils/dsa.h"
+#include "utils/linearsearch.h"
#include "utils/lsyscache.h"
#include "utils/memutils.h"
#include "utils/snapmgr.h"
@@ -1022,12 +1023,15 @@ ExecParallelRetrieveInstrumentation(PlanState *planstate,
int ibytes;
int plan_node_id = planstate->plan->plan_node_id;
MemoryContext oldcontext;
+ int *match;
/* Find the instrumentation for this node. */
- for (i = 0; i < instrumentation->num_plan_nodes; ++i)- if (instrumentation->plan_node_id[i] == plan_node_id)- break;- if (i >= instrumentation->num_plan_nodes)+ match = (int *) pg_linearsearch_uint32(plan_node_id,+ (uint32 *) instrumentation->plan_node_id,+ instrumentation->num_plan_nodes);+ if (match)+ i = match - instrumentation->plan_node_id;+ else
elog(ERROR, "plan node %d not found", plan_node_id);
/* Accumulate the statistics from all workers. */
@@ -1265,6 +1269,7 @@ ExecParallelReportInstrumentation(PlanState *planstate,
int i;
int plan_node_id = planstate->plan->plan_node_id;
Instrumentation *instrument;
+ int *match;
InstrEndLoop(planstate->instrument);
@@ -1274,10 +1279,12 @@ ExecParallelReportInstrumentation(PlanState *planstate,
* we're pushing down sufficiently large plan trees. For now, do it the
* slow, dumb way.
*/
- for (i = 0; i < instrumentation->num_plan_nodes; ++i)- if (instrumentation->plan_node_id[i] == plan_node_id)- break;- if (i >= instrumentation->num_plan_nodes)+ match = (int *) pg_linearsearch_uint32(plan_node_id,+ (uint32 *) instrumentation->plan_node_id,+ instrumentation->num_plan_nodes);+ if (match)+ i = match - instrumentation->plan_node_id;+ else
elog(ERROR, "plan node %d not found", plan_node_id);
/*
diff --git a/src/backend/parser/parse_coerce.c b/src/backend/parser/parse_coerce.cindex c4e958e4aa..fd9291a4a4 100644--- a/src/backend/parser/parse_coerce.c+++ b/src/backend/parser/parse_coerce.c@@ -27,6 +27,7 @@
#include "utils/builtins.h"
#include "utils/datum.h" /* needed for datumIsEqual() */
#include "utils/fmgroids.h"
+#include "utils/linearsearch.h"
#include "utils/lsyscache.h"
#include "utils/syscache.h"
#include "utils/typcache.h"
@@ -2920,11 +2921,11 @@ check_valid_internal_signature(Oid ret_type,
{
if (ret_type == INTERNALOID)
{
- for (int i = 0; i < nargs; i++)- {- if (declared_arg_types[i] == ret_type)- return NULL; /* OK */- }+ if (pg_linearsearch_uint32(ret_type,+ unconstify(Oid *, declared_arg_types),+ nargs))+ return NULL; /* OK */+
return pstrdup(_("A result of type internal requires at least one input of type internal."));
}
else
diff --git a/src/backend/storage/ipc/procarray.c b/src/backend/storage/ipc/procarray.cindex 0555b02a8d..157dab61d1 100644--- a/src/backend/storage/ipc/procarray.c+++ b/src/backend/storage/ipc/procarray.c@@ -63,6 +63,7 @@
#include "storage/spin.h"
#include "utils/acl.h"
#include "utils/builtins.h"
+#include "utils/linearsearch.h"
#include "utils/rel.h"
#include "utils/snapmgr.h"
@@ -1588,11 +1589,8 @@ TransactionIdIsInProgress(TransactionId xid)
Assert(TransactionIdIsValid(topxid));
if (!TransactionIdEquals(topxid, xid))
{
- for (int i = 0; i < nxids; i++)- {- if (TransactionIdEquals(xids[i], topxid))- return true;- }+ if (pg_linearsearch_uint32(topxid, xids, nxids))+ return true;
}
cachedXidIsNotInProgress = xid;
diff --git a/src/backend/storage/lmgr/predicate.c b/src/backend/storage/lmgr/predicate.cindex 5136da6ea3..11d3412650 100644--- a/src/backend/storage/lmgr/predicate.c+++ b/src/backend/storage/lmgr/predicate.c@@ -207,6 +207,7 @@
#include "storage/predicate_internals.h"
#include "storage/proc.h"
#include "storage/procarray.h"
+#include "utils/linearsearch.h"
#include "utils/rel.h"
#include "utils/snapmgr.h"
@@ -4065,7 +4066,6 @@ static bool
XidIsConcurrent(TransactionId xid)
{
Snapshot snap;
- uint32 i;
Assert(TransactionIdIsValid(xid));
Assert(!TransactionIdEquals(xid, GetTopTransactionIdIfAny()));
@@ -4078,11 +4078,8 @@ XidIsConcurrent(TransactionId xid)
if (TransactionIdFollowsOrEquals(xid, snap->xmax))
return true;
- for (i = 0; i < snap->xcnt; i++)- {- if (xid == snap->xip[i])- return true;- }+ if (pg_linearsearch_uint32(xid, snap->xip, snap->xcnt))+ return true;
return false;
}
diff --git a/src/backend/utils/adt/lockfuncs.c b/src/backend/utils/adt/lockfuncs.cindex f9b324efec..48cb0c87bb 100644--- a/src/backend/utils/adt/lockfuncs.c+++ b/src/backend/utils/adt/lockfuncs.c@@ -20,6 +20,7 @@
#include "storage/predicate_internals.h"
#include "utils/array.h"
#include "utils/builtins.h"
+#include "utils/linearsearch.h"
/*
@@ -506,17 +507,15 @@ pg_blocking_pids(PG_FUNCTION_ARGS)
{
/* conflict in lock requests; who's in front in wait queue? */
bool ahead = false;
- int k;- for (k = 0; k < bproc->num_waiters; k++)+ if (pg_linearsearch_uint32(instance->pid,+ (uint32 *) preceding_waiters,+ bproc->num_waiters))
{
- if (preceding_waiters[k] == instance->pid)- {- /* soft block: this entry is ahead of blocked proc */- ahead = true;- break;- }+ /* soft block: this entry is ahead of blocked proc */+ ahead = true;
}
+
if (!ahead)
continue; /* not blocked by this entry */
}
@@ -598,8 +597,7 @@ pg_isolation_test_session_is_blocked(PG_FUNCTION_ARGS)
int num_interesting_pids;
int num_blocking_pids;
int dummy;
- int i,- j;+ int i;
/* Validate the passed-in array */
Assert(ARR_ELEMTYPE(interesting_pids_a) == INT4OID);
@@ -632,11 +630,10 @@ pg_isolation_test_session_is_blocked(PG_FUNCTION_ARGS)
* for a match.
*/
for (i = 0; i < num_blocking_pids; i++)
- for (j = 0; j < num_interesting_pids; j++)- {- if (blocking_pids[i] == interesting_pids[j])- PG_RETURN_BOOL(true);- }+ if (pg_linearsearch_uint32(blocking_pids[i],+ (uint32 *) interesting_pids,+ num_interesting_pids))+ PG_RETURN_BOOL(true);
/*
* Check if blocked_pid is waiting for a safe snapshot. We could in
--
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, john.naylor@enterprisedb.com, andres@anarazel.de, jcnaylor@gmail.com
Subject: Re: optimize lookups in snapshot [sub]xip arrays
In-Reply-To: <20220802221301.GA742739@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