Re: inefficient loop in StandbyReleaseLockList()

On Thu, Oct 28, 2021 at 9:07 AM Bossart, Nathan <bossartn(at)amazon(dot)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