Horton

Re: inefficient loop in StandbyReleaseLockList()

Andres Freund <andres@anarazel.de>

View thread View on postgr.es
From: Andres Freund <andres@anarazel.de>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: bossartn@amazon.com, Kyotaro Horiguchi <horikyota.ntt@gmail.com>, michael@paquier.xyz, sulamul@gmail.com, pgsql-hackers@postgresql.org
Date: 2021-11-04T22:12:48Z
Lists: pgsql-hackers 
Hi,

On 2021-11-02 11:35:55 -0400, Tom Lane wrote:
> It's not clear that the remaining list_delete_first
> callers have any real problem; and changing them would be complex.

I wonder if it's worth adding a note to list_delete_first() mentioning its
O(N) behaviour. It's not immediately visible from the code, and from the list
name one could very well be excused to not be worried about O(N) costs.

Greetings,

Andres Freund

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.