Simplified a bit and more commented patch version is in attach.
Algorithm were switched to linear probing, it makes code simpler and
clearer.
Flag usages were toggled: now it indicates that hash table were built,
it also makes code clearer.
XidInXip and some other functions got comments.
--
With regards,
Sokolov Yura aka funny_falcon
Postgres Professional: https://postgrespro.ru
The Russian Postgres Company
From 5851f01de6b793be5e682c67db8db339667be92d Mon Sep 17 00:00:00 2001
From: Sokolov Yura <funny.fal...@postgrespro.ru>
Date: Mon, 10 Jul 2017 12:34:48 +0000
Subject: [PATCH] Make hash table for xip in XidInMVCCSnapshot
When lot of concurrent transactions attempts to update single
row, then linear scan through running list in XidInMVCCSnapshot
became noticebale bottleneck.
With this change, hash table is built on first search of xid in
snapshot->xip and snapshot->subxip arrays.
If size of array is smaller than 60, then linear scan is still
used, cause there is no much benefits from building hash then.
(at least on Intel Xeon).
---
src/backend/storage/ipc/procarray.c | 67 +++++++++++++++++++++------
src/backend/utils/time/snapmgr.c | 24 ++++++----
src/backend/utils/time/tqual.c | 91 ++++++++++++++++++++++++++++---------
src/include/utils/snapshot.h | 11 +++++
4 files changed, 151 insertions(+), 42 deletions(-)
diff --git a/src/backend/storage/ipc/procarray.c b/src/backend/storage/ipc/procarray.c
index a7e8cf2d43..2c7e065342 100644
--- a/src/backend/storage/ipc/procarray.c
+++ b/src/backend/storage/ipc/procarray.c
@@ -1469,6 +1469,54 @@ GetMaxSnapshotSubxidCount(void)
}
/*
+ * ExtendXipSizeForHash - calculate xip array size with space for hash table.
+ *
+ * Hash table should be at least twice larger than array to not depend on
+ * cleverness of algorithm.
+ *
+ * But if xipcnt < SnapshotMinHash, then no need in hash-table at all.
+ */
+int
+ExtendXipSizeForHash(int xipcnt, uint8* plog)
+{
+ int size;
+ uint8 log = 0;
+
+ size = xipcnt;
+ if (xipcnt >= SnapshotMinHash)
+ {
+ log = 1;
+ while (xipcnt) {
+ log++;
+ xipcnt >>= 1;
+ }
+ size += 1<<log;
+ }
+ *plog = log;
+ return size;
+}
+
+/*
+ * AllocateXip - allocate xip array, extended for hash part if needed.
+ *
+ * Hash part will be used in tqual.c in XidInMVCCSnapshot (XidInXip).
+ */
+static TransactionId *
+AllocateXip(int max, uint8* plog)
+{
+ int size;
+ TransactionId *xip;
+
+ size = ExtendXipSizeForHash(max, plog);
+ xip = (TransactionId *) malloc(size * sizeof(TransactionId));
+ if (xip == NULL)
+ ereport(ERROR,
+ (errcode(ERRCODE_OUT_OF_MEMORY),
+ errmsg("out of memory")));
+ return xip;
+}
+
+/*
* GetSnapshotData -- returns information about running transactions.
*
* The returned snapshot includes xmin (lowest still-running xact ID),
@@ -1537,19 +1585,10 @@ GetSnapshotData(Snapshot snapshot)
* First call for this snapshot. Snapshot is same size whether or not
* we are in recovery, see later comments.
*/
- snapshot->xip = (TransactionId *)
- malloc(GetMaxSnapshotXidCount() * sizeof(TransactionId));
- if (snapshot->xip == NULL)
- ereport(ERROR,
- (errcode(ERRCODE_OUT_OF_MEMORY),
- errmsg("out of memory")));
- Assert(snapshot->subxip == NULL);
- snapshot->subxip = (TransactionId *)
- malloc(GetMaxSnapshotSubxidCount() * sizeof(TransactionId));
- if (snapshot->subxip == NULL)
- ereport(ERROR,
- (errcode(ERRCODE_OUT_OF_MEMORY),
- errmsg("out of memory")));
+ snapshot->xip = AllocateXip(GetMaxSnapshotXidCount(),
+ &snapshot->xhlog);
+ snapshot->subxip = AllocateXip(GetMaxSnapshotSubxidCount(),
+ &snapshot->subxhlog);
}
/*
@@ -1757,6 +1796,8 @@ GetSnapshotData(Snapshot snapshot)
snapshot->active_count = 0;
snapshot->regd_count = 0;
snapshot->copied = false;
+ snapshot->xhlog &= ~SnapshotHashBuilt;
+ snapshot->subxhlog &= ~SnapshotHashBuilt;
if (old_snapshot_threshold < 0)
{
diff --git a/src/backend/utils/time/snapmgr.c b/src/backend/utils/time/snapmgr.c
index 08a08c8e8f..7c3fe7563e 100644
--- a/src/backend/utils/time/snapmgr.c
+++ b/src/backend/utils/time/snapmgr.c
@@ -662,13 +662,16 @@ CopySnapshot(Snapshot snapshot)
Snapshot newsnap;
Size subxipoff;
Size size;
+ int xcnt, subxcnt;
+ uint8 xhlog, subxhlog;
Assert(snapshot != InvalidSnapshot);
+ xcnt = ExtendXipSizeForHash(snapshot->xcnt, &xhlog);
+ subxcnt = ExtendXipSizeForHash(snapshot->subxcnt, &subxhlog);
/* We allocate any XID arrays needed in the same palloc block. */
- size = subxipoff = sizeof(SnapshotData) +
- snapshot->xcnt * sizeof(TransactionId);
- if (snapshot->subxcnt > 0)
+ size = subxipoff = sizeof(SnapshotData) + xcnt * sizeof(TransactionId);
+ if (subxcnt > 0)
size += snapshot->subxcnt * sizeof(TransactionId);
newsnap = (Snapshot) MemoryContextAlloc(TopTransactionContext, size);
@@ -677,6 +680,8 @@ CopySnapshot(Snapshot snapshot)
newsnap->regd_count = 0;
newsnap->active_count = 0;
newsnap->copied = true;
+ newsnap->xhlog = xhlog;
+ newsnap->subxhlog = subxhlog;
/* setup XID array */
if (snapshot->xcnt > 0)
@@ -2124,16 +2129,18 @@ RestoreSnapshot(char *start_address)
Size size;
Snapshot snapshot;
TransactionId *serialized_xids;
+ int xcnt, subxcnt;
+ uint8 xhlog, subxhlog;
memcpy(&serialized_snapshot, start_address,
sizeof(SerializedSnapshotData));
serialized_xids = (TransactionId *)
(start_address + sizeof(SerializedSnapshotData));
+ xcnt = ExtendXipSizeForHash(serialized_snapshot.xcnt, &xhlog);
+ subxcnt = ExtendXipSizeForHash(serialized_snapshot.subxcnt, &subxhlog);
/* We allocate any XID arrays needed in the same palloc block. */
- size = sizeof(SnapshotData)
- + serialized_snapshot.xcnt * sizeof(TransactionId)
- + serialized_snapshot.subxcnt * sizeof(TransactionId);
+ size = sizeof(SnapshotData) + (xcnt + subxcnt) * sizeof(TransactionId);
/* Copy all required fields */
snapshot = (Snapshot) MemoryContextAlloc(TopTransactionContext, size);
@@ -2142,8 +2149,10 @@ RestoreSnapshot(char *start_address)
snapshot->xmax = serialized_snapshot.xmax;
snapshot->xip = NULL;
snapshot->xcnt = serialized_snapshot.xcnt;
+ snapshot->xhlog = xhlog;
snapshot->subxip = NULL;
snapshot->subxcnt = serialized_snapshot.subxcnt;
+ snapshot->subxhlog = subxhlog;
snapshot->suboverflowed = serialized_snapshot.suboverflowed;
snapshot->takenDuringRecovery = serialized_snapshot.takenDuringRecovery;
snapshot->curcid = serialized_snapshot.curcid;
@@ -2161,8 +2170,7 @@ RestoreSnapshot(char *start_address)
/* Copy SubXIDs, if present. */
if (serialized_snapshot.subxcnt > 0)
{
- snapshot->subxip = ((TransactionId *) (snapshot + 1)) +
- serialized_snapshot.xcnt;
+ snapshot->subxip = ((TransactionId *) (snapshot + 1)) + xcnt;
memcpy(snapshot->subxip, serialized_xids + serialized_snapshot.xcnt,
serialized_snapshot.subxcnt * sizeof(TransactionId));
}
diff --git a/src/backend/utils/time/tqual.c b/src/backend/utils/time/tqual.c
index f9da9e17f5..a5e7d427b4 100644
--- a/src/backend/utils/time/tqual.c
+++ b/src/backend/utils/time/tqual.c
@@ -1451,6 +1451,69 @@ HeapTupleIsSurelyDead(HeapTuple htup, TransactionId OldestXmin)
}
/*
+ * XidInXip searches xid in xip array.
+ *
+ * If xcnt is smaller than SnapshotMinHash (60), or *xhlog is zero, then simple
+ * linear scan of xip array used. Looks like there is no benifit in hash table
+ * for small xip array.
+ *
+ * If xhlog points to non-zero byte, then space for hash table is allocated
+ * after xip array, and logarithm of its size is in xhlog.
+ * Most significant xhlog bit should be set if hash table is already built.
+ *
+ * Hash table is built using simple linear probing. It allows keep both
+ * insertion and lookup loop small.
+ */
+static bool
+XidInXip(TransactionId xid, TransactionId *xip, uint32 xcnt, uint8 *xhlog)
+{
+ TransactionId *xiphash;
+ uint32 i, pos, mask;
+ int found = 0;
+
+ if (!TransactionIdIsNormal(xid))
+ return false;
+
+ if (xcnt < SnapshotMinHash || *xhlog == 0)
+ {
+ /* full scan for small snapshots and if xiphash is not allocated */
+ for (i = 0; i < xcnt; i++)
+ if (TransactionIdEquals(xid, xip[i]))
+ return true;
+ return false;
+ }
+
+ mask = ((uint32)1 << (*xhlog & ~SnapshotHashBuilt)) - 1;
+ xiphash = xip + xcnt;
+
+ if (*xhlog & SnapshotHashBuilt)
+ {
+ /* Hash table already built. Do lookup */
+ pos = xid & mask;
+ while (xiphash[pos] != InvalidTransactionId)
+ {
+ if (TransactionIdEquals(xiphash[pos], xid))
+ return true;
+ pos = (pos + 1) & mask;
+ }
+ return false;
+ }
+
+ /* Build hash table. */
+ *xhlog |= SnapshotHashBuilt;
+ memset(xiphash, 0, (mask+1) * sizeof(TransactionId));
+ for (i = 0; i < xcnt; i++)
+ {
+ found |= TransactionIdEquals(xip[i], xid);
+ pos = xip[i] & mask;
+ while (xiphash[pos] != InvalidTransactionId)
+ pos = (pos + 1) & mask;
+ xiphash[pos] = xip[i];
+ }
+ return found != 0;
+}
+
+/*
* XidInMVCCSnapshot
* Is the given XID still-in-progress according to the snapshot?
*
@@ -1463,8 +1526,6 @@ HeapTupleIsSurelyDead(HeapTuple htup, TransactionId OldestXmin)
static 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
@@ -1496,13 +1557,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, &snapshot->subxhlog))
+ return true;
/* not there, fall through to search xip[] */
}
@@ -1523,16 +1579,12 @@ 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, &snapshot->xhlog))
+ 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
@@ -1562,11 +1614,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, &snapshot->subxhlog))
+ return true;
}
return false;
diff --git a/src/include/utils/snapshot.h b/src/include/utils/snapshot.h
index 074cc81864..c2c77f046c 100644
--- a/src/include/utils/snapshot.h
+++ b/src/include/utils/snapshot.h
@@ -23,6 +23,15 @@
typedef struct SnapshotData *Snapshot;
#define InvalidSnapshot ((Snapshot) NULL)
+/*
+ * Big running list will be converted into hash table on demand.
+ * SnapshotMinHash is threshold between "linear scan" and "hashtable on demand".
+ * SnapshotHashBuilt indicates that hash table was already built.
+ */
+#define SnapshotMinHash (60)
+#define SnapshotHashBuilt ((uint8)0x80)
+/* Calculate size to hold both array and hash table (if needed) */
+int ExtendXipSizeForHash(int xipcnt, uint8* plog);
/*
* We use SnapshotData structures to represent both "regular" (MVCC)
@@ -76,6 +85,7 @@ typedef struct SnapshotData
*/
TransactionId *xip;
uint32 xcnt; /* # of xact ids in xip[] */
+ uint8 xhlog; /* log2 of allocated xip hash part */
/*
* For non-historic MVCC snapshots, this contains subxact IDs that are in
@@ -92,6 +102,7 @@ typedef struct SnapshotData
bool takenDuringRecovery; /* recovery-shaped snapshot? */
bool copied; /* false if it's a static snapshot */
+ uint8 subxhlog; /* log2 of allocated subxip hash part */
CommandId curcid; /* in my xact, CID < curcid are visible */
--
2.11.0
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
