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

Commitfba2a10

Browse files
committed
Marginal performance improvements in dynahash: make sure that everything
associated with a hashtable is allocated in that hashtable's privatecontext, so that hash_destroy only has to destroy the context and notdo any retail pfree's; and tighten the inner loop of hash_seq_search.
1 parent6f1ca7e commitfba2a10

File tree

1 file changed

+118
-90
lines changed

1 file changed

+118
-90
lines changed

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

Lines changed: 118 additions & 90 deletions
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@
99
*
1010
*
1111
* IDENTIFICATION
12-
* $PostgreSQL: pgsql/src/backend/utils/hash/dynahash.c,v 1.58 2004/12/31 22:01:37 pgsql Exp $
12+
* $PostgreSQL: pgsql/src/backend/utils/hash/dynahash.c,v 1.59 2005/05/06 00:19:14 tgl Exp $
1313
*
1414
*-------------------------------------------------------------------------
1515
*/
@@ -72,9 +72,8 @@ static void hash_corrupted(HTAB *hashp);
7272

7373

7474
/*
75-
* memory allocationroutines
75+
* memory allocationsupport
7676
*/
77-
staticMemoryContextDynaHashCxt=NULL;
7877
staticMemoryContextCurrentDynaHashCxt=NULL;
7978

8079
staticvoid*
@@ -84,10 +83,6 @@ DynaHashAlloc(Size size)
8483
returnMemoryContextAlloc(CurrentDynaHashCxt,size);
8584
}
8685

87-
#defineMEM_ALLOCDynaHashAlloc
88-
#undefMEM_FREE/* already in windows header files */
89-
#defineMEM_FREEpfree
90-
9186

9287
#ifHASH_STATISTICS
9388
staticlonghash_accesses,
@@ -98,31 +93,60 @@ static long hash_accesses,
9893

9994
/************************** CREATE ROUTINES **********************/
10095

