Horton

Thread

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.

  1. inefficient loop in StandbyReleaseLockList()

    Nathan Bossart <bossartn@amazon.com> — 2021-10-28T03:37:29Z

    Hi hackers,

I've seen a few cases now for v13 where the startup process on a
standby appears to be stuck on StandbyReleaseLockList().  It looks
like most of the time is spent on list_delete_first().  I believe this
is related to the recent list rewrite (1cff1b9), which has the
following note in the commit message:

        * Inserting or deleting a list element now takes time proportional to
        the distance to the end of the list, due to moving the array elements.
        (However, it typically *doesn't* require palloc or pfree, so except in
        long lists it's probably still faster than before.)  Notably, lcons()
        used to be about the same cost as lappend(), but that's no longer true
        if the list is long.  Code that uses lcons() and list_delete_first()
        to maintain a stack might usefully be rewritten to push and pop at the
        end of the list rather than the beginning.

The current form of StandbyReleaseLockList() is something like this:

        while (mylist != NIL)
        {
                int i = linitial_int(mylist);
                ...
                mylist = list_delete_first(mylist);
        }

For a long enough list, this is wildly inefficient.  The following
form is much faster for longer lists:

        foreach(lc, mylist)
        {
                int i = lfirst_int(lc);
                ...
        }
        list_free(mylist);

I wrote up a simple test function for each form.  For a list of
500,000 integers, the first form took about a minute, while the second
form took about 6 milliseconds.

I've attached a patch that converts StandbyReleaseLockList() to the
second loop form.

Nathan

  2. Re: inefficient loop in StandbyReleaseLockList()

    Amul Sul <sulamul@gmail.com> — 2021-10-28T04:24:42Z

    On Thu, Oct 28, 2021 at 9:07 AM Bossart, Nathan <bossartn@amazon.com> wrote:
>
> Hi hackers,
>
> I've seen a few cases now for v13 where the startup process on a
> standby appears to be stuck on StandbyReleaseLockList().  It looks
> like most of the time is spent on list_delete_first().  I believe this
> is related to the recent list rewrite (1cff1b9), which has the
> following note in the commit message:
>
>         * Inserting or deleting a list element now takes time proportional to
>         the distance to the end of the list, due to moving the array elements.
>         (However, it typically *doesn't* require palloc or pfree, so except in
>         long lists it's probably still faster than before.)  Notably, lcons()
>         used to be about the same cost as lappend(), but that's no longer true
>         if the list is long.  Code that uses lcons() and list_delete_first()
>         to maintain a stack might usefully be rewritten to push and pop at the
>         end of the list rather than the beginning.
>
> The current form of StandbyReleaseLockList() is something like this:
>
>         while (mylist != NIL)
>         {
>                 int i = linitial_int(mylist);
>                 ...
>                 mylist = list_delete_first(mylist);
>         }
>
> For a long enough list, this is wildly inefficient.  The following
> form is much faster for longer lists:
>
>         foreach(lc, mylist)
>         {
>                 int i = lfirst_int(lc);
>                 ...
>         }
>         list_free(mylist);
>
> I wrote up a simple test function for each form.  For a list of
> 500,000 integers, the first form took about a minute, while the second
> form took about 6 milliseconds.
>
> I've attached a patch that converts StandbyReleaseLockList() to the
> second loop form.
>

+1, deleting everything at once is much better.  Deleting one by one
using list_delete_first is a bit heavy; does the element shifting that
involves memory allocation and copy operation which is unnecessary
here.

Regards,
Amul

  3. Re: inefficient loop in StandbyReleaseLockList()

    Kyotaro Horiguchi <horikyota.ntt@gmail.com> — 2021-10-28T06:57:51Z

    At Thu, 28 Oct 2021 09:54:42 +0530, Amul Sul <sulamul@gmail.com> wrote in 
> On Thu, Oct 28, 2021 at 9:07 AM Bossart, Nathan <bossartn@amazon.com> wrote:
> >
> > Hi hackers,
> >
> > I've seen a few cases now for v13 where the startup process on a
> > standby appears to be stuck on StandbyReleaseLockList().  It looks
> > like most of the time is spent on list_delete_first().  I believe this
> > is related to the recent list rewrite (1cff1b9), which has the
> > following note in the commit message:
> >
> >         * Inserting or deleting a list element now takes time proportional to
> >         the distance to the end of the list, due to moving the array elements.
> >         (However, it typically *doesn't* require palloc or pfree, so except in
> >         long lists it's probably still faster than before.)  Notably, lcons()
> >         used to be about the same cost as lappend(), but that's no longer true
> >         if the list is long.  Code that uses lcons() and list_delete_first()
> >         to maintain a stack might usefully be rewritten to push and pop at the
> >         end of the list rather than the beginning.
> >
> > The current form of StandbyReleaseLockList() is something like this:
> >
> >         while (mylist != NIL)
> >         {
> >                 int i = linitial_int(mylist);
> >                 ...
> >                 mylist = list_delete_first(mylist);
> >         }
> >
> > For a long enough list, this is wildly inefficient.  The following
> > form is much faster for longer lists:
> >
> >         foreach(lc, mylist)
> >         {
> >                 int i = lfirst_int(lc);
> >                 ...
> >         }
> >         list_free(mylist);
> >
> > I wrote up a simple test function for each form.  For a list of
> > 500,000 integers, the first form took about a minute, while the second
> > form took about 6 milliseconds.

Nice finding!

> > I've attached a patch that converts StandbyReleaseLockList() to the
> > second loop form.
> >
> 
> +1, deleting everything at once is much better.  Deleting one by one
> using list_delete_first is a bit heavy; does the element shifting that
> involves memory allocation and copy operation which is unnecessary
> here.

+1.

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().

regards.

-- 
Kyotaro Horiguchi
NTT Open Source Software Center

  4. Re: inefficient loop in StandbyReleaseLockList()

    Michael Paquier <michael@paquier.xyz> — 2021-10-28T07:57:29Z

    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

  5. Re: inefficient loop in StandbyReleaseLockList()

    Nathan Bossart <bossartn@amazon.com> — 2021-10-28T16:37:49Z

    On 10/28/21, 12:58 AM, "Michael Paquier" <michael@paquier.xyz> wrote:
> On Thu, Oct 28, 2021 at 03:57:51PM +0900, Kyotaro Horiguchi wrote:
>> 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.

+1

> 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.

I just did my own scan through uses of list_delete_first(), and I only
found a couple that might be easily transitioned to the foreach()
approach.  I don't think I'm going to pick that up at the moment, but
I'd readily help review such patches if there is a demonstrable
improvement.

Nathan

  6. Re: inefficient loop in StandbyReleaseLockList()

    Andres Freund <andres@anarazel.de> — 2021-10-28T22:07:48Z

    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

  7. Re: inefficient loop in StandbyReleaseLockList()

    Andres Freund <andres@anarazel.de> — 2021-10-28T22:14:24Z

    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

  8. Re: inefficient loop in StandbyReleaseLockList()

    Tom Lane <tgl@sss.pgh.pa.us> — 2021-10-28T22:24:51Z

    Andres Freund <andres@anarazel.de> writes:
> 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.

Does it matter what order we're releasing the locks in?

			regards, tom lane

  9. Re: inefficient loop in StandbyReleaseLockList()

    Nathan Bossart <bossartn@amazon.com> — 2021-10-28T22:40:12Z

    On 10/28/21, 3:15 PM, "Andres Freund" <andres@anarazel.de> wrote:
> 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.

Yeah, deleting from the end of the list yields a similar improvement.
foreach() appears to be slightly faster, but the difference is
basically negligible.  For a list of a million integers, foreach()
consistently takes ~12ms, deleting from the end of the list takes
~15ms, and deleting from the beginning of the list takes ~4 minutes.

Nathan

  10. Re: inefficient loop in StandbyReleaseLockList()

    Nathan Bossart <bossartn@amazon.com> — 2021-10-28T23:15:50Z

    On 10/28/21, 3:25 PM, "Tom Lane" <tgl@sss.pgh.pa.us> wrote:
> Andres Freund <andres@anarazel.de> writes:
>> 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.
>
> Does it matter what order we're releasing the locks in?

I'm not seeing anything that indicates the ordering matters.  AFAICT
either approach would work in this case.  IMO changing the order is
scarier than switching to foreach(), though.

Nathan

  11. Re: inefficient loop in StandbyReleaseLockList()

    Tom Lane <tgl@sss.pgh.pa.us> — 2021-10-28T23:24:08Z

    "Bossart, Nathan" <bossartn@amazon.com> writes:
> On 10/28/21, 3:25 PM, "Tom Lane" <tgl@sss.pgh.pa.us> wrote:
>> Does it matter what order we're releasing the locks in?

> I'm not seeing anything that indicates the ordering matters.  AFAICT
> either approach would work in this case.  IMO changing the order is
> scarier than switching to foreach(), though.

Yeah, that was my feeling...

			regards, tom lane

  12. Re: inefficient loop in StandbyReleaseLockList()

    Andres Freund <andres@anarazel.de> — 2021-10-28T23:52:48Z

    Hi,

On 2021-10-28 19:24:08 -0400, Tom Lane wrote:
> "Bossart, Nathan" <bossartn@amazon.com> writes:
> > On 10/28/21, 3:25 PM, "Tom Lane" <tgl@sss.pgh.pa.us> wrote:
> >> Does it matter what order we're releasing the locks in?
> 
> > I'm not seeing anything that indicates the ordering matters.  AFAICT
> > either approach would work in this case.  IMO changing the order is
> > scarier than switching to foreach(), though.
> 
> Yeah, that was my feeling...

I suspect the reverse lock order release could be tad faster. But I probably
wouldn't change it either - I was more thinking of some of the other cases
that deleted the first element, here it's a bit harder to know wether there's
a chance of a CFI() or such.

Greetings,

Andres Freund

  13. Re: inefficient loop in StandbyReleaseLockList()

    Michael Paquier <michael@paquier.xyz> — 2021-10-29T06:52:30Z

    On Thu, Oct 28, 2021 at 04:52:48PM -0700, Andres Freund wrote:
> I suspect the reverse lock order release could be tad faster. But I probably
> wouldn't change it either - I was more thinking of some of the other cases
> that deleted the first element, here it's a bit harder to know wether there's
> a chance of a CFI() or such.

Actually, as the list of recovery locks is saved in TopMemoryContext,
wouldn't it be better to keep a per-cell deletion of the list, which
would mean that we'd better do the operation in the reverse order to
make things faster with the new list implementation?  But that's what
Andres points at with CFIs in the middle of one list of the hash table
processed?
--
Michael

  14. Re: inefficient loop in StandbyReleaseLockList()

    Nathan Bossart <bossartn@amazon.com> — 2021-10-29T17:30:44Z

    On 10/28/21, 11:53 PM, "Michael Paquier" <michael@paquier.xyz> wrote:
> On Thu, Oct 28, 2021 at 04:52:48PM -0700, Andres Freund wrote:
>> I suspect the reverse lock order release could be tad faster. But I probably
>> wouldn't change it either - I was more thinking of some of the other cases
>> that deleted the first element, here it's a bit harder to know wether there's
>> a chance of a CFI() or such.
>
> Actually, as the list of recovery locks is saved in TopMemoryContext,
> wouldn't it be better to keep a per-cell deletion of the list, which
> would mean that we'd better do the operation in the reverse order to
> make things faster with the new list implementation?  But that's what
> Andres points at with CFIs in the middle of one list of the hash table
> processed?

Hm.  IIUC anything bad enough to cause the startup process to break
out of the StandbyReleaseLockList() loop will also cause the entire
process to be restarted.  I'm not seeing any risk of reusing a half-
released lock list.  I might be misunderstanding the concern, though.

Nathan

  15. Re: inefficient loop in StandbyReleaseLockList()

    Tom Lane <tgl@sss.pgh.pa.us> — 2021-10-31T19:38:15Z

    "Bossart, Nathan" <bossartn@amazon.com> writes:
> On 10/28/21, 11:53 PM, "Michael Paquier" <michael@paquier.xyz> wrote:
>> Actually, as the list of recovery locks is saved in TopMemoryContext,
>> wouldn't it be better to keep a per-cell deletion of the list, which
>> would mean that we'd better do the operation in the reverse order to
>> make things faster with the new list implementation?  But that's what
>> Andres points at with CFIs in the middle of one list of the hash table
>> processed?

> Hm.  IIUC anything bad enough to cause the startup process to break
> out of the StandbyReleaseLockList() loop will also cause the entire
> process to be restarted.  I'm not seeing any risk of reusing a half-
> released lock list.  I might be misunderstanding the concern, though.

Yeah, there's no expectation that this data structure needs to be kept
consistent after an error; and I'm not real sure that the existing
code could claim to satisfy such a requirement if we did need it.
(There's at least a short window where the caller's hash table entry
will point at an already-freed List.)

Pushed the patch as given.  I've not yet reviewed other list_delete_first
callers, but I'll take a look.  (I seem to remember that I did survey
them while writing 1cff1b95a, but I evidently missed that this code
could be dealing with a list long enough to be problematic.)

			regards, tom lane

  16. Re: inefficient loop in StandbyReleaseLockList()

    Andres Freund <andres@anarazel.de> — 2021-10-31T20:37:48Z

    Hi,

On 2021-10-31 15:38:15 -0400, Tom Lane wrote:
> Yeah, there's no expectation that this data structure needs to be kept
> consistent after an error; and I'm not real sure that the existing
> code could claim to satisfy such a requirement if we did need it.

To be clear, I was making that comment in response to the search for
other places doing the while(!empty) delete_first() style loops. Some of
them are reached via resowners etc, where reaching the same code
repeatedly is perhaps more realistic.

Greetings,

Andres Freund

  17. Re: inefficient loop in StandbyReleaseLockList()

    Tom Lane <tgl@sss.pgh.pa.us> — 2021-10-31T20:55:01Z

    I wrote:
> Pushed the patch as given.  I've not yet reviewed other list_delete_first
> callers, but I'll take a look.  (I seem to remember that I did survey
> them while writing 1cff1b95a, but I evidently missed that this code
> could be dealing with a list long enough to be problematic.)

I looked at the remaining list_delete_first callers.

1. Attached is a proposed patch to get rid of the calls in trgm_regexp.c.
I'm not certain that those lists could get long enough to be a problem,
given the existing complexity limits in that file (MAX_EXPANDED_STATES
etc).  But I'm not certain they can't, either, and it's easy enough to
fix along the same lines as in StandbyReleaseLockList.

2. I think we almost certainly have a problem in SyncPostCheckpoint.

3. Is agg_refill_hash_table a problem?  Probably; we've seen cases
with lots of batches.

4. I'm a bit worried about the uses in access/gist/, but I don't know
that code well enough to want to mess with it.  It's possible the
list lengths are bounded by the index tree height, in which case it
likely doesn't matter.  The logic in gistFindPath looks like a mess
anyway since it's appending to both ends of the "fifo" list in different
places (is that really necessary?).

5. Not sure about CopyMultiInsertInfoFlush ... how many buffers
could we have there?

6. llvm_release_context may not have a long enough list to be a
problem, but on the other hand, it looks easy to fix.

7. The list lengths in the parser and dependency.c, ruleutils.c,
explain.c are bounded by subquery nesting depth or plan tree depth,
so I doubt it's worth worrying about.

8. The uses in namespace.c don't seem like an issue either -- for
instance, GetOverrideSearchPath can't iterate more than twice,
and the overrideStack list shouldn't get very deep.

			regards, tom lane

  18. Re: inefficient loop in StandbyReleaseLockList()

    Kyotaro Horiguchi <horikyota.ntt@gmail.com> — 2021-11-01T02:40:19Z

    At Sun, 31 Oct 2021 16:55:01 -0400, Tom Lane <tgl@sss.pgh.pa.us> wrote in 
> I wrote:
> > Pushed the patch as given.  I've not yet reviewed other list_delete_first
> > callers, but I'll take a look.  (I seem to remember that I did survey
> > them while writing 1cff1b95a, but I evidently missed that this code
> > could be dealing with a list long enough to be problematic.)
> 
> I looked at the remaining list_delete_first callers.
> 
> 1. Attached is a proposed patch to get rid of the calls in trgm_regexp.c.
> I'm not certain that those lists could get long enough to be a problem,
> given the existing complexity limits in that file (MAX_EXPANDED_STATES
> etc).  But I'm not certain they can't, either, and it's easy enough to
> fix along the same lines as in StandbyReleaseLockList.

