Horton

Re: inefficient loop in StandbyReleaseLockList()

Michael Paquier <michael@paquier.xyz>

View thread View on postgr.es
From: Michael Paquier <michael@paquier.xyz>
To: Kyotaro Horiguchi <horikyota.ntt@gmail.com>
Cc: sulamul@gmail.com, bossartn@amazon.com, pgsql-hackers@postgresql.org
Date: 2021-10-28T07:57:29Z
Lists: pgsql-hackers 
On Thu, Oct 28, 2021 at 03:57:51PM +0900, Kyotaro Horiguchi wrote:
> I found several other instances of the pattern
> "while(list){list_delete_first(); /*no-break*/}" in
> llvm_release_context, gistProcessEmptyingQueue, AtEOXact_Namespace and
> maybe transformGraph and processState in trgm_regexp.c.  We might want
> to apply this technique to the three first, and maybe to the last two.
> 
> However, I'm fine with fixing only StandbyRelaseLockList(), which
> actually suffers from list_delete_first().

I can also see a large gap between one technique and the other, so
this looks like a good catch to me coming from Nathan :)

As it could indeed hurt badly the time it takes to do a shutdown or to 
end recovery, we had better back-patch that down to 13 in my opinion.

transformGraph and processState seem to be worth improving on
performance ground, as well, but they look less critical than this
one but we could do something on HEAD.  Skimming through the rest of
the code, we may be able to improve some areas related to namespaces,
but that does not seem worth it in terms of code complication.
--
Michael

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.