96+
/*
97+
* hash_create -- create a new dynamic hash table
98+
*
99+
*tabname: a name for the table (for debugging purposes)
100+
*nelem: maximum number of elements expected
101+
**info: additional table parameters, as indicated by flags
102+
*flags: bitmask indicating which parameters to take from *info
103+
*
104+
* Note: for a shared-memory hashtable, nelem needs to be a pretty good
105+
* estimate, since we can't expand the table on the fly. But an unshared
106+
* hashtable can be expanded on-the-fly, so it's better for nelem to be
107+
* on the small side and let the table grow if it's exceeded. An overly
108+
* large nelem will penalize hash_seq_search speed without buying much.
109+
*/
101110
HTAB*
102111
hash_create(constchar*tabname,longnelem,HASHCTL*info,intflags)
103112
{
104113
HTAB*hashp;
105114
HASHHDR*hctl;
106115

107-
/* First time through, create a memory context for hash tables */
108-
if (!DynaHashCxt)
109-
DynaHashCxt=AllocSetContextCreate(TopMemoryContext,
110-
"DynaHash",
111-
ALLOCSET_DEFAULT_MINSIZE,
112-
ALLOCSET_DEFAULT_INITSIZE,
113-
ALLOCSET_DEFAULT_MAXSIZE);
114-
115-
/* Select allocation context for this hash table */
116-
if (flags&HASH_CONTEXT)
117-
CurrentDynaHashCxt=info->hcxt;
116+
/*
117+
* For shared hash tables, we have a local hash header (HTAB struct)
118+
* that we allocate in TopMemoryContext; all else is in shared memory.
119+
*
120+
* For non-shared hash tables, everything including the hash header
121+
* is in a memory context created specially for the hash table ---
122+
* this makes hash_destroy very simple. The memory context is made
123+
* a child of either a context specified by the caller, or
124+
* TopMemoryContext if nothing is specified.
125+
*/
126+
if (flags&HASH_SHARED_MEM)
127+
{
128+
/* Set up to allocate the hash header */
129+
CurrentDynaHashCxt=TopMemoryContext;
130+
}
118131
else
119-
CurrentDynaHashCxt=DynaHashCxt;
132+
{
133+
/* Create the hash table's private memory context */
134+
if (flags&HASH_CONTEXT)
135+
CurrentDynaHashCxt=info->hcxt;
136+
else
137+
CurrentDynaHashCxt=TopMemoryContext;
138+
CurrentDynaHashCxt=AllocSetContextCreate(CurrentDynaHashCxt,
139+
tabname,
140+
ALLOCSET_DEFAULT_MINSIZE,
141+
ALLOCSET_DEFAULT_INITSIZE,
142+
ALLOCSET_DEFAULT_MAXSIZE);
143+
}
120144

121-
/* Initialize the hash header */
122-
hashp= (HTAB*)MEM_ALLOC(sizeof(HTAB));
145+
/* Initialize the hash header, plus a copy of the table name */
146+
hashp= (HTAB*)DynaHashAlloc(sizeof(HTAB)+strlen(tabname)+1);
123147
MemSet(hashp,0,sizeof(HTAB));
124148

125-
hashp->tabname= (char*)MEM_ALLOC(strlen(tabname)+1);
149+
hashp->tabname= (char*)(hashp+1);
126150
strcpy(hashp->tabname,tabname);
127151

128152
if (flags&HASH_FUNCTION)
@@ -143,6 +167,11 @@ hash_create(const char *tabname, long nelem, HASHCTL *info, int flags)
143167
else
144168
hashp->match=memcmp;
145169

170+
if (flags&HASH_ALLOC)
171+
hashp->alloc=info->alloc;
172+
else
173+
hashp->alloc=DynaHashAlloc;
174+
146175
if (flags&HASH_SHARED_MEM)
147176
{
148177
/*
@@ -151,7 +180,6 @@ hash_create(const char *tabname, long nelem, HASHCTL *info, int flags)
151180
*/
152181
hashp->hctl=info->hctl;
153182
hashp->dir=info->dir;
154-
hashp->alloc=info->alloc;
155183
hashp->hcxt=NULL;
156184
hashp->isshared= true;
157185

@@ -164,7 +192,6 @@ hash_create(const char *tabname, long nelem, HASHCTL *info, int flags)
164192
/* setup hash table defaults */
165193
hashp->hctl=NULL;
166194
hashp->dir=NULL;
167-
hashp->alloc=MEM_ALLOC;
168195
hashp->hcxt=CurrentDynaHashCxt;
169196
hashp->isshared= false;
170197
}
@@ -210,23 +237,11 @@ hash_create(const char *tabname, long nelem, HASHCTL *info, int flags)
210237
*/
211238
if (flags&HASH_ELEM)
212239
{
240+
Assert(info->entrysize >=info->keysize);
213241
hctl->keysize=info->keysize;
214242
hctl->entrysize=info->entrysize;
215243
}
216244

217-
if (flags&HASH_ALLOC)
218-
hashp->alloc=info->alloc;
219-
else
220-
{
221-
/* remaining hash table structures live in child of given context */
222-
hashp->hcxt=AllocSetContextCreate(CurrentDynaHashCxt,
223-
tabname,
224-
ALLOCSET_DEFAULT_MINSIZE,
225-
ALLOCSET_DEFAULT_INITSIZE,
226-
ALLOCSET_DEFAULT_MAXSIZE);
227-
CurrentDynaHashCxt=hashp->hcxt;
228-
}
229-
230245
/* Build the hash directory structure */
231246
if (!init_htab(hashp,nelem))
232247
{
@@ -431,26 +446,16 @@ hash_destroy(HTAB *hashp)
431446
if (hashp!=NULL)
432447
{
433448
/* allocation method must be one we know how to free, too */
434-
Assert(hashp->alloc==MEM_ALLOC);
449+
Assert(hashp->alloc==DynaHashAlloc);
435450
/* so this hashtable must have it's own context */
436451
Assert(hashp->hcxt!=NULL);
437452

438453
hash_stats("destroy",hashp);
439454

440455
/*
441-
* Free buckets, dir etc. by destroying the hash table's memory
442-
* context.
456+
* Free everything by destroying the hash table's memory context.
443457
*/
444458
MemoryContextDelete(hashp->hcxt);
445-
446-
/*
447-
* Free the HTAB and control structure, which are allocated in the
448-
* parent context (DynaHashCxt or the context given by the caller
449-
* of hash_create()).
450-
*/
451-
MEM_FREE(hashp->hctl);
452-
MEM_FREE(hashp->tabname);
453-
MEM_FREE(hashp);
454459
}
455460
}
456461

@@ -702,55 +707,74 @@ hash_seq_init(HASH_SEQ_STATUS *status, HTAB *hashp)
702707
void*
703708
hash_seq_search(HASH_SEQ_STATUS*status)
704709
{
705-
HTAB*hashp=status->hashp;
706-
HASHHDR*hctl=hashp->hctl;
710+
HTAB*hashp;
711+
HASHHDR*hctl;
712+
uint32max_bucket;
713+
longssize;
714+
longsegment_num;
715+
longsegment_ndx;
716+
HASHSEGMENTsegp;
717+
uint32curBucket;
718+
HASHELEMENT*curElem;
707719

708-
while (status->curBucket <=hctl->max_bucket)
720+
if ((curElem=status->curEntry)!=NULL)
709721
{
710-
longsegment_num;
711-
longsegment_ndx;
712-
HASHSEGMENTsegp;
722+
/* Continuing scan of curBucket... */
723+
status->curEntry=curElem->link;
724+
if (status->curEntry==NULL)/* end of this bucket */
725+
++status->curBucket;
726+
return (void*)ELEMENTKEY(curElem);
727+
}
713728

714-
if (status->curEntry!=NULL)
715-
{
716-
/* Continuing scan of curBucket... */
717-
HASHELEMENT*curElem;
718-
719-
curElem=status->curEntry;
720-
status->curEntry=curElem->link;
721-
if (status->curEntry==NULL)/* end of this bucket */
722-
++status->curBucket;
723-
return (void*)ELEMENTKEY(curElem);
724-
}
729+
/*
730+
* Search for next nonempty bucket starting at curBucket.
731+
*/
732+
curBucket=status->curBucket;
733+
hashp=status->hashp;
734+
hctl=hashp->hctl;
735+
ssize=hctl->ssize;
736+
max_bucket=hctl->max_bucket;
725737

726-
/*
727-
* initialize the search within this bucket.
728-
*/
729-
segment_num=status->curBucket >>hctl->sshift;
730-
segment_ndx=MOD(status->curBucket,hctl->ssize);
738+
if (curBucket>max_bucket)
739+
returnNULL;/* search is done */
731740

732-
/*
733-
* first find the right segment in the table directory.
734-
*/
735-
segp=hashp->dir[segment_num];
736-
if (segp==NULL)
737-
hash_corrupted(hashp);
741+
/*
742+
* first find the right segment in the table directory.
743+
*/
744+
segment_num=curBucket >>hctl->sshift;
745+
segment_ndx=MOD(curBucket,ssize);
738746

739-
/*
740-
* now find the right index into the segment for the first item in
741-
* this bucket's chain. if the bucket is not empty (its entry in
742-
* the dir is valid), we know this must correspond to a valid
743-
* element and not a freed element because it came out of the
744-
* directory of valid stuff. if there are elements in the bucket
745-
* chains that point to the freelist we're in big trouble.
746-
*/
747-
status->curEntry=segp[segment_ndx];
747+
segp=hashp->dir[segment_num];
748748

749-
if (status->curEntry==NULL)/* empty bucket */
750-
++status->curBucket;
749+
/*
750+
* Pick up the first item in this bucket's chain. If chain is
751+
* not empty we can go back around the outer loop to search it.
752+
* Otherwise we have to advance to find the next nonempty bucket.
753+
* We try to optimize that case since searching a near-empty
754+
* hashtable has to iterate this loop a lot.
755+
*/
756+
while ((curElem=segp[segment_ndx])==NULL)
757+
{
758+
/* empty bucket, advance to next */
759+
if (++curBucket>max_bucket)
760+
{
761+
status->curBucket=curBucket;
762+
returnNULL;/* search is done */
763+
}
764+
if (++segment_ndx >=ssize)
765+
{
766+
segment_num++;
767+
segment_ndx=0;
768+
segp=hashp->dir[segment_num];
769+
}
751770
}
752771

753-
returnNULL;/* out of buckets */
772+
/* Begin scan of curBucket... */
773+
status->curEntry=curElem->link;
774+
if (status->curEntry==NULL)/* end of this bucket */
775+
++curBucket;
776+
status->curBucket=curBucket;
777+
return (void*)ELEMENTKEY(curElem);
754778
}
755779

756780

@@ -880,9 +904,13 @@ dir_realloc(HTAB *hashp)
880904
{
881905
memcpy(p,old_p,old_dirsize);
882906
MemSet(((char*)p)+old_dirsize,0,new_dirsize-old_dirsize);
883-
MEM_FREE((char*)old_p);
884907
hashp->dir=p;
885908
hashp->hctl->dsize=new_dsize;
909+
910+
/* XXX assume the allocator is palloc, so we know how to free */
911+
Assert(hashp->alloc==DynaHashAlloc);
912+
pfree(old_p);
913+
886914
return true;
887915
}
888916

0 commit comments

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