I should be missing something, but at the added list_free() there's a
case where keysQueue has some elelments.  I think the remaining
elements are useless but AFAICS all the memory allocated there is
freed after createTrgmNFAInternal returnes, before the "next cycle"
comes. Do we need to add that list_free there?

> 2. I think we almost certainly have a problem in SyncPostCheckpoint.

Maybe we want list_delete_first_n() or such to remove the first n
elements in a list at once.

> 3. Is agg_refill_hash_table a problem?  Probably; we've seen cases
> with lots of batches.

I excluded it since I'm not sure it is in the pattern at a glance. I
would want to leave it alone, since changing the logic there seems
making things a bit complex and the gain by removing list_delete_first
doesn't look so large..

> 4. I'm a bit worried about the uses in access/gist/, but I don't know
> that code well enough to want to mess with it.  It's possible the
> list lengths are bounded by the index tree height, in which case it
> likely doesn't matter.  The logic in gistFindPath looks like a mess
> anyway since it's appending to both ends of the "fifo" list in different
> places (is that really necessary?).

From the other side, the elemnts are inserted by lcons, then removed
by list_delete_first.  It is the worst usage of the current list
implementation as a FIFO. Couldn't we construct and iterate over a
list in the reverse order?

> 5. Not sure about CopyMultiInsertInfoFlush ... how many buffers
> could we have there?

