Re: inefficient loop in StandbyReleaseLockList()

On Thu, Oct 28, 2021 at 9:07 AM Bossart, Nathan <bossartn@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.
>
> 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.

Regards,
Amul