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

Commitd97b714

Browse files
committed
Avoid using lcons and list_delete_first where it's easy to do so.
Formerly, lcons was about the same speed as lappend, but with the newList implementation, that's not so; with a long List, data movementimposes an O(N) cost on lcons and list_delete_first, but not lappend.Hence, invent list_delete_last with semantics parallel tolist_delete_first (but O(1) cost), and change various places to uselappend and list_delete_last where this can be done without muchviolence to the code logic.There are quite a few places that construct result lists using lcons notlappend. Some have semantic rationales for that; I added comments aboutit to a couple that didn't have them already. In many such places though,I think the coding is that way only because back in the dark ages lconswas faster than lappend. Hence, switch to lappend where this can be donewithout causing semantic changes.In ExecInitExprRec(), this results in aggregates and window functions thatare in the same plan node being executed in a different order than before.Generally, the executions of such functions ought to be independent ofeach other, so this shouldn't result in visibly different query results.But if you push it, as one regression test case does, you can show thatthe order is different. The new order seems saner; it's closer tothe order of the functions in the query text. And we never documentedor promised anything about this, anyway.Also, in gistfinishsplit(), don't bother building a reverse-order list;it's easy now to iterate backwards through the original list.It'd be possible to go further towards removing uses of lcons andlist_delete_first, but it'd require more extensive logic changes,and I'm not convinced it's worth it. Most of the remaining usesdeal with queues that probably never get long enough to be worthsweating over. (Actually, I doubt that any of the changes in thispatch will have measurable performance effects either. But betterto have good examples than bad ones in the code base.)Patch by me, thanks to David Rowley and Daniel Gustafsson for review.Discussion:https://postgr.es/m/21272.1563318411@sss.pgh.pa.us
1 parentdfd0121 commitd97b714

File tree

15 files changed

+72
-47
lines changed

15 files changed

+72
-47
lines changed

‎src/backend/access/gist/gist.c