(I'm not sure..)

> 6. llvm_release_context may not have a long enough list to be a
> problem, but on the other hand, it looks easy to fix.

Agreed.

> 7. The list lengths in the parser and dependency.c, ruleutils.c,
> explain.c are bounded by subquery nesting depth or plan tree depth,
> so I doubt it's worth worrying about.

Agreed.

> 8. The uses in namespace.c don't seem like an issue either -- for
> instance, GetOverrideSearchPath can't iterate more than twice,
> and the overrideStack list shouldn't get very deep.

If we didn't need the resulting list I'm for changing it but actually
it is needed. So I think we won't get so much by changing the
function.

regards.

-- 
Kyotaro Horiguchi
NTT Open Source Software Center

  19. Re: inefficient loop in StandbyReleaseLockList()

    Tom Lane <tgl@sss.pgh.pa.us> — 2021-11-01T15:58:35Z

    Kyotaro Horiguchi <horikyota.ntt@gmail.com> writes:
> At Sun, 31 Oct 2021 16:55:01 -0400, Tom Lane <tgl@sss.pgh.pa.us> wrote in 
>> I looked at the remaining list_delete_first callers.
>> 
>> 1. Attached is a proposed patch to get rid of the calls in trgm_regexp.c.
>> I'm not certain that those lists could get long enough to be a problem,
>> given the existing complexity limits in that file (MAX_EXPANDED_STATES
>> etc).  But I'm not certain they can't, either, and it's easy enough to
>> fix along the same lines as in StandbyReleaseLockList.

> I should be missing something, but at the added list_free() there's a
> case where keysQueue has some elelments.  I think the remaining
> elements are useless but AFAICS all the memory allocated there is
> freed after createTrgmNFAInternal returnes, before the "next cycle"
> comes. Do we need to add that list_free there?

I was mainly trying to preserve the memory allocation behavior of the
current code, which will free the List when its last element is removed.
I agree that it *probably* doesn't matter --- but processState is
invoked multiple times during one createTrgmNFAInternal call, so I'm
not quite sure that leaking all those lists couldn't amount to anything.
It seemed prudent to ensure that things couldn't be made worse by this
patch.

>> 3. Is agg_refill_hash_table a problem?  Probably; we've seen cases
>> with lots of batches.

> I excluded it since I'm not sure it is in the pattern at a glance. I
> would want to leave it alone, since changing the logic there seems
> making things a bit complex and the gain by removing list_delete_first
> doesn't look so large..

It looks to me like nodeAgg.c uses the hash_batches list as a stack:
it's pushing things on with lcons, and later popping them off with
list_delete_first.  This is exactly the pattern that 1cff1b95a
recommended reversing.  Now, it's possible that that stack never gets
deep enough for the O(N^2) cost to matter, but ...

>> The logic in gistFindPath looks like a mess
>> anyway since it's appending to both ends of the "fifo" list in different
>> places (is that really necessary?).

> From the other side, the elemnts are inserted by lcons, then removed
> by list_delete_first.  It is the worst usage of the current list
> implementation as a FIFO. Couldn't we construct and iterate over a
> list in the reverse order?

Yeah; at the very least, the use of both lcons and lappend falsifies
the variable name "fifo".  I wonder though if that was intentional
or just somebody's sloppy coding.

			regards, tom lane

  20. Re: inefficient loop in StandbyReleaseLockList()

    Nathan Bossart <bossartn@amazon.com> — 2021-11-01T16:00:54Z

    On 10/31/21, 12:39 PM, "Tom Lane" <tgl@sss.pgh.pa.us> wrote:
> Yeah, there's no expectation that this data structure needs to be kept
> consistent after an error; and I'm not real sure that the existing
> code could claim to satisfy such a requirement if we did need it.
> (There's at least a short window where the caller's hash table entry
> will point at an already-freed List.)

Right.

> Pushed the patch as given.  I've not yet reviewed other list_delete_first
> callers, but I'll take a look.  (I seem to remember that I did survey
> them while writing 1cff1b95a, but I evidently missed that this code
> could be dealing with a list long enough to be problematic.)

