Re: inefficient loop in StandbyReleaseLockList()

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