Horton

Re: inefficient loop in StandbyReleaseLockList()

Nathan Bossart <bossartn@amazon.com>

View thread View on postgr.es
From: "Bossart, Nathan" <bossartn@amazon.com>
To: Tom Lane <tgl@sss.pgh.pa.us>, Andres Freund <andres@anarazel.de>
Cc: Kyotaro Horiguchi <horikyota.ntt@gmail.com>, "sulamul@gmail.com" <sulamul@gmail.com>, "pgsql-hackers@postgresql.org" <pgsql-hackers@postgresql.org>
Date: 2021-10-28T22:40:12Z
Lists: pgsql-hackers 
On 10/28/21, 3:15 PM, "Andres Freund" <andres@anarazel.de> wrote:
> Which leads to to wonder whether the better fix would be to switch to deleting
> the last element, but still use the while (!empty) style. That should convert
> the O(n^2) due to 1cff1b9 back to O(n). It might or might not be faster/slower
> than using foreach(), but it should be within the same ballpark.

Yeah, deleting from the end of the list yields a similar improvement.
foreach() appears to be slightly faster, but the difference is
basically negligible.  For a list of a million integers, foreach()
consistently takes ~12ms, deleting from the end of the list takes
~15ms, and deleting from the beginning of the list takes ~4 minutes.

Nathan

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.