Use list_delete_xxxcell O(1) instead of list_delete_ptr O(N) in some places

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Use list_delete_xxxcell O(1) instead of list_delete_ptr O(N) in some places

Hou, Zhijie
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



0001-Use-list_delete_xxxcell-instead-of-list_delete_ptr.patch (2K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

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 more the expressive macro's for the list interface, so looks good to me.

The new status of this patch is: Ready for Committer
Reply | Threaded
Open this post in threaded view
|

Re: Use list_delete_xxxcell O(1) instead of list_delete_ptr O(N) in some places

David Rowley
In reply to this post by Hou, Zhijie
On Sat, 10 Oct 2020 at 15:45, Hou, Zhijie <[hidden email]> 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

optimize_a_few_list_delete_ptr_calls.patch (4K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

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




0001-optimize-a-few-list_delete_ptr-calls.patch (7K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

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 <[hidden email]> 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