Thanks!

Nathan

  21. Re: inefficient loop in StandbyReleaseLockList()

    Nathan Bossart <bossartn@amazon.com> — 2021-11-01T16:50:55Z

    On 10/31/21, 1:55 PM, "Tom Lane" <tgl@sss.pgh.pa.us> wrote:
> 1. Attached is a proposed patch to get rid of the calls in trgm_regexp.c.
> I'm not certain that those lists could get long enough to be a problem,
> given the existing complexity limits in that file (MAX_EXPANDED_STATES
> etc).  But I'm not certain they can't, either, and it's easy enough to
> fix along the same lines as in StandbyReleaseLockList.

Should there be a list_free(trgmNFA->queue) at the end of
transformGraph()?

> 2. I think we almost certainly have a problem in SyncPostCheckpoint.

This one doesn't look as straightforward.  It looks like we might need
a list_delete_first_n() to delete the first N entries all at once to
improve this one.

> 3. Is agg_refill_hash_table a problem?  Probably; we've seen cases
> with lots of batches.

IIUC this one can be improved by pushing/popping from the end of the
list instead of the beginning.

> 4. I'm a bit worried about the uses in access/gist/, but I don't know
> that code well enough to want to mess with it.  It's possible the
> list lengths are bounded by the index tree height, in which case it
> likely doesn't matter.  The logic in gistFindPath looks like a mess
> anyway since it's appending to both ends of the "fifo" list in different
> places (is that really necessary?).
>
> 5. Not sure about CopyMultiInsertInfoFlush ... how many buffers
> could we have there?

