At Thu, 28 Oct 2021 09:54:42 +0530, Amul Sul <sula...@gmail.com> wrote in
> On Thu, Oct 28, 2021 at 9:07 AM Bossart, Nathan <bossa...@amazon.com> wrote:
> >
> > Hi hackers,
> >
> > I've seen a few cases now for v13 where the startup process on a
> > standby appears to be stuck on StandbyReleaseLockList(). It looks
> > like most of the time is spent on list_delete_first(). I believe this
> > is related to the recent list rewrite (1cff1b9), which has the
> > following note in the commit message:
> >
> > * Inserting or deleting a list element now takes time proportional
> > to
> > the distance to the end of the list, due to moving the array
> > elements.
> > (However, it typically *doesn't* require palloc or pfree, so except
> > in
> > long lists it's probably still faster than before.) Notably,
> > lcons()
> > used to be about the same cost as lappend(), but that's no longer
> > true
> > if the list is long. Code that uses lcons() and list_delete_first()
> > to maintain a stack might usefully be rewritten to push and pop at
> > the
> > end of the list rather than the beginning.
> >
> > The current form of StandbyReleaseLockList() is something like this:
> >
> > while (mylist != NIL)
> > {
> > int i = linitial_int(mylist);
> > ...
> > mylist = list_delete_first(mylist);
> > }
> >
> > For a long enough list, this is wildly inefficient. The following
> > form is much faster for longer lists:
> >
> > foreach(lc, mylist)
> > {
> > int i = lfirst_int(lc);
> > ...
> > }
> > list_free(mylist);
> >
> > I wrote up a simple test function for each form. For a list of
> > 500,000 integers, the first form took about a minute, while the second
> > form took about 6 milliseconds.
Nice finding!
> > I've attached a patch that converts StandbyReleaseLockList() to the
> > second loop form.
> >
>
> +1, deleting everything at once is much better. Deleting one by one
> using list_delete_first is a bit heavy; does the element shifting that
> involves memory allocation and copy operation which is unnecessary
> here.
+1.
I found several other instances of the pattern
"while(list){list_delete_first(); /*no-break*/}" in
llvm_release_context, gistProcessEmptyingQueue, AtEOXact_Namespace and
maybe transformGraph and processState in trgm_regexp.c. We might want
to apply this technique to the three first, and maybe to the last two.
However, I'm fine with fixing only StandbyRelaseLockList(), which
actually suffers from list_delete_first().
regards.
--
Kyotaro Horiguchi
NTT Open Source Software Center
