Horton

Re: A qsort template

Thomas Munro <thomas.munro@gmail.com>

View thread View on postgr.es
From: Thomas Munro <thomas.munro@gmail.com>
To: John Naylor <john.naylor@enterprisedb.com>
Cc: pgsql-hackers <pgsql-hackers@postgresql.org>
Date: 2021-07-04T04:27:21Z
Lists: pgsql-hackers

Attachments

On Fri, Jul 2, 2021 at 2:32 PM John Naylor <john.naylor@enterprisedb.com> wrote:
> I suspect if we experiment on two extremes of type "heaviness" (accessing and comparing trivial or not), such as uint32 and tuplesort, we'll have a pretty good idea what the parameters should be, if anything different. I'll do some testing along those lines.

Cool.

Since you are experimenting with tuplesort and likely thinking similar
thoughts, here's a patch I've been using to explore that area.  I've
seen it get, for example, ~1.18x speedup for simple index builds in
favourable winds (YMMV, early hacking results only).  Currently, it
kicks in when the leading column is of type int4, int8, timestamp,
timestamptz, date or text + friends (when abbreviatable, currently
that means "C" and ICU collations only), while increasing the
executable by only 8.5kB (Clang, amd64, -O2, no debug).

These types are handled with just three specialisations.  Their custom
"fast" comparators all boiled down to comparisons of datum bits,
varying only in signedness and width, so I tried throwing them away
and using 3 new common routines.  Then I extended
tuplesort_sort_memtuples()'s pre-existing specialisation dispatch to
recognise qualifying users of those and select 3 corresponding sort
specialisations.

It might turn out to be worth burning some more executable size on
extra variants (for example, see XXX notes in the code comments for
opportunities; one could also go nuts trying smaller things like
special cases for not-null, nulls first, reverse sort, ... to kill all
those branches), or not.

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.