Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commite97b672

Browse files
committed
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 usefulfor building inline hash functions for simplehash. Instead of tryingto whack around hash_bytes while maintaining its current behavior onall platforms, we base this work on fasthash (MIT licensed) whichis 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-onincremental interface to validate that this method will still givethe same answer, provided we have the input length ahead of time.This functionality lives in a new header hashfn_unstable.h. The nameimplies we have the freedom to change things across versions thatwould be unacceptable for our other hash functions that are used fore.g. hash indexes and hash partitioning. As such, these should onlybe used for in-memory data structures like hash tables. There is alsono guarantee of being independent of endianness or pointer size.As demonstration, use fasthash for pgstat_hash_hash_key. Previouslythis 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 biasbehavior were almost certainly fine with the previous coding, now wehave objective confidence of that.There are other places that could benefit from this, but that is leftfor future work.Reviewed by Jeff Davis, Heikki Linnakangas, Jian He, Junwang ZhaoCredit to Andres Freund for the ideaDiscussion:https://postgr.es/m/20231122223432.lywt4yz2bn7tlp27%40awork3.anarazel.de
1 parent04c0897 commite97b672

File tree

3 files changed

+225
-9
lines changed

3 files changed

+225
-9
lines changed

‎src/include/common/hashfn_unstable.h

Lines changed: 221 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,221 @@
1+
/*
2+
* hashfn_unstable.h
3+
*
4+
* Building blocks for creating fast inlineable hash functions. The
5+
* functions in this file are not guaranteed to be stable between versions,
6+
* and may differ by hardware platform. Hence they must not be used in
7+
* indexes or other on-disk structures. See hashfn.h if you need stability.
8+
*
9+
*
10+
* Portions Copyright (c) 2024, PostgreSQL Global Development Group
11+
*
12+
* src/include/common/hashfn_unstable.h
13+
*/
14+
#ifndefHASHFN_UNSTABLE_H
15+
#defineHASHFN_UNSTABLE_H
16+
17+
#include"port/pg_bitutils.h"
18+
#include"port/pg_bswap.h"
19+
20+
/*
21+
* fasthash is a modification of code taken from
22+
* https://code.google.com/archive/p/fast-hash/source/default/source
23+
* under the terms of the MIT license. The original copyright
24+
* notice follows:
25+
*/
26+
27+
/* The MIT License
28+
29+
Copyright (C) 2012 Zilong Tan (eric.zltan@gmail.com)
30+
31+
Permission is hereby granted, free of charge, to any person
32+
obtaining a copy of this software and associated documentation
33+
files (the "Software"), to deal in the Software without
34+
restriction, including without limitation the rights to use, copy,
35+
modify, merge, publish, distribute, sublicense, and/or sell copies
36+
of the Software, and to permit persons to whom the Software is
37+
furnished to do so, subject to the following conditions:
38+
39+
The above copyright notice and this permission notice shall be
40+
included in all copies or substantial portions of the Software.
41+
42+
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
43+
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
44+
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
45+
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
46+
BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
47+
ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
48+
CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
49+
SOFTWARE.
50+
*/
51+
52+
/*
53+
* fasthash as implemented here has two interfaces:
54+
*
55+
* 1) Standalone functions, e.g. fasthash32() for a single value with a
56+
* known length.
57+
*
58+
* 2) Incremental interface. This can used for incorporating multiple
59+
* inputs. The standalone functions use this internally, so see fasthash64()
60+
* for an an example of how this works.
61+
*/
62+
63+
64+
typedefstructfasthash_state
65+
{
66+
/* staging area for chunks of input */
67+
uint64accum;
68+
69+
uint64hash;
70+
}fasthash_state;
71+
72+
#defineFH_SIZEOF_ACCUM sizeof(uint64)
73+
74+
#defineFH_UNKNOWN_LENGTH 1
75+
76+
/*
77+
* Initialize the hash state.
78+
*
79+
* 'len' is the length of the input, if known ahead of time.
80+
* If that is not known, pass FH_UNKNOWN_LENGTH.
81+
* 'seed' can be zero.
82+
*/
83+
staticinlinevoid
84+
fasthash_init(fasthash_state*hs,intlen,uint64seed)
85+
{
86+
memset(hs,0,sizeof(fasthash_state));
87+
hs->hash=seed ^ (len*0x880355f21e6d1965);
88+
}
89+
90+
/* both the finalizer and part of the combining step */
91+
staticinlineuint64
92+
fasthash_mix(uint64h,uint64tweak)
93+
{
94+
h ^= (h >>23)+tweak;
95+
h *=0x2127599bf4325c37;
96+
h ^=h >>47;
97+
returnh;
98+
}
99+
100+
/* combine one chunk of input into the hash */
101+
staticinlinevoid
102+
fasthash_combine(fasthash_state*hs)
103+
{
104+
hs->hash ^=fasthash_mix(hs->accum,0);
105+
hs->hash *=0x880355f21e6d1965;
106+
107+
/* reset hash state for next input */
108+
hs->accum=0;
109+
}
110+
111+
/* accumulate up to 8 bytes of input and combine it into the hash */
112+
staticinlinevoid
113+
fasthash_accum(fasthash_state*hs,constchar*k,intlen)
114+
{
115+
uint32lower_four;
116+
117+
Assert(hs->accum==0);
118+
Assert(len <=FH_SIZEOF_ACCUM);
119+
120+
switch (len)
121+
{
122+
case8:
123+
memcpy(&hs->accum,k,8);
124+
break;
125+
case7:
126+
hs->accum |= (uint64)k[6] <<48;
127+
/* FALLTHROUGH */
128+
case6:
129+
hs->accum |= (uint64)k[5] <<40;
130+
/* FALLTHROUGH */
131+
case5:
132+
hs->accum |= (uint64)k[4] <<32;
133+
/* FALLTHROUGH */
134+
case4:
135+
memcpy(&lower_four,k,sizeof(lower_four));
136+
hs->accum |=lower_four;
137+
break;
138+
case3:
139+
hs->accum |= (uint64)k[2] <<16;
140+
/* FALLTHROUGH */
141+
case2:
142+
hs->accum |= (uint64)k[1] <<8;
143+
/* FALLTHROUGH */
144+
case1:
145+
hs->accum |= (uint64)k[0];
146+
break;
147+
case0:
148+
return;
149+
}
150+
151+
fasthash_combine(hs);
152+
}
153+
154+
/*
155+
* The finalizer
156+
*
157+
* 'tweak' is intended to be the input length when the caller doesn't know
158+
* the length ahead of time, such as for NUL-terminated strings, otherwise
159+
* zero.
160+
*/
161+
staticinlineuint64
162+
fasthash_final64(fasthash_state*hs,uint64tweak)
163+
{
164+
returnfasthash_mix(hs->hash,tweak);
165+
}
166+
167+
/*
168+
* Reduce a 64-bit hash to a 32-bit hash.
169+
*
170+
* This optional step provides a bit more additional mixing compared to
171+
* just taking the lower 32-bits.
172+
*/
173+
staticinlineuint32
174+
fasthash_reduce32(uint64h)
175+
{
176+
/*
177+
* Convert the 64-bit hashcode to Fermat residue, which shall retain
178+
* information from both the higher and lower parts of hashcode.
179+
*/
180+
returnh- (h >>32);
181+
}
182+
183+
/* finalize and reduce */
184+
staticinlineuint32
185+
fasthash_final32(fasthash_state*hs,uint64tweak)
186+
{
187+
returnfasthash_reduce32(fasthash_final64(hs,tweak));
188+
}
189+
190+
/*
191+
* The original fasthash64 function, re-implemented using the incremental
192+
* interface. Returns a 64-bit hashcode. 'len' controls not only how
193+
* many bytes to hash, but also modifies the internal seed.
194+
* 'seed' can be zero.
195+
*/
196+
staticinlineuint64
197+
fasthash64(constchar*k,intlen,uint64seed)
198+
{
199+
fasthash_statehs;
200+
201+
fasthash_init(&hs,len,seed);
202+
203+
while (len >=FH_SIZEOF_ACCUM)
204+
{
205+
fasthash_accum(&hs,k,FH_SIZEOF_ACCUM);
206+
k+=FH_SIZEOF_ACCUM;
207+
len-=FH_SIZEOF_ACCUM;
208+
}
209+
210+
fasthash_accum(&hs,k,len);
211+
returnfasthash_final64(&hs,0);
212+
}
213+
214+
/* like fasthash64, but returns a 32-bit hashcode */
215+
staticinlineuint64
216+
fasthash32(constchar*k,intlen,uint64seed)
217+
{
218+
returnfasthash_reduce32(fasthash64(k,len,seed));
219+
}
220+
221+
#endif/* HASHFN_UNSTABLE_H */

