From 6338a5397e9103609ba9e842e2390ffab4b9aa5c Mon Sep 17 00:00:00 2001
From: Kyotaro Horiguchi <horikyota.ntt@gmail.com>
Date: Fri, 15 Oct 2021 14:09:30 +0900
Subject: [PATCH v2 4/5] Get rid of two O(1) behavior in procarray.

GetVirtualXIDsDelayingChkpt had O(N^2) behavior and
SignalVirtualTransaction had O(N) behavior.  Since the old BackendId
has gone they can be reduced to O(N) and O(1) respectively.
---
 src/backend/storage/ipc/procarray.c | 74 ++++++++++-------------------
 1 file changed, 26 insertions(+), 48 deletions(-)

diff --git a/src/backend/storage/ipc/procarray.c b/src/backend/storage/ipc/procarray.c
index 100c0dae8c..70ce58b3fc 100644
--- a/src/backend/storage/ipc/procarray.c
+++ b/src/backend/storage/ipc/procarray.c
@@ -3079,41 +3079,24 @@ GetVirtualXIDsDelayingChkpt(int *nvxids)
  *
  * This is used with the results of GetVirtualXIDsDelayingChkpt to see if any
  * of the specified VXIDs are still in critical sections of code.
- *
- * Note: this is O(N^2) in the number of vxacts that are/were delaying, but
- * those numbers should be small enough for it not to be a problem.
  */
 bool
 HaveVirtualXIDsDelayingChkpt(VirtualTransactionId *vxids, int nvxids)
 {
 	bool		result = false;
-	ProcArrayStruct *arrayP = procArray;
 	int			index;
 
 	LWLockAcquire(ProcArrayLock, LW_SHARED);
 
-	for (index = 0; index < arrayP->numProcs; index++)
+	for (index = 0; index < nvxids; index++)
 	{
-		int			pgprocno = arrayP->pgprocnos[index];
-		PGPROC	   *proc = &allProcs[pgprocno];
-		VirtualTransactionId vxid;
+		VirtualTransactionId *vxid = &vxids[index];
+		PGPROC				 *proc = &allProcs[vxid->backendId];
 
-		GET_VXID_FROM_PGPROC(vxid, *proc);
-
-		if (proc->delayChkpt && VirtualTransactionIdIsValid(vxid))
+		if (proc->delayChkpt && vxid->localTransactionId == proc->lxid)
 		{
-			int			i;
-
-			for (i = 0; i < nvxids; i++)
-			{
-				if (VirtualTransactionIdEquals(vxid, vxids[i]))
-				{
-					result = true;
-					break;
-				}
-			}
-			if (result)
-				break;
+			result = true;
+			break;
 		}
 	}
 
@@ -3429,35 +3412,30 @@ pid_t
 SignalVirtualTransaction(VirtualTransactionId vxid, ProcSignalReason sigmode,
 						 bool conflictPending)
 {
-	ProcArrayStruct *arrayP = procArray;
-	int			index;
-	pid_t		pid = 0;
+	PGPROC	   *proc;
+	pid_t		pid;
+	VirtualTransactionId procvxid PG_USED_FOR_ASSERTS_ONLY;
 
 	LWLockAcquire(ProcArrayLock, LW_SHARED);
 
-	for (index = 0; index < arrayP->numProcs; index++)
+	proc = &allProcs[vxid.backendId];
+
+#ifdef USE_ASSERT_CHECKING
+	GET_VXID_FROM_PGPROC(procvxid, *proc);
+	Assert (procvxid.backendId == vxid.backendId &&
+			procvxid.localTransactionId == vxid.localTransactionId);
+#endif
+
+	pid = proc->pid;
+	proc->recoveryConflictPending = conflictPending;
+
+	if (pid != 0)
 	{
-		int			pgprocno = arrayP->pgprocnos[index];
-		PGPROC	   *proc = &allProcs[pgprocno];
-		VirtualTransactionId procvxid;
-
-		GET_VXID_FROM_PGPROC(procvxid, *proc);
-
-		if (procvxid.backendId == vxid.backendId &&
-			procvxid.localTransactionId == vxid.localTransactionId)
-		{
-			proc->recoveryConflictPending = conflictPending;
-			pid = proc->pid;
-			if (pid != 0)
-			{
-				/*
-				 * Kill the pid if it's still here. If not, that's what we
-				 * wanted so ignore any errors.
-				 */
-				(void) SendProcSignal(pid, sigmode, proc->pgprocno);
-			}
-			break;
-		}
+		/*
+		 * Kill the pid if it's still here. If not, that's what we
+		 * wanted so ignore any errors.
+		 */
+		(void) SendProcSignal(pid, sigmode, proc->pgprocno);
 	}
 
 	LWLockRelease(ProcArrayLock);
-- 
2.27.0