From 3f4cd31478d3e725ab3900eac8c9e7f8982727c5 Mon Sep 17 00:00:00 2001
From: Matthias van de Meent <boekewurm+postgres@gmail.com>
Date: Wed, 18 Dec 2024 16:43:27 +0100
Subject: [PATCH v0 1/2] Dynahash: Allow improved packing of hash elements

On 64-bit builds, there is a 4-byte gap in each Element, which is
wasteful when the entries align to 4 bytes, too.

This adds APIs to indicate entries align by 4 bytes, thus reducing
the space wastage by some bytes per entry (when the alignment works
out).

This will be used in future commits to reduce the size of each
buf_table element by 24 bytes down to 16 bytes, a reduction of 60%.
---
 src/include/utils/hsearch.h       | 10 +++-
 src/backend/utils/hash/dynahash.c | 90 ++++++++++++++++++++++++-------
 2 files changed, 79 insertions(+), 21 deletions(-)

diff --git a/src/include/utils/hsearch.h b/src/include/utils/hsearch.h
index 932cc4f34d9..0856e1209f3 100644
--- a/src/include/utils/hsearch.h
+++ b/src/include/utils/hsearch.h
@@ -74,6 +74,9 @@ typedef struct HASHCTL
 	/* Used if HASH_ELEM flag is set (which is now required): */
 	Size		keysize;		/* hash key length in bytes */
 	Size		entrysize;		/* total user element size in bytes */
+	/* Used if HASH_ALIGN flag is set: */
+	int			entryalign;		/* alignment of entries; either ALIGNOF_INT or
+								 * MAXIMUM_ALIGNOF */
 	/* Used if HASH_FUNCTION flag is set: */
 	HashValueFunc hash;			/* hash function */
 	/* Used if HASH_COMPARE flag is set: */
@@ -103,6 +106,7 @@ typedef struct HASHCTL
 #define HASH_SHARED_MEM 0x0800	/* Hashtable is in shared memory */
 #define HASH_ATTACH		0x1000	/* Do not initialize hctl */
 #define HASH_FIXED_SIZE 0x2000	/* Initial size is a hard limit */
+#define HASH_ALIGN		0x4000	/* Pack-align elements */
 
 /* max_dsize value to indicate expansible directory */
 #define NO_MAX_DSIZE			(-1)
@@ -149,7 +153,11 @@ extern void hash_seq_init_with_hash_value(HASH_SEQ_STATUS *status,
 extern void *hash_seq_search(HASH_SEQ_STATUS *status);
 extern void hash_seq_term(HASH_SEQ_STATUS *status);
 extern void hash_freeze(HTAB *hashp);
-extern Size hash_estimate_size(long num_entries, Size entrysize);
+
+#define hash_estimate_size(num_entries, size) \
+	hash_estimate_size_aligned(num_entries, size, MAXIMUM_ALIGNOF)
+extern Size hash_estimate_size_aligned(long num_entries, Size entrysize,
+									   Size entryalign);
 extern long hash_select_dirsize(long num_entries);
 extern Size hash_get_shared_size(HASHCTL *info, int flags);
 extern void AtEOXact_HashTables(bool isCommit);
diff --git a/src/backend/utils/hash/dynahash.c b/src/backend/utils/hash/dynahash.c
index cd5a00132fc..f74c3ba0682 100644
--- a/src/backend/utils/hash/dynahash.c
+++ b/src/backend/utils/hash/dynahash.c
@@ -190,6 +190,10 @@ struct HASHHDR
 	/* These fields are fixed at hashtable creation */
 	Size		keysize;		/* hash key length in bytes */
 	Size		entrysize;		/* total user element size in bytes */
+	int			entryalign;		/* offset of user data into element, to pack
+								 * data tightly */
+	int			entryoffset;	/* offset of entry into element, may point
+								 * into the alignment gap in HASHELEMENT */
 	long		num_partitions; /* # partitions (must be power of 2), or 0 */
 	long		max_dsize;		/* 'dsize' limit if directory is fixed size */
 	long		ssize;			/* segment size --- must be power of 2 */
@@ -234,6 +238,7 @@ struct HTAB
 
 	/* We keep local copies of these fixed values to reduce contention */
 	Size		keysize;		/* hash key length in bytes */
+	Size		keyoff;			/* key start offset off the base entry pointer */
 	long		ssize;			/* segment size --- must be power of 2 */
 	int			sshift;			/* segment shift = log2(ssize) */
 };