I haven't looked too closely at these.

> 6. llvm_release_context may not have a long enough list to be a
> problem, but on the other hand, it looks easy to fix.

Yeah, I reviewed this one earlier.  I didn't see any reason this one
couldn't be changed to foreach().

> 7. The list lengths in the parser and dependency.c, ruleutils.c,
> explain.c are bounded by subquery nesting depth or plan tree depth,
> so I doubt it's worth worrying about.

+1

> 8. The uses in namespace.c don't seem like an issue either -- for
> instance, GetOverrideSearchPath can't iterate more than twice,
> and the overrideStack list shouldn't get very deep.

+1

Nathan

  22. Re: inefficient loop in StandbyReleaseLockList()

    Tom Lane <tgl@sss.pgh.pa.us> — 2021-11-01T16:57:27Z

    "Bossart, Nathan" <bossartn@amazon.com> writes:
> On 10/31/21, 1:55 PM, "Tom Lane" <tgl@sss.pgh.pa.us> wrote:
>> 1. Attached is a proposed patch to get rid of the calls in trgm_regexp.c.

> Should there be a list_free(trgmNFA->queue) at the end of
> transformGraph()?

There could be, but that's visibly invoked only once per 
createTrgmNFAInternal call, so I didn't think it was worthwhile
to do so (unlike the case for processState).  If we were concerned
about leakage in that function, the hash table would be a far
bigger issue.

			regards, tom lane

  23. Re: inefficient loop in StandbyReleaseLockList()

    Nathan Bossart <bossartn@amazon.com> — 2021-11-01T17:02:49Z

    On 11/1/21, 9:58 AM, "Tom Lane" <tgl@sss.pgh.pa.us> wrote:
> "Bossart, Nathan" <bossartn@amazon.com> writes:
>> Should there be a list_free(trgmNFA->queue) at the end of
>> transformGraph()?
>
> There could be, but that's visibly invoked only once per
> createTrgmNFAInternal call, so I didn't think it was worthwhile
> to do so (unlike the case for processState).  If we were concerned
> about leakage in that function, the hash table would be a far
> bigger issue.

Ah, I see it now.  The patch looks good to me, then.

Nathan

  24. Re: inefficient loop in StandbyReleaseLockList()

    Tom Lane <tgl@sss.pgh.pa.us> — 2021-11-01T17:32:41Z

    "Bossart, Nathan" <bossartn@amazon.com> writes:
> Ah, I see it now.  The patch looks good to me, then.

