Обсуждение: Use list_delete_xxxcell O(1) instead of list_delete_ptr O(N) in some places
Hi I found some code places call list_delete_ptr can be replaced by list_delete_xxxcell which can be faster. diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c index db54a6b..61ef7c8 100644 --- a/src/backend/optimizer/path/joinpath.c +++ b/src/backend/optimizer/path/joinpath.c @@ -1005,8 +1005,8 @@ sort_inner_and_outer(PlannerInfo *root, /* Make a pathkey list with this guy first */ if (l != list_head(all_pathkeys)) outerkeys = lcons(front_pathkey, - list_delete_ptr(list_copy(all_pathkeys), - front_pathkey)); + list_delete_nth_cell(list_copy(all_pathkeys), + foreach_current_index(l))); else outerkeys = all_pathkeys; /* no work at first one... */ diff --git a/src/backend/rewrite/rewriteHandler.c b/src/backend/rewrite/rewriteHandler.c index fe777c3..d0f15b8 100644 --- a/src/backend/rewrite/rewriteHandler.c +++ b/src/backend/rewrite/rewriteHandler.c @@ -650,7 +650,7 @@ adjustJoinTreeList(Query *parsetree, bool removert, int rt_index) if (IsA(rtr, RangeTblRef) && rtr->rtindex == rt_index) { - newjointree = list_delete_ptr(newjointree, rtr); + newjointree = list_delete_cell(newjointree, l); Best regards, houzj
Вложения
Re: Use list_delete_xxxcell O(1) instead of list_delete_ptr O(N) in some places
От
Luc Vlaming
Дата:
The following review has been posted through the commitfest application: make installcheck-world: tested, passed Implements feature: not tested Spec compliant: not tested Documentation: not tested Patch applies cleanly on master & 13 and installcheck-world runs on 13 & master. Seem to follow the new style of using morethe expressive macro's for the list interface, so looks good to me. The new status of this patch is: Ready for Committer
Re: Use list_delete_xxxcell O(1) instead of list_delete_ptr O(N) in some places
От
David Rowley
Дата:
On Sat, 10 Oct 2020 at 15:45, Hou, Zhijie <houzj.fnst@cn.fujitsu.com> wrote: > I found some code places call list_delete_ptr can be replaced by list_delete_xxxcell which can be faster. > > diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c > index db54a6b..61ef7c8 100644 > --- a/src/backend/optimizer/path/joinpath.c > +++ b/src/backend/optimizer/path/joinpath.c > @@ -1005,8 +1005,8 @@ sort_inner_and_outer(PlannerInfo *root, > /* Make a pathkey list with this guy first */ > if (l != list_head(all_pathkeys)) > outerkeys = lcons(front_pathkey, > - list_delete_ptr(list_copy(all_pathkeys), > - front_pathkey)); > + list_delete_nth_cell(list_copy(all_pathkeys), > + foreach_current_index(l))); > else > outerkeys = all_pathkeys; /* no work at first one... */ That looks ok to me. It would be more optimal if we had a method to move an element to the front of a list, or to any specified position, but I can't imagine it's worth making such a function just for that. So what you have there seems fine. > diff --git a/src/backend/rewrite/rewriteHandler.c b/src/backend/rewrite/rewriteHandler.c > index fe777c3..d0f15b8 100644 > --- a/src/backend/rewrite/rewriteHandler.c > +++ b/src/backend/rewrite/rewriteHandler.c > @@ -650,7 +650,7 @@ adjustJoinTreeList(Query *parsetree, bool removert, int rt_index) > if (IsA(rtr, RangeTblRef) && > rtr->rtindex == rt_index) > { > - newjointree = list_delete_ptr(newjointree, rtr); > + newjointree = list_delete_cell(newjointree, l); I think you may as well just use newjointree = foreach_delete_current(newjointree, l);. The comment about why the list_delete is ok inside a foreach is then irrelevant since foreach_delete_current() is designed for deleting the current foreach cell. Looking around for other places I found two more in equivclass.c. These two do require an additional moving part to keep track of the index we want to delete, so they're not quite as clear cut a win to do. However, I don't think tracking the index makes the code overly complex, so I'm thinking they're both fine to do. Does anyone think differently? Updated patch attached. David
Вложения
RE: Use list_delete_xxxcell O(1) instead of list_delete_ptr O(N) in some places
От
"Hou, Zhijie"
Дата:
> > I found some code places call list_delete_ptr can be replaced by > list_delete_xxxcell which can be faster. > > > > diff --git a/src/backend/optimizer/path/joinpath.c > > b/src/backend/optimizer/path/joinpath.c > > index db54a6b..61ef7c8 100644 > > --- a/src/backend/optimizer/path/joinpath.c > > +++ b/src/backend/optimizer/path/joinpath.c > > @@ -1005,8 +1005,8 @@ sort_inner_and_outer(PlannerInfo *root, > > /* Make a pathkey list with this guy first */ > > if (l != list_head(all_pathkeys)) > > outerkeys = lcons(front_pathkey, > > - > list_delete_ptr(list_copy(all_pathkeys), > > - > front_pathkey)); > > + > list_delete_nth_cell(list_copy(all_pathkeys), > > + > > + foreach_current_index(l))); > > else > > outerkeys = all_pathkeys; /* no work at > first one... */ > > That looks ok to me. It would be more optimal if we had a method to move > an element to the front of a list, or to any specified position, but I can't > imagine it's worth making such a function just for that. > So what you have there seems fine. > > > diff --git a/src/backend/rewrite/rewriteHandler.c > > b/src/backend/rewrite/rewriteHandler.c > > index fe777c3..d0f15b8 100644 > > --- a/src/backend/rewrite/rewriteHandler.c > > +++ b/src/backend/rewrite/rewriteHandler.c > > @@ -650,7 +650,7 @@ adjustJoinTreeList(Query *parsetree, bool removert, > int rt_index) > > if (IsA(rtr, RangeTblRef) && > > rtr->rtindex == rt_index) > > { > > - newjointree = > list_delete_ptr(newjointree, rtr); > > + newjointree = > > + list_delete_cell(newjointree, l); > > I think you may as well just use newjointree = > foreach_delete_current(newjointree, l);. The comment about why the > list_delete is ok inside a foreach is then irrelevant since > foreach_delete_current() is designed for deleting the current foreach cell. > > Looking around for other places I found two more in equivclass.c. > These two do require an additional moving part to keep track of the index > we want to delete, so they're not quite as clear cut a win to do. However, > I don't think tracking the index makes the code overly complex, so I'm > thinking they're both fine to do. Does anyone think differently? > > Updated patch attached. > Thanks for reviewing the patch! And after checking the code again and I found two more places which can be improved. 1. --- a/src/backend/parser/parse_expr.c +++ b/src/backend/parser/parse_expr.c @@ -1702,7 +1702,7 @@ transformMultiAssignRef(ParseState *pstate, MultiAssignRef *maref) */ if (maref->colno == maref->ncolumns) pstate->p_multiassign_exprs = - list_delete_ptr(pstate->p_multiassign_exprs, tle); + list_delete_last(pstate->p_multiassign_exprs); Based on the logic above in function transformMultiAssignRef, I found 'tle' is always the last one in list ' pstate->p_multiassign_exprs ' , So list_delete_last seems can be used here. 2. + nameEl_idx = foreach_current_index(option); } } @@ -405,7 +407,7 @@ generateSerialExtraStmts(CreateStmtContext *cxt, ColumnDef *column, } sname = rv->relname; /* Remove the SEQUENCE NAME item from seqoptions */ - seqoptions = list_delete_ptr(seqoptions, nameEl); + seqoptions = list_delete_nth_cell(seqoptions, nameEl_idx); Add a new var ' nameEl_idx ' to catch the index. Best regards, houzj
Вложения
Re: Use list_delete_xxxcell O(1) instead of list_delete_ptr O(N) in some places
От
David Rowley
Дата:
On Fri, 16 Oct 2020 at 16:42, Hou, Zhijie <houzj.fnst@cn.fujitsu.com> wrote: > And after checking the code again and I found two more places which can be improved. > > 1. > --- a/src/backend/parser/parse_expr.c > +++ b/src/backend/parser/parse_expr.c > @@ -1702,7 +1702,7 @@ transformMultiAssignRef(ParseState *pstate, MultiAssignRef *maref) > */ > if (maref->colno == maref->ncolumns) > pstate->p_multiassign_exprs = > - list_delete_ptr(pstate->p_multiassign_exprs, tle); > + list_delete_last(pstate->p_multiassign_exprs); > > Based on the logic above in function transformMultiAssignRef, > I found 'tle' is always the last one in list ' pstate->p_multiassign_exprs ' , > So list_delete_last seems can be used here. Yeah. After a bit of looking I agree. There's a similar assumption there already with: /* * Second or later column in a multiassignment. Re-fetch the * transformed SubLink or RowExpr, which we assume is still the last * entry in p_multiassign_exprs. */ Assert(pstate->p_multiassign_exprs != NIL); tle = (TargetEntry *) llast(pstate->p_multiassign_exprs); > 2. > > + nameEl_idx = foreach_current_index(option); > } > } > > @@ -405,7 +407,7 @@ generateSerialExtraStmts(CreateStmtContext *cxt, ColumnDef *column, > } > sname = rv->relname; > /* Remove the SEQUENCE NAME item from seqoptions */ > - seqoptions = list_delete_ptr(seqoptions, nameEl); > + seqoptions = list_delete_nth_cell(seqoptions, nameEl_idx); > > Add a new var ' nameEl_idx ' to catch the index. Yeah. That looks fine too. Pushed. David