I spent some time rewriting the comments and a couple other cosmetic changes, and squashed into two patches: the second one has the optimized string hashing. They each have still just one demo use case. It looks pretty close to commitable, but I'll leave this up for a few days in case anyone wants to have another look.
After this first step is out of the way, we can look into using this more widely, including dynahash and the GUC hash.
From cff2bfda6a3067936ef17162a2db2609185afb24 Mon Sep 17 00:00:00 2001 From: John Naylor <john.nay...@postgresql.org> Date: Tue, 16 Jan 2024 16:32:48 +0700 Subject: [PATCH v14 2/2] Add optimized C string hashing Given an already-initialized hash state and a NUL-terminated string, accumulate the hash of the string into the hash state and return the length for the caller to (optionally) 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 NUL lookahead. The aligned case is only used on 64-bit platforms, since it's not worth the extra complexity for 32-bit. As demonstration, use this in the search path cache. This brings the general case performance closer to the optimization done in commit a86c61c9ee. There are other places that could benefit from this, but that is left for future work. Handling the tail of the string after finishing the word-wise loop was inspired by NetBSD's strlen(), but no code was taken since that is written in assembly language. Jeff Davis and John Naylor Discussion: https://postgr.es/m/3820f030fd008ff14134b3e9ce5cc6dd623ed479.camel%40j-davis.com Discussion: https://postgr.es/m/b40292c99e623defe5eadedab1d438cf51a4107c.camel%40j-davis.com --- src/backend/catalog/namespace.c | 20 +++-- src/include/common/hashfn_unstable.h | 130 +++++++++++++++++++++++++++ 2 files changed, 145 insertions(+), 5 deletions(-) diff --git a/src/backend/catalog/namespace.c b/src/backend/catalog/namespace.c index eecc50a958..b610aa6242 100644 --- a/src/backend/catalog/namespace.c +++ b/src/backend/catalog/namespace.c @@ -41,7 +41,7 @@ #include "catalog/pg_ts_template.h" #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" @@ -253,11 +253,21 @@ 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; - int blen = strlen(key.searchPath); + fasthash_state hs; + int sp_len; - return hash_combine(hash_bytes(bytes, blen), - hash_uint32(key.roleid)); + fasthash_init(&hs, FH_UNKNOWN_LENGTH, 0); + + hs.accum = key.roleid; + fasthash_combine(&hs); + + /* + * Combine search path into the hash and save the length for tweaking the + * final mix. + */ + sp_len = fasthash_accum_cstring(&hs, key.searchPath); + + 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 88fa613d4e..ff36114379 100644 --- a/src/include/common/hashfn_unstable.h +++ b/src/include/common/hashfn_unstable.h @@ -61,6 +61,24 @@ * 2) Incremental interface. This can used for incorporating multiple * inputs. The standalone functions use this internally, so see fasthash64() * for an an example of how this works. + * + * The incremental interface is especially useful if any of the inputs + * are NUL-terminated C strings, since the length is not needed ahead + * of time. This avoids needing to call strlen(). This case is optimized + * in fasthash_accum_cstring() : + * + * fasthash_state hs; + * fasthash_init(&hs, FH_UNKNOWN_LENGTH, 0); + * len = fasthash_accum_cstring(&hs, *str); + * ... + * return fasthash_final32(&hs, len); + * + * Here we pass FH_UNKNOWN_LENGTH as a convention, since passing zero + * would zero out the internal seed as well. fasthash_accum_cstring() + * returns the length of the string, which is computed on-the-fly while + * mixing the string into the hash. Experimentation has found that + * SMHasher fails unless we incorporate the length, so it is passed to + * the finalizer as a tweak. */ @@ -154,6 +172,118 @@ fasthash_accum(fasthash_state *hs, const char *k, int len) fasthash_combine(hs); } +/* + * Set high bit in lowest byte where the input is zero, from: + * https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord + */ +#define haszero64(v) \ + (((v) - 0x0101010101010101) & ~(v) & 0x8080808080808080) + +/* + * all-purpose workhorse for fasthash_accum_cstring + */ +static inline int +fasthash_accum_cstring_unaligned(fasthash_state *hs, const char *str) +{ + const char *const start = str; + + while (*str) + { + int chunk_len = 0; + + while (chunk_len < FH_SIZEOF_ACCUM && str[chunk_len] != '\0') + chunk_len++; + + fasthash_accum(hs, str, chunk_len); + str += chunk_len; + } + + return str - start; +} + +/* + * specialized workhorse 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. + */ +static inline int +fasthash_accum_cstring_aligned(fasthash_state *hs, const char *str) +{ + const char *const start = str; + int remainder; + uint64 zero_bytes_le; + + Assert(PointerIsAligned(start, uint64)); + for (;;) + { + uint64 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 + zero_bytes_le = haszero64(pg_bswap(chunk)); +#else + zero_bytes_le = haszero64(chunk); +#endif + if (zero_bytes_le) + break; + + hs->accum = chunk; + fasthash_combine(hs); + str += FH_SIZEOF_ACCUM; + } + + /* + * For the last word, only use bytes up to the NUL for the hash. 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 trailing (because + * little-endian) zeros and dividing the result by 8. + */ + remainder = pg_rightmost_one_pos64(zero_bytes_le) / BITS_PER_BYTE; + fasthash_accum(hs, str, remainder); + str += remainder; + + return str - start; +} + +/* + * Mix 'str' 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 >= 8 + + int len; +#ifdef USE_ASSERT_CHECKING + int len_check; + fasthash_state hs_check; + + 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 */ + + /* + * 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); +} + /* * The finalizer * -- 2.43.0
From 1f484009e93277525603acc4ece31412eaf173cb 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 v14 1/2] Add inline incremental hash functions for in-memory use It can be useful for a hash function to expose separate initialization, accumulation, and finalization steps. In particular, this is useful for building inline hash functions for simplehash. Instead of trying to whack around hash_bytes while maintaining its current behavior on all platforms, we base this work on fasthash (MIT licensed) which is simple, faster than hash_bytes for inputs over 12 bytes long, and also passes the hash function testing suite SMHasher. The fasthash functions have been reimplemented using our added-on incremental interface to validate that this method will still give the same answer, provided we have the input length ahead of time. This functionality lives in a new header hashfn_unstable.h. The name implies we have the freedom to change things across versions that would be unacceptable for our other hash functions that are used for e.g. hash indexes and hash partitioning. As such, these should only be used for in-memory data structures like hash tables. There is also no guarantee of being independent of endianness or pointer size. As demonstration, use fasthash for pgstat_hash_hash_key. Previously this called the 32-bit murmur finalizer on the three elements, then joined them with hash_combine(). The new function is simpler, faster and takes up less binary space. While the collision and bias behavior were almost certainly fine with the previous coding, now we have objective confidence of that. There are other places that could benefit from this, but that is left for future work. Reviewed by Jeff Davis, Heikki Linnakangas, Jian He, Junwang Zhao Credit to Andres Freund for the idea Discussion: https://postgr.es/m/20231122223432.lywt4yz2bn7tlp27%40awork3.anarazel.de Discussion: https://postgr.es/m/20231122223432.lywt4yz2bn7tlp27%40awork3.anarazel.de --- src/include/common/hashfn_unstable.h | 224 +++++++++++++++++++++++++++ src/include/utils/pgstat_internal.h | 11 +- src/tools/pgindent/typedefs.list | 1 + 3 files changed, 228 insertions(+), 8 deletions(-) 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..88fa613d4e --- /dev/null +++ b/src/include/common/hashfn_unstable.h @@ -0,0 +1,224 @@ +/* + * hashfn_unstable.h + * + * 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 written to disk and so must produce + * the same hashes between versions. + * + * The functions in this file are not guaranteed to be stable between + * versions, and may differ by hardware platform. + * + * + * Portions Copyright (c) 2024, PostgreSQL Global Development Group + * + * src/include/common/hashfn_unstable.h + */ +#ifndef HASHFN_UNSTABLE_H +#define HASHFN_UNSTABLE_H + +#include "port/pg_bitutils.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 + * under the terms of the MIT licencse. The original copyright + * notice follows: + */ + +/* 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. +*/ + +/* + * fasthash as implemented here has two interfaces: + * + * 1) Standalone functions, e.g. fasthash32() for a single value with a + * known length. + * + * 2) Incremental interface. This can used for incorporating multiple + * inputs. The standalone functions use this internally, so see fasthash64() + * for an an example of how this works. + */ + + +typedef struct fasthash_state +{ + /* staging area for chunks of input */ + uint64 accum; + + uint64 hash; +} fasthash_state; + +#define FH_SIZEOF_ACCUM sizeof(uint64) + +#define FH_UNKNOWN_LENGTH 1 + +/* + * Initialize the hash state. + * + * 'len' is the length of the input, if known ahead of time. + * If that is not known, pass FH_UNKNOWN_LENGTH. + * 'seed' can be zero. + */ +static inline void +fasthash_init(fasthash_state *hs, int len, uint64 seed) +{ + memset(hs, 0, sizeof(fasthash_state)); + hs->hash = seed ^ (len * 0x880355f21e6d1965); +} + +/* both the finalizer and part of the combining step */ +static inline uint64 +fasthash_mix(uint64 h, uint64 tweak) +{ + h ^= (h >> 23) + tweak; + h *= 0x2127599bf4325c37; + h ^= h >> 47; + return h; +} + +/* combine one chunk of input into the hash */ +static inline void +fasthash_combine(fasthash_state *hs) +{ + hs->hash ^= fasthash_mix(hs->accum, 0); + hs->hash *= 0x880355f21e6d1965; + + /* reset hash state for next input */ + hs->accum = 0; +} + +/* accumulate up to 8 bytes of input and combine it into the hash */ +static inline void +fasthash_accum(fasthash_state *hs, const char *k, int len) +{ + uint32 lower_four; + + 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: + memcpy(&lower_four, k, sizeof(lower_four)); + hs->accum |= lower_four; + break; + 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); +} + +/* + * The finalizer + * + * 'tweak' is intended to be the input length when the caller doesn't know + * the length ahead of time, such as for NUL-terminated strings, otherwise + * zero. + */ +static inline uint64 +fasthash_final64(fasthash_state *hs, uint64 tweak) +{ + return fasthash_mix(hs->hash, tweak); +} + +/* + * Reduce a 64-bit hash to a 32-bit hash. + * + * This optional step provides a bit more additional mixing compared to + * just taking the lower 32-bits. + */ +static inline uint32 +fasthash_reduce32(uint64 h) +{ + /* + * Convert the 64-bit hashcode to Fermat residue, which shall retain + * information from both the higher and lower parts of hashcode. + */ + return h - (h >> 32); +} + +/* finalize and reduce */ +static inline uint32 +fasthash_final32(fasthash_state *hs, uint64 tweak) +{ + return fasthash_reduce32(fasthash_final64(hs, tweak)); +} + +/* + * The original fasthash64 function, re-implemented using the incremental + * interface. Returns a 64-bit hashcode. 'len' controls not only how + * many bytes to hash, but also modifies the internal seed. + * 'seed' can be zero. + */ +static inline uint64 +fasthash64(const 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, 0); +} + +/* like fasthash64, but returns a 32-bit hashcode */ +static inline uint64 +fasthash32(const char *k, int len, uint64 seed) +{ + return fasthash_reduce32(fasthash64(k, len, seed)); +} + +#endif /* HASHFN_UNSTABLE_H */ diff --git a/src/include/utils/pgstat_internal.h b/src/include/utils/pgstat_internal.h index 9862589f36..207944f100 100644 --- a/src/include/utils/pgstat_internal.h +++ b/src/include/utils/pgstat_internal.h @@ -14,7 +14,7 @@ #define PGSTAT_INTERNAL_H -#include "common/hashfn.h" +#include "common/hashfn_unstable.h" #include "lib/dshash.h" #include "lib/ilist.h" #include "pgstat.h" @@ -776,16 +776,11 @@ pgstat_cmp_hash_key(const void *a, const void *b, size_t size, void *arg) static inline uint32 pgstat_hash_hash_key(const void *d, size_t size, void *arg) { - const PgStat_HashKey *key = (PgStat_HashKey *) d; - uint32 hash; + const char *key = (const char *) d; Assert(size == sizeof(PgStat_HashKey) && arg == NULL); - hash = murmurhash32(key->kind); - hash = hash_combine(hash, murmurhash32(key->dboid)); - hash = hash_combine(hash, murmurhash32(key->objoid)); - - return hash; + return fasthash32(key, size, 0); } /* diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list index 5fd46b7bd1..eb2e6b6309 100644 --- a/src/tools/pgindent/typedefs.list +++ b/src/tools/pgindent/typedefs.list @@ -3329,6 +3329,7 @@ exec_thread_arg execution_state explain_get_index_name_hook_type f_smgr +fasthash_state fd_set fe_scram_state fe_scram_state_enum -- 2.43.0
