Re: ArrayLists instead of List (for some things)

On 3 November 2017 at 03:38, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> David Rowley <david(dot)rowley(at)2ndquadrant(dot)com> writes:
>> On 3 November 2017 at 03:17, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>>> We've jacked up the List API and driven a new implementation underneath
>>> once before. Maybe it's time to do that again.
>
>> Maybe, but the new implementation is not going to do well with places
>> where we perform lcons(). Probably many of those places could be
>> changed to lappend(), but I bet there's plenty that need prepend.
>
> [ shrug... ] To me, that means this implementation isn't necessarily
> the right solution.

True, of course, could be worked around probably with some bit flags
to record if lcons was called, and then consume the elements in
reverse. We might have to shuffle things along a bit for Lists that
get lcons and lappend calls.

The API break that I can't see a way around is:

/* does the list have 0 elements? */
if (list == NIL) ...

That would need to be rewritten as:

if (list_length(list) == 0) ...

> It seems to me that a whole lot of the complaints about this could be
> resolved simply by improving the List infrastructure to allocate ListCells
> in batches. That would address the question of "too much palloc traffic"
> and greatly improve the it-accesses-all-over-memory situation too.
>
> Possibly there are more aggressive changes that could be implemented
> without breaking too many places, but I think it would be useful to
> start there and see what it buys us.

Yeah, certainly would be a good way of determining the worth of changing.

--
David Rowley http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services