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: Michael Paquier <michael@paquier.xyz>
Cc: Andres Freund <andres@anarazel.de>, bossartn@amazon.com, Kyotaro Horiguchi <horikyota.ntt@gmail.com>, sulamul@gmail.com, pgsql-hackers@postgresql.org
Date: 2021-11-05T02:47:23Z
Lists: pgsql-hackers 
Michael Paquier <michael@paquier.xyz> writes:
> On Thu, Nov 04, 2021 at 08:21:56PM -0400, Tom Lane 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.

> Documenting that makes sense.  Shouldn't we be careful to do that in
> both pg_list.h and list.c, then?

We have seldom, if ever, put function API-definition comments into .h files.
I do not see a reason why this case deserves an exception.  (It's tough
enough to get people to maintain definition comments that are right beside
the code they describe --- I think putting them in .h files would be a
disaster.)

			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.