Lines changed: 5 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -1323,8 +1323,6 @@ static void
13231323
gistfinishsplit(GISTInsertState*state,GISTInsertStack*stack,
13241324
GISTSTATE*giststate,List*splitinfo,boolunlockbuf)
13251325
{
1326-
ListCell*lc;
1327-
List*reversed;
13281326
GISTPageSplitInfo*right;
13291327
GISTPageSplitInfo*left;
13301328
IndexTupletuples[2];
@@ -1339,25 +1337,17 @@ gistfinishsplit(GISTInsertState *state, GISTInsertStack *stack,
13391337
* left. Finally insert the downlink for the last new page and update the
13401338
* downlink for the original page as one operation.
13411339
*/
1342-
1343-
/* for convenience, create a copy of the list in reverse order */
1344-
reversed=NIL;
1345-
foreach(lc,splitinfo)
1346-
{
1347-
reversed=lcons(lfirst(lc),reversed);
1348-
}
1349-
13501340
LockBuffer(stack->parent->buffer,GIST_EXCLUSIVE);
13511341
gistFindCorrectParent(state->r,stack);
13521342

13531343
/*
13541344
* insert downlinks for the siblings from right to left, until there are
13551345
* only two siblings left.
13561346
*/
1357-
while (list_length(reversed)>2)
1347+
for (intpos=list_length(splitinfo)-1;pos>1;pos--)
13581348
{
1359-
right= (GISTPageSplitInfo*)linitial(reversed);
1360-
left= (GISTPageSplitInfo*)lsecond(reversed);
1349+
right= (GISTPageSplitInfo*)list_nth(splitinfo,pos);
1350+
left= (GISTPageSplitInfo*)list_nth(splitinfo,pos-1);
13611351

13621352
if (gistinserttuples(state,stack->parent,giststate,
13631353
&right->downlink,1,
@@ -1371,11 +1361,10 @@ gistfinishsplit(GISTInsertState *state, GISTInsertStack *stack,
13711361
gistFindCorrectParent(state->r,stack);
13721362
}
13731363
/* gistinserttuples() released the lock on right->buf. */
1374-
reversed=list_delete_first(reversed);
13751364
}
13761365

1377-
right= (GISTPageSplitInfo*)linitial(reversed);
1378-
left= (GISTPageSplitInfo*)lsecond(reversed);
1366+
right= (GISTPageSplitInfo*)lsecond(splitinfo);
1367+
left= (GISTPageSplitInfo*)linitial(splitinfo);
13791368

13801369
/*
13811370
* Finally insert downlink for the remaining right page and update the

‎src/backend/catalog/heap.c

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -633,7 +633,7 @@ CheckAttributeType(const char *attname,
633633
errmsg("composite type %s cannot be made a member of itself",
634634
format_type_be(atttypid))));
635635

636-
containing_rowtypes=lcons_oid(atttypid,containing_rowtypes);
636+
containing_rowtypes=lappend_oid(containing_rowtypes,atttypid);
637637

638638
relation=relation_open(get_typ_typrelid(atttypid),AccessShareLock);
639639

@@ -653,7 +653,7 @@ CheckAttributeType(const char *attname,
653653

654654
relation_close(relation,AccessShareLock);
655655

656-
containing_rowtypes=list_delete_first(containing_rowtypes);
656+
containing_rowtypes=list_delete_last(containing_rowtypes);
657657
}
658658
elseif (OidIsValid((att_typelem=get_element_type(atttypid))))
659659
{

‎src/backend/commands/cluster.c

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1566,7 +1566,7 @@ get_tables_to_cluster(MemoryContext cluster_context)
15661566
rvtc= (RelToCluster*)palloc(sizeof(RelToCluster));
15671567
rvtc->tableOid=index->indrelid;
15681568
rvtc->indexOid=index->indexrelid;
1569-
rvs=lcons(rvtc,rvs);
1569+
rvs=lappend(rvs,rvtc);
15701570

15711571
MemoryContextSwitchTo(old_context);
15721572
}

‎src/backend/commands/lockcmds.c

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -281,11 +281,11 @@ LockViewRecurse(Oid reloid, LOCKMODE lockmode, bool nowait, List *ancestor_views
281281
context.nowait=nowait;
282282
context.viewowner=view->rd_rel->relowner;
283283
context.viewoid=reloid;
284-
context.ancestor_views=lcons_oid(reloid,ancestor_views);
284+
context.ancestor_views=lappend_oid(ancestor_views,reloid);
285285

286286
LockViewRecurse_walker((Node*)viewquery,&context);
287287

288-
ancestor_views=list_delete_oid(ancestor_views,reloid);
288+
(void)list_delete_last(context.ancestor_views);
289289

290290
table_close(view,NoLock);
291291
}

‎src/backend/commands/tablecmds.c

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -14480,6 +14480,11 @@ register_on_commit_action(Oid relid, OnCommitAction action)
1448014480
oc->creating_subid = GetCurrentSubTransactionId();
1448114481
oc->deleting_subid = InvalidSubTransactionId;
1448214482

14483+
/*
14484+
* We use lcons() here so that ON COMMIT actions are processed in reverse
14485+
* order of registration. That might not be essential but it seems
14486+
* reasonable.
14487+
*/
1448314488
on_commits = lcons(oc, on_commits);
1448414489

1448514490
MemoryContextSwitchTo(oldcxt);

‎src/backend/commands/typecmds.c

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2999,7 +2999,7 @@ get_rels_with_domain(Oid domainOid, LOCKMODE lockmode)
29992999
rtc->rel=rel;
30003000
rtc->natts=0;
30013001
rtc->atts= (int*)palloc(sizeof(int)*RelationGetNumberOfAttributes(rel));
3002-
result=lcons(rtc,result);
3002+
result=lappend(result,rtc);
30033003
}
30043004

30053005
/*

‎src/backend/executor/execExpr.c

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -786,7 +786,7 @@ ExecInitExprRec(Expr *node, ExprState *state,
786786
{
787787
AggState*aggstate= (AggState*)state->parent;
788788

789-
aggstate->aggs=lcons(astate,aggstate->aggs);
789+
aggstate->aggs=lappend(aggstate->aggs,astate);
790790
aggstate->numaggs++;
791791
}
792792
else
@@ -834,7 +834,7 @@ ExecInitExprRec(Expr *node, ExprState *state,
834834
WindowAggState*winstate= (WindowAggState*)state->parent;
835835
intnfuncs;
836836

837-
winstate->funcs=lcons(wfstate,winstate->funcs);
837+
winstate->funcs=lappend(winstate->funcs,wfstate);
838838
nfuncs=++winstate->numfuncs;
839839
if (wfunc->winagg)
840840
winstate->numaggs++;

‎src/backend/nodes/list.c

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -826,6 +826,30 @@ list_delete_first(List *list)
826826
returnlist_delete_nth_cell(list,0);
827827
}
828828

829+
/*
830+
* Delete the last element of the list.
831+
*
832+
* This is the opposite of list_delete_first(), but is noticeably cheaper
833+
* with a long list, since no data need be moved.
834+
*/
835+
List*
836+
list_delete_last(List*list)
837+
{
838+
check_list_invariants(list);
839+
840+
if (list==NIL)
841+
returnNIL;/* would an error be better? */
842+
843+
/* list_truncate won't free list if it goes to empty, but this should */
844+
if (list_length(list) <=1)
845+
{
846+
list_free(list);
847+
returnNIL;
848+
}
849+
850+
returnlist_truncate(list,list_length(list)-1);
851+
}
852+
829853
/*
830854
* Generate the union of two lists. This is calculated by copying
831855
* list1 via list_copy(), then adding to it all the members of list2

‎src/backend/optimizer/util/clauses.c

Lines changed: 7 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -881,11 +881,9 @@ is_parallel_safe(PlannerInfo *root, Node *node)
881881
foreach(l,proot->init_plans)
882882
{
883883
SubPlan*initsubplan= (SubPlan*)lfirst(l);
884-
ListCell*l2;
885884

886-
foreach(l2,initsubplan->setParam)
887-
context.safe_param_ids=lcons_int(lfirst_int(l2),
888-
context.safe_param_ids);
885+
context.safe_param_ids=list_concat(context.safe_param_ids,
886+
initsubplan->setParam);
889887
}
890888
}
891889

@@ -1015,6 +1013,7 @@ max_parallel_hazard_walker(Node *node, max_parallel_hazard_context *context)
10151013
context->safe_param_ids);
10161014
if (max_parallel_hazard_walker(subplan->testexpr,context))
10171015
return true;/* no need to restore safe_param_ids */
1016+
list_free(context->safe_param_ids);
10181017
context->safe_param_ids=save_safe_param_ids;
10191018
/* we must also check args, but no special Param treatment there */
10201019
if (max_parallel_hazard_walker((Node*)subplan->args,context))
@@ -4185,8 +4184,8 @@ add_function_defaults(List *args, HeapTuple func_tuple)
41854184
ndelete=nargsprovided+list_length(defaults)-funcform->pronargs;
41864185
if (ndelete<0)
41874186
elog(ERROR,"not enough default arguments");
4188-
while (ndelete-->0)
4189-
defaults=list_delete_first(defaults);
4187+
if (ndelete>0)
4188+
defaults=list_copy_tail(defaults,ndelete);
41904189

41914190
/* And form the combined argument list, not modifying the input list */
41924191
returnlist_concat(list_copy(args),defaults);
@@ -4701,9 +4700,9 @@ inline_function(Oid funcid, Oid result_type, Oid result_collid,
47014700
* Recursively try to simplify the modified expression. Here we must add
47024701
* the current function to the context list of active functions.
47034702
*/
4704-
context->active_fns=lcons_oid(funcid,context->active_fns);
4703+
context->active_fns=lappend_oid(context->active_fns,funcid);
47054704
newexpr=eval_const_expressions_mutator(newexpr,context);
4706-
context->active_fns=list_delete_first(context->active_fns);
4705+
context->active_fns=list_delete_last(context->active_fns);
47074706

47084707
error_context_stack=sqlerrcontext.previous;
47094708

‎src/backend/optimizer/util/plancat.c

Lines changed: 10 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -419,6 +419,13 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,
419419

420420
index_close(indexRelation,NoLock);
421421

422+
/*
423+
* We've historically used lcons() here. It'd make more sense to
424+
* use lappend(), but that causes the planner to change behavior
425+
* in cases where two indexes seem equally attractive. For now,
426+
* stick with lcons() --- few tables should have so many indexes
427+
* that the O(N^2) behavior of lcons() is really a problem.
428+
*/
422429
indexinfos=lcons(info,indexinfos);
423430
}
424431

@@ -1339,7 +1346,7 @@ get_relation_statistics(RelOptInfo *rel, Relation relation)
13391346
info->kind=STATS_EXT_NDISTINCT;
13401347
info->keys=bms_copy(keys);
13411348

1342-
stainfos=lcons(info,stainfos);
1349+
stainfos=lappend(stainfos,info);
13431350
}
13441351

13451352
if (statext_is_kind_built(dtup,STATS_EXT_DEPENDENCIES))
@@ -1351,7 +1358,7 @@ get_relation_statistics(RelOptInfo *rel, Relation relation)
13511358
info->kind=STATS_EXT_DEPENDENCIES;
13521359
info->keys=bms_copy(keys);
13531360

1354-
stainfos=lcons(info,stainfos);
1361+
stainfos=lappend(stainfos,info);
13551362
}
13561363

13571364
if (statext_is_kind_built(dtup,STATS_EXT_MCV))
@@ -1363,7 +1370,7 @@ get_relation_statistics(RelOptInfo *rel, Relation relation)
13631370
info->kind=STATS_EXT_MCV;
13641371
info->keys=bms_copy(keys);
13651372

1366-
stainfos=lcons(info,stainfos);
1373+
stainfos=lappend(stainfos,info);
13671374
}
13681375

