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-25T16:46:19Z
Lists: pgsql-hackers 
David Rowley <david.rowley@2ndquadrant.com> writes:
> If we're doing an API break for this, wouldn't it be better to come up
> with something that didn't have to shuffle list elements around every
> time one is deleted?

Agreed that as long as there's an API break anyway, we could consider
more extensive changes for this use-case.  But ...

> For example, we could have a foreach_delete() that instead of taking a
> pointer to a ListCell, it took a ListDeleteIterator which contained a
> ListCell pointer and a Bitmapset, then just have a macro that marks a
> list item as deleted (list_delete_current(di)) and have a final
> cleanup at the end of the loop.

... I'm not quite sold on this particular idea.  The amount of added
bitmapset manipulation overhead seems rather substantial in comparison
to the memmove work saved.  It might win for cases involving very
long lists with many entries being deleted in one operation, but
I don't think that's a common scenario for us.  It's definitely a
loss when there's just one item to be deleted, which I think is a
common case.  (Of course, callers expecting that could just not
use this multi-delete API.)

> Or maybe we should worry about having the list in an inconsistent
> state during the loop?  e.g if the list is getting passed into a
> function call to do something.

Not following that?  If I understand your idea correctly, the list
doesn't actually get changed until the cleanup step.  If we pass it to
another operation that independently deletes some members meanwhile,
that's trouble; but it'd be trouble for the existing code, and for my
version of the patch too.

FWIW, I don't really see a need to integrate this idea into the
loop logic as such.  You could just define it as "make a bitmap
of the list indexes to delete, then call
"list = list_delete_multi(list, bitmapset)".  It would be
helpful perhaps if we provided official access to the current
list index that the foreach macro is maintaining internally.

			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.