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

Commitab9f2c4

Browse files
committed
Prevent growth of simplehash tables when they're "too empty".
In cases where simplehash tables where filled with either a lot ofconflicting hash-values, or values that hash to consecutivevalues (i.e. build "chains") the growth heuristics ind4c62a6 could trigger ratherexplosively.To fix that, address some of the reasons (see previous commit) of whythe growth heuristics where needed, and only allow growth when thetable isn't too empty. While that means there's a few cases of badinput that can be slower, that seems a lot better than running veryquickly out of memory.Author: Tomas Vondra and Andres Freund, with additional input by Thomas Munro, Tom Lane Todd A. CookReported-By: Todd A. Cook, Tomas Vondra, Thomas MunroDiscussion:https://postgr.es/m/20171127185700.1470.20362@wrigleys.postgresql.orgBackpatch: 10, where simplehash was introduced
1 parentc068f87 commitab9f2c4

File tree

1 file changed

+15
-4
lines changed

1 file changed

+15
-4
lines changed

‎src/include/lib/simplehash.h

Lines changed: 15 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -174,6 +174,10 @@ SH_SCOPE void SH_STAT(SH_TYPE * tb);
174174
#ifndefSH_GROW_MAX_MOVE
175175
#defineSH_GROW_MAX_MOVE 150
176176
#endif
177+
#ifndefSH_GROW_MIN_FILLFACTOR
178+
/* but do not grow due to SH_GROW_MAX_* if below */
179+
#defineSH_GROW_MIN_FILLFACTOR 0.1
180+
#endif
177181

178182
#ifdefSH_STORE_HASH
179183
#defineSH_COMPARE_KEYS(tb,ahash,akey,b) (ahash == SH_GET_HASH(tb, b) && SH_EQUAL(tb, b->SH_KEY, akey))
@@ -574,9 +578,12 @@ SH_INSERT(SH_TYPE * tb, SH_KEY_TYPE key, bool *found)
574578
* hashtables, grow the hashtable if collisions would require
575579
* us to move a lot of entries. The most likely cause of such
576580
* imbalance is filling a (currently) small table, from a
577-
* currently big one, in hash-table order.
581+
* currently big one, in hash-table order. Don't grow if the
582+
* hashtable would be too empty, to prevent quick space
583+
* explosion for some weird edge cases.
578584
*/
579-
if (++emptydist>SH_GROW_MAX_MOVE)
585+
if (unlikely(++emptydist>SH_GROW_MAX_MOVE)&&
586+
((double)tb->members /tb->size) >=SH_GROW_MIN_FILLFACTOR)
580587
{
581588
tb->grow_threshold=0;
582589
gotorestart;
@@ -621,9 +628,12 @@ SH_INSERT(SH_TYPE * tb, SH_KEY_TYPE key, bool *found)
621628
* To avoid negative consequences from overly imbalanced hashtables,
622629
* grow the hashtable if collisions lead to large runs. The most
623630
* likely cause of such imbalance is filling a (currently) small
624-
* table, from a currently big one, in hash-table order.
631+
* table, from a currently big one, in hash-table order. Don't grow
632+
* if the hashtable would be too empty, to prevent quick space
633+
* explosion for some weird edge cases.
625634
*/
626-
if (insertdist>SH_GROW_MAX_DIB)
635+
if (unlikely(insertdist>SH_GROW_MAX_DIB)&&
636+
((double)tb->members /tb->size) >=SH_GROW_MIN_FILLFACTOR)
627637
{
628638
tb->grow_threshold=0;
629639
gotorestart;
@@ -923,6 +933,7 @@ SH_STAT(SH_TYPE * tb)
923933
#undef SH_MAX_FILLFACTOR
924934
#undef SH_GROW_MAX_DIB
925935
#undef SH_GROW_MAX_MOVE
936+
#undef SH_GROW_MIN_FILLFACTOR
926937
#undef SH_MAX_SIZE
927938

928939
/* types */

0 commit comments

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