Horton

Re: POC: converting Lists into arrays

Tom Lane <tgl@sss.pgh.pa.us>

View thread View on postgr.es
From: Tom Lane <tgl@sss.pgh.pa.us>
To: David Rowley <david.rowley@2ndquadrant.com>
Cc: Andres Freund <andres@anarazel.de>, Robert Haas <robertmhaas@gmail.com>, PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Date: 2019-05-25T00:53:47Z
Lists: pgsql-hackers

Attachments

Here's a new version of the Lists-as-arrays patch.  It's rebased up to
HEAD, and I also realized that I could fix the problem with multiple
evaluation of the List arguments of foreach etc. by using structure
assignment.  So that gets rid of a large chunk of the semantic gotchas
that were in the previous patch.  You still have to be careful about
code that deletes list entries within a foreach() over the list ---
but nearly all such code is using list_delete_cell, which means
you'll have to touch it anyway because of the API change for that
function.

Previously, the typical logic for deletion-within-a-loop involved
either advancing or not advancing a "prev" pointer that was used
with list_delete_cell.  The way I've recoded that here changes those
loops to use an integer list index that gets incremented or not.

Now, it turns out that the new formulation of foreach() is really
strictly equivalent to

	for (int pos = 0; pos < list_length(list); pos++)
	{
		whatever-type item = list_nth(list, pos);
		...
	}

which means that it could cope fine with deletion of the current
list element if we were to provide some supported way of not
incrementing the list index counter.  That is, instead of
code that looks more or less like this:

	for (int pos = 0; pos < list_length(list); pos++)
	{
		whatever-type item = list_nth(list, pos);
		...
		if (delete_cur)
		{
			list = list_delete_nth_cell(list, pos);
			pos--;   /* keep loop in sync with deletion */
		}
	}

we could write, say:

	foreach(lc, list)
	{
		whatever-type item = lfirst(lc);
		...
		if (delete_cur)
		{
			list = list_delete_cell(list, lc);
			foreach_backup(lc); /* keep loop in sync with deletion */
		}
	}

which is the same thing under the hood.  I'm not quite sure if that way
is better or not.  It's more magical than explicitly manipulating a list
index, but it's also shorter and therefore less subject to typos.

			regards, tom lane

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.