Horton

Re: POC: converting Lists into arrays

David Steele <david@pgmasters.net>

View thread View on postgr.es
From: David Steele <david@pgmasters.net>
To: Tom Lane <tgl@sss.pgh.pa.us>, David Rowley <david.rowley@2ndquadrant.com>
Cc: Jesper Pedersen <jesper.pedersen@redhat.com>, Andres Freund <andres@anarazel.de>, Robert Haas <robertmhaas@gmail.com>, PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Date: 2019-07-16T03:33:48Z
Lists: pgsql-hackers 
On 7/15/19 11:07 PM, Tom Lane wrote:
> David Rowley <david.rowley@2ndquadrant.com> writes:
>> The only thoughts I have so far here are that it's a shame that the
>> function got called list_qsort() and not just list_sort().  I don't
>> see why callers need to know anything about the sort algorithm that's
>> being used.
> 
> Meh.  list_qsort() is quicksort only to the extent that qsort()
> is quicksort, which in our current implementation is a bit of a
> lie already --- and, I believe, it's much more of a lie in some
> versions of libc.  I don't really think of either name as promising
> anything about the underlying sort algorithm.  What they do share
> is an API based on a callback comparison function, and if you are
> looking for uses of those, it's a lot easier to grep for "qsort"
> than some more-generic term.

I agree with David -- list_sort() is better.  I don't think "sort" is 
such a common stem that searching is a big issue, especially with modern 
code indexing tools.

-- 
-David
david@pgmasters.net

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.