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

Commitad87bf3

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 parent494ec00 commitad87bf3

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
@@ -905,6 +905,7 @@ transformGraph(TrgmNFA *trgmNFA)
905905
HASHCTLhashCtl;
906906
TrgmStateKeyinitkey;
907907
TrgmState*initstate;
908+
ListCell*lc;
908909

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

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

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

979-
trgmNFA->keysQueue=list_delete_first(trgmNFA->keysQueue);
983+
if (state->flags&TSTATE_FIN)
984+
break;
980985
addKey(trgmNFA,state,key);
981986
}
982987

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

2605-
batch=linitial(aggstate->hash_batches);
2606-
aggstate->hash_batches=list_delete_first(aggstate->hash_batches);
2605+
/* hash_batches is a stack, with the top item at the end of the list */
2606+
batch=llast(aggstate->hash_batches);
2607+
aggstate->hash_batches=list_delete_last(aggstate->hash_batches);
26072608

26082609
hash_agg_set_limits(aggstate->hashentrysize,batch->input_card,
26092610
batch->used_bits,&aggstate->hash_mem_limit,
@@ -3182,7 +3183,7 @@ hashagg_spill_finish(AggState *aggstate, HashAggSpill *spill, int setno)
31823183
new_batch=hashagg_batch_new(tapeset,tapenum,setno,
31833184
spill->ntuples[i],cardinality,
31843185
used_bits);
3185-
aggstate->hash_batches=lcons(new_batch,aggstate->hash_batches);
3186+
aggstate->hash_batches=lappend(aggstate->hash_batches,new_batch);
31863187
aggstate->hash_batches_used++;
31873188
}
31883189

@@ -3197,8 +3198,6 @@ hashagg_spill_finish(AggState *aggstate, HashAggSpill *spill, int setno)
31973198
staticvoid
31983199
hashagg_reset_spill_state(AggState*aggstate)
31993200
{
3200-
ListCell*lc;
3201-
32023201
/* free spills from initial pass */
32033202
if (aggstate->hash_spills!=NULL)
32043203
{
@@ -3216,13 +3215,7 @@ hashagg_reset_spill_state(AggState *aggstate)
32163215
}
32173216

32183217
/* free batches */
3219-
foreach(lc,aggstate->hash_batches)
3220-
{
3221-
HashAggBatch*batch= (HashAggBatch*)lfirst(lc);
3222-
3223-
pfree(batch);
3224-
}
3225-
list_free(aggstate->hash_batches);
3218+
list_free_deep(aggstate->hash_batches);
32263219
aggstate->hash_batches=NIL;
32273220

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