Horton

Re: inefficient loop in StandbyReleaseLockList()

Tom Lane <tgl@sss.pgh.pa.us>

View thread View on postgr.es
From: Tom Lane <tgl@sss.pgh.pa.us>
To: Andres Freund <andres@anarazel.de>
Cc: bossartn@amazon.com, Kyotaro Horiguchi <horikyota.ntt@gmail.com>, michael@paquier.xyz, sulamul@gmail.com, pgsql-hackers@postgresql.org
Date: 2021-11-05T00:21:56Z
Lists: pgsql-hackers 
Andres Freund <andres@anarazel.de> writes:
> 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.

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.

			regards, tom lane

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.