v11-0004-Add-optimized-string-hashing-to-hashfn_unstable..patch

From 3dd1cdb0b322fdec0955c999bbffc8bf86e5a941 Mon Sep 17 00:00:00 2001
From: John Naylor <john.naylor@postgresql.org>
Date: Wed, 20 Dec 2023 11:40:11 +0700
Subject: [PATCH v11 4/8] Add optimized string hashing to hashfn_unstable.h

Given an already-initialized hash state and a C-string,
accumulate the hash of the string into the hash state
and return the length for the caller to save for the
finalizer. This avoids a strlen call.

If the string pointer is aligned, we can use a word-
at-a-time algorithm for the NUL check and for computing
the remainder length up to the NUL. This is only used on 64-bit,
since it's not worth the extra complexity for 32-bit platforms.
The big-endian case is simulated, and this will be rationalized
in a later commit.

Based on Jeff Davis's v10jd-0004, with
optimized tail inspired by NetBSD's strlen.

simulate big endian coding
---
 src/backend/catalog/namespace.c      |  30 ++++---
 src/include/common/hashfn_unstable.h | 116 ++++++++++++++++++++++++++-
 2 files changed, 133 insertions(+), 13 deletions(-)

diff --git a/src/backend/catalog/namespace.c b/src/backend/catalog/namespace.c
index 7fe2fd1fd4..32597bea20 100644
--- a/src/backend/catalog/namespace.c
+++ b/src/backend/catalog/namespace.c
@@ -247,25 +247,31 @@ static bool MatchNamedCall(HeapTuple proctup, int nargs, List *argnames,
 static inline uint32
 spcachekey_hash(SearchPathCacheKey key)
 {
-	const char *const start = key.searchPath;
-	const char *buf = key.searchPath;
 	fasthash_state hs;
+	int sp_len;
 
 	/* WIP: maybe roleid should be mixed in normally */
-	fasthash_init(&hs, FH_UNKNOWN_LENGTH, key.roleid);
-	while (*buf)
-	{
-		int			chunk_len = 0;
+	uint64 seed = key.roleid;
 
-		while (chunk_len < FH_SIZEOF_ACCUM && buf[chunk_len] != '\0')
-			chunk_len++;
+	// XXX not for commit
+#ifdef USE_ASSERT_CHECKING
 
-		fasthash_accum(&hs, buf, chunk_len);
-		buf += chunk_len;
-	}
+	int			blen = strlen(key.searchPath);
+
+	uint64 h_orig = fasthash64(key.searchPath, blen, key.roleid);
+
+	// Compare orig to optimized string interface
+	fasthash_init(&hs, blen, key.roleid);
+	(void) fasthash_accum_cstring(&hs, key.searchPath);
+	Assert(fasthash_final64(&hs, 0) == h_orig);
+#endif
+
+	fasthash_init(&hs, FH_UNKNOWN_LENGTH, seed);
+
+	sp_len = fasthash_accum_cstring(&hs, key.searchPath);
 
 	/* pass the length to tweak the final mix */
-	return fasthash_final32(&hs, buf - start);
+	return fasthash_final32(&hs, sp_len);
 }
 
 static inline bool
diff --git a/src/include/common/hashfn_unstable.h b/src/include/common/hashfn_unstable.h
index bf1dbee28d..4fc9edba6e 100644
--- a/src/include/common/hashfn_unstable.h
+++ b/src/include/common/hashfn_unstable.h
@@ -13,6 +13,8 @@ the same hashes between versions.
 #ifndef HASHFN_UNSTABLE_H
 #define HASHFN_UNSTABLE_H
 
+#include "port/pg_bitutils.h"
+
 /*
  * fasthash is a modification of code taken from
  * https://code.google.com/archive/p/fast-hash/source/default/source
@@ -63,11 +65,12 @@ return fasthash_final32(&hs, <final length>);
 typedef struct fasthash_state
 {
 	uint64		accum;
-#define FH_SIZEOF_ACCUM sizeof(uint64)
 
 	uint64		hash;
 } fasthash_state;
 
+#define FH_SIZEOF_ACCUM 8
+StaticAssertDecl(sizeof(((fasthash_state*) 0)->accum) == FH_SIZEOF_ACCUM, "wrong size for size macro");
 
 #define FH_UNKNOWN_LENGTH 1
 
@@ -145,6 +148,117 @@ fasthash_accum(fasthash_state *hs, const char *k, int len)
 	fasthash_combine(hs);
 }
 
+/* From: https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord */
+#define haszero64(v) \
+	(((v) - 0x0101010101010101UL) & ~(v) & 0x8080808080808080UL)
+
+#define SIM_BE 1
+#include "port/pg_bswap.h"
+
+/*
+ * With an aligned pointer, we consume the string a word at a time. Loading
+ * the word containing the NUL terminator cannot segfault since page boundaries
+ * are MAXALIGN'd. For that last word, only use bytes up to the NUL for the hash.
+ * The algorithm was adopted from NetBSD's strlen.
+ */
+static inline int
+fasthash_accum_cstring_aligned(fasthash_state *hs, const char *str)
+{
+	const char *const start = str;
+	const char *buf = start;
+	int remainder;
+	uint64 zero_bytes;
+
+	Assert(PointerIsAligned(start, uint64));
+	while (true)
+	{
+		uint64 chunk = *(uint64 *)buf;
+#ifdef SIM_BE
+		uint64 low_bits = 0x7F7F7F7F7F7F7F7F;
+
+		chunk = pg_bswap64(chunk); /* simulate BE */
+
+		/*
+		 * This expression evaluates has the useful property that all bytes in the result word
+		 * that correspond to non-zero bytes in the original word have
+		 * the value 0x00, while all bytes corresponding to zero bytes have
+		 * the value 0x80.
+		 */
+		zero_bytes = ~(((chunk & low_bits) + low_bits) | chunk | low_bits);
+#else
+		/*
+		 * On little endian machines, we can use a slightly faster calculation,
+		 * which sets bits in the first byte in the result word
+		 * that corresponds to a zero byte in the original word.
+		 * The rest of the bytes are indeterminate, so cannot be used
+		 * on big-endian machines unless we resort to a bytewise check.
+		 */
+		zero_bytes = haszero64(chunk);
+#endif
+		if (zero_bytes)
+			break;
+
+#ifdef SIM_BE
+		hs->accum = pg_bswap64(chunk); /* not needed with real BE, because we won't need the same answer */
+#else
+		hs->accum = chunk;
+#endif
+		fasthash_combine(hs);
+		buf += FH_SIZEOF_ACCUM;
+	}
+
+	/*
+	 * Bytes with set bits will be 0x80, so
+	 * calculate the first occurrence of a zero byte within the input word
+	 * by counting the number of leading (on BE) or trailing (on LE)
+	 * zeros and dividing the result by 8.
+	 */
+#ifdef SIM_BE
+	remainder = (63 - pg_leftmost_one_pos64(zero_bytes)) / BITS_PER_BYTE;
+#else
+	remainder = pg_rightmost_one_pos64(zero_bytes) / BITS_PER_BYTE;
+#endif
+	fasthash_accum(hs, buf, remainder);
+	buf += remainder;
+
+	return buf - start;
+}
+
+static inline int
+fasthash_accum_cstring_unaligned(fasthash_state *hs, const char *str)
+{
+	const char *const start = str;
+	const char *buf = str;
+
+	while (*buf)
+	{
+		int			chunk_len = 0;
+
+		while (chunk_len < FH_SIZEOF_ACCUM && buf[chunk_len] != '\0')
+			chunk_len++;
+
+		fasthash_accum(hs, buf, chunk_len);
+		buf += chunk_len;
+	}
+
+	return buf - start;
+}
+
+/*
+ * Accumulate the input into the hash state
+ * and return the length of the string.
+ */
+static inline int
+fasthash_accum_cstring(fasthash_state *hs, const char *str)
+{
+#if SIZEOF_VOID_P >= FH_SIZEOF_ACCUM
+	if (PointerIsAligned(str, uint64))
+		return fasthash_accum_cstring_aligned(hs, str);
+	else
+#endif
+		return fasthash_accum_cstring_unaligned(hs, str);
+}
+
 /*
  * The finalizer
  *
-- 
2.43.0