Skip to content

Commit be0a666

Browse files
macdicemacdice
committed
Remove large fill factor support from dynahash.c.
Since ancient times we have had support for a fill factor (maximum load factor) to be set for a dynahash hash table, but: 1. It was an integer, whereas for in-memory hash tables interesting load factor targets are probably somewhere near the 0.75-1.0 range. 2. It was implemented in a way that performed an expensive division operation that regularly showed up in profiles. 3. We are not aware of anyone ever having used a non-default value. Therefore, remove support, effectively fixing it at 1. Author: Jakub Wartak <Jakub.Wartak@tomtom.com> Reviewed-by: Alvaro Herrera <alvherre@2ndquadrant.com> Reviewed-by: Tomas Vondra <tomas.vondra@2ndquadrant.com> Reviewed-by: Thomas Munro <thomas.munro@gmail.com> Reviewed-by: David Rowley <dgrowleyml@gmail.com> Discussion: https://postgr.es/m/VI1PR0701MB696044FC35013A96FECC7AC8F62D0%40VI1PR0701MB6960.eurprd07.prod.outlook.com
1 parent 06a7c31 commit be0a666

File tree

2 files changed

+6
-16
lines changed

2 files changed

+6
-16
lines changed

‎src/backend/utils/hash/dynahash.c

Lines changed: 6 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -122,7 +122,6 @@
122122
#define DEF_SEGSIZE 256
123123
#define DEF_SEGSIZE_SHIFT 8 /* must be log2(DEF_SEGSIZE) */
124124
#define DEF_DIRSIZE 256
125-
#define DEF_FFACTOR 1 /* default fill factor */
126125

127126
/* Number of freelists to be used for a partitioned hash table. */
128127
#define NUM_FREELISTS 32
@@ -191,7 +190,6 @@ struct HASHHDR
191190
Size keysize; /* hash key length in bytes */
192191
Size entrysize; /* total user element size in bytes */
193192
long num_partitions; /* # partitions (must be power of 2), or 0 */
194-
long ffactor; /* target fill factor */
195193
long max_dsize; /* 'dsize' limit if directory is fixed size */
196194
long ssize; /* segment size --- must be power of 2 */
197195
int sshift; /* segment shift = log2(ssize) */
@@ -497,8 +495,6 @@ hash_create(const char *tabname, long nelem, HASHCTL *info, int flags)
497495
/* ssize had better be a power of 2 */
498496
Assert(hctl->ssize == (1L << hctl->sshift));
499497
}
500-
if (flags & HASH_FFACTOR)
501-
hctl->ffactor = info->ffactor;
502498

503499
/*
504500
* SHM hash tables have fixed directory size passed by the caller.
@@ -603,8 +599,6 @@ hdefault(HTAB *hashp)
603599

604600
hctl->num_partitions = 0; /* not partitioned */
605601

606-
hctl->ffactor = DEF_FFACTOR;
607-
608602
/* table has no fixed maximum size */
609603
hctl->max_dsize = NO_MAX_DSIZE;
610604

@@ -670,11 +664,10 @@ init_htab(HTAB *hashp, long nelem)
670664
SpinLockInit(&(hctl->freeList[i].mutex));
671665

672666
/*
673-
* Divide number of elements by the fill factor to determine a desired
674-
* number of buckets. Allocate space for the next greater power of two
675-
* number of buckets
667+
* Allocate space for the next greater power of two number of buckets,
668+
* assuming a desired maximum load factor of 1.
676669
*/
677-
nbuckets = next_pow2_int((nelem - 1) / hctl->ffactor + 1);
670+
nbuckets = next_pow2_int(nelem);
678671

679672
/*
680673
* In a partitioned table, nbuckets must be at least equal to
@@ -733,7 +726,6 @@ init_htab(HTAB *hashp, long nelem)
733726
"DIRECTORY SIZE ", hctl->dsize,
734727
"SEGMENT SIZE ", hctl->ssize,
735728
"SEGMENT SHIFT ", hctl->sshift,
736-
"FILL FACTOR ", hctl->ffactor,
737729
"MAX BUCKET ", hctl->max_bucket,
738730
"HIGH MASK ", hctl->high_mask,
739731
"LOW MASK ", hctl->low_mask,
@@ -761,7 +753,7 @@ hash_estimate_size(long num_entries, Size entrysize)
761753
elementAllocCnt;
762754

763755
/* estimate number of buckets wanted */
764-
nBuckets = next_pow2_long((num_entries - 1) / DEF_FFACTOR + 1);
756+
nBuckets = next_pow2_long(num_entries);
765757
/* # of segments needed for nBuckets */
766758
nSegments = next_pow2_long((nBuckets - 1) / DEF_SEGSIZE + 1);
767759
/* directory entries */
@@ -804,7 +796,7 @@ hash_select_dirsize(long num_entries)
804796
nDirEntries;
805797

806798
/* estimate number of buckets wanted */
807-
nBuckets = next_pow2_long((num_entries - 1) / DEF_FFACTOR + 1);
799+
nBuckets = next_pow2_long(num_entries);
808800
/* # of segments needed for nBuckets */
809801
nSegments = next_pow2_long((nBuckets - 1) / DEF_SEGSIZE + 1);
810802
/* directory entries */
@@ -975,7 +967,7 @@ hash_search_with_hash_value(HTAB *hashp,
975967
* order of these tests is to try to check cheaper conditions first.
976968
*/
977969
if (!IS_PARTITIONED(hctl) && !hashp->frozen &&
978-
hctl->freeList[0].nentries / (long) (hctl->max_bucket + 1) >= hctl->ffactor &&
970+
hctl->freeList[0].nentries > (long) (hctl->max_bucket + 1) &&
979971
!has_seq_scans(hashp))
980972
(void) expand_table(hashp);
981973
}

‎src/include/utils/hsearch.h

Lines changed: 0 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -68,7 +68,6 @@ typedef struct HASHCTL
6868
long ssize; /* segment size */
6969
long dsize; /* (initial) directory size */
7070
long max_dsize; /* limit to dsize if dir size is limited */
71-
long ffactor; /* fill factor */
7271
Size keysize; /* hash key length in bytes */
7372
Size entrysize; /* total user element size in bytes */
7473
HashValueFunc hash; /* hash function */
@@ -83,7 +82,6 @@ typedef struct HASHCTL
8382
#define HASH_PARTITION 0x0001 /* Hashtable is used w/partitioned locking */
8483
#define HASH_SEGMENT 0x0002 /* Set segment size */
8584
#define HASH_DIRSIZE 0x0004 /* Set directory size (initial and max) */
86-
#define HASH_FFACTOR 0x0008 /* Set fill factor */
8785
#define HASH_ELEM 0x0010 /* Set keysize and entrysize */
8886
#define HASH_BLOBS 0x0020 /* Select support functions for binary keys */
8987
#define HASH_FUNCTION 0x0040 /* Set user defined hash function */

0 commit comments

Comments
 (0)