I wrote:
>
> It occurred to me that it's strange to have two places that length can
> be passed. That was a side effect of the original, which used length
> to both know how many bytes to read, and to modify the internal seed.
> With the incremental API, it doesn't make sense to pass the length (or
> a dummy macro) up front -- with a compile-time fixed length, it can't
> possibly break a tie, so it's just noise.
This was a wart, so pushed removing initial length from the incremental API.
On Mon, Jan 22, 2024 at 11:16 AM Jeff Davis <pg...@j-davis.com> wrote:
>
> On Mon, 2024-01-22 at 09:03 +0700, John Naylor wrote:
> > v15-0004 is a stab at that. As an idea, it also renames zero_bytes_le
> > to zero_byte_low to reflect the effect better. There might be some
> > other comment edits needed to explain usage, so I plan to hold on to
> > this for later. Let me know what you think.
>
> 0004 looks good to me. No urgency so feel free to hold it until a
> convenient time.
Thanks for looking, I pushed this along with an expanded explanation of usage.
> 0002 and 0003 use fasthash for dynahash and GUC hash, respectively.
> These cannot use the existing cstring hashing directly because of
> truncation and case-folding, respectively. (Some simplehash uses can,
> but that can come later)
I've re-attached these as well as a cleaned-up version of the tail
optimization. For the CF entry, the GUC hash function in this form
might only be necessary if we went ahead with simple hash. We don't
yet have a new benchmark to show if that's still worthwhile after
867dd2dc87 improved the one upthread.
For dynahash, one tricky part seems to be the comment about the
default and when it was an assertion error. I've tried to reword this,
but maybe needs work. When that's in shape, I'll incorporate removing
other strlen calls.
From 0acceeb59c44cacb1f8a1a0bdeb7fdef81499155 Mon Sep 17 00:00:00 2001
From: John Naylor <john.nay...@postgresql.org>
Date: Sun, 21 Jan 2024 16:04:16 +0700
Subject: [PATCH v18 1/3] Use fasthash for dynahash's default string hash
This avoids strlen calls. string_hash is kept around in case
extensions are using it.
---
src/backend/utils/hash/dynahash.c | 52 +++++++++++++++++++++++++++----
src/common/hashfn.c | 3 +-
2 files changed, 48 insertions(+), 7 deletions(-)
diff --git a/src/backend/utils/hash/dynahash.c b/src/backend/utils/hash/dynahash.c
index a4152080b5..92c7989575 100644
--- a/src/backend/utils/hash/dynahash.c
+++ b/src/backend/utils/hash/dynahash.c
@@ -98,6 +98,7 @@
#include "access/xact.h"
#include "common/hashfn.h"
+#include "common/hashfn_unstable.h"
#include "port/pg_bitutils.h"
#include "storage/shmem.h"
#include "storage/spin.h"
@@ -307,6 +308,45 @@ string_compare(const char *key1, const char *key2, Size keysize)
return strncmp(key1, key2, keysize - 1);
}
+/*
+ * default_string_hash: hash function for keys that are NUL-terminated strings.
+ *
+ * NOTE: this is the default hash function if none is specified.
+ */
+static uint32
+default_string_hash(const void *key, Size keysize)
+{
+ const char *k = (const char *) key;
+ Size s_len = 0;
+ fasthash_state hs;
+
+ /*
+ * If the string exceeds keysize-1 bytes, we want to hash only that many,
+ * because when it is copied into the hash table it will be truncated at
+ * that length.
+ */
+
+ fasthash_init(&hs, 0);
+
+ while (*k && s_len < keysize - 1)
+ {
+ int chunk_len = 0;
+
+ while (k[chunk_len] != '\0' &&
+ s_len < keysize - 1 &&
+ chunk_len < FH_SIZEOF_ACCUM)
+ {
+ chunk_len++;
+ s_len++;
+ }
+
+ fasthash_accum(&hs, k, chunk_len);
+ k += chunk_len;
+ }
+
+ return fasthash_final32(&hs, s_len);
+}
+
/************************** CREATE ROUTINES **********************/
@@ -418,8 +458,8 @@ hash_create(const char *tabname, long nelem, const HASHCTL *info, int flags)
else
{
/*
- * string_hash used to be considered the default hash method, and in a
- * non-assert build it effectively still is. But we now consider it
+ * string_hash used to be considered the default hash method, and
+ * it effectively still was until version 17. Since version 14 we consider it
* an assertion error to not say HASH_STRINGS explicitly. To help
* catch mistaken usage of HASH_STRINGS, we also insist on a
* reasonably long string length: if the keysize is only 4 or 8 bytes,
@@ -428,12 +468,12 @@ hash_create(const char *tabname, long nelem, const HASHCTL *info, int flags)
Assert(flags & HASH_STRINGS);
Assert(info->keysize > 8);
- hashp->hash = string_hash;
+ hashp->hash = default_string_hash;
}
/*
* If you don't specify a match function, it defaults to string_compare if
- * you used string_hash, and to memcmp otherwise.
+ * you used default_string_hash, and to memcmp otherwise.
*
* Note: explicitly specifying string_hash is deprecated, because this
* might not work for callers in loadable modules on some platforms due to
@@ -442,7 +482,7 @@ hash_create(const char *tabname, long nelem, const HASHCTL *info, int flags)
*/
if (flags & HASH_COMPARE)
hashp->match = info->match;
- else if (hashp->hash == string_hash)
+ else if (hashp->hash == default_string_hash)
hashp->match = (HashCompareFunc) string_compare;
else
hashp->match = memcmp;
@@ -452,7 +492,7 @@ hash_create(const char *tabname, long nelem, const HASHCTL *info, int flags)
*/
if (flags & HASH_KEYCOPY)
hashp->keycopy = info->keycopy;
- else if (hashp->hash == string_hash)
+ else if (hashp->hash == default_string_hash)
{
/*
* The signature of keycopy is meant for memcpy(), which returns
diff --git a/src/common/hashfn.c b/src/common/hashfn.c
index 4db468cf85..3090b3cbd9 100644
--- a/src/common/hashfn.c
+++ b/src/common/hashfn.c
@@ -654,7 +654,8 @@ hash_bytes_uint32_extended(uint32 k, uint64 seed)
/*
* string_hash: hash function for keys that are NUL-terminated strings.
*
- * NOTE: this is the default hash function if none is specified.
+ * NOTE: this was the default string hash for dynahash until vesion 17,
+ * and is now here only for backward compatibility.
*/
uint32
string_hash(const void *key, Size keysize)
--
2.43.0
From aa8d1f727b20f65b0506380c318ee823c0657849 Mon Sep 17 00:00:00 2001
From: John Naylor <john.nay...@postgresql.org>
Date: Sun, 21 Jan 2024 17:49:22 +0700
Subject: [PATCH v18 2/3] Use fasthash for guc_name_hash
---
src/backend/utils/misc/guc.c | 36 +++++++++++++++++++++++++++---------
1 file changed, 27 insertions(+), 9 deletions(-)
diff --git a/src/backend/utils/misc/guc.c b/src/backend/utils/misc/guc.c
index 8f65ef3d89..67859baf69 100644
--- a/src/backend/utils/misc/guc.c
+++ b/src/backend/utils/misc/guc.c
@@ -33,6 +33,7 @@
#include "catalog/objectaccess.h"
#include "catalog/pg_authid.h"
#include "catalog/pg_parameter_acl.h"
+#include "common/hashfn_unstable.h"
#include "guc_internal.h"
#include "libpq/pqformat.h"
#include "parser/scansup.h"
@@ -1324,22 +1325,39 @@ guc_name_compare(const char *namea, const char *nameb)
static uint32
guc_name_hash(const void *key, Size keysize)
{
- uint32 result = 0;
const char *name = *(const char *const *) key;
+ const char *const start = name;
+ fasthash_state hs;
+
+ fasthash_init(&hs, 0);
while (*name)
{
- char ch = *name++;
+ int chunk_len = 0;
- /* Case-fold in the same way as guc_name_compare */
- if (ch >= 'A' && ch <= 'Z')
- ch += 'a' - 'A';
+ while (chunk_len < FH_SIZEOF_ACCUM && name[chunk_len] != '\0')
+ {
+ chunk_len++;
+ hs.accum <<= BITS_PER_BYTE;
+ hs.accum |= name[chunk_len];
+ }
- /* Merge into hash ... not very bright, but it needn't be */
- result = pg_rotate_left32(result, 5);
- result ^= (uint32) ch;
+ /*
+ * Quick ASCII-only downcasing. Note: This effectively pads spaces
+ * when the input is not a multiple of 8. This would be okay even if
+ * space were a valid name character, since the actual length acts as
+ * a tiebreaker for the finalizer.
+ */
+ hs.accum |= 0x2020202020202020;
+
+ /* merge into hash and reset for next iteration */
+ fasthash_combine(&hs);
+ hs.accum = 0;
+
+ name += chunk_len;
}
- return result;
+
+ return fasthash_final32(&hs, name - start);
}
/*
--
2.43.0
From 88a2bdb6b03dd4bc0e1cc1d289485461d025f51b Mon Sep 17 00:00:00 2001
From: John Naylor <john.nay...@postgresql.org>
Date: Tue, 6 Feb 2024 13:11:33 +0700
Subject: [PATCH v18 3/3] Speed up tail processing when hashing aligned C
strings
After encountering the NUL terminator, the word-at-a-time loop exits
and we must hash the remaining bytes. Previously we calculated the
terminator's position and re-loaded the remaining bytes from the input
string. We already have all the data we need in a register, so lets's
just mask off the bytes we need and hash them immediately. The mask can
be cheaply computed without knowing the terminator's position. We still
need that position for the length calculation, but the CPU can now
do that in parallel with other work, shortening the dependency chain.
Ants Aasma and John Naylor
Discussion: https://postgr.es/m/CANwKhkP7pCiW_5fAswLhs71-JKGEz1c1%2BPC0a_w1fwY4iGMqUA%40mail.gmail.com
---
src/include/common/hashfn_unstable.h | 44 +++++++++++++++++++++-------
1 file changed, 34 insertions(+), 10 deletions(-)
diff --git a/src/include/common/hashfn_unstable.h b/src/include/common/hashfn_unstable.h
index af80e65fef..308d1982c8 100644
--- a/src/include/common/hashfn_unstable.h
+++ b/src/include/common/hashfn_unstable.h
@@ -219,8 +219,9 @@ static inline int
fasthash_accum_cstring_aligned(fasthash_state *hs, const char *str)
{
const char *const start = str;
- int remainder;
+ uint64 chunk;
uint64 zero_byte_low;
+ uint64 mask;
Assert(PointerIsAligned(start, uint64));
@@ -239,7 +240,7 @@ fasthash_accum_cstring_aligned(fasthash_state *hs, const char *str)
*/
for (;;)
{
- uint64 chunk = *(uint64 *) str;
+ chunk = *(uint64 *) str;
#ifdef WORDS_BIGENDIAN
zero_byte_low = haszero64(pg_bswap64(chunk));
@@ -254,14 +255,37 @@ fasthash_accum_cstring_aligned(fasthash_state *hs, const char *str)
str += FH_SIZEOF_ACCUM;
}
- /*
- * The byte corresponding to the NUL will be 0x80, so the rightmost bit
- * position will be in the range 7, 15, ..., 63. Turn this into byte
- * position by dividing by 8.
- */
- remainder = pg_rightmost_one_pos64(zero_byte_low) / BITS_PER_BYTE;
- fasthash_accum(hs, str, remainder);
- str += remainder;
+ if (zero_byte_low & 0xFF)
+ {
+ /*
+ * The next byte in the input is the NUL terminator, so we have
+ * nothing to do.
+ */
+ }
+ else
+ {
+ /*
+ * Create a mask for the remaining bytes so we can combine them into
+ * the hash. The mask also covers the NUL terminator, but that's
+ * harmless. The mask could contain 0x80 in bytes corresponding to the
+ * input past the terminator, but only where the input byte is zero or
+ * one, so also harmless.
+ */
+ mask = zero_byte_low | (zero_byte_low - 1);
+#ifdef WORDS_BIGENDIAN
+ /* need to mask the upper bytes */
+ mask = pg_bswap64(mask);
+#endif
+ hs->accum = chunk & mask;
+ fasthash_combine(hs);
+
+ /*
+ * The byte corresponding to the NUL will be 0x80, so the rightmost
+ * bit position will be in the range 15, 23, ..., 63. Turn this into
+ * byte position by dividing by 8.
+ */
+ str += pg_rightmost_one_pos64(zero_byte_low) / BITS_PER_BYTE;
+ }
return str - start;
}
--
2.43.0
