> Um, that's not too surprising, because they're exactly the same patch?
Wrong diff. Here is correct one.
Everything else is right. I just re-checked :)
step2a:
number of transactions actually processed: 16325
latency average: 49.008 ms
latency stddev: 8.780 ms
tps = 163.182594 (including connections establishing)
tps = 163.189818 (excluding connections establishing)
step2b-fixed:
number of transactions actually processed: 16374
latency average: 48.867 ms
latency stddev: 8.223 ms
tps = 163.658269 (including connections establishing)
tps = 163.666318 (excluding connections establishing)
diff --git a/src/backend/access/hash/hashfunc.c b/src/backend/access/hash/hashfunc.c
index dabaf5a..39f3115 100644
--- a/src/backend/access/hash/hashfunc.c
+++ b/src/backend/access/hash/hashfunc.c
@@ -297,6 +297,9 @@ hashvarlena(PG_FUNCTION_ARGS)
* of 2. There is no need to do mod a prime (mod is sooo slow!).
* If you need less than 32 bits, use a bitmask.
*
+ * This procedure never fails. Its important. Some code notably ResourceOwner
+ * relies on this.
+ *
* Note: we could easily change this function to return a 64-bit hash value
* by using the final values of both b and c. b is perhaps a little less
* well mixed than c, however.
diff --git a/src/backend/utils/resowner/resowner.c b/src/backend/utils/resowner/resowner.c
index 69217b5..02319ef 100644
--- a/src/backend/utils/resowner/resowner.c
+++ b/src/backend/utils/resowner/resowner.c
@@ -37,17 +37,35 @@
* which should be called before corresponding ResourceOwnerRemember* calls
* (see below). Internally each type of resource is stored in separate
* ResourceArray.
+ *
+ * There are two major reasons for using ResourceArray instead of, say,
+ * regular C arrays.
+ *
+ * Firstly we would like to prevent code duplication. For instance
+ * ResourceArray provides generic Remember/Forget/Enlarge procedures, so
+ * corresponding ResourceOwner* procedures are just a typesafe wrappers for
+ * these procedures.
+ *
+ * Secondly ResourceArray must be more efficient than regular C array.
+ * Current implementation in general could be considered a hash table. It has
+ * O(1) complexity of both Remember and Forget procedures.
*/
typedef struct ResourceArray
{
Datum *itemsarr; /* buffer for storing values */
+ Datum invalidval; /* value that is considered invalid */
uint32 capacity; /* capacity of array */
uint32 nitems; /* how many items is stored in items array */
+ uint32 maxitems; /* precalculated RESARRAY_MAX_ITEMS(capacity) */
+ uint32 lastidx; /* index of last item returned by GetAny */
} ResourceArray;
/*
* This number is used as initial size of resource array. If given number of
* items is not enough, we double array size and reallocate memory.
+ *
+ * Should be power of two since we use (arrsize - 1) as mask for hash value.
+ *
*/
#define RESARRAY_INIT_SIZE 16
@@ -64,14 +82,27 @@ typedef struct ResourceArray
#define DatumGetBuffer(datum)((Buffer)(datum))
/*
+ * How many items could be stored in a resource array of given capacity. If
+ * this number is reached we need to resize an array to prevent hash collisions.
+ *
+ * This computation actually costs only two additions and one binary shift.
+ */
+#define RESARRAY_MAX_ITEMS(capacity) ((capacity)*3/4)
+
+/*
* Initialize ResourceArray
*/
static void
-ResourceArrayInit(ResourceArray * resarr)
+ResourceArrayInit(ResourceArray * resarr, Datum invalidval)
{
Assert(resarr->itemsarr == NULL);
Assert(resarr->capacity == 0);
Assert(resarr->nitems == 0);
+ Assert(resarr->maxitems == 0);
+ Assert(resarr->invalidval == 0);
+ Assert(resarr->lastidx == 0);
+
+ resarr->invalidval = invalidval;
}
/*
@@ -82,11 +113,32 @@ ResourceArrayInit(ResourceArray * resarr)
static void
ResourceArrayAdd(ResourceArray * resarr, Datum data)
{
+ Datum idx;
+ Datum mask = resarr->capacity - 1;
+
+ Assert(resarr->maxitems > resarr->nitems);
Assert(resarr->capacity > 0);
Assert(resarr->itemsarr != NULL);
- Assert(resarr->nitems < resarr->capacity);
+ Assert(data != resarr->invalidval);
+
+ /* For small arrays don't calculate hashes */
+ if (resarr->capacity == RESARRAY_INIT_SIZE)
+ {
+ resarr->itemsarr[resarr->nitems] = data;
+ resarr->nitems++;
+ return;
+ }
+
+ idx = hash_any((void *) &data, sizeof(data)) & mask;
+
+ while (true)
+ {
+ if (resarr->itemsarr[idx] == resarr->invalidval)
+ break;
+ idx = (idx + 1) & mask;
+ }
- resarr->itemsarr[resarr->nitems] = data;
+ resarr->itemsarr[idx] = data;
resarr->nitems++;
}
@@ -98,24 +150,45 @@ ResourceArrayAdd(ResourceArray * resarr, Datum data)
static bool
ResourceArrayRemove(ResourceArray * resarr, Datum data)
{
- int i,
+ uint32 i,
j,
lastidx;
+ Datum idx;
+ Datum mask = resarr->capacity - 1;
Assert(resarr->capacity > 0);
Assert(resarr->itemsarr != NULL);
+ Assert(data != resarr->invalidval);
+
+ /* For small arrays don't calculate hashes */
+ if (resarr->capacity == RESARRAY_INIT_SIZE)
+ {
+ lastidx = resarr->nitems - 1;
+
+ for (i = lastidx; i >= 0; i--)
+ {
+ if (resarr->itemsarr[i] == data)
+ {
+ for (j = i; j < lastidx; j++)
+ resarr->itemsarr[j] = resarr->itemsarr[j + 1];
+ resarr->nitems--;
+ return true;
+ }
+ }
- lastidx = ((int) resarr->nitems) - 1;
+ return false;
+ }
- for (i = lastidx; i >= 0; i--)
+ idx = hash_any((void *) &data, sizeof(data)) & mask;
+ for (i = 0; i < resarr->capacity; i++)
{
- if (resarr->itemsarr[i] == data)
+ if (resarr->itemsarr[idx] == data)
{
- for (j = i; j < lastidx; j++)
- resarr->itemsarr[j] = resarr->itemsarr[j + 1];
+ resarr->itemsarr[idx] = resarr->invalidval;
resarr->nitems--;
return true;
}
+ idx = (idx + 1) & mask;
}
return false;
@@ -131,27 +204,33 @@ static void
ResourceArrayEnlarge(ResourceArray * resarr)
{
uint32 i,
- oldcap,
- oldnitems;
+ oldcap;
Datum *olditemsarr;
- if (resarr->nitems < resarr->capacity)
+ if (resarr->nitems < resarr->maxitems)
return; /* nothing to do */
olditemsarr = resarr->itemsarr;
oldcap = resarr->capacity;
- oldnitems = resarr->nitems;
resarr->capacity = oldcap > 0 ? oldcap * 2 : RESARRAY_INIT_SIZE;
resarr->itemsarr = (Datum *)
MemoryContextAlloc(TopMemoryContext,
resarr->capacity * sizeof(Datum));
+ resarr->maxitems = RESARRAY_MAX_ITEMS(resarr->capacity);
resarr->nitems = 0;
+ for (i = 0; i < resarr->capacity; i++)
+ resarr->itemsarr[i] = resarr->invalidval;
+
if (olditemsarr != NULL)
{
- for (i = 0; i < oldnitems; i++)
- ResourceArrayAdd(resarr, olditemsarr[i]);
+ while (oldcap > 0)
+ {
+ oldcap--;
+ if (olditemsarr[oldcap] != resarr->invalidval)
+ ResourceArrayAdd(resarr, olditemsarr[oldcap]);
+ }
pfree(olditemsarr);
}
}
@@ -164,12 +243,24 @@ ResourceArrayEnlarge(ResourceArray * resarr)
static bool
ResourceArrayGetAny(ResourceArray * resarr, Datum *out)
{
+ uint32 mask;
+
if (resarr->nitems == 0)
return false;
Assert(resarr->capacity > 0);
+ mask = resarr->capacity - 1;
+
+ for (;;)
+ {
+ resarr->lastidx = resarr->lastidx & mask;
+ if (resarr->itemsarr[resarr->lastidx] != resarr->invalidval)
+ break;
+
+ resarr->lastidx++;
+ }
- *out = resarr->itemsarr[resarr->nitems - 1];
+ *out = resarr->itemsarr[resarr->lastidx];
return true;
}
@@ -182,6 +273,7 @@ ResourceArrayFree(ResourceArray * resarr)
Assert(resarr->nitems == 0);
resarr->capacity = 0;
+ resarr->maxitems = 0;
if (!resarr->itemsarr)
return;
@@ -299,15 +391,15 @@ ResourceOwnerCreate(ResourceOwner parent, const char *name)
parent->firstchild = owner;
}
- ResourceArrayInit(&(owner->catrefarr));
- ResourceArrayInit(&(owner->catlistrefarr));
- ResourceArrayInit(&(owner->relrefarr));
- ResourceArrayInit(&(owner->planrefarr));
- ResourceArrayInit(&(owner->tupdescarr));
- ResourceArrayInit(&(owner->snapshotarr));
- ResourceArrayInit(&(owner->dsmarr));
- ResourceArrayInit(&(owner->bufferarr));
- ResourceArrayInit(&(owner->filearr));
+ ResourceArrayInit(&(owner->catrefarr), PointerGetDatum(NULL));
+ ResourceArrayInit(&(owner->catlistrefarr), PointerGetDatum(NULL));
+ ResourceArrayInit(&(owner->relrefarr), PointerGetDatum(NULL));
+ ResourceArrayInit(&(owner->planrefarr), PointerGetDatum(NULL));
+ ResourceArrayInit(&(owner->tupdescarr), PointerGetDatum(NULL));
+ ResourceArrayInit(&(owner->snapshotarr), PointerGetDatum(NULL));
+ ResourceArrayInit(&(owner->dsmarr), PointerGetDatum(NULL));
+ ResourceArrayInit(&(owner->bufferarr), BufferGetDatum(InvalidBuffer));
+ ResourceArrayInit(&(owner->filearr), FileGetDatum(-1));
return owner;
}
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