Thanks for looking!  Here's an expanded patch that also takes care
of the other two easy-to-fix cases, nodeAgg.c and llvmjit.c.
AFAICS, llvm_release_context is like StandbyReleaseLockList
in that we don't need to worry about whether the data structure
is valid after an error partway through.  (Maybe we should be
worrying, but I think the callers would need work as well if
that's to be the standard.)

			regards, tom lane

  25. Re: inefficient loop in StandbyReleaseLockList()

    Nathan Bossart <bossartn@amazon.com> — 2021-11-01T18:35:30Z

    On 11/1/21, 10:34 AM, "Tom Lane" <tgl@sss.pgh.pa.us> wrote:
> Thanks for looking!  Here's an expanded patch that also takes care
> of the other two easy-to-fix cases, nodeAgg.c and llvmjit.c.
> AFAICS, llvm_release_context is like StandbyReleaseLockList
> in that we don't need to worry about whether the data structure
> is valid after an error partway through.  (Maybe we should be
> worrying, but I think the callers would need work as well if
> that's to be the standard.)

LGTM.

Nathan

  26. Re: inefficient loop in StandbyReleaseLockList()

    Tom Lane <tgl@sss.pgh.pa.us> — 2021-11-01T22:01:18Z

    "Bossart, Nathan" <bossartn@amazon.com> writes:
> On 10/31/21, 1:55 PM, "Tom Lane" <tgl@sss.pgh.pa.us> wrote:
>> 2. I think we almost certainly have a problem in SyncPostCheckpoint.

> This one doesn't look as straightforward.  It looks like we might need
> a list_delete_first_n() to delete the first N entries all at once to
> improve this one.

Yeah.  We don't absolutely need a new list primitive: we could use
list_copy_tail() and then free the old list.  But the extra palloc
traffic involved makes this sound like a bad idea.  It does have
the advantage that we could shorten the List's storage even when
it doesn't go to empty, but I'm not sure that's worth anything.
If the List isn't going to empty, that implies that we're getting
a steady stream of unlink requests, meaning we'd probably just
fill it up again.

The minimum-change patch would have us truncating the list before
each AbsorbSyncRequests call, so that the list state meets that
function's expectations.  However, as long as UNLINKS_PER_ABSORB
is only 10, I don't think that gets us out of the O(N^2) woods.
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.

			regards, tom lane

  27. Re: inefficient loop in StandbyReleaseLockList()

    Kyotaro Horiguchi <horikyota.ntt@gmail.com> — 2021-11-02T00:57:48Z

    At Mon, 01 Nov 2021 11:58:35 -0400, Tom Lane <tgl@sss.pgh.pa.us> wrote in 
> Kyotaro Horiguchi <horikyota.ntt@gmail.com> writes:
> > At Sun, 31 Oct 2021 16:55:01 -0400, Tom Lane <tgl@sss.pgh.pa.us> wrote in 
> >> I looked at the remaining list_delete_first callers.
> >> 
> >> 1. Attached is a proposed patch to get rid of the calls in trgm_regexp.c.
> >> I'm not certain that those lists could get long enough to be a problem,
> >> given the existing complexity limits in that file (MAX_EXPANDED_STATES
> >> etc).  But I'm not certain they can't, either, and it's easy enough to
> >> fix along the same lines as in StandbyReleaseLockList.
> 
> > I should be missing something, but at the added list_free() there's a
> > case where keysQueue has some elelments.  I think the remaining
> > elements are useless but AFAICS all the memory allocated there is
> > freed after createTrgmNFAInternal returnes, before the "next cycle"
> > comes. Do we need to add that list_free there?
> 
> I was mainly trying to preserve the memory allocation behavior of the
> current code, which will free the List when its last element is removed.
> I agree that it *probably* doesn't matter --- but processState is
> invoked multiple times during one createTrgmNFAInternal call, so I'm
> not quite sure that leaking all those lists couldn't amount to anything.
> It seemed prudent to ensure that things couldn't be made worse by this
> patch.

Hmm. Actually that's a kind of convincing.  Thinking together with the
reason for not releasing ramaining elements,  It's fine with me.

> >> 3. Is agg_refill_hash_table a problem?  Probably; we've seen cases
> >> with lots of batches.
> 
> > I excluded it since I'm not sure it is in the pattern at a glance. I
> > would want to leave it alone, since changing the logic there seems
> > making things a bit complex and the gain by removing list_delete_first
> > doesn't look so large..
> 
> It looks to me like nodeAgg.c uses the hash_batches list as a stack:
> it's pushing things on with lcons, and later popping them off with
> list_delete_first.  This is exactly the pattern that 1cff1b95a
> recommended reversing.  Now, it's possible that that stack never gets
> deep enough for the O(N^2) cost to matter, but ...

Right. And the patch in another branch looks good to me.

> >> The logic in gistFindPath looks like a mess
> >> anyway since it's appending to both ends of the "fifo" list in different
> >> places (is that really necessary?).
> 
> > From the other side, the elemnts are inserted by lcons, then removed
> > by list_delete_first.  It is the worst usage of the current list
> > implementation as a FIFO. Couldn't we construct and iterate over a
> > list in the reverse order?
> 
> Yeah; at the very least, the use of both lcons and lappend falsifies
> the variable name "fifo".  I wonder though if that was intentional
> or just somebody's sloppy coding.

It looks like intentional.

> /* Append this child to the list of pages to visit later */

So we would replace the lappend with lcons for the same effect with
the reverse list.

regards.

-- 
Kyotaro Horiguchi
NTT Open Source Software Center

  28. Re: inefficient loop in StandbyReleaseLockList()

    Kyotaro Horiguchi <horikyota.ntt@gmail.com> — 2021-11-02T00:58:16Z

    At Mon, 1 Nov 2021 17:02:49 +0000, "Bossart, Nathan" <bossartn@amazon.com> wrote in 
> On 11/1/21, 9:58 AM, "Tom Lane" <tgl@sss.pgh.pa.us> wrote:
> > "Bossart, Nathan" <bossartn@amazon.com> writes:
> >> Should there be a list_free(trgmNFA->queue) at the end of
> >> transformGraph()?
> >
> > There could be, but that's visibly invoked only once per
> > createTrgmNFAInternal call, so I didn't think it was worthwhile
> > to do so (unlike the case for processState).  If we were concerned
> > about leakage in that function, the hash table would be a far
> > bigger issue.
> 
> Ah, I see it now.  The patch looks good to me, then.

+1

-- 
Kyotaro Horiguchi
NTT Open Source Software Center

  29. Re: inefficient loop in StandbyReleaseLockList()

    Kyotaro Horiguchi <horikyota.ntt@gmail.com> — 2021-11-02T02:43:13Z

    At Mon, 01 Nov 2021 18:01:18 -0400, Tom Lane <tgl@sss.pgh.pa.us> wrote in 
> "Bossart, Nathan" <bossartn@amazon.com> writes:
> > On 10/31/21, 1:55 PM, "Tom Lane" <tgl@sss.pgh.pa.us> wrote:
> >> 2. I think we almost certainly have a problem in SyncPostCheckpoint.
> 
> > This one doesn't look as straightforward.  It looks like we might need
> > a list_delete_first_n() to delete the first N entries all at once to
> > improve this one.
> 
> Yeah.  We don't absolutely need a new list primitive: we could use
> list_copy_tail() and then free the old list.  But the extra palloc
> traffic involved makes this sound like a bad idea.  It does have
> the advantage that we could shorten the List's storage even when
> it doesn't go to empty, but I'm not sure that's worth anything.
> If the List isn't going to empty, that implies that we're getting
> a steady stream of unlink requests, meaning we'd probably just
> fill it up again.

I agree to that.  In general I think it's better not to resize storage
on truncation (or shortning) of a list except for a few special cases.
(for example, for a list that temporarily grows prominently but won't
go empty)

> The minimum-change patch would have us truncating the list before
> each AbsorbSyncRequests call, so that the list state meets that
> function's expectations.  However, as long as UNLINKS_PER_ABSORB
> is only 10, I don't think that gets us out of the O(N^2) woods.

Agreed.

> 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?  A canceled elements should be invisible from later
accesses at all.  I vaguely feel the name "cancel" might be better be
"consumed" or such but I don't object to "cancel".

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.

Otherwise it looks good to me.

regards.

-- 
Kyotaro Horiguchi
NTT Open Source Software Center

  30. Re: inefficient loop in StandbyReleaseLockList()

    Tom Lane <tgl@sss.pgh.pa.us> — 2021-11-02T14:21:48Z

    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

  31. Re: inefficient loop in StandbyReleaseLockList()

    Tom Lane <tgl@sss.pgh.pa.us> — 2021-11-02T15:35:55Z

    I've pushed the SyncPostCheckpoint change, and I think I'm going
to stop here.  It's not clear that the remaining list_delete_first
callers have any real problem; and changing them would be complex.
We can revisit the question if we find out there is an issue.
Or, if somebody else wants to pursue the issue, feel free.

			regards, tom lane

  32. Re: inefficient loop in StandbyReleaseLockList()

    Nathan Bossart <bossartn@amazon.com> — 2021-11-02T15:39:38Z

    On 11/2/21, 8:36 AM, "Tom Lane" <tgl@sss.pgh.pa.us> wrote:
> I've pushed the SyncPostCheckpoint change, and I think I'm going
> to stop here.  It's not clear that the remaining list_delete_first
> callers have any real problem; and changing them would be complex.
> We can revisit the question if we find out there is an issue.
> Or, if somebody else wants to pursue the issue, feel free.

Thanks!

Nathan

  33. Re: inefficient loop in StandbyReleaseLockList()

    Andres Freund <andres@anarazel.de> — 2021-11-04T22:12:48Z

    Hi,

On 2021-11-02 11:35:55 -0400, Tom Lane wrote:
> It's not clear that the remaining list_delete_first
> callers have any real problem; and changing them would be complex.

I wonder if it's worth adding a note to list_delete_first() mentioning its
O(N) behaviour. It's not immediately visible from the code, and from the list
name one could very well be excused to not be worried about O(N) costs.

Greetings,

Andres Freund

  34. Re: inefficient loop in StandbyReleaseLockList()

    Tom Lane <tgl@sss.pgh.pa.us> — 2021-11-05T00:21:56Z

    Andres Freund <andres@anarazel.de> writes:
> I wonder if it's worth adding a note to list_delete_first() mentioning its
> O(N) behaviour. It's not immediately visible from the code, and from the list
> name one could very well be excused to not be worried about O(N) costs.

Hm.  I think it's not the only list function with O(N) behavior;
in fact there used to be more such functions than there are now.
But I could get behind a patch that annotates all of them.

			regards, tom lane

  35. Re: inefficient loop in StandbyReleaseLockList()

    Michael Paquier <michael@paquier.xyz> — 2021-11-05T02:40:00Z

    On Thu, Nov 04, 2021 at 08:21:56PM -0400, Tom Lane wrote:
> Andres Freund <andres@anarazel.de> writes:
> > I wonder if it's worth adding a note to list_delete_first() mentioning its
> > O(N) behaviour. It's not immediately visible from the code, and from the list
> > name one could very well be excused to not be worried about O(N) costs.
> 
> Hm.  I think it's not the only list function with O(N) behavior;
> in fact there used to be more such functions than there are now.
> But I could get behind a patch that annotates all of them.

Documenting that makes sense.  Shouldn't we be careful to do that in
both pg_list.h and list.c, then?
--
Michael

  36. Re: inefficient loop in StandbyReleaseLockList()

    Tom Lane <tgl@sss.pgh.pa.us> — 2021-11-05T02:47:23Z

    Michael Paquier <michael@paquier.xyz> writes:
> On Thu, Nov 04, 2021 at 08:21:56PM -0400, Tom Lane wrote:
>> Hm.  I think it's not the only list function with O(N) behavior;
>> in fact there used to be more such functions than there are now.
>> But I could get behind a patch that annotates all of them.

> Documenting that makes sense.  Shouldn't we be careful to do that in
> both pg_list.h and list.c, then?

We have seldom, if ever, put function API-definition comments into .h files.
I do not see a reason why this case deserves an exception.  (It's tough
enough to get people to maintain definition comments that are right beside
the code they describe --- I think putting them in .h files would be a
disaster.)

			regards, tom lane

  37. Re: inefficient loop in StandbyReleaseLockList()

    Tom Lane <tgl@sss.pgh.pa.us> — 2021-11-06T18:06:12Z

    I wrote:
> Hm.  I think it's not the only list function with O(N) behavior;
> in fact there used to be more such functions than there are now.
> But I could get behind a patch that annotates all of them.

Here's a quick hack at that.  Having done it, I'm not sure if it's
really worth the trouble or not ... thoughts?

			regards, tom lane

  38. Re: inefficient loop in StandbyReleaseLockList()

    Andres Freund <andres@anarazel.de> — 2021-11-06T22:22:51Z

    Hi,

On 2021-11-06 14:06:12 -0400, Tom Lane wrote:
> I wrote:
> > Hm.  I think it's not the only list function with O(N) behavior;
> > in fact there used to be more such functions than there are now.
> > But I could get behind a patch that annotates all of them.

Personally I think the delete first is particularly easy to run into, due to
implementing fifo like behaviour. But I'm i


> Here's a quick hack at that.  Having done it, I'm not sure if it's
> really worth the trouble or not ... thoughts?

In favor of adding them.


> @@ -870,6 +890,9 @@ list_delete_oid(List *list, Oid datum)
>   * where the intent is to alter the list rather than just traverse it.
>   * Beware that the list is modified, whereas the Lisp-y coding leaves
>   * the original list head intact in case there's another pointer to it.
> + *
> + * Note that this takes time proportional to the length of the list,
> + * since the remaining entries must be moved.
>   */
>  List *
>  list_delete_first(List *list)

Perhaps we could point to list_delete_last()? But it's an improvement without
that too.

This reminds me that I wanted a list splicing operation for ilist.h...

Greetings,

Andres Freund

  39. Re: inefficient loop in StandbyReleaseLockList()

    Tom Lane <tgl@sss.pgh.pa.us> — 2021-11-06T22:32:54Z

    Andres Freund <andres@anarazel.de> writes:
> On 2021-11-06 14:06:12 -0400, Tom Lane wrote:
>> + * Note that this takes time proportional to the length of the list,
>> + * since the remaining entries must be moved.
>> */
>> List *
>> list_delete_first(List *list)

> Perhaps we could point to list_delete_last()? But it's an improvement without
> that too.

Good point.  The note at list_delete_last that it's O(1) isn't really
on point --- instead, the text for list_delete_first should be like

+ * Note that this takes time proportional to the length of the list,
+ * since the remaining entries must be moved.  Consider reversing the
+ * list order so that you can use list_delete_last() instead.  However,
+ * if that causes you to replace lappend() with lcons(), you haven't
+ * improved matters.

			regards, tom lane

  40. Re: inefficient loop in StandbyReleaseLockList()

    Andres Freund <andres@anarazel.de> — 2021-11-06T22:46:48Z

    On 2021-11-06 18:32:54 -0400, Tom Lane wrote:
> Andres Freund <andres@anarazel.de> writes:
> > On 2021-11-06 14:06:12 -0400, Tom Lane wrote:
> >> + * Note that this takes time proportional to the length of the list,
> >> + * since the remaining entries must be moved.
> >> */
> >> List *
> >> list_delete_first(List *list)
> 
> > Perhaps we could point to list_delete_last()? But it's an improvement without
> > that too.
> 
> Good point.  The note at list_delete_last that it's O(1) isn't really
> on point --- instead, the text for list_delete_first should be like
> 
> + * Note that this takes time proportional to the length of the list,
> + * since the remaining entries must be moved.  Consider reversing the
> + * list order so that you can use list_delete_last() instead.  However,
> + * if that causes you to replace lappend() with lcons(), you haven't
> + * improved matters.

LGTM

  41. Re: inefficient loop in StandbyReleaseLockList()

    Tom Lane <tgl@sss.pgh.pa.us> — 2021-11-06T23:13:31Z

    Andres Freund <andres@anarazel.de> writes:
> On 2021-11-06 18:32:54 -0400, Tom Lane wrote:
>> Good point.  The note at list_delete_last that it's O(1) isn't really
>> on point --- instead, the text for list_delete_first should be like
>> 
>> + * Note that this takes time proportional to the length of the list,
>> + * since the remaining entries must be moved.  Consider reversing the
>> + * list order so that you can use list_delete_last() instead.  However,
>> + * if that causes you to replace lappend() with lcons(), you haven't
>> + * improved matters.

> LGTM

Done that way, then.

			regards, tom lane