diff --git a/src/backend/utils/resowner/resowner.c b/src/backend/utils/resowner/resowner.c index 39324fe..d2b37d5 100644 --- a/src/backend/utils/resowner/resowner.c +++ b/src/backend/utils/resowner/resowner.c @@ -37,6 +37,27 @@ * 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. Note that different resources have different sizeof. Thus + * ResourceArray should know size of resource and store all data in char[] + * buffer. + * + * Secondly ResourceArray must be more efficient than regular C array. + * Previous implementation of ResourceOwner used arrays. It had O(1) complexity + * of Remember procedures and O(N) complexity of Forget procedures where N is a + * number of remembered resources. It turned out that such implementation + * creates a bottleneck in some cases, e.g. when working with partitioned + * tables which have a lot of (say, thousands) partitions. New implementation + * in general could be considered a hash table with some specific optimizations. + * It has O(1) complexity of both Remember and Forget procedures and + * apparently doesn't cause any performance degradation compared to previous + * implementation. */ typedef struct ResourceArray { @@ -44,21 +65,60 @@ typedef struct ResourceArray uint32 itemsizelg:2; /* sizeof one item log 2 */ uint32 capacity:30; /* capacity of array */ uint32 nitems; /* how many items is stored in items array */ + uint32 maxitems; /* precalculated RESARRAY_MAX_ITEMS(capacity) */ } 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 /* + * 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) + +/* * Such type of callback function is called when resource stored in * ResourceArray is released using ResourceArrayFree. Callback should * _actually_ release a resource so nitems value will be decremented. */ typedef void (*ResourceArrayRemoveCallback) (const void *ref, bool isCommit); +/* Used as argument to memcmp to determine if ResourceArray[i] is free. */ +static const char RESOURCE_ARRAY_ZERO_ELEMENT[sizeof(void *)] = +{ + 0 +}; + +/* + * Calculate hash_any of given data. For uint32 values use faster hash_uint32. + */ +static Datum +ResourceArrayHash(const void *data, int size) +{ + uint32 tmp; + + Assert(size == sizeof(uint32) || size == sizeof(void *)); + + if (size == sizeof(uint32)) + { + tmp = *((const uint32 *) data); + return hash_uint32(tmp); + } + else + { + return hash_any(data, size); + } +} + /* * Initialize ResourceArray */ @@ -69,6 +129,7 @@ ResourceArrayInit(ResourceArray * resarr, uint32 itemsize) Assert(resarr->itemsarr == NULL); Assert(resarr->capacity == 0); Assert(resarr->nitems == 0); + Assert(resarr->maxitems == 0); resarr->itemsizelg = 0; while (itemsize > 1) @@ -89,22 +150,42 @@ static void ResourceArrayAdd(ResourceArray * resarr, const void *dataref) { char *itemptr; + Datum idx; + Datum mask = resarr->capacity - 1; uint32 itemsize = 1 << resarr->itemsizelg; + Assert(memcmp(dataref, RESOURCE_ARRAY_ZERO_ELEMENT, itemsize) != 0); + Assert(resarr->maxitems > resarr->nitems); Assert(resarr->capacity > 0); Assert(resarr->itemsarr != NULL); - Assert(resarr->nitems < resarr->capacity); /* - * Read next line as: - * - * itemptr = &(itemsarr[resarr->nitems]) - * - * We use binary shift since compiler doesn't know that itemsize is always - * power of two. It would use multiplication instead of efficient binary - * shift in code `resarr->nitems * itemsize`. + * Hashing is quite expensive, so we use it only for large arrays. For + * small arrays we just use a linear scan. */ - itemptr = resarr->itemsarr + (resarr->nitems << resarr->itemsizelg); + if (resarr->capacity == RESARRAY_INIT_SIZE) + idx = resarr->nitems; + else + idx = ResourceArrayHash(dataref, itemsize); + idx &= mask; + + while (true) + { + /* + * Read next line as: + * + * itemptr = &(itemsarr[idx]) + * + * We use binary shift since compiler doesn't know that itemsize is + * always power of two. It would use multiplication instead of + * efficient binary shift in code `idx * itemsize`. + */ + itemptr = resarr->itemsarr + (idx << resarr->itemsizelg); + if (memcmp(itemptr, RESOURCE_ARRAY_ZERO_ELEMENT, itemsize) == 0) + break; + idx = (idx + 1) & mask; + } + memcpy(itemptr, dataref, itemsize); resarr->nitems++; } @@ -117,17 +198,27 @@ ResourceArrayAdd(ResourceArray * resarr, const void *dataref) static bool ResourceArrayRemove(ResourceArray * resarr, const void *dataref) { - Datum idx; char *itemptr; - char *lastitemptr; + Datum idx; + uint32 i; + Datum mask = resarr->capacity - 1; uint32 itemsize = 1 << resarr->itemsizelg; + Assert(memcmp(dataref, RESOURCE_ARRAY_ZERO_ELEMENT, itemsize) != 0); Assert(resarr->capacity > 0); Assert(resarr->itemsarr != NULL); - lastitemptr = resarr->itemsarr + - ((resarr->nitems - 1) << resarr->itemsizelg); - for (idx = 0; idx < resarr->nitems; idx++) + /* + * Hashing is quite expensive, so we use it only for large arrays. For + * small arrays we use a linear scan. + */ + if (resarr->capacity == RESARRAY_INIT_SIZE) + idx = 0; + else + idx = ResourceArrayHash(dataref, itemsize); + idx &= mask; + + for (i = 0; i < resarr->capacity; i++) { /* * Read next line as: @@ -141,10 +232,11 @@ ResourceArrayRemove(ResourceArray * resarr, const void *dataref) itemptr = resarr->itemsarr + (idx << resarr->itemsizelg); if (memcmp(itemptr, dataref, itemsize) == 0) { - memcpy(itemptr, lastitemptr, itemsize); + memset(itemptr, 0, itemsize); resarr->nitems--; return true; } + idx = (idx + 1) & mask; } return false; @@ -166,7 +258,7 @@ ResourceArrayEnlarge(ResourceArray * resarr) Assert(resarr->itemsizelg != 0); - if (resarr->nitems < resarr->capacity) + if (resarr->nitems < resarr->maxitems) return; /* nothing to do */ olditemsarr = resarr->itemsarr; @@ -176,6 +268,7 @@ ResourceArrayEnlarge(ResourceArray * resarr) resarr->itemsarr = (char *) MemoryContextAllocZero(TopMemoryContext, resarr->capacity * itemsize); + resarr->maxitems = RESARRAY_MAX_ITEMS(resarr->capacity); resarr->nitems = 0; if (olditemsarr != NULL) @@ -194,7 +287,8 @@ ResourceArrayEnlarge(ResourceArray * resarr) * efficient binary shift in code `oldcap * itemsize`. */ olditemptr = olditemsarr + (oldcap << resarr->itemsizelg); - ResourceArrayAdd(resarr, olditemptr); + if (memcmp(olditemptr, RESOURCE_ARRAY_ZERO_ELEMENT, itemsize) != 0) + ResourceArrayAdd(resarr, olditemptr); } pfree(olditemsarr); } @@ -208,9 +302,28 @@ ResourceArrayRemoveAll(ResourceArray * resarr, ResourceArrayRemoveCallback releasecb, bool isCommit) { + uint32 idx = 0; + char *itemptr; + uint32 itemsize = 1 << resarr->itemsizelg; + while (resarr->nitems > 0) { - releasecb(resarr->itemsarr, isCommit); + /* + * Read next line as: + * + * itemptr = &(itemsarr[idx]) + * + * We use binary shift since compiler doesn't know that itemsize is + * always power of two. It would use multiplication instead of + * efficient binary shift in code `idx * itemsize`. + */ + itemptr = resarr->itemsarr + (idx << resarr->itemsizelg); + if (memcmp(itemptr, RESOURCE_ARRAY_ZERO_ELEMENT, itemsize) == 0) + { + idx++; + continue; + } + releasecb(itemptr, isCommit); } } @@ -223,6 +336,7 @@ ResourceArrayFree(ResourceArray * resarr) Assert(resarr->nitems == 0); resarr->capacity = 0; + resarr->maxitems = 0; if (!resarr->itemsarr) return;