From: Antonin Houska <ah@cybertec.at>
To: pgsql-hackers@lists.postgresql.org
Subject: Missed opportunity for bsearch() in TransactionIdIsCurrentTransactionId()?
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="=-=-="
Date: Wed, 10 Jul 2024 17:00:13 +0200
Message-ID: <36977.1720623613@antos>
Archived-At: <https://www.postgresql.org/message-id/36977.1720623613%40antos>
Precedence: bulk

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

I don't quite understand why TransactionIdIsCurrentTransactionId() implements
binary search in ParallelCurrentXids "from scratch" instead of using
bsearch().

If I read the code correctly, the contents of the ParallelCurrentXids is
composed in SerializeTransactionState(), which uses xidComparator:

	qsort(workspace, nxids, sizeof(TransactionId), xidComparator);

so it should be o.k. to use bsearch(..., xidComparator).

For example, ReorderBufferCopySnap() also uses xidComparator to sort the
'subxip' array, and HeapTupleSatisfiesHistoricMVCC() then uses
TransactionIdInArray() (which is effectively bsearch(..., xidComparator)) to
search for particular XID in the array.

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


--=-=-=
Content-Type: text/x-diff
Content-Disposition: attachment;
 filename=use_bsearch_for_ParallelCurrentXids.diff

diff --git a/src/backend/access/transam/xact.c b/src/backend/access/transam/xact.c
index d119ab909d..8540e70e70 100644
--- a/src/backend/access/transam/xact.c
+++ b/src/backend/access/transam/xact.c
@@ -965,29 +965,9 @@ TransactionIdIsCurrentTransactionId(TransactionId xid)
 	 * the XIDs in this array are sorted numerically rather than according to
 	 * transactionIdPrecedes order.
 	 */
-	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 (bsearch(&xid, ParallelCurrentXids, nParallelCurrentXids,
+				sizeof(TransactionId), xidComparator))
+		return true;
 
 	/*
 	 * We will return true for the Xid of the current subtransaction, any of

--=-=-=--