Horton

Re: POC: converting Lists into arrays

Andres Freund <andres@anarazel.de>

View thread View on postgr.es
From: Andres Freund <andres@anarazel.de>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: pgsql-hackers@lists.postgresql.org
Date: 2019-02-26T01:55:46Z
Lists: pgsql-hackers 
Hi,

On 2019-02-25 18:41:17 -0500, Tom Lane wrote:
> I wrote:
> > Andres Freund <andres@anarazel.de> writes:
> >>> 1. This still involves at least two palloc's for every nonempty List,
> >>> because I kept the header and the data array separate.  Perhaps it's
> >>> worth allocating those in one palloc.
> 
> >> Hm, I think if we force external code to audit their code, we better
> >> also do this. This is a significant number of allocations, and I don't
> >> think it'd be good to spread this out over two releases.
> 
> > If we choose to do it, I'd agree with doing both in the same major release
> > cycle, so that extensions see just one breakage.  But I think it'd still
> > best be developed as a follow-on patch.
> 
> By the by ... this idea actively breaks the mechanism I'd proposed for
> preserving foreach's behavior of evaluating the List reference only once.
> If we save a hidden copy of whatever the user says the List reference
> is, and then he assigns a new value to it mid-loop, we're screwed if
> the list header can move.

Hm, I wonder if that's necessary / whether we can just work around user
visible breakage at a small cost. I think I'm mostly concerned with two
allocations for the very common case of small (1-3 entries) lists. We
could just allocate the first array together with the header, and not
free that if the list grows beyond that point. That'd mean we'd only do
separate allocations once they actually amortize over a number of
allocations.

Greetings,

Andres Freund

Commits

  1. Remove EState.es_range_table_array.

  2. Rationalize use of list_concat + list_copy combinations.

  3. Cosmetic improvements in setup of planner's per-RTE arrays.

  4. Make better use of the new List implementation in a couple of places

  5. Fix sepgsql test results for commit d97b714a2.

  6. Avoid using lcons and list_delete_first where it's easy to do so.

  7. Remove lappend_cell...() family of List functions.

  8. Clean up some ad-hoc code for sorting and de-duplicating Lists.

  9. Redesign the API for list sorting (list_qsort becomes list_sort).

  10. Remove dead code.

  11. Represent Lists as expansible arrays, not chains of cons-cells.

  12. Standardize some more loops that chase down parallel lists.

  13. Reimplement the linked list data structure used throughout the backend.