Date: Thu, 1 Sep 2022 11:51:53 -0700
From: Nathan Bossart <nathandbossart@gmail.com>
To: pgsql-hackers@postgresql.org
Subject: make additional use of optimized linear search routines
Message-ID: <20220901185153.GA783106@nathanxps13>
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="HlL+5n6rz5pIUxbD"
Content-Disposition: inline
Archived-At: 
 <https://www.postgresql.org/message-id/20220901185153.GA783106%40nathanxps13>
Precedence: bulk


--HlL+5n6rz5pIUxbD
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline

Hi hackers,

Now that we have some optimized linear search routines [0], I thought I'd
quickly check whether we could use them elsewhere.  To start, I took
another look at a previously posted patch [1] and noticed two potentially
useful applications of pg_lfind32().  The attached patches replace the
open-coded linear searches with calls to pg_lfind32().  I haven't done any
performance analysis with these patches yet, and the overall impact might
be limited, but it seemed like low-hanging fruit.

I'm hoping to spend a bit more time looking for additional applications of
the pg_lfind*() suite of functions (and anywhere else where SIMD might be
useful, really).  If you have any ideas in mind, I'm all ears.

[0] https://git.postgresql.org/gitweb/?p=postgresql.git;a=blob;f=src/include/port/pg_lfind.h
[1] https://postgr.es/m/20220802221301.GA742739%40nathanxps13

-- 
Nathan Bossart
Amazon Web Services: https://aws.amazon.com

--HlL+5n6rz5pIUxbD
Content-Type: text/x-diff; charset=us-ascii
Content-Disposition: attachment;
	filename="v1-0001-use-optimized-linear-search-in-TransactionIdIsInP.patch"

From 1ea31af477d66557fdbc5f83a5bdacadd6159a9d Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathandbossart@gmail.com>
Date: Thu, 1 Sep 2022 11:23:15 -0700
Subject: [PATCH v1 1/2] use optimized linear search in
 TransactionIdIsInProgress

---
 src/backend/storage/ipc/procarray.c | 12 ++++--------
 1 file changed, 4 insertions(+), 8 deletions(-)

diff --git a/src/backend/storage/ipc/procarray.c b/src/backend/storage/ipc/procarray.c
index 0555b02a8d..a8b7b65518 100644
--- a/src/backend/storage/ipc/procarray.c
+++ b/src/backend/storage/ipc/procarray.c
@@ -58,6 +58,7 @@
 #include "commands/dbcommands.h"
 #include "miscadmin.h"
 #include "pgstat.h"
+#include "port/pg_lfind.h"
 #include "storage/proc.h"
 #include "storage/procarray.h"
 #include "storage/spin.h"
@@ -1586,14 +1587,9 @@ TransactionIdIsInProgress(TransactionId xid)
 	 */
 	topxid = SubTransGetTopmostTransaction(xid);
 	Assert(TransactionIdIsValid(topxid));
-	if (!TransactionIdEquals(topxid, xid))
-	{
-		for (int i = 0; i < nxids; i++)
-		{
-			if (TransactionIdEquals(xids[i], topxid))
-				return true;
-		}
-	}
+	if (!TransactionIdEquals(topxid, xid) &&
+		pg_lfind32(topxid, xids, nxids))
+		return true;
 
 	cachedXidIsNotInProgress = xid;
 	return false;
-- 
2.25.1


--HlL+5n6rz5pIUxbD
Content-Type: text/x-diff; charset=us-ascii
Content-Disposition: attachment;
	filename="v1-0002-use-optimized-linear-search-in-XidIsConcurrent.patch"

From d82f9b1a6e3f41e434bb5826d277269b891c9882 Mon Sep 17 00:00:00 2001
From: Nathan Bossart <nathandbossart@gmail.com>
Date: Thu, 1 Sep 2022 11:29:38 -0700
Subject: [PATCH v1 2/2] use optimized linear search in XidIsConcurrent

---
 src/backend/storage/lmgr/predicate.c | 10 ++--------
 1 file changed, 2 insertions(+), 8 deletions(-)

diff --git a/src/backend/storage/lmgr/predicate.c b/src/backend/storage/lmgr/predicate.c
index 5136da6ea3..f287ddfa73 100644
--- a/src/backend/storage/lmgr/predicate.c
+++ b/src/backend/storage/lmgr/predicate.c
@@ -202,6 +202,7 @@
 #include "access/xlog.h"
 #include "miscadmin.h"
 #include "pgstat.h"
+#include "port/pg_lfind.h"
 #include "storage/bufmgr.h"
 #include "storage/predicate.h"
 #include "storage/predicate_internals.h"
@@ -4065,7 +4066,6 @@ static bool
 XidIsConcurrent(TransactionId xid)
 {
 	Snapshot	snap;
-	uint32		i;
 
 	Assert(TransactionIdIsValid(xid));
 	Assert(!TransactionIdEquals(xid, GetTopTransactionIdIfAny()));
@@ -4078,13 +4078,7 @@ XidIsConcurrent(TransactionId xid)
 	if (TransactionIdFollowsOrEquals(xid, snap->xmax))
 		return true;
 
-	for (i = 0; i < snap->xcnt; i++)
-	{
-		if (xid == snap->xip[i])
-			return true;
-	}
-
-	return false;
+	return pg_lfind32(xid, snap->xip, snap->xcnt);
 }
 
 bool
-- 
2.25.1


--HlL+5n6rz5pIUxbD--