Re: inefficient loop in StandbyReleaseLockList()

At Mon, 01 Nov 2021 11:58:35 -0400, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote in
> Kyotaro Horiguchi <horikyota(dot)ntt(at)gmail(dot)com> writes:
> > At Sun, 31 Oct 2021 16:55:01 -0400, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)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