Re: ArrayLists instead of List (for some things)

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.

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.

regards, tom lane