inefficient loop in StandbyReleaseLockList()
Nathan Bossart <bossartn@amazon.com>
From: "Bossart, Nathan" <bossartn@amazon.com>
To: "pgsql-hackers@postgresql.org" <pgsql-hackers@postgresql.org>
Date: 2021-10-28T03:37:29Z
Lists: pgsql-hackers
Attachments
- improve_loop.patch (application/octet-stream) patch
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.
Nathan
Commits
-
Doc: add some notes about performance of the List functions.
- 27ef132a805c 15.0 landed
-
Avoid O(N^2) behavior in SyncPostCheckpoint().
- 65c6cab1365a 15.0 landed
- 08cfa5981e17 14.1 landed
- 0151af40cd4e 13.5 landed
-
Avoid some other O(N^2) hazards in list manipulation.
- e477642a1ba8 13.5 landed
- ad87bf355214 14.1 landed
- e9d9ba2a4ddc 15.0 landed
-
Avoid O(N^2) behavior when the standby process releases many locks.
- df238aed1090 13.5 landed
- 8424dfced790 14.1 landed
- 6301c3adabd9 15.0 landed