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: Andres Freund <andres@anarazel.de>
Cc: Daniel Gustafsson <daniel@yesql.se>, pgsql-hackers <pgsql-hackers@postgresql.org>
Date: 2021-03-14T02:35:23Z
Lists: pgsql-hackers

Attachments

On Sat, Mar 13, 2021 at 3:49 PM Thomas Munro <thomas.munro@gmail.com> wrote:
> On Fri, Mar 12, 2021 at 7:58 AM Andres Freund <andres@anarazel.de> wrote:
> > I wish we had the same for bsearch... :)
>
> Glibc already has the definition of the traditional void-based
> function in /usr/include/bits/stdlib-bsearch.h, so the generated code
> when the compiler can see the comparator definition is already good in
> eg lazy_tid_reaped() and eg some nbtree search routines.  We could
> probably expose more trivial comparators in headers to get more of
> that, and we could perhaps put our own bsearch definition in a header
> for other platforms that didn't think of that...
>
> It might be worth doing type-safe macro templates as well, though (as
> I already did in an earlier proposal[1]), just to have nice type safe
> code though, not sure, I'm thinking about that...

I remembered a very good reason to do this: the ability to do
branch-free comparators in more places by introducing optional wider
results.  That's good for TIDs (needs 49 bits), and places that want
to "reverse" a traditional comparator (just doing -result on an int
comparator that might theoretically return INT_MIN requires at least
33 bits).  So I rebased the relevant parts of my earlier version, and
went through and wrote a bunch of examples to demonstrate all this
stuff actually working.

There are two categories of change in these patches:

0002-0005: Places that sort/unique/search OIDs, BlockNumbers and TIDs,
which can reuse a small set of typed functions (a few more could be
added, if useful).  See sortitemptr.h and sortscalar.h.  Mostly this
is just a notational improvement, and an excuse to drop a bunch of
duplicated code.  In a few places this might really speed something
important up!  Like VACUUM's lazy_tid_reaped().

0006-0009.  Places where a specialised function is generated for one
special purpose, such as ANALYZE's HeapTuple sort, tidbitmap.c's
pagetable sort,  some places in nbtree code etc.  These may require
some case-by-case research on whether the extra executable size is
worth the speedup, and there are surely more opportunities like that;
I just picked on these arbitrarily.

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.