Date: Sat, 16 Jul 2022 20:59:57 -0700
From: Nathan Bossart <nathandbossart@gmail.com>
To: Andres Freund <andres@anarazel.de>
Cc: John Naylor <jcnaylor@gmail.com>, pgsql-hackers@postgresql.org
Subject: Re: optimize lookups in snapshot [sub]xip arrays
Message-ID: <20220717035957.GA3631071@nathanxps13>
References: <20220713170950.GA3116318@nathanxps13>
 <20220715200857.nm2gc4weixwlwbnx@awork3.anarazel.de>
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="y0ulUmNC+osPPQO6"
Content-Disposition: inline
In-Reply-To: <20220715200857.nm2gc4weixwlwbnx@awork3.anarazel.de>
Archived-At: 
 <https://www.postgresql.org/message-id/20220717035957.GA3631071%40nathanxps13>
Precedence: bulk


--y0ulUmNC+osPPQO6
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline

Hi Andres,

Thanks for taking a look.

On Fri, Jul 15, 2022 at 01:08:57PM -0700, Andres Freund wrote:
> Hm. Are there any contexts where we'd not want the potential for failing due
> to OOM?

I'm not sure about this one.

> I wonder if we additionally / alternatively could use a faster method of
> searching the array linearly, e.g. using SIMD.

I looked into using SIMD.  The patch is attached, but it is only intended
for benchmarking purposes and isn't anywhere close to being worth serious
review.  There may be a simpler/better way to implement the linear search,
but this seemed to work well.  Overall, SIMD provided a decent improvement.
I had to increase the number of writers quite a bit in order to demonstrate
where the hash tables began winning.  Here are the numbers:

    writers head simd hash
    256     663  632  694
    512     530  618  637
    768     489  544  573
    1024    364  508  562
    2048    185  306  485
    4096    146  197  441

While it is unsurprising that the hash tables perform the best, there are a
couple of advantages to SIMD that might make that approach worth
considering.  For one, there's really no overhead (i.e., you don't need to
sort the array or build a hash table), so we can avoid picking an arbitrary
threshold and just have one code path.  Also, a SIMD implementation for a
linear search through an array of integers could likely be easily reused
elsewhere.

> Another thing that might be worth looking into is to sort the xip/subxip
> arrays into a binary-search optimized layout. That'd make the binary search
> faster, wouldn't require additional memory (a boolean indicating whether
> sorted somewhere, I guess), and would easily persist across copies of the
> snapshot.

I spent some time looking into this, but I haven't attempted to implement
it.  IIUC the most difficult part of this is sorting the array in place to
the special layout.

>> These hash tables are regarded as ephemeral; they only live in
>> process-local memory and are never rewritten, copied, or
>> serialized.
> 
> What does rewriting refer to here?

I mean that a hash table created for one snapshot will not be cleared and
reused for another.

> Not convinced that's the right idea in case of copying. I think we often end
> up copying snapshots frequently, and building & allocating the hashed xids
> separately every time seems not great.

Right.  My concern with reusing the hash tables is that we'd need to
allocate much more space that would go largely unused in many cases.

>> +	snapshot->xiph = NULL;
>> +	snapshot->subxiph = NULL;
> 
> Do we need separate hashes for these? ISTM that if we're overflowed then we
> don't need ->subxip[h], and if not, then the action for an xid being in ->xip
> and ->subxiph is the same?

Do you mean that we can combine these into one hash table?  That might
work.

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

--y0ulUmNC+osPPQO6
Content-Type: text/x-diff; charset=us-ascii
Content-Disposition: attachment; filename="xip_search_simd.patch"

diff --git a/src/backend/utils/time/snapmgr.c b/src/backend/utils/time/snapmgr.c
index 5bc2a15160..25d1a3564c 100644
--- a/src/backend/utils/time/snapmgr.c
+++ b/src/backend/utils/time/snapmgr.c
@@ -45,6 +45,7 @@
  */
 #include "postgres.h"
 
+#include <nmmintrin.h>
 #include <sys/stat.h>
 #include <unistd.h>
 
@@ -2271,6 +2272,40 @@ RestoreTransactionSnapshot(Snapshot snapshot, void *source_pgproc)
 	SetTransactionSnapshot(snapshot, NULL, InvalidPid, source_pgproc);
 }
 
+static inline bool
+XidInXip(TransactionId xid, TransactionId *xip, uint32 len)
+{
+	__m128i xids = _mm_set1_epi32(xid);
+	uint32  its = len & ~15;  /* round down to nearest multiple of 16 */
+	uint32	i;
+
+	for (i = 0; i < its; i += 16)
+	{
+		__m128i xips1 = _mm_loadu_si128((__m128i *) &xip[i]);
+		__m128i xips2 = _mm_loadu_si128((__m128i *) &xip[i + 4]);
+		__m128i xips3 = _mm_loadu_si128((__m128i *) &xip[i + 8]);
+		__m128i xips4 = _mm_loadu_si128((__m128i *) &xip[i + 12]);
+		__m128i result1 = _mm_cmpeq_epi32(xids, xips1);
+		__m128i result2 = _mm_cmpeq_epi32(xids, xips2);
+		__m128i result3 = _mm_cmpeq_epi32(xids, xips3);
+		__m128i result4 = _mm_cmpeq_epi32(xids, xips4);
+		__m128i tmp1 = _mm_packs_epi32(result1, result2);
+		__m128i tmp2 = _mm_packs_epi32(result3, result4);
+		__m128i result = _mm_packs_epi16(tmp1, tmp2);
+
+		if (_mm_movemask_epi8(result) != 0)
+			return true;
+	}
+
+	while (i < len)
+	{
+		if (TransactionIdEquals(xid, xip[i++]))
+			return true;
+	}
+
+	return false;
+}
+
 /*
  * XidInMVCCSnapshot
  *		Is the given XID still-in-progress according to the snapshot?
@@ -2284,8 +2319,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 +2350,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 (XidInXip(xid, snapshot->subxip, snapshot->subxcnt))
+				return true;
 
 			/* not there, fall through to search xip[] */
 		}
@@ -2344,16 +2372,11 @@ XidInMVCCSnapshot(TransactionId xid, Snapshot snapshot)
 				return false;
 		}
 
-		for (i = 0; i < snapshot->xcnt; i++)
-		{
-			if (TransactionIdEquals(xid, snapshot->xip[i]))
-				return true;
-		}
+		if (XidInXip(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 +2406,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 (XidInXip(xid, snapshot->subxip, snapshot->subxcnt))
+			return true;
 	}
 
 	return false;

--y0ulUmNC+osPPQO6--