Horton

Re: A qsort template

Daniel Gustafsson <daniel@yesql.se>

View thread View on postgr.es
From: Daniel Gustafsson <daniel@yesql.se>
To: Thomas Munro <thomas.munro@gmail.com>
Cc: pgsql-hackers <pgsql-hackers@postgresql.org>
Date: 2021-03-02T21:25:39Z
Lists: pgsql-hackers

Attachments

> On 18 Feb 2021, at 04:09, Thomas Munro <thomas.munro@gmail.com> wrote:

> In another thread[1], I proposed $SUBJECT, but then we found a better
> solution to that thread's specific problem.  The general idea is still
> good though: it's possible to (1) replace several existing copies of
> our qsort algorithm with one, and (2) make new specialised versions a
> bit more easily than the existing Perl generator allows.  So, I'm back
> with a rebased stack of patches.  I'll leave specific cases for new
> worthwhile specialisations for separate proposals; I've heard about
> several.

Just to play around with this while reviewing I made a qsort_strcmp, like in
the attached, and tested it using a ~9M word [0] randomly shuffled wordlist.
While being too small input to make any meaningful difference in runtime (it
shaved a hair off but it might well be within the error margin) there was no
regression either.  More importantly, it was really simple and quick to make a
tailored qsort which is the intention with the patch.  While still being a bit
of magic, moving from the Perl generator makes this slightly less magic IMO so
+1 on this approach.

A tiny nitpick on the patch itself:

+ *       - ST_COMPARE(a, b) - a simple comparison expression
+ *   - ST_COMPARE(a, b, arg) - variant that takes an extra argument
Indentation.

All tests pass and the documentation in the the sort_template.h is enough to go
on, but I would prefer to see a comment in port/qsort.c referring back to
sort_template.h for documentation.

--
Daniel Gustafsson		https://vmware.com/

[0] https://github.com/dwyl/english-words/ shuffled 20 times over

Commits

  1. Remove debug messages from tuplesort_sort_memtuples()

  2. Fix performance regression in tuplesort specializations

  3. Fix tuplesort optimization for CLUSTER-on-expression.

  4. Initial pgindent and pgperltidy run for v14.

  5. Specialize checkpointer sort functions.

  6. Use sort_template.h for qsort() and qsort_arg().

  7. Use sort_template.h for qsort_tuple() and qsort_ssup().

  8. Add sort_template.h for making sort functions.

  9. Use abbreviated keys for faster sorting of text datums.