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-06T22:46:48Z
Lists: pgsql-hackers 
On 2021-11-06 18:32:54 -0400, Tom Lane wrote:
> Andres Freund <andres@anarazel.de> writes:
> > On 2021-11-06 14:06:12 -0400, Tom Lane wrote:
> >> + * Note that this takes time proportional to the length of the list,
> >> + * since the remaining entries must be moved.
> >> */
> >> List *
> >> list_delete_first(List *list)
> 
> > Perhaps we could point to list_delete_last()? But it's an improvement without
> > that too.
> 
> Good point.  The note at list_delete_last that it's O(1) isn't really
> on point --- instead, the text for list_delete_first should be like
> 
> + * Note that this takes time proportional to the length of the list,
> + * since the remaining entries must be moved.  Consider reversing the
> + * list order so that you can use list_delete_last() instead.  However,
> + * if that causes you to replace lappend() with lcons(), you haven't
> + * improved matters.

LGTM

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.