0002-Unaligned-fasthash-word-at-a-time-hashing.patch

From 912f46be12536985dda7bcfb669d4ec13e79d073 Mon Sep 17 00:00:00 2001
From: Ants Aasma <ants@cybertec.at>
Date: Mon, 29 Jan 2024 21:07:44 +0200
Subject: [PATCH 2/2] Unaligned fasthash word at a time hashing

About 10% performance benefit on short strings, 50% on long ones,
making the performance almost identical to the aligned case.
---
 src/include/common/hashfn_unstable.h | 156 +++++++++++++++++++++++----
 1 file changed, 138 insertions(+), 18 deletions(-)

diff --git a/src/include/common/hashfn_unstable.h b/src/include/common/hashfn_unstable.h
index 8ee1b99a204..1e44814d84a 100644
--- a/src/include/common/hashfn_unstable.h
+++ b/src/include/common/hashfn_unstable.h
@@ -189,6 +189,38 @@ first_byte_nonzero(uint64 v)
 #endif
 }
 
+/*
+ * Selects first n bits in memory order and masks the rest with NUL.
+ * Using value 0 for n results in undefined behavior.
+ */
+static inline uint64
+first_n64(uint64 v, uint64 n)
+{
+	Assert(0 < n && n <= 64);
+#ifdef WORDS_BIGENDIAN
+		return v & ((~0ULL) << (64 - n));
+#else
+		return v & ((~0ULL) >> (64 - n));
+#endif
+}
+
+/*
+ * Does the equivalent of an unaligned word access into two consecutive
+ * words, taking the last 8 - offset bytes from first and adding first
+ * offset bytes from second word. offset must be in range [1..7]
+ */
+static inline uint64
+align_n64(uint64 a, uint64 b, int offset)
+{
+	Assert(offset > 0 && offset < 8);
+#ifdef WORDS_BIGENDIAN
+		return (a << (offset * 8)) | (b >> (64 - offset * 8));
+#else
+		return (a >> (offset * 8)) | (b << (64 - offset * 8));
+#endif
+}
+
+
 /*
  * all-purpose workhorse for fasthash_accum_cstring
  */