@@ -241,7 +246,7 @@ struct HTAB
 /*
  * Key (also entry) part of a HASHELEMENT
  */
-#define ELEMENTKEY(helem)  (((char *)(helem)) + MAXALIGN(sizeof(HASHELEMENT)))
+#define ELEMENTKEY(helem, off)  (((char *)(helem)) + off)
 
 /*
  * Obtain element pointer given pointer to key
@@ -270,7 +275,7 @@ static bool dir_realloc(HTAB *hashp);
 static bool expand_table(HTAB *hashp);
 static HASHBUCKET get_hash_entry(HTAB *hashp, int freelist_idx);
 static void hdefault(HTAB *hashp);
-static int	choose_nelem_alloc(Size entrysize);
+static int choose_nelem_alloc(Size entrysize, Size entryalign);
 static bool init_htab(HTAB *hashp, long nelem);
 static void hash_corrupted(HTAB *hashp) pg_attribute_noreturn();
 static uint32 hash_initial_lookup(HTAB *hashp, uint32 hashvalue,
@@ -361,6 +366,8 @@ hash_create(const char *tabname, long nelem, const HASHCTL *info, int flags)
 	Assert(flags & HASH_ELEM);
 	Assert(info->keysize > 0);
 	Assert(info->entrysize >= info->keysize);
+	Assert(flags & (~HASH_ALIGN) || info->entryalign == ALIGNOF_INT ||
+		   info->entryalign == MAXIMUM_ALIGNOF);
 
 	/*
 	 * For shared hash tables, we have a local hash header (HTAB struct) that
@@ -558,8 +565,37 @@ hash_create(const char *tabname, long nelem, const HASHCTL *info, int flags)
 	hctl->keysize = info->keysize;
 	hctl->entrysize = info->entrysize;
 
+	if (flags & HASH_ALIGN)
+	{
+		if (info->entryalign != MAXIMUM_ALIGNOF &&
+			info->entryalign != ALIGNOF_INT)
+		{
+			elog(ERROR, "Invalid hash table entry alignment %d",
+				 info->entryalign);
+		}
+
+		hctl->entryalign = info->entryalign;
+
+		if (info->entryalign == MAXIMUM_ALIGNOF)
+			hctl->entryoffset = sizeof(HASHELEMENT);
+		else if (info->entryalign == ALIGNOF_INT)
+		{
+			const Size startOfGap = offsetof(HASHELEMENT, hashvalue) + sizeof(uint32);
+			Size aligned = TYPEALIGN(ALIGNOF_INT, startOfGap);
+
+			hctl->entryoffset = aligned;
+		}
+	}
+	else
+	{
+		hctl->entryalign = MAXIMUM_ALIGNOF;
+		hctl->entryoffset = sizeof(HASHELEMENT);
+	}
+	Assert(TYPEALIGN(hctl->entryalign, hctl->entryoffset) == hctl->entryoffset);
+
 	/* make local copies of heavily-used constant fields */
 	hashp->keysize = hctl->keysize;
+	hashp->keyoff = hctl->entryoffset;
 	hashp->ssize = hctl->ssize;
 	hashp->sshift = hctl->sshift;
 
@@ -653,15 +689,19 @@ hdefault(HTAB *hashp)
  * elements to add to the hash table when we need more.
  */
 static int
