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

Commite9d9ba2

Browse files
committed
Avoid some other O(N^2) hazards in list manipulation.
In the same spirit as6301c3a, fix some more places where we wereusing list_delete_first() in a loop and thereby risking O(N^2)behavior. It's not clear that the lists manipulated in these spotscan get long enough to be really problematic ... but it's not clearthat they can't, either, and the fixes are simple enough.As before, back-patch to v13.Discussion:https://postgr.es/m/CD2F0E7F-9822-45EC-A411-AE56F14DEA9F@amazon.com
1 parent40c516b commite9d9ba2

File tree

3 files changed

+27
-25
lines changed

3 files changed

+27
-25
lines changed

‎contrib/pg_trgm/trgm_regexp.c

Lines changed: 17 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -907,6 +907,7 @@ transformGraph(TrgmNFA *trgmNFA)
907907
HASHCTLhashCtl;
908908
TrgmStateKeyinitkey;
909909
TrgmState*initstate;
910+
ListCell*lc;
910911

911912
/* Initialize this stage's workspace in trgmNFA struct */
912913
trgmNFA->queue=NIL;
@@ -937,12 +938,13 @@ transformGraph(TrgmNFA *trgmNFA)
937938
/*
938939
* Recursively build the expanded graph by processing queue of states
939940
* (breadth-first search). getState already put initstate in the queue.
941+
* Note that getState will append new states to the queue within the loop,
942+
* too; this works as long as we don't do repeat fetches using the "lc"
943+
* pointer.
940944
*/
941-
while (trgmNFA->queue!=NIL)
945+
foreach(lc,trgmNFA->queue)
942946
{
943-
TrgmState*state= (TrgmState*)linitial(trgmNFA->queue);
944-
945-
trgmNFA->queue=list_delete_first(trgmNFA->queue);
947+
TrgmState*state= (TrgmState*)lfirst(lc);
946948

947949
/*
948950
* If we overflowed then just mark state as final. Otherwise do
@@ -966,22 +968,29 @@ transformGraph(TrgmNFA *trgmNFA)
966968
staticvoid
967969
processState(TrgmNFA*trgmNFA,TrgmState*state)
968970
{
971+
ListCell*lc;
972+
969973
/* keysQueue should be NIL already, but make sure */
970974
trgmNFA->keysQueue=NIL;
971975

972976
/*
973977
* Add state's own key, and then process all keys added to keysQueue until
974-
* queue isempty. But we can quit if the state gets marked final.
978+
* queue isfinished. But we can quit if the state gets marked final.
975979
*/
976980
addKey(trgmNFA,state,&state->stateKey);
977-
while (trgmNFA->keysQueue!=NIL&& !(state->flags&TSTATE_FIN))
981+
foreach(lc,trgmNFA->keysQueue)
978982
{
979-
TrgmStateKey*key= (TrgmStateKey*)linitial(trgmNFA->keysQueue);
983+
TrgmStateKey*key= (TrgmStateKey*)lfirst(lc);
980984

981-
trgmNFA->keysQueue=list_delete_first(trgmNFA->keysQueue);
985+
if (state->flags&TSTATE_FIN)
986+
break;
982987
addKey(trgmNFA,state,key);
983988
}
984989

990+
/* Release keysQueue to clean up for next cycle */
991+
list_free(trgmNFA->keysQueue);
992+
trgmNFA->keysQueue=NIL;
993+
985994
/*
986995
* Add outgoing arcs only if state isn't final (we have no interest in
987996
* outgoing arcs if we already match)

‎src/backend/executor/nodeAgg.c

Lines changed: 5 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -2584,8 +2584,9 @@ agg_refill_hash_table(AggState *aggstate)
25842584
if (aggstate->hash_batches==NIL)
25852585
return false;
25862586

2587-
batch=linitial(aggstate->hash_batches);
2588-
aggstate->hash_batches=list_delete_first(aggstate->hash_batches);
2587+
/* hash_batches is a stack, with the top item at the end of the list */
2588+
batch=llast(aggstate->hash_batches);
2589+
aggstate->hash_batches=list_delete_last(aggstate->hash_batches);
25892590

25902591
hash_agg_set_limits(aggstate->hashentrysize,batch->input_card,
25912592
batch->used_bits,&aggstate->hash_mem_limit,
@@ -3098,7 +3099,7 @@ hashagg_spill_finish(AggState *aggstate, HashAggSpill *spill, int setno)
30983099
new_batch=hashagg_batch_new(tape,setno,
30993100
spill->ntuples[i],cardinality,
31003101
used_bits);
3101-
aggstate->hash_batches=lcons(new_batch,aggstate->hash_batches);
3102+
aggstate->hash_batches=lappend(aggstate->hash_batches,new_batch);
31023103
aggstate->hash_batches_used++;
31033104
}
31043105

@@ -3113,8 +3114,6 @@ hashagg_spill_finish(AggState *aggstate, HashAggSpill *spill, int setno)
31133114
staticvoid
31143115
hashagg_reset_spill_state(AggState*aggstate)
31153116
{
3116-
ListCell*lc;
3117-
31183117
/* free spills from initial pass */
31193118
if (aggstate->hash_spills!=NULL)
31203119
{
@@ -3132,13 +3131,7 @@ hashagg_reset_spill_state(AggState *aggstate)
31323131
}
31333132

31343133
/* free batches */
3135-
foreach(lc,aggstate->hash_batches)
3136-
{
3137-
HashAggBatch*batch= (HashAggBatch*)lfirst(lc);
3138-
3139-
pfree(batch);
3140-
}
3141-
list_free(aggstate->hash_batches);
3134+
list_free_deep(aggstate->hash_batches);
31423135
aggstate->hash_batches=NIL;
31433136

31443137
/* close tape set */

‎src/backend/jit/llvm/llvmjit.c

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -171,6 +171,7 @@ static void
171171
llvm_release_context(JitContext*context)
172172
{
173173
LLVMJitContext*llvm_context= (LLVMJitContext*)context;
174+
ListCell*lc;
174175

175176
/*
176177
* When this backend is exiting, don't clean up LLVM. As an error might
@@ -188,12 +189,9 @@ llvm_release_context(JitContext *context)
188189
llvm_context->module=NULL;
189190
}
190191

191-
while (llvm_context->handles!=NIL)
192+
foreach(lc,llvm_context->handles)
192193
{
193-
LLVMJitHandle*jit_handle;
194-
195-
jit_handle= (LLVMJitHandle*)linitial(llvm_context->handles);
196-
llvm_context->handles=list_delete_first(llvm_context->handles);
194+
LLVMJitHandle*jit_handle= (LLVMJitHandle*)lfirst(lc);
197195

198196
#ifLLVM_VERSION_MAJOR>11
199197
{
@@ -221,6 +219,8 @@ llvm_release_context(JitContext *context)
221219

222220
pfree(jit_handle);
223221
}
222+
list_free(llvm_context->handles);
223+
llvm_context->handles=NIL;
224224
}
225225

226226
/*

0 commit comments

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