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

Commite477642

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 parent1722782 commite477642

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
@@ -904,6 +904,7 @@ transformGraph(TrgmNFA *trgmNFA)
904904
HASHCTLhashCtl;
905905
TrgmStateKeyinitkey;
906906
TrgmState*initstate;
907+
ListCell*lc;
907908

908909
/* Initialize this stage's workspace in trgmNFA struct */
909910
trgmNFA->queue=NIL;
@@ -934,12 +935,13 @@ transformGraph(TrgmNFA *trgmNFA)
934935
/*
935936
* Recursively build the expanded graph by processing queue of states
936937
* (breadth-first search). getState already put initstate in the queue.
938+
* Note that getState will append new states to the queue within the loop,
939+
* too; this works as long as we don't do repeat fetches using the "lc"
940+
* pointer.
937941
*/
938-
while (trgmNFA->queue!=NIL)
942+
foreach(lc,trgmNFA->queue)
939943
{
940-
TrgmState*state= (TrgmState*)linitial(trgmNFA->queue);
941-
942-
trgmNFA->queue=list_delete_first(trgmNFA->queue);
944+
TrgmState*state= (TrgmState*)lfirst(lc);
943945

944946
/*
945947
* If we overflowed then just mark state as final. Otherwise do
@@ -963,22 +965,29 @@ transformGraph(TrgmNFA *trgmNFA)
963965
staticvoid
964966
processState(TrgmNFA*trgmNFA,TrgmState*state)
965967
{
968+
ListCell*lc;
969+
966970
/* keysQueue should be NIL already, but make sure */
967971
trgmNFA->keysQueue=NIL;
968972

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

978-
trgmNFA->keysQueue=list_delete_first(trgmNFA->keysQueue);
982+
if (state->flags&TSTATE_FIN)
983+
break;
979984
addKey(trgmNFA,state,key);
980985
}
981986

987+
/* Release keysQueue to clean up for next cycle */
988+
list_free(trgmNFA->keysQueue);
989+
trgmNFA->keysQueue=NIL;
990+
982991
/*
983992
* Add outgoing arcs only if state isn't final (we have no interest in
984993
* 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
@@ -2610,8 +2610,9 @@ agg_refill_hash_table(AggState *aggstate)
26102610
if (aggstate->hash_batches==NIL)
26112611
return false;
26122612

2613-
batch=linitial(aggstate->hash_batches);
2614-
aggstate->hash_batches=list_delete_first(aggstate->hash_batches);
2613+
/* hash_batches is a stack, with the top item at the end of the list */
2614+
batch=llast(aggstate->hash_batches);
2615+
aggstate->hash_batches=list_delete_last(aggstate->hash_batches);
26152616

26162617
hash_agg_set_limits(aggstate->hashentrysize,batch->input_card,
26172618
batch->used_bits,&aggstate->hash_mem_limit,
@@ -3190,7 +3191,7 @@ hashagg_spill_finish(AggState *aggstate, HashAggSpill *spill, int setno)
31903191
new_batch=hashagg_batch_new(tapeset,tapenum,setno,
31913192
spill->ntuples[i],cardinality,
31923193
used_bits);
3193-
aggstate->hash_batches=lcons(new_batch,aggstate->hash_batches);
3194+
aggstate->hash_batches=lappend(aggstate->hash_batches,new_batch);
31943195
aggstate->hash_batches_used++;
31953196
}
31963197

@@ -3205,8 +3206,6 @@ hashagg_spill_finish(AggState *aggstate, HashAggSpill *spill, int setno)
32053206
staticvoid
32063207
hashagg_reset_spill_state(AggState*aggstate)
32073208
{
3208-
ListCell*lc;
3209-
32103209
/* free spills from initial pass */
32113210
if (aggstate->hash_spills!=NULL)
32123211
{
@@ -3224,13 +3223,7 @@ hashagg_reset_spill_state(AggState *aggstate)
32243223
}
32253224

32263225
/* free batches */
3227-
foreach(lc,aggstate->hash_batches)
3228-
{
3229-
HashAggBatch*batch= (HashAggBatch*)lfirst(lc);
3230-
3231-
pfree(batch);
3232-
}
3233-
list_free(aggstate->hash_batches);
3226+
list_free_deep(aggstate->hash_batches);
32343227
aggstate->hash_batches=NIL;
32353228

32363229
/* 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