13691376
ReleaseSysCache(htup);

‎src/backend/parser/parse_agg.c

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1132,7 +1132,7 @@ parseCheckAggregates(ParseState *pstate, Query *qry)
11321132
if (expr==NULL)
11331133
continue;/* probably cannot happen */
11341134

1135-
groupClauses=lcons(expr,groupClauses);
1135+
groupClauses=lappend(groupClauses,expr);
11361136
}
11371137

11381138
/*

‎src/backend/rewrite/rewriteHandler.c

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1973,7 +1973,7 @@ fireRIRrules(Query *parsetree, List *activeRIRs)
19731973
(errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
19741974
errmsg("infinite recursion detected in rules for relation \"%s\"",
19751975
RelationGetRelationName(rel))));
1976-
activeRIRs=lcons_oid(RelationGetRelid(rel),activeRIRs);
1976+
activeRIRs=lappend_oid(activeRIRs,RelationGetRelid(rel));
19771977

19781978
foreach(l,locks)
19791979
{
@@ -1986,7 +1986,7 @@ fireRIRrules(Query *parsetree, List *activeRIRs)
19861986
activeRIRs);
19871987
}
19881988

1989-
activeRIRs=list_delete_first(activeRIRs);
1989+
activeRIRs=list_delete_last(activeRIRs);
19901990
}
19911991
}
19921992

@@ -2059,7 +2059,7 @@ fireRIRrules(Query *parsetree, List *activeRIRs)
20592059
errmsg("infinite recursion detected in policy for relation \"%s\"",
20602060
RelationGetRelationName(rel))));
20612061

2062-
activeRIRs=lcons_oid(RelationGetRelid(rel),activeRIRs);
2062+
activeRIRs=lappend_oid(activeRIRs,RelationGetRelid(rel));
20632063

20642064
/*
20652065
* get_row_security_policies just passed back securityQuals
@@ -2084,7 +2084,7 @@ fireRIRrules(Query *parsetree, List *activeRIRs)
20842084
expression_tree_walker((Node*)withCheckOptions,
20852085
fireRIRonSubLink, (void*)activeRIRs);
20862086

2087-
activeRIRs=list_delete_first(activeRIRs);
2087+
activeRIRs=list_delete_last(activeRIRs);
20882088
}
20892089

20902090
/*
@@ -3711,7 +3711,7 @@ RewriteQuery(Query *parsetree, List *rewrite_events)
37113711
rev= (rewrite_event*)palloc(sizeof(rewrite_event));
37123712
rev->relation=RelationGetRelid(rt_entry_relation);
37133713
rev->event=event;
3714-
rewrite_events=lcons(rev,rewrite_events);
3714+
rewrite_events=lappend(rewrite_events,rev);
37153715

37163716
foreach(n,product_queries)
37173717
{
@@ -3722,7 +3722,7 @@ RewriteQuery(Query *parsetree, List *rewrite_events)
37223722
rewritten=list_concat(rewritten,newstuff);
37233723
}
37243724

3725-
rewrite_events=list_delete_first(rewrite_events);
3725+
rewrite_events=list_delete_last(rewrite_events);
37263726
}
37273727

37283728
/*

‎src/backend/utils/adt/selfuncs.c

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -3201,20 +3201,20 @@ estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows,
32013201
* Split the list of varinfos in two - one for the current rel, one
32023202
* for remaining Vars on other rels.
32033203
*/
3204-
relvarinfos=lcons(varinfo1,relvarinfos);
3204+
relvarinfos=lappend(relvarinfos,varinfo1);
32053205
for_each_cell(l,varinfos,list_second_cell(varinfos))
32063206
{
32073207
GroupVarInfo*varinfo2= (GroupVarInfo*)lfirst(l);
32083208

32093209
if (varinfo2->rel==varinfo1->rel)
32103210
{
32113211
/* varinfos on current rel */
3212-
relvarinfos=lcons(varinfo2,relvarinfos);
3212+
relvarinfos=lappend(relvarinfos,varinfo2);
32133213
}
32143214
else
32153215
{
32163216
/* not time to process varinfo2 yet */
3217-
newvarinfos=lcons(varinfo2,newvarinfos);
3217+
newvarinfos=lappend(newvarinfos,varinfo2);
32183218
}
32193219
}
32203220

‎src/include/nodes/pg_list.h

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -531,6 +531,7 @@ extern List *list_delete_ptr(List *list, void *datum);
531531
externList*list_delete_int(List*list,intdatum);
532532
externList*list_delete_oid(List*list,Oiddatum);
533533
externList*list_delete_first(List*list);
534+
externList*list_delete_last(List*list);
534535
externList*list_delete_nth_cell(List*list,intn);
535536
externList*list_delete_cell(List*list,ListCell*cell);
536537

‎src/test/regress/expected/aggregates.out

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -2030,10 +2030,10 @@ NOTICE: avg_transfn called with 3
20302030

20312031
-- this should not share the state due to different input columns.
20322032
select my_avg(one),my_sum(two) from (values(1,2),(3,4)) t(one,two);
2033-
NOTICE: avg_transfn called with 2
20342033
NOTICE: avg_transfn called with 1
2035-
NOTICE: avg_transfn called with4
2034+
NOTICE: avg_transfn called with2
20362035
NOTICE: avg_transfn called with 3
2036+
NOTICE: avg_transfn called with 4
20372037
my_avg | my_sum
20382038
--------+--------
20392039
2 | 6

0 commit comments

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