From: Antonin Houska <ah@cybertec.at>
To: Nathan Bossart <nathandbossart@gmail.com>
cc: pgsql-hackers@lists.postgresql.org
Subject: Re: Missed opportunity for bsearch() in
 TransactionIdIsCurrentTransactionId()?
In-reply-to: <Zo7aA2m35vGR56MN@nathan>
References: <36977.1720623613@antos> <Zo7aA2m35vGR56MN@nathan>
Comments: In-reply-to Nathan Bossart <nathandbossart@gmail.com>
   message dated "Wed, 10 Jul 2024 13:59:15 -0500."
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="=-=-="
Date: Fri, 12 Jul 2024 12:01:11 +0200
Message-ID: <47366.1720778471@antos>
Archived-At: <https://www.postgresql.org/message-id/47366.1720778471%40antos>
Precedence: bulk

--=-=-=
Content-Type: text/plain

Nathan Bossart <nathandbossart@gmail.com> wrote:

> On Wed, Jul 10, 2024 at 05:00:13PM +0200, Antonin Houska wrote:
> > I don't quite understand why TransactionIdIsCurrentTransactionId() implements
> > binary search in ParallelCurrentXids "from scratch" instead of using
> > bsearch().
> 
> I believe there are a number of open-coded binary searches in the tree.

Not sure if there are many, but I could find some:

* TransactionIdIsCurrentTransactionId()

* RelationHasSysCache()

* pg_dump.c:getRoleName()

> My concern with switching them to bsearch() would be the performance impact
> of using a function pointer for the comparisons.  Perhaps we could add a
> couple of inlined binary search implementations for common types to replace
> many of the open-coded ones.

bsearch() appears to be used widely, but o.k., I don't insist on using it to
replace the existing open-coded searches.

What actually bothers me more than the absence of bsearch() is that
TransactionIdIsCurrentTransactionId() implements the binary search from
scratch. Even w/o bsearch(), it can still call TransactionIdInArray(). I ran
into the problem when working on [1], which adds one more XID array.

Does the attached patch seem worth being applied separately, or at all?

[1] https://www.postgresql.org/message-id/82651.1720540558%40antos

-- 
Antonin Houska
Web: https://www.cybertec-postgresql.com


--=-=-=
Content-Type: text/x-diff
Content-Disposition: attachment;
 filename=0001-Refactor-search-in-a-sorted-XID-array.patch

From 470a66d0086bd8b656f88c86aec9f5861a763df7 Mon Sep 17 00:00:00 2001
From: Antonin Houska <ah@cybertec.at>
Date: Fri, 12 Jul 2024 10:06:32 +0200
Subject: [PATCH] Refactor search in a sorted XID array.

First, avoid duplicate definition of TransactionIdInArray().

Second, prefer open-coded implementation to bsearch(): it's probably cheaper
to compare two XIDs directly than via a bsearch() callback.
---
 src/backend/access/heap/heapam_visibility.c   | 10 ------
 src/backend/access/transam/xact.c             | 29 ++---------------
 .../replication/logical/reorderbuffer.c       | 11 -------
 src/include/access/transam.h                  | 32 +++++++++++++++++++
 4 files changed, 35 insertions(+), 47 deletions(-)

diff --git a/src/backend/access/heap/heapam_visibility.c b/src/backend/access/heap/heapam_visibility.c
index 9243feed01..d4653a28db 100644
--- a/src/backend/access/heap/heapam_visibility.c
+++ b/src/backend/access/heap/heapam_visibility.c
@@ -1559,16 +1559,6 @@ HeapTupleHeaderIsOnlyLocked(HeapTupleHeader tuple)
 	return true;
 }
 
-/*
- * check whether the transaction id 'xid' is in the pre-sorted array 'xip'.
- */
-static bool
-TransactionIdInArray(TransactionId xid, TransactionId *xip, Size num)
-{
-	return num > 0 &&
-		bsearch(&xid, xip, num, sizeof(TransactionId), xidComparator) != NULL;
-}
-
 /*
  * See the comments for HeapTupleSatisfiesMVCC for the semantics this function
  * obeys.
diff --git a/src/backend/access/transam/xact.c b/src/backend/access/transam/xact.c
index d119ab909d..795c04a879 100644
--- a/src/backend/access/transam/xact.c
+++ b/src/backend/access/transam/xact.c
@@ -961,33 +961,10 @@ TransactionIdIsCurrentTransactionId(TransactionId xid)
 
 	/*
 	 * In parallel workers, the XIDs we must consider as current are stored in
-	 * ParallelCurrentXids rather than the transaction-state stack.  Note that
-	 * the XIDs in this array are sorted numerically rather than according to
-	 * transactionIdPrecedes order.
+	 * ParallelCurrentXids rather than the transaction-state stack.
 	 */
-	if (nParallelCurrentXids > 0)
-	{
-		int			low,
-					high;
-
-		low = 0;
-		high = nParallelCurrentXids - 1;
-		while (low <= high)
-		{
-			int			middle;
-			TransactionId probe;
-
-			middle = low + (high - low) / 2;
-			probe = ParallelCurrentXids[middle];
-			if (probe == xid)
-				return true;
-			else if (probe < xid)
-				low = middle + 1;
-			else
-				high = middle - 1;
-		}
-		return false;
-	}
+	if (TransactionIdInArray(xid, ParallelCurrentXids, nParallelCurrentXids))
+		return true;
 
 	/*
 	 * We will return true for the Xid of the current subtransaction, any of
diff --git a/src/backend/replication/logical/reorderbuffer.c b/src/backend/replication/logical/reorderbuffer.c
index 00a8327e77..bd3edd0b47 100644
--- a/src/backend/replication/logical/reorderbuffer.c
+++ b/src/backend/replication/logical/reorderbuffer.c
@@ -5136,17 +5136,6 @@ ApplyLogicalMappingFile(HTAB *tuplecid_data, Oid relid, const char *fname)
 				 errmsg("could not close file \"%s\": %m", path)));
 }
 
-
-/*
- * Check whether the TransactionId 'xid' is in the pre-sorted array 'xip'.
- */
-static bool
-TransactionIdInArray(TransactionId xid, TransactionId *xip, Size num)
-{
-	return bsearch(&xid, xip, num,
-				   sizeof(TransactionId), xidComparator) != NULL;
-}
-
 /*
  * list_sort() comparator for sorting RewriteMappingFiles in LSN order.
  */
diff --git a/src/include/access/transam.h b/src/include/access/transam.h
index 28a2d287fd..78739b2490 100644
--- a/src/include/access/transam.h
+++ b/src/include/access/transam.h
@@ -370,6 +370,38 @@ FullTransactionIdNewer(FullTransactionId a, FullTransactionId b)
 	return b;
 }
 
+/*
+ * Check whether the transaction id 'xid' is in the pre-sorted array 'xip'.
+ *
+ * Note that the XIDs in this array must be sorted numerically rather than
+ * according to TransactionIdPrecedes order.
+ */
+static inline bool
+TransactionIdInArray(TransactionId xid, TransactionId *xip, Size num)
+{
+	int			low, high;
+
+	if (num == 0)
+		return false;
+
+	low = 0;
+	high = num - 1;
+	while (low <= high)
+	{
+		int			middle;
+		TransactionId probe;
+
+		middle = low + (high - low) / 2;
+		probe = xip[middle];
+		if (probe == xid)
+			return true;
+		else if (probe < xid)
+			low = middle + 1;
+		else
+			high = middle - 1;
+	}
+	return false;
+}
 #endif							/* FRONTEND */
 
 #endif							/* TRANSAM_H */
-- 
2.45.2


--=-=-=--