@@ -212,17 +244,15 @@ fasthash_accum_cstring_unaligned(fasthash_state *hs, const char *str)
 }
 
 /*
- * specialized workhorse for fasthash_accum_cstring
+ * specialized workhorse for fasthash_accum_cstring_autoaligned
  *
- * With an aligned pointer, we consume the string a word at a time.
- * Loading the word containing the NUL terminator cannot segfault since
- * allocation boundaries are suitably aligned.
+ * If the string is aligned we don't need to correct for alignment.
  */
 static inline int
 fasthash_accum_cstring_aligned(fasthash_state *hs, const char *str)
 {
 	const char *const start = str;
-	int			remainder;
+	int			remainder_bits;
 	uint64		zero_bytes_le;
 	uint64		chunk;
 
@@ -259,18 +289,111 @@ fasthash_accum_cstring_aligned(fasthash_state *hs, const char *str)
 	 */
 	if (first_byte_nonzero(chunk))
 	{
-		remainder = pg_rightmost_one_pos64(zero_bytes_le) / BITS_PER_BYTE;
+		remainder_bits = pg_rightmost_one_pos64(zero_bytes_le);
+		hs->accum = first_n64(chunk, remainder_bits);
+		fasthash_combine(hs);
+
+		str += remainder_bits / BITS_PER_BYTE;
+	}
+
+	return str - start;
+}
+
+/*
+ * specialized implementation for fasthash_accum_cstring
+ *
+ * With an aligned pointer, we consume the string a word at a time.
+ * Loading the word containing the NUL terminator cannot segfault since
+ * allocation boundaries are suitably aligned.
+ *
+ * If the pointer is not aligned we can still load a word at a time, but
+ * have to combine the hashed word from two words using the alignment
+ * offset.
+ */
+static inline int
+fasthash_accum_cstring_autoaligned(fasthash_state *hs, const char *str)
+{
+	const char *const start = str;
+	int			remainder_bits;
+	uint64		zero_bytes_le;
+	int			offset;
+	uint64		chunk, prev;
+
+	offset = (uintptr_t) str & 7;
+
+	/*
+	 * Special case aligned string. Needed to avoid shift by 64 in
+	 * alignment code. It's also faster.
+	 */
+	if (!offset)
+		return fasthash_accum_cstring_aligned(hs, str);
+
+	/* Not using MAXALIGN here because we need to round down */
+	str = (const char *) ((uintptr_t) str & ~7);
+	chunk = *(uint64 *) str;
+	/* Mask out the preceding bytes with -1 */
+	chunk |= (-1ULL >> (64 - 8*offset));
+	zero_bytes_le = haszero64(chunk);
+	/* String ends in first loaded word. */
+	if (zero_bytes_le) {
+		remainder_bits = pg_rightmost_one_pos64(zero_bytes_le);
+
+		/*
+		 * Special case empty string to avoid shift by 64 below and have
+		 * the number of combine operations match the unaligned version.
+		 **/
+		if (remainder_bits < BITS_PER_BYTE)
+		{
+			return 0;
+		}
+
+		/* Mask out everything past the last byte and align */
+		hs->accum = align_n64(first_n64(chunk , remainder_bits), 0, offset);
+		fasthash_combine(hs);
+		return remainder_bits / BITS_PER_BYTE - offset;
+	}
+
+	prev = chunk;
+	str += FH_SIZEOF_ACCUM;
+	for (;;)
+	{
+		chunk = *(uint64 *) str;
+
+		/*
+		 * With little-endian representation, we can use this 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
+		 * without either swapping or a bytewise check.
+		 */
 #ifdef WORDS_BIGENDIAN
-		hs->accum = chunk & ((~0ULL) << (64 - BITS_PER_BYTE*remainder));
+		zero_bytes_le = haszero64(pg_bswap64(chunk));
 #else
-		hs->accum = chunk & ((~0ULL) >> (64 - BITS_PER_BYTE*remainder));
+		zero_bytes_le = haszero64(chunk);
 #endif
+		if (zero_bytes_le)
+			break;
+
+		hs->accum = align_n64(prev, chunk, offset);
 		fasthash_combine(hs);
+		str += FH_SIZEOF_ACCUM;
+		prev = chunk;
+	}
+
+	remainder_bits = pg_rightmost_one_pos64(zero_bytes_le);
+	/* Relying on 0 remaining character having 7 zero bits */
+	chunk = first_n64(chunk, remainder_bits);
+
+	hs->accum = align_n64(prev, chunk, offset);
+	fasthash_combine(hs);
 
-		str += remainder;
+	if (remainder_bits / BITS_PER_BYTE > offset)
+	{
+		hs->accum = align_n64(chunk, 0, offset);
+		fasthash_combine(hs);
 	}
 
-	return str - start;
+	return (str - start) + remainder_bits / BITS_PER_BYTE;
 }
 
 /*
@@ -289,19 +412,16 @@ fasthash_accum_cstring(fasthash_state *hs, const char *str)
 	memcpy(&hs_check, hs, sizeof(fasthash_state));
 	len_check = fasthash_accum_cstring_unaligned(&hs_check, str);
 #endif
-	if (PointerIsAligned(str, uint64))
-	{
-		len = fasthash_accum_cstring_aligned(hs, str);
-		Assert(hs_check.hash == hs->hash && len_check == len);
-		return len;
-	}
-#endif							/* SIZEOF_VOID_P */
-
+	len = fasthash_accum_cstring_autoaligned(hs, str);
+	Assert(hs_check.hash == hs->hash && len_check == len);
+	return len;
+#else
 	/*
 	 * It's not worth it to try to make the word-at-a-time optimization work
 	 * on 32-bit platforms.
 	 */
 	return fasthash_accum_cstring_unaligned(hs, str);
+#endif							/* SIZEOF_VOID_P */
 }
 
 /*
-- 
2.34.1