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:14:24Z
Lists: pgsql-hackers 
Hi,

On 2021-10-28 15:07:48 -0700, Andres Freund wrote:
> 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...

Which leads to to wonder whether the better fix would be to switch to deleting
the last element, but still use the while (!empty) style. That should convert
the O(n^2) due to 1cff1b9 back to O(n). It might or might not be faster/slower
than using foreach(), but it should be within the same ballpark.

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.