-choose_nelem_alloc(Size entrysize)
+choose_nelem_alloc(Size entrysize, Size entryalign)
 {
 	int			nelem_alloc;
 	Size		elementSize;
 	Size		allocSize;
 
+	Assert(entryalign == 4 || entryalign == MAXIMUM_ALIGNOF);
 	/* Each element has a HASHELEMENT header plus user data. */
 	/* NB: this had better match element_alloc() */
-	elementSize = MAXALIGN(sizeof(HASHELEMENT)) + MAXALIGN(entrysize);
+	elementSize = offsetof(HASHELEMENT, hashvalue) + sizeof(uint32);
+	elementSize = TYPEALIGN(entryalign, elementSize);
+
+	elementSize = MAXALIGN(elementSize + entrysize);
 
 	/*
 	 * The idea here is to choose nelem_alloc at least 32, but round up so
@@ -756,7 +796,7 @@ init_htab(HTAB *hashp, long nelem)
 	}
 
 	/* Choose number of entries to allocate at a time */
-	hctl->nelem_alloc = choose_nelem_alloc(hctl->entrysize);
+	hctl->nelem_alloc = choose_nelem_alloc(hctl->entrysize, hctl->entryalign);
 
 #ifdef HASH_DEBUG
 	fprintf(stderr, "init_htab:\n%s%p\n%s%ld\n%s%ld\n%s%d\n%s%ld\n%s%u\n%s%x\n%s%x\n%s%ld\n",
@@ -772,6 +812,8 @@ init_htab(HTAB *hashp, long nelem)
 	return true;
 }
 
+
+
 /*
  * Estimate the space needed for a hashtable containing the given number
  * of entries of given size.
@@ -780,7 +822,7 @@ init_htab(HTAB *hashp, long nelem)
  * NB: assumes that all hash structure parameters have default values!
  */
 Size
-hash_estimate_size(long num_entries, Size entrysize)
+hash_estimate_size_aligned(long num_entries, Size entrysize, Size entryalign)
 {
 	Size		size;
 	long		nBuckets,
@@ -807,9 +849,12 @@ hash_estimate_size(long num_entries, Size entrysize)
 	size = add_size(size, mul_size(nSegments,
 								   MAXALIGN(DEF_SEGSIZE * sizeof(HASHBUCKET))));
 	/* elements --- allocated in groups of choose_nelem_alloc() entries */
-	elementAllocCnt = choose_nelem_alloc(entrysize);
+	elementAllocCnt = choose_nelem_alloc(entrysize, entryalign);
 	nElementAllocs = (num_entries - 1) / elementAllocCnt + 1;
-	elementSize = MAXALIGN(sizeof(HASHELEMENT)) + MAXALIGN(entrysize);
+	
+	elementSize = offsetof(HASHELEMENT, hashvalue) + sizeof(uint32);
+	elementSize = TYPEALIGN(entryalign, elementSize);
+	elementSize = MAXALIGN(elementSize + entrysize);
 	size = add_size(size,
 					mul_size(nElementAllocs,
 							 mul_size(elementAllocCnt, elementSize)));
@@ -974,6 +1019,7 @@ hash_search_with_hash_value(HTAB *hashp,
 	HASHHDR    *hctl = hashp->hctl;
 	int			freelist_idx = FREELIST_IDX(hctl, hashvalue);
 	Size		keysize;
+	Size		keyoff;
 	HASHBUCKET	currBucket;
 	HASHBUCKET *prevBucketPtr;
 	HashCompareFunc match;
@@ -1014,11 +1060,12 @@ hash_search_with_hash_value(HTAB *hashp,
 	 */
 	match = hashp->match;		/* save one fetch in inner loop */
 	keysize = hashp->keysize;	/* ditto */
+	keyoff = hashp->keyoff;	/* ditto */
 
 	while (currBucket != NULL)
 	{
 		if (currBucket->hashvalue == hashvalue &&
-			match(ELEMENTKEY(currBucket), keyPtr, keysize) == 0)
+			match(ELEMENTKEY(currBucket, keyoff), keyPtr, keysize) == 0)
 			break;
 		prevBucketPtr = &(currBucket->link);
 		currBucket = *prevBucketPtr;
@@ -1038,7 +1085,7 @@ hash_search_with_hash_value(HTAB *hashp,
 	{
 		case HASH_FIND:
 			if (currBucket != NULL)
-				return ELEMENTKEY(currBucket);
+				return ELEMENTKEY(currBucket, keyoff);
 			return NULL;
 
 		case HASH_REMOVE:
@@ -1067,7 +1114,7 @@ hash_search_with_hash_value(HTAB *hashp,
 				 * element, because someone else is going to reuse it the next
 				 * time something is added to the table
 				 */
-				return ELEMENTKEY(currBucket);
+				return ELEMENTKEY(currBucket, keyoff);
 			}
 			return NULL;
 
@@ -1075,7 +1122,7 @@ hash_search_with_hash_value(HTAB *hashp,
 		case HASH_ENTER_NULL:
 			/* Return existing element if found, else create one */
 			if (currBucket != NULL)
-				return ELEMENTKEY(currBucket);
+				return ELEMENTKEY(currBucket, keyoff);
 
 			/* disallow inserts if frozen */
 			if (hashp->frozen)
@@ -1105,7 +1152,7 @@ hash_search_with_hash_value(HTAB *hashp,
 
 			/* copy key into record */
 			currBucket->hashvalue = hashvalue;
-			hashp->keycopy(ELEMENTKEY(currBucket), keyPtr, keysize);
+			hashp->keycopy(ELEMENTKEY(currBucket, keyoff), keyPtr, keysize);
 
 			/*
 			 * Caller is expected to fill the data field on return.  DO NOT
@@ -1114,7 +1161,7 @@ hash_search_with_hash_value(HTAB *hashp,
 			 * caller's data structure.
 			 */
 
-			return ELEMENTKEY(currBucket);
+			return ELEMENTKEY(currBucket, keyoff);
 	}
 
 	elog(ERROR, "unrecognized hash action code: %d", (int) action);
@@ -1149,6 +1196,7 @@ hash_update_hash_key(HTAB *hashp,
 	HASHELEMENT *existingElement = ELEMENT_FROM_KEY(existingEntry);
 	uint32		newhashvalue;
 	Size		keysize;
+	Size		keyoff;
 	uint32		bucket;
 	uint32		newbucket;
 	HASHBUCKET	currBucket;
@@ -1202,11 +1250,12 @@ hash_update_hash_key(HTAB *hashp,
 	 */
 	match = hashp->match;		/* save one fetch in inner loop */
 	keysize = hashp->keysize;	/* ditto */
+	keyoff = hashp->keyoff;	/* ditto */
 
 	while (currBucket != NULL)
 	{
 		if (currBucket->hashvalue == newhashvalue &&
-			match(ELEMENTKEY(currBucket), newKeyPtr, keysize) == 0)
+			match(ELEMENTKEY(currBucket, keyoff), newKeyPtr, keysize) == 0)
 			break;
 		prevBucketPtr = &(currBucket->link);
 		currBucket = *prevBucketPtr;
@@ -1240,7 +1289,7 @@ hash_update_hash_key(HTAB *hashp,
 
 	/* copy new key into record */
 	currBucket->hashvalue = newhashvalue;
-	hashp->keycopy(ELEMENTKEY(currBucket), newKeyPtr, keysize);
+	hashp->keycopy(ELEMENTKEY(currBucket, keyoff), newKeyPtr, keysize);
 
 	/* rest of record is untouched */
 
@@ -1440,7 +1489,7 @@ hash_seq_search(HASH_SEQ_STATUS *status)
 			status->curEntry = curElem->link;
 			if (status->hashvalue != curElem->hashvalue)
 				continue;
-			return (void *) ELEMENTKEY(curElem);
+			return (void *) ELEMENTKEY(curElem, status->hashp->keyoff);
 		}
 
 		hash_seq_term(status);
@@ -1453,7 +1502,7 @@ hash_seq_search(HASH_SEQ_STATUS *status)
 		status->curEntry = curElem->link;
 		if (status->curEntry == NULL)	/* end of this bucket */
 			++status->curBucket;
-		return ELEMENTKEY(curElem);
+		return ELEMENTKEY(curElem, status->hashp->keyoff);
 	}
 
 	/*
@@ -1507,7 +1556,7 @@ hash_seq_search(HASH_SEQ_STATUS *status)
 	if (status->curEntry == NULL)	/* end of this bucket */
 		++curBucket;
 	status->curBucket = curBucket;
-	return ELEMENTKEY(curElem);
+	return ELEMENTKEY(curElem, status->hashp->keyoff);
 }
 
 void
@@ -1716,7 +1765,8 @@ element_alloc(HTAB *hashp, int nelem, int freelist_idx)
 		return false;
 
 	/* Each element has a HASHELEMENT header plus user data. */
-	elementSize = MAXALIGN(sizeof(HASHELEMENT)) + MAXALIGN(hctl->entrysize);
+	Assert(hctl->entryoffset >= offsetof(HASHELEMENT, hashvalue) + sizeof(uint32));
+	elementSize = MAXALIGN(hctl->entryoffset + hctl->entrysize);
 
 	CurrentDynaHashCxt = hashp->hcxt;
 	firstElement = (HASHELEMENT *) hashp->alloc(nelem * elementSize);
-- 
2.45.2

