Horton

Re: inefficient loop in StandbyReleaseLockList()

Andres Freund <andres@anarazel.de>

View thread View on postgr.es
From: Andres Freund <andres@anarazel.de>
To: Kyotaro Horiguchi <horikyota.ntt@gmail.com>
Cc: sulamul@gmail.com, bossartn@amazon.com, pgsql-hackers@postgresql.org
Date: 2021-10-28T22:07:48Z
Lists: pgsql-hackers 
Hi,

On 2021-10-28 15:57:51 +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.

We should be careful with changes like this, because there's some advantages
in the while(!empty) pattern too. Iterating over the whole list doesn't work
if there's any other modifications to the list, or if there's a chance of
errors. For the latter there just needs to be a CHECK_FOR_INTERRUPTS()
somewhere...

Greetings,

Andres Freund

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.