Re: A qsort template

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
uint32and tuplesort, we'll have a pretty good idea what the parameters should be, if anything different. I'll do some
testingalong 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.