Re: inefficient loop in StandbyReleaseLockList()

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.

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