Alexander Korotkov <aekorotkov@gmail.com> writes:
> On Mon, Oct 21, 2024 at 8:40 AM Andrei Lepikhov <lepihov@gmail.com> wrote:
>>
>> On 21/10/2024 06:32, Dagfinn Ilmari Mannsåker wrote:
>> > Alexander Korotkov <aekorotkov@gmail.com> writes:
>> >
>> >> +static Oid *in_progress_list;
>> >> +static int in_progress_list_len;
>> >> +static int in_progress_list_maxlen;
>> >
>> > Is there any particular reason not to use pg_list.h for this?
>> Sure. The type cache lookup has to be as much optimal as possible.
>> Using an array and relating sequential access to it, we avoid memory
>> allocations and deallocations 99.9% of the time. Also, quick access to
>> the single element (which we will have in real life almost all of the
>> time) is much faster than employing list machinery.
Lists are actually dynamically resized arrays these days (see commit
1cff1b95ab6ddae32faa3efe0d95a820dbfdc164), not linked lists, so
accessing arbitrary elements is O(1), not O(n). Just like this patch,
the size is doubled (starting at 16) whenever array is full.
> +1,
> List with zero elements has to be NIL. That means continuous
> allocations/deallocations.
This however is a valid point (unless we keep a dummy zeroth element to
avoid it, which is even uglier than open-coding the array extension
logic), so objection withdrawn.
- ilmari