Re: inefficient loop in StandbyReleaseLockList()
Tom Lane <tgl@sss.pgh.pa.us>
From: Tom Lane <tgl@sss.pgh.pa.us>
To: "Bossart, Nathan" <bossartn@amazon.com>
Cc: Michael Paquier <michael@paquier.xyz>, Andres Freund <andres@anarazel.de>,
Kyotaro Horiguchi <horikyota.ntt@gmail.com>,
"sulamul@gmail.com" <sulamul@gmail.com>,
"pgsql-hackers@postgresql.org" <pgsql-hackers@postgresql.org>
Date: 2021-10-31T19:38:15Z
Lists: pgsql-hackers
"Bossart, Nathan" <bossartn@amazon.com> writes: > On 10/28/21, 11:53 PM, "Michael Paquier" <michael@paquier.xyz> wrote: >> Actually, as the list of recovery locks is saved in TopMemoryContext, >> wouldn't it be better to keep a per-cell deletion of the list, which >> would mean that we'd better do the operation in the reverse order to >> make things faster with the new list implementation? But that's what >> Andres points at with CFIs in the middle of one list of the hash table >> processed? > Hm. IIUC anything bad enough to cause the startup process to break > out of the StandbyReleaseLockList() loop will also cause the entire > process to be restarted. I'm not seeing any risk of reusing a half- > released lock list. I might be misunderstanding the concern, though. Yeah, there's no expectation that this data structure needs to be kept consistent after an error; and I'm not real sure that the existing code could claim to satisfy such a requirement if we did need it. (There's at least a short window where the caller's hash table entry will point at an already-freed List.) Pushed the patch as given. I've not yet reviewed other list_delete_first callers, but I'll take a look. (I seem to remember that I did survey them while writing 1cff1b95a, but I evidently missed that this code could be dealing with a list long enough to be problematic.) regards, tom lane
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