I wrote:
> On Sun, Dec 10, 2023 at 2:18 AM Jeff Davis <pg...@j-davis.com> wrote:
> >
> > On Sat, 2023-12-09 at 18:52 +0700, John Naylor wrote:
> > > > I tested using the new hash function APIs for my search path cache,
> > > > and
> > > > there's a significant speedup for cases not benefiting from
> > > > a86c61c9ee.
> > > > It's enough that we almost don't need a86c61c9ee. So a definite +1
> > > > to
> > > > the new APIs.
>
> Interesting, thanks for testing! SearchPathCache is a better starting
> point than dynahash for removing strlen calls anyway -- it's more
> localized, uses simplehash, and we can test it with at-hand tests.
Since I had to fix a misalignment in the original to keep ubsan from
crashing CI anyway (v8-0005), I thought I'd take the experiment with
search path cache and put the temporary validation of the hash
function output in there (v8-0004). I had to finagle a bit to get the
bytewise interface to give the same answer as the original, but that's
okay: The bytewise interface is intended for when we don't know the
length up front (and therefore the internal seed can't be tweaked with
the length), but it's nice to make sure nothing's broken.
There is also a chunkwise version for search path cache. That might be
a little faster. Perf testing can be done as is, because I put the
validation in assert builds only.
I've left out the GUC stuff for now, just want to get CI green again.
From 54e6419a632b04d97cad847603035050ab48c84f Mon Sep 17 00:00:00 2001
From: John Naylor <john.nay...@postgresql.org>
Date: Sat, 9 Dec 2023 16:32:05 +0700
Subject: [PATCH v8 3/5] Add bytewise interface
This is useful for hashing values with unknown length,
like NUL-terminated strings. It should be faster than calling
strlen() first and passing the length, which most hash
functions require.
Note: This method can't give the same answer as
regular fasthash, so it will need to be evaluated. It's possible
we need to mix in the length at the finalization step (at which
time can know the length), in order to safeguard against
collisions.
---
src/include/common/hashfn_unstable.h | 19 +++++++++++++++++++
1 file changed, 19 insertions(+)
diff --git a/src/include/common/hashfn_unstable.h b/src/include/common/hashfn_unstable.h
index fbae7a5522..80aec98dc9 100644
--- a/src/include/common/hashfn_unstable.h
+++ b/src/include/common/hashfn_unstable.h
@@ -49,6 +49,7 @@ typedef struct fasthash_state
{
uint64 accum;
#define FH_SIZEOF_ACCUM sizeof(uint64)
+ int8 accum_len;
uint64 hash;
} fasthash_state;
@@ -69,6 +70,7 @@ fasthash_combine(fasthash_state* hs)
/* reset hash state for next input */
hs->accum = 0;
+ hs->accum_len = 0;
}
static inline void
@@ -82,6 +84,18 @@ fasthash_init(fasthash_state *hs, int len, uint64 seed)
hs->hash = seed ^ (len * 0x880355f21e6d1965ULL);
}
+static inline void
+fasthash_accum_byte(fasthash_state *hs, const unsigned char ch)
+{
+ hs->accum <<= BITS_PER_BYTE;
+ hs->accum |= ch;
+ hs->accum_len++;
+
+ // wip: is there a better way to get sizeof struct member?
+ if (hs->accum_len == sizeof(((fasthash_state *) 0)->accum))
+ fasthash_combine(hs);
+}
+
static inline void
fasthash_accum(fasthash_state *hs, const unsigned char *k, int len)
{
@@ -117,6 +131,11 @@ fasthash_accum(fasthash_state *hs, const unsigned char *k, int len)
static inline uint64
fasthash_final64(fasthash_state *hs)
{
+ // check for remaining bytes to combine into hash
+ // should only be used by the bytewise interface
+ if (hs->accum_len > 0)
+ fasthash_combine(hs);
+
return fasthash_mix(hs->hash);
}
--
2.43.0
From f5ab683d61724e9766d43e58c6f3177a30f708d0 Mon Sep 17 00:00:00 2001
From: John Naylor <john.nay...@postgresql.org>
Date: Sun, 10 Dec 2023 12:11:37 +0700
Subject: [PATCH v8 2/5] Rewrite fasthash functions using a homegrown
incremental interface
The incremental interface will be useful for cases we don't know
the length up front, such as NUL-terminated strings. First, we
need to validate that this interface can give the same answer
as the original functions when we do know the length. A future
commit will add a temporary assert for testing in CI.
---
src/include/common/hashfn_unstable.h | 161 +++++++++++++++++++++++++--
1 file changed, 153 insertions(+), 8 deletions(-)
diff --git a/src/include/common/hashfn_unstable.h b/src/include/common/hashfn_unstable.h
index a5bf965fa2..fbae7a5522 100644
--- a/src/include/common/hashfn_unstable.h
+++ b/src/include/common/hashfn_unstable.h
@@ -1,3 +1,25 @@
+/*
+Building blocks for creating fast inlineable hash functions. The
+unstable designation is in contrast to hashfn.h, which cannot break
+compatibility because hashes can be writen to disk and so must have
+the same hashes between versions.
+
+ *
+ * Portions Copyright (c) 2018-2023, PostgreSQL Global Development Group
+ *
+ * src/include/common/hashfn_unstable.c
+ */
+
+#ifndef HASHFN_UNSTABLE_H
+#define HASHFN_UNSTABLE_H
+
+/*
+ * fasthash is a modification of code taken from
+ * https://code.google.com/archive/p/fast-hash/source/default/source
+ * under the terms of the MIT licencse. The original copyright
+ * notice follows:
+ */
+
/* The MIT License
Copyright (C) 2012 Zilong Tan (eric.zl...@gmail.com)
@@ -23,16 +45,130 @@
SOFTWARE.
*/
-#include "fasthash.h"
+typedef struct fasthash_state
+{
+ uint64 accum;
+#define FH_SIZEOF_ACCUM sizeof(uint64)
+ uint64 hash;
+} fasthash_state;
+
+static inline uint64
+fasthash_mix(uint64 h)
+{
+ h ^= h >> 23;
+ h *= 0x2127599bf4325c37ULL;
+ h ^= h >> 47;
+ return h;
+}
+
+static inline void
+fasthash_combine(fasthash_state* hs)
+{
+ hs->hash ^= fasthash_mix(hs->accum);
+ hs->hash *= 0x880355f21e6d1965ULL;
+
+ /* reset hash state for next input */
+ hs->accum = 0;
+}
+
+static inline void
+fasthash_init(fasthash_state *hs, int len, uint64 seed)
+{
+ memset(hs, 0, sizeof(fasthash_state));
+
+ // since we don't know the length for a nul-terminated string
+ // handle some other way -- maybe we can accum the length in
+ // the state and fold it in during the finalizer (cf. xxHash3)
+ hs->hash = seed ^ (len * 0x880355f21e6d1965ULL);
+}
+
+static inline void
+fasthash_accum(fasthash_state *hs, const unsigned char *k, int len)
+{
+ Assert(hs->accum == 0);
+ Assert(len <= FH_SIZEOF_ACCUM);
+
+ switch (len)
+ {
+ case 8: memcpy(&hs->accum, k, 8);
+ break;
+ case 7: hs->accum |= (uint64) k[6] << 48;
+ /* FALLTHROUGH */
+ case 6: hs->accum |= (uint64) k[5] << 40;
+ /* FALLTHROUGH */
+ case 5: hs->accum |= (uint64) k[4] << 32;
+ /* FALLTHROUGH */
+ case 4: hs->accum |= (uint64) k[3] << 24;
+ /* FALLTHROUGH */
+ case 3: hs->accum |= (uint64) k[2] << 16;
+ /* FALLTHROUGH */
+ case 2: hs->accum |= (uint64) k[1] << 8;
+ /* FALLTHROUGH */
+ case 1: hs->accum |= (uint64) k[0];
+ break;
+ case 0:
+ return;
+ }
+
+ fasthash_combine(hs);
+}
+
+
+static inline uint64
+fasthash_final64(fasthash_state *hs)
+{
+ return fasthash_mix(hs->hash);
+}
+
+static inline uint32
+fasthash_final32(fasthash_state *hs)
+{
+ // the following trick converts the 64-bit hashcode to Fermat
+ // residue, which shall retain information from both the higher
+ // and lower parts of hashcode.
+ uint64 h = fasthash_final64(hs);
+ return h - (h >> 32);
+}
+
+static inline uint64
+fasthash64(const unsigned char * k, int len, uint64 seed)
+{
+ fasthash_state hs;
+
+ fasthash_init(&hs, len, seed);
+
+ while (len >= FH_SIZEOF_ACCUM)
+ {
+ fasthash_accum(&hs, k, FH_SIZEOF_ACCUM);
+ k += FH_SIZEOF_ACCUM;
+ len -= FH_SIZEOF_ACCUM;
+ }
+
+ fasthash_accum(&hs, k, len);
+ return fasthash_final64(&hs);
+}
+
+static inline uint64
+fasthash32(const unsigned char * k, int len, uint64 seed)
+{
+ uint64 h = fasthash64(k, len, seed);
+ return h - (h >> 32);
+}
+
+
+// XXX NOT FOR COMMIT
// Compression function for Merkle-Damgard construction.
// This function is generated using the framework provided.
-#define mix(h) ({ \
- (h) ^= (h) >> 23; \
- (h) *= 0x2127599bf4325c37ULL; \
- (h) ^= (h) >> 47; })
+static inline uint64_t mix(uint64_t h) {
+ h ^= h >> 23;
+ h *= 0x2127599bf4325c37ULL;
+ h ^= h >> 47;
+ return h;
+}
-uint64_t fasthash64(const void *buf, size_t len, uint64_t seed)
+static inline
+uint64_t fasthash64_orig(const void *buf, size_t len, uint64_t seed)
{
const uint64_t m = 0x880355f21e6d1965ULL;
const uint64_t *pos = (const uint64_t *)buf;
@@ -52,11 +188,17 @@ uint64_t fasthash64(const void *buf, size_t len, uint64_t seed)
switch (len & 7) {
case 7: v ^= (uint64_t)pos2[6] << 48;
+ /* FALLTHROUGH */
case 6: v ^= (uint64_t)pos2[5] << 40;
+ /* FALLTHROUGH */
case 5: v ^= (uint64_t)pos2[4] << 32;
+ /* FALLTHROUGH */
case 4: v ^= (uint64_t)pos2[3] << 24;
+ /* FALLTHROUGH */
case 3: v ^= (uint64_t)pos2[2] << 16;
+ /* FALLTHROUGH */
case 2: v ^= (uint64_t)pos2[1] << 8;
+ /* FALLTHROUGH */
case 1: v ^= (uint64_t)pos2[0];
h ^= mix(v);
h *= m;
@@ -65,11 +207,14 @@ uint64_t fasthash64(const void *buf, size_t len, uint64_t seed)
return mix(h);
}
-uint32_t fasthash32(const void *buf, size_t len, uint32_t seed)
+static inline
+uint32_t fasthash32_orig(const void *buf, size_t len, uint32_t seed)
{
// the following trick converts the 64-bit hashcode to Fermat
// residue, which shall retain information from both the higher
// and lower parts of hashcode.
- uint64_t h = fasthash64(buf, len, seed);
+ uint64_t h = fasthash64_orig(buf, len, seed);
return h - (h >> 32);
}
+
+#endif /* HASHFN_UNSTABLE_H */
--
2.43.0
From 90b5aa53284604b7a592f49a7e8424051e681da0 Mon Sep 17 00:00:00 2001
From: John Naylor <john.nay...@postgresql.org>
Date: Sun, 10 Dec 2023 15:14:24 +0700
Subject: [PATCH v8 4/5] Assert that the fasthash variants give (or can give)
the same answer as the original
Test that incremental hashing gives the right answer for strings
Use the initial length only for the init step. Test that
we can ignore the length afterwards, and only use the
presence of the NUL terminator to stop iterating. Assert
that this results in the same hash.
Based on "Use new hash APIs for search path cache" by Jeff Davis,
rebased over v7.
---
src/backend/catalog/namespace.c | 56 ++++++++++++++++++++++++++--
src/include/common/hashfn_unstable.h | 18 ++++++++-
2 files changed, 69 insertions(+), 5 deletions(-)
diff --git a/src/backend/catalog/namespace.c b/src/backend/catalog/namespace.c
index 5027efc91d..afbfaf5dd4 100644
--- a/src/backend/catalog/namespace.c
+++ b/src/backend/catalog/namespace.c
@@ -42,6 +42,7 @@
#include "catalog/pg_type.h"
#include "commands/dbcommands.h"
#include "common/hashfn.h"
+#include "common/hashfn_unstable.h"
#include "funcapi.h"
#include "mb/pg_wchar.h"
#include "miscadmin.h"
@@ -247,11 +248,60 @@ static bool MatchNamedCall(HeapTuple proctup, int nargs, List *argnames,
static inline uint32
spcachekey_hash(SearchPathCacheKey key)
{
- const unsigned char *bytes = (const unsigned char *) key.searchPath;
+ const char *buf = key.searchPath;
+ fasthash_state hs;
+
+ // XXX not for commit
+#ifdef USE_ASSERT_CHECKING
int blen = strlen(key.searchPath);
- return hash_combine(hash_bytes(bytes, blen),
- hash_uint32(key.roleid));
+ uint64 h_orig = fasthash64_orig(buf, blen, key.roleid);
+
+ // check full function that calls incremental interface
+ Assert(fasthash64((const unsigned char *) buf, blen, key.roleid) == h_orig);
+
+ // Test that bytewise interface can give the same answer,
+ // if we have length up front. We would typically use it
+ // for cases where we don't know, but let's try to make
+ // it as similar as conveniently possible.
+ fasthash_init(&hs, blen, key.roleid);
+ while (*buf)
+ {
+ fasthash_accum_byte(&hs, *buf);
+ buf++;
+ }
+ Assert(fasthash_final64(&hs) == h_orig);
+ buf = key.searchPath; /* reset */
+
+ // Now compare chunked incremental interface
+ fasthash_init(&hs, blen, key.roleid);
+ while (*buf)
+ {
+ int chunk_len = 0;
+
+ while(chunk_len < FH_SIZEOF_ACCUM && buf[chunk_len] != '\0')
+ chunk_len++;
+
+ fasthash_accum(&hs, (const unsigned char *) buf, chunk_len);
+ buf += chunk_len;
+ }
+ Assert(fasthash_final64(&hs) == h_orig);
+ buf = key.searchPath; /* reset */
+#endif
+
+ // TODO: Test if chunked accum has better performance
+
+ // WIP: maybe roleid should be mixed in normally
+ // WIP: For now fake the length to preserve the internal seed
+ fasthash_init(&hs, 1, key.roleid);
+ while (*buf)
+ {
+ fasthash_accum_byte(&hs, *buf);
+ buf++;
+ }
+
+ // WIP: consider returning lower 32 bits, rather than mixing the high bits with the lower
+ return fasthash_final32(&hs);
}
static inline bool
diff --git a/src/include/common/hashfn_unstable.h b/src/include/common/hashfn_unstable.h
index 80aec98dc9..13d6d70910 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_bswap.h"
+
/*
* fasthash is a modification of code taken from
* https://code.google.com/archive/p/fast-hash/source/default/source
@@ -91,9 +93,14 @@ fasthash_accum_byte(fasthash_state *hs, const unsigned char ch)
hs->accum |= ch;
hs->accum_len++;
- // wip: is there a better way to get sizeof struct member?
- if (hs->accum_len == sizeof(((fasthash_state *) 0)->accum))
+ if (hs->accum_len == FH_SIZEOF_ACCUM)
+ {
+#ifdef USE_ASSERT_CHECKING
+ // XXX not for commit
+ hs->accum = pg_bswap64(hs->accum);
+#endif
fasthash_combine(hs);
+ }
}
static inline void
@@ -134,7 +141,14 @@ fasthash_final64(fasthash_state *hs)
// check for remaining bytes to combine into hash
// should only be used by the bytewise interface
if (hs->accum_len > 0)
+ {
+#ifdef USE_ASSERT_CHECKING
+ // XXX not for commit
+ hs->accum <<= ((FH_SIZEOF_ACCUM - hs->accum_len) * BITS_PER_BYTE);
+ hs->accum = pg_bswap64(hs->accum);
+#endif
fasthash_combine(hs);
+ }
return fasthash_mix(hs->hash);
}
--
2.43.0
From 2f452e621a07433a4f539614d7b7c09eef29b1e8 Mon Sep 17 00:00:00 2001
From: John Naylor <john.nay...@postgresql.org>
Date: Sun, 10 Dec 2023 21:27:13 +0700
Subject: [PATCH v8 5/5] Fix alignment issue in the original fastash
Found by UBSan in CI
---
src/include/common/hashfn_unstable.h | 3 ++-
1 file changed, 2 insertions(+), 1 deletion(-)
diff --git a/src/include/common/hashfn_unstable.h b/src/include/common/hashfn_unstable.h
index 13d6d70910..a13d577965 100644
--- a/src/include/common/hashfn_unstable.h
+++ b/src/include/common/hashfn_unstable.h
@@ -211,9 +211,10 @@ uint64_t fasthash64_orig(const void *buf, size_t len, uint64_t seed)
uint64_t v;
while (pos != end) {
- v = *pos++;
+ memcpy(&v, pos, 8);
h ^= mix(v);
h *= m;
+ pos++;
}
pos2 = (const unsigned char*)pos;
--
2.43.0
From 4258073d786d338da788a9290ddc29aefd1aad78 Mon Sep 17 00:00:00 2001
From: John Naylor <john.nay...@postgresql.org>
Date: Mon, 27 Nov 2023 17:03:38 +0700
Subject: [PATCH v8 1/5] Vendor fasthash
MIT licensed
---
src/include/common/hashfn_unstable.h | 75 ++++++++++++++++++++++++++++
1 file changed, 75 insertions(+)
create mode 100644 src/include/common/hashfn_unstable.h
diff --git a/src/include/common/hashfn_unstable.h b/src/include/common/hashfn_unstable.h
new file mode 100644
index 0000000000..a5bf965fa2
--- /dev/null
+++ b/src/include/common/hashfn_unstable.h
@@ -0,0 +1,75 @@
+/* The MIT License
+
+ Copyright (C) 2012 Zilong Tan (eric.zl...@gmail.com)
+
+ Permission is hereby granted, free of charge, to any person
+ obtaining a copy of this software and associated documentation
+ files (the "Software"), to deal in the Software without
+ restriction, including without limitation the rights to use, copy,
+ modify, merge, publish, distribute, sublicense, and/or sell copies
+ of the Software, and to permit persons to whom the Software is
+ furnished to do so, subject to the following conditions:
+
+ The above copyright notice and this permission notice shall be
+ included in all copies or substantial portions of the Software.
+
+ THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
+ BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
+ ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+ CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ SOFTWARE.
+*/
+
+#include "fasthash.h"
+
+// Compression function for Merkle-Damgard construction.
+// This function is generated using the framework provided.
+#define mix(h) ({ \
+ (h) ^= (h) >> 23; \
+ (h) *= 0x2127599bf4325c37ULL; \
+ (h) ^= (h) >> 47; })
+
+uint64_t fasthash64(const void *buf, size_t len, uint64_t seed)
+{
+ const uint64_t m = 0x880355f21e6d1965ULL;
+ const uint64_t *pos = (const uint64_t *)buf;
+ const uint64_t *end = pos + (len / 8);
+ const unsigned char *pos2;
+ uint64_t h = seed ^ (len * m);
+ uint64_t v;
+
+ while (pos != end) {
+ v = *pos++;
+ h ^= mix(v);
+ h *= m;
+ }
+
+ pos2 = (const unsigned char*)pos;
+ v = 0;
+
+ switch (len & 7) {
+ case 7: v ^= (uint64_t)pos2[6] << 48;
+ case 6: v ^= (uint64_t)pos2[5] << 40;
+ case 5: v ^= (uint64_t)pos2[4] << 32;
+ case 4: v ^= (uint64_t)pos2[3] << 24;
+ case 3: v ^= (uint64_t)pos2[2] << 16;
+ case 2: v ^= (uint64_t)pos2[1] << 8;
+ case 1: v ^= (uint64_t)pos2[0];
+ h ^= mix(v);
+ h *= m;
+ }
+
+ return mix(h);
+}
+
+uint32_t fasthash32(const void *buf, size_t len, uint32_t seed)
+{
+ // the following trick converts the 64-bit hashcode to Fermat
+ // residue, which shall retain information from both the higher
+ // and lower parts of hashcode.
+ uint64_t h = fasthash64(buf, len, seed);
+ return h - (h >> 32);
+}
--
2.43.0
