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:22:51Z
Lists: pgsql-hackers 
Hi,

On 2021-11-06 14:06:12 -0400, Tom Lane wrote:
> I wrote:
> > Hm.  I think it's not the only list function with O(N) behavior;
> > in fact there used to be more such functions than there are now.
> > But I could get behind a patch that annotates all of them.

Personally I think the delete first is particularly easy to run into, due to
implementing fifo like behaviour. But I'm i


> Here's a quick hack at that.  Having done it, I'm not sure if it's
> really worth the trouble or not ... thoughts?

In favor of adding them.


> @@ -870,6 +890,9 @@ list_delete_oid(List *list, Oid datum)
>   * where the intent is to alter the list rather than just traverse it.
>   * Beware that the list is modified, whereas the Lisp-y coding leaves
>   * the original list head intact in case there's another pointer to it.
> + *
> + * 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.

This reminds me that I wanted a list splicing operation for ilist.h...

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.