Re: inefficient loop in StandbyReleaseLockList()

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

From: Tom Lane <tgl@sss.pgh.pa.us>
To: Kyotaro Horiguchi <horikyota.ntt@gmail.com>
Cc: bossartn@amazon.com, michael@paquier.xyz, andres@anarazel.de, sulamul@gmail.com, pgsql-hackers@postgresql.org
Date: 2021-11-02T14:21:48Z
Lists: pgsql-hackers
Kyotaro Horiguchi <horikyota.ntt@gmail.com> writes:
> At Mon, 01 Nov 2021 18:01:18 -0400, Tom Lane <tgl@sss.pgh.pa.us> wrote in 
>> So what I did in the attached is add a "canceled" flag to
>> PendingUnlinkEntry, which lets us deal with canceled or finished
>> entries without having to delete them from the list right away.
>> Then we only need to physically clean up the list once per
>> SyncPostCheckpoint call.

> We don't loop over so many canceled elements usually so I think it
> works well. However, shouldn't we consider canceled before checking
> cycle_ctr?

Good point.  I was thinking that it's best to break out of the loop
at the first opportunity.  But if the first few entries with the next
cycle_ctr value are canceled, it's best to advance over them in the
current SyncPostCheckpoint call.  It saves nothing to postpone that
work to later, and indeed adds a few cycles by leaving more data to
be copied by list_delete_first_n.  Will change it.

> I feel that we might need to wipe_mem for the memmove case as well
> (together with list_delete_nth_cell) but that is another thing even if
> that's correct.

Hm.  I made this function by copying-and-modifying list_delete_nth_cell,
so if there's something wrong there then this code inherited it.  But
I don't think it's wrong.  The wipe_mem business is only intended to
be used when enabling expensive debug options.

> Otherwise it looks good to me.

Thanks for looking!

			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.