‎src/include/utils/pgstat_internal.h

Lines changed: 3 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -14,7 +14,7 @@
1414
#definePGSTAT_INTERNAL_H
1515

1616

17-
#include"common/hashfn.h"
17+
#include"common/hashfn_unstable.h"
1818
#include"lib/dshash.h"
1919
#include"lib/ilist.h"
2020
#include"pgstat.h"
@@ -776,16 +776,10 @@ pgstat_cmp_hash_key(const void *a, const void *b, size_t size, void *arg)
776776
staticinlineuint32
777777
pgstat_hash_hash_key(constvoid*d,size_tsize,void*arg)
778778
{
779-
constPgStat_HashKey*key= (PgStat_HashKey*)d;
780-
uint32hash;
779+
constchar*key= (constchar*)d;
781780

782781
Assert(size==sizeof(PgStat_HashKey)&&arg==NULL);
783-
784-
hash=murmurhash32(key->kind);
785-
hash=hash_combine(hash,murmurhash32(key->dboid));
786-
hash=hash_combine(hash,murmurhash32(key->objoid));
787-
788-
returnhash;
782+
returnfasthash32(key,size,0);
789783
}
790784

791785
/*

‎src/tools/pgindent/typedefs.list

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3328,6 +3328,7 @@ exec_thread_arg
33283328
execution_state
33293329
explain_get_index_name_hook_type
33303330
f_smgr
3331+
fasthash_state
33313332
fd_set
33323333
fe_scram_state
33333334
fe_scram_state_enum

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp