Re: ArrayLists instead of List (for some things)

David Rowley <david(dot)rowley(at)2ndquadrant(dot)com> writes:
>> 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.

BTW, with just a little more work that could be made to address the
list-nth-is-expensive problem too. I'm imagining a call that preallocates
an empty list with room for N ListCells (or perhaps, if we need to
preserve compatibility with NIL == NULL, creates a single-element list
with room for N-1 more cells), plus some tracking in list.c of whether
the list cells have been consumed in order. Given the typical use-case of
building lists strictly with lappend, list_nth() could index directly into
the ListCell slab as long as it saw the List header's "is_linear" flag was
true.

regards, tom lane