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
-
Doc: add some notes about performance of the List functions.
- 27ef132a805c 15.0 landed
-
Avoid O(N^2) behavior in SyncPostCheckpoint().
- 65c6cab1365a 15.0 landed
- 08cfa5981e17 14.1 landed
- 0151af40cd4e 13.5 landed
-
Avoid some other O(N^2) hazards in list manipulation.
- e477642a1ba8 13.5 landed
- ad87bf355214 14.1 landed
- e9d9ba2a4ddc 15.0 landed
-
Avoid O(N^2) behavior when the standby process releases many locks.
- df238aed1090 13.5 landed
- 8424dfced790 14.1 landed
- 6301c3adabd9 15.0 landed