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

  1. Doc: add some notes about performance of the List functions.

  2. Avoid O(N^2) behavior in SyncPostCheckpoint().

  3. Avoid some other O(N^2) hazards in list manipulation.

  4. Avoid O(N^2) behavior when the standby process releases many locks.