Subject: A qsort template

From: Thomas Munro <[email-masked]>
Date: Thu, 18 Feb 2021 16:09:49 +1300

Hello,

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.

[1] https://www.postgresql.org/message-id/flat/CA%2BhUKGKMQFVpjr106gRhwk6R-nXv0qOcTreZuQzxgpHESAL6dw%40mail.gmail.com
From edfa27a45eca139d683bd0a02136e1da5a489243 Mon Sep 17 00:00:00 2001
From: Thomas Munro <[email-masked]>
Date: Mon, 17 Aug 2020 21:31:56 +1200
Subject: [PATCH 1/3] Add sort_template.h for making fast sort functions.

Move our qsort implementation into a header that can be used to
define specialized functions for better performance.
---
 src/include/lib/sort_template.h | 431 ++++++++++++++++++++++++++++++++
 1 file changed, 431 insertions(+)
 create mode 100644 src/include/lib/sort_template.h

diff --git a/src/include/lib/sort_template.h b/src/include/lib/sort_template.h
new file mode 100644
index 0000000000..09523a8e4c
--- /dev/null
+++ b/src/include/lib/sort_template.h
@@ -0,0 +1,431 @@
+/*-------------------------------------------------------------------------
+ *
+ * sort_template.h
+ *
+ *	  A template for a sort algorithm that supports varying degrees of
+ *	  specialization.
+ *
+ * Copyright (c) 2021, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1992-1994, Regents of the University of California
+ *
+ * Usage notes:
+ *
+ *	  To generate functions specialized for a type, the following parameter
+ *	  macros should be #define'd before this file is included.
+ *
+ *	  - ST_SORT - the name of a sort function to be generated
+ *	  - ST_ELEMENT_TYPE - type of the referenced elements
+ *	  - ST_DECLARE - if defined the functions and types are declared
+ *	  - ST_DEFINE - if defined the functions and types are defined
+ *	  - ST_SCOPE - scope (e.g. extern, static inline) for functions
+ *
+ *	  Instead of ST_ELEMENT_TYPE, ST_ELEMENT_TYPE_VOID can be defined.  Then
+ *	  the generated functions will automatically gain an "element_size"
+ *	  parameter.  This allows us to generate a traditional qsort function.
+ *
+ *	  One of the following macros must be defined, to show how to compare
+ *	  elements.  The first two options are arbitrary expressions depending
+ *	  on whether an extra pass-through argument is desired, and the third
+ *	  option should be defined if the sort function should receive a
+ *	  function pointer at runtime.
+ *
+ * 	  - ST_COMPARE(a, b) - a simple comparison expression
+ *	  - ST_COMPARE(a, b, arg) - variant that takes an extra argument
+ *	  - ST_COMPARE_RUNTIME_POINTER - sort function takes a function pointer
+ *
+ *	  To say that the comparator and therefore also sort function should
+ *	  receive an extra pass-through argument, specify the type of the
+ *	  argument.
+ *
+ *	  - ST_COMPARE_ARG_TYPE - type of extra argument
+ *
+ *	  The prototype of the generated sort function is:
+ *
+ *	  void ST_SORT(ST_ELEMENT_TYPE *data, size_t n,
+ *				   [size_t element_size,]
+ *				   [ST_SORT_compare_function compare,]
+ *				   [ST_COMPARE_ARG_TYPE *arg]);
+ *
+ *	  ST_SORT_compare_function is a function pointer of the following type:
+ *
+ *	  int (*)(const ST_ELEMENT_TYPE *a, const ST_ELEMENT_TYPE *b,
+ *			  [ST_COMPARE_ARG_TYPE *arg])
+ *
+ * HISTORY
+ *
+ *	  Modifications from vanilla NetBSD source:
+ *	  - Add do ... while() macro fix
+ *	  - Remove __inline, _DIAGASSERTs, __P
+ *	  - Remove ill-considered "swap_cnt" switch to insertion sort, in favor
+ *		of a simple check for presorted input.
+ *	  - Take care to recurse on the smaller partition, to bound stack usage
+ *	  - Convert into a header that can generate specialized functions
+ *
+ * IDENTIFICATION
+ *		src/include/lib/sort_template.h
+ *
+ *-------------------------------------------------------------------------
+ */
+
+/*	  $NetBSD: qsort.c,v 1.13 2003/08/07 16:43:42 agc Exp $   */
+
+/*-
+ * Copyright (c) 1992, 1993
+ *	  The Regents of the University of California.  All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *	  notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *	  notice, this list of conditions and the following disclaimer in the
+ *	  documentation and/or other materials provided with the distribution.
+ * 3. Neither the name of the University nor the names of its contributors
+ *	  may be used to endorse or promote products derived from this software
+ *	  without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+/*
+ * Qsort routine based on J. L. Bentley and M. D. McIlroy,
+ * "Engineering a sort function",
+ * Software--Practice and Experience 23 (1993) 1249-1265.
+ *
+ * We have modified their original by adding a check for already-sorted
+ * input, which seems to be a win per discussions on pgsql-hackers around
+ * 2006-03-21.
+ *
+ * Also, we recurse on the smaller partition and iterate on the larger one,
+ * which ensures we cannot recurse more than log(N) levels (since the
+ * partition recursed to is surely no more than half of the input).  Bentley
+ * and McIlroy explicitly rejected doing this on the grounds that it's "not
+ * worth the effort", but we have seen crashes in the field due to stack
+ * overrun, so that judgment seems wrong.
+ */
+
+#define ST_MAKE_PREFIX(a) CppConcat(a,_)
+#define ST_MAKE_NAME(a,b) ST_MAKE_NAME_(ST_MAKE_PREFIX(a),b)
+#define ST_MAKE_NAME_(a,b) CppConcat(a,b)
+
+/*
+ * If the element type is void, we'll also need an element_size argument
+ * because we don't know the size.
+ */
+#ifdef ST_ELEMENT_TYPE_VOID
+#define ST_ELEMENT_TYPE void
+#define ST_SORT_PROTO_ELEMENT_SIZE , size_t element_size
+#define ST_SORT_INVOKE_ELEMENT_SIZE , element_size
+#else
+#define ST_SORT_PROTO_ELEMENT_SIZE
+#define ST_SORT_INVOKE_ELEMENT_SIZE
+#endif
+
+/*
+ * If the user wants to be able to pass in compare functions at runtime,
+ * we'll need to make that an argument of the sort and med3 functions.
+ */
+#ifdef ST_COMPARE_RUNTIME_POINTER
+/*
+ * The type of the comparator function pointer that ST_SORT will take, unless
+ * you've already declared a type name manually and want to use that instead of
+ * having a new one defined.
+ */
+#ifndef ST_COMPARATOR_TYPE_NAME
+#define ST_COMPARATOR_TYPE_NAME ST_MAKE_NAME(ST_SORT, compare_function)
+#endif
+#define ST_COMPARE compare
+#ifndef ST_COMPARE_ARG_TYPE
+#define ST_SORT_PROTO_COMPARE , ST_COMPARATOR_TYPE_NAME compare
+#define ST_SORT_INVOKE_COMPARE , compare
+#else
+#define ST_SORT_PROTO_COMPARE , ST_COMPARATOR_TYPE_NAME compare
+#define ST_SORT_INVOKE_COMPARE , compare
+#endif
+#else
+#define ST_SORT_PROTO_COMPARE
+#define ST_SORT_INVOKE_COMPARE
+#endif
+
+/*
+ * If the user wants to use a compare function or expression that takes an
+ * extra argument, we'll need to make that an argument of the sort, compare and
+ * med3 functions.
+ */
+#ifdef ST_COMPARE_ARG_TYPE
+#define ST_SORT_PROTO_ARG , ST_COMPARE_ARG_TYPE *arg
+#define ST_SORT_INVOKE_ARG , arg
+#else
+#define ST_SORT_PROTO_ARG
+#define ST_SORT_INVOKE_ARG
+#endif
+
+#ifdef ST_DECLARE
+
+#ifdef ST_COMPARE_RUNTIME_POINTER
+typedef int (*ST_COMPARATOR_TYPE_NAME)(const ST_ELEMENT_TYPE *,
+									   const ST_ELEMENT_TYPE *
+									   ST_SORT_PROTO_ARG);
+#endif
+
+/* Declare the sort function.  Note optional arguments at end. */
+ST_SCOPE void ST_SORT(ST_ELEMENT_TYPE *first, size_t n
+					  ST_SORT_PROTO_ELEMENT_SIZE
+					  ST_SORT_PROTO_COMPARE
+					  ST_SORT_PROTO_ARG);
+
+#endif
+
+#ifdef ST_DEFINE
+
+/* sort private helper functions */
+#define ST_MED3 ST_MAKE_NAME(ST_SORT, med3)
+#define ST_SWAP ST_MAKE_NAME(ST_SORT, swap)
+#define ST_SWAPN ST_MAKE_NAME(ST_SORT, swapn)
+
+/* Users expecting to run very large sorts may need them to be interruptible. */
+#ifdef ST_CHECK_FOR_INTERRUPTS
+#define DO_CHECK_FOR_INTERRUPTS() CHECK_FOR_INTERRUPTS()
+#else
+#define DO_CHECK_FOR_INTERRUPTS()
+#endif
+
+/*
+ * Create wrapper macros that know how to invoke compare, med3 and sort with
+ * the right arguments.
+ */
+#ifdef ST_COMPARE_RUNTIME_POINTER
+#define DO_COMPARE(a_, b_) ST_COMPARE((a_), (b_) ST_SORT_INVOKE_ARG)
+#elif defined(ST_COMPARE_ARG_TYPE)
+#define DO_COMPARE(a_, b_) ST_COMPARE((a_), (b_), arg)
+#else
+#define DO_COMPARE(a_, b_) ST_COMPARE((a_), (b_))
+#endif
+#define DO_MED3(a_, b_, c_)												\
+	ST_MED3((a_), (b_), (c_)											\
+			ST_SORT_INVOKE_COMPARE										\
+			ST_SORT_INVOKE_ARG)
+#define DO_SORT(a_, n_)													\
+	ST_SORT((a_), (n_)													\
+			ST_SORT_INVOKE_ELEMENT_SIZE									\
+			ST_SORT_INVOKE_COMPARE										\
+			ST_SORT_INVOKE_ARG)
+
+/*
+ * If we're working with void pointers, we'll use pointer arithmetic based on
+ * uint8, and use the runtime element_size to step through the array and swap
+ * elements.  Otherwise we'll work with ST_ELEMENT_TYPE.
+ */
+#ifndef ST_ELEMENT_TYPE_VOID
+#define ST_POINTER_TYPE ST_ELEMENT_TYPE
+#define ST_POINTER_STEP 1
+#define DO_SWAPN(a_, b_, n_) ST_SWAPN((a_), (b_), (n_))
+#define DO_SWAP(a_, b_) ST_SWAP((a_), (b_))
+#else
+#define ST_POINTER_TYPE uint8
+#define ST_POINTER_STEP element_size
+#define DO_SWAPN(a_, b_, n_) ST_SWAPN((a_), (b_), (n_))
+#define DO_SWAP(a_, b_) DO_SWAPN((a_), (b_), element_size)
+#endif
+
+/*
+ * Find the median of three values.  Currently, performance seems to be best
+ * if the the comparator is inlined here, but the med3 function is not inlined
+ * in the qsort function.
+ */
+static pg_noinline ST_ELEMENT_TYPE *
+ST_MED3(ST_ELEMENT_TYPE *a,
+		ST_ELEMENT_TYPE *b,
+		ST_ELEMENT_TYPE *c
+		ST_SORT_PROTO_COMPARE
+		ST_SORT_PROTO_ARG)
+{
+		return DO_COMPARE(a, b) < 0 ?
+		(DO_COMPARE(b, c) < 0 ? b : (DO_COMPARE(a, c) < 0 ? c : a))
+		: (DO_COMPARE(b, c) > 0 ? b : (DO_COMPARE(a, c) < 0 ? a : c));
+}
+
+static inline void
+ST_SWAP(ST_POINTER_TYPE *a, ST_POINTER_TYPE *b)
+{
+	ST_POINTER_TYPE tmp = *a;
+
+	*a = *b;
+	*b = tmp;
+}
+
+static inline void
+ST_SWAPN(ST_POINTER_TYPE *a, ST_POINTER_TYPE *b, size_t n)
+{
+	for (size_t i = 0; i < n; ++i)
+		ST_SWAP(&a[i], &b[i]);
+}
+
+/*
+ * Sort an array.
+ */
+ST_SCOPE void
+ST_SORT(ST_ELEMENT_TYPE *data, size_t n
+		ST_SORT_PROTO_ELEMENT_SIZE
+		ST_SORT_PROTO_COMPARE
+		ST_SORT_PROTO_ARG)
+{
+	ST_POINTER_TYPE *a = (ST_POINTER_TYPE *) data,
+			   *pa,
+			   *pb,
+			   *pc,
+			   *pd,
+			   *pl,
+			   *pm,
+			   *pn;
+	size_t		d1,
+				d2;
+	int			r,
+				presorted;
+
+loop:
+	DO_CHECK_FOR_INTERRUPTS();
+	if (n < 7)
+	{
+		for (pm = a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP;
+			 pm += ST_POINTER_STEP)
+			for (pl = pm; pl > a && DO_COMPARE(pl - ST_POINTER_STEP, pl) > 0;
+				 pl -= ST_POINTER_STEP)
+				DO_SWAP(pl, pl - ST_POINTER_STEP);
+		return;
+	}
+	presorted = 1;
+	for (pm = a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP;
+		 pm += ST_POINTER_STEP)
+	{
+		DO_CHECK_FOR_INTERRUPTS();
+		if (DO_COMPARE(pm - ST_POINTER_STEP, pm) > 0)
+		{
+			presorted = 0;
+			break;
+		}
+	}
+	if (presorted)
+		return;
+	pm = a + (n / 2) * ST_POINTER_STEP;
+	if (n > 7)
+	{
+		pl = a;
+		pn = a + (n - 1) * ST_POINTER_STEP;
+		if (n > 40)
+		{
+			size_t		d = (n / 8) * ST_POINTER_STEP;
+
+			pl = DO_MED3(pl, pl + d, pl + 2 * d);
+			pm = DO_MED3(pm - d, pm, pm + d);
+			pn = DO_MED3(pn - 2 * d, pn - d, pn);
+		}
+		pm = DO_MED3(pl, pm, pn);
+	}
+	DO_SWAP(a, pm);
+	pa = pb = a + ST_POINTER_STEP;
+	pc = pd = a + (n - 1) * ST_POINTER_STEP;
+	for (;;)
+	{
+		while (pb <= pc && (r = DO_COMPARE(pb, a)) <= 0)
+		{
+			if (r == 0)
+			{
+				DO_SWAP(pa, pb);
+				pa += ST_POINTER_STEP;
+			}
+			pb += ST_POINTER_STEP;
+			DO_CHECK_FOR_INTERRUPTS();
+		}
+		while (pb <= pc && (r = DO_COMPARE(pc, a)) >= 0)
+		{
+			if (r == 0)
+			{
+				DO_SWAP(pc, pd);
+				pd -= ST_POINTER_STEP;
+			}
+			pc -= ST_POINTER_STEP;
+			DO_CHECK_FOR_INTERRUPTS();
+		}
+		if (pb > pc)
+			break;
+		DO_SWAP(pb, pc);
+		pb += ST_POINTER_STEP;
+		pc -= ST_POINTER_STEP;
+	}
+	pn = a + n * ST_POINTER_STEP;
+	d1 = Min(pa - a, pb - pa);
+	DO_SWAPN(a, pb - d1, d1);
+	d1 = Min(pd - pc, pn - pd - ST_POINTER_STEP);
+	DO_SWAPN(pb, pn - d1, d1);
+	d1 = pb - pa;
+	d2 = pd - pc;
+	if (d1 <= d2)
+	{
+		/* Recurse on left partition, then iterate on right partition */
+		if (d1 > ST_POINTER_STEP)
+			DO_SORT(a, d1 / ST_POINTER_STEP);
+		if (d2 > ST_POINTER_STEP)
+		{
+			/* Iterate rather than recurse to save stack space */
+			/* DO_SORT(pn - d2, d2 / ST_POINTER_STEP) */
+			a = pn - d2;
+			n = d2 / ST_POINTER_STEP;
+			goto loop;
+		}
+	}
+	else
+	{
+		/* Recurse on right partition, then iterate on left partition */
+		if (d2 > ST_POINTER_STEP)
+			DO_SORT(pn - d2, d2 / ST_POINTER_STEP);
+		if (d1 > ST_POINTER_STEP)
+		{
+			/* Iterate rather than recurse to save stack space */
+			/* DO_SORT(a, d1 / ST_POINTER_STEP) */
+			n = d1 / ST_POINTER_STEP;
+			goto loop;
+		}
+	}
+}
+#endif
+
+#undef DO_CHECK_FOR_INTERRUPTS
+#undef DO_COMPARE
+#undef DO_MED3
+#undef DO_SORT
+#undef DO_SWAP
+#undef DO_SWAPN
+#undef ST_COMPARATOR_TYPE_NAME
+#undef ST_COMPARE
+#undef ST_COMPARE_ARG_TYPE
+#undef ST_COMPARE_RUNTIME_POINTER
+#undef ST_ELEMENT_TYPE
+#undef ST_ELEMENT_TYPE_VOID
+#undef ST_MAKE_NAME
+#undef ST_MAKE_NAME_
+#undef ST_MAKE_PREFIX
+#undef ST_MED3
+#undef ST_POINTER_STEP
+#undef ST_POINTER_TYPE
+#undef ST_SCOPE
+#undef ST_SORT
+#undef ST_SORT_INVOKE_ARG
+#undef ST_SORT_INVOKE_COMPARE
+#undef ST_SORT_INVOKE_ELEMENT_SIZE
+#undef ST_SORT_PROTO_ARG
+#undef ST_SORT_PROTO_COMPARE
+#undef ST_SORT_PROTO_ELEMENT_SIZE
+#undef ST_SWAP
+#undef ST_SWAPN
-- 
2.30.0

From c73967d0ca14e06432949c96e047297c9e9f37c9 Mon Sep 17 00:00:00 2001
From: Thomas Munro <[email-masked]>
Date: Wed, 19 Aug 2020 19:34:45 +1200
Subject: [PATCH 2/3] Use sort_template.h for qsort() and qsort_arg().

Reduce duplication by using the new template.
---
 src/port/qsort.c     | 227 ++----------------------------------------
 src/port/qsort_arg.c | 228 ++-----------------------------------------
 2 files changed, 15 insertions(+), 440 deletions(-)

diff --git a/src/port/qsort.c b/src/port/qsort.c
index fa992e2081..7879e6cd56 100644
--- a/src/port/qsort.c
+++ b/src/port/qsort.c
@@ -1,229 +1,16 @@
 /*
  *	qsort.c: standard quicksort algorithm
- *
- *	Modifications from vanilla NetBSD source:
- *	  Add do ... while() macro fix
- *	  Remove __inline, _DIAGASSERTs, __P
- *	  Remove ill-considered "swap_cnt" switch to insertion sort,
- *	  in favor of a simple check for presorted input.
- *	  Take care to recurse on the smaller partition, to bound stack usage.
- *
- *	CAUTION: if you change this file, see also qsort_arg.c, gen_qsort_tuple.pl
- *
- *	src/port/qsort.c
- */
-
-/*	$NetBSD: qsort.c,v 1.13 2003/08/07 16:43:42 agc Exp $	*/
-
-/*-
- * Copyright (c) 1992, 1993
- *	The Regents of the University of California.  All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *	  notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *	  notice, this list of conditions and the following disclaimer in the
- *	  documentation and/or other materials provided with the distribution.
- * 3. Neither the name of the University nor the names of its contributors
- *	  may be used to endorse or promote products derived from this software
- *	  without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
  */
 
 #include "c.h"
 
-
-static char *med3(char *a, char *b, char *c,
-				  int (*cmp) (const void *, const void *));
-static void swapfunc(char *, char *, size_t, int);
-
-/*
- * Qsort routine based on J. L. Bentley and M. D. McIlroy,
- * "Engineering a sort function",
- * Software--Practice and Experience 23 (1993) 1249-1265.
- *
- * We have modified their original by adding a check for already-sorted input,
- * which seems to be a win per discussions on pgsql-hackers around 2006-03-21.
- *
- * Also, we recurse on the smaller partition and iterate on the larger one,
- * which ensures we cannot recurse more than log(N) levels (since the
- * partition recursed to is surely no more than half of the input).  Bentley
- * and McIlroy explicitly rejected doing this on the grounds that it's "not
- * worth the effort", but we have seen crashes in the field due to stack
- * overrun, so that judgment seems wrong.
- */
-
-#define swapcode(TYPE, parmi, parmj, n) \
-do {		\
-	size_t i = (n) / sizeof (TYPE);			\
-	TYPE *pi = (TYPE *)(void *)(parmi);			\
-	TYPE *pj = (TYPE *)(void *)(parmj);			\
-	do {						\
-		TYPE	t = *pi;			\
-		*pi++ = *pj;				\
-		*pj++ = t;				\
-		} while (--i > 0);				\
-} while (0)
-
-#define SWAPINIT(a, es) swaptype = ((char *)(a) - (char *)0) % sizeof(long) || \
-	(es) % sizeof(long) ? 2 : (es) == sizeof(long)? 0 : 1
-
-static void
-swapfunc(char *a, char *b, size_t n, int swaptype)
-{
-	if (swaptype <= 1)
-		swapcode(long, a, b, n);
-	else
-		swapcode(char, a, b, n);
-}
-
-#define swap(a, b)						\
-	if (swaptype == 0) {					\
-		long t = *(long *)(void *)(a);			\
-		*(long *)(void *)(a) = *(long *)(void *)(b);	\
-		*(long *)(void *)(b) = t;			\
-	} else							\
-		swapfunc(a, b, es, swaptype)
-
-#define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
-
-static char *
-med3(char *a, char *b, char *c, int (*cmp) (const void *, const void *))
-{
-	return cmp(a, b) < 0 ?
-		(cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a))
-		: (cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c));
-}
-
-void
-pg_qsort(void *a, size_t n, size_t es, int (*cmp) (const void *, const void *))
-{
-	char	   *pa,
-			   *pb,
-			   *pc,
-			   *pd,
-			   *pl,
-			   *pm,
-			   *pn;
-	size_t		d1,
-				d2;
-	int			r,
-				swaptype,
-				presorted;
-
-loop:SWAPINIT(a, es);
-	if (n < 7)
-	{
-		for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
-			for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
-				 pl -= es)
-				swap(pl, pl - es);
-		return;
-	}
-	presorted = 1;
-	for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
-	{
-		if (cmp(pm - es, pm) > 0)
-		{
-			presorted = 0;
-			break;
-		}
-	}
-	if (presorted)
-		return;
-	pm = (char *) a + (n / 2) * es;
-	if (n > 7)
-	{
-		pl = (char *) a;
-		pn = (char *) a + (n - 1) * es;
-		if (n > 40)
-		{
-			size_t		d = (n / 8) * es;
-
-			pl = med3(pl, pl + d, pl + 2 * d, cmp);
-			pm = med3(pm - d, pm, pm + d, cmp);
-			pn = med3(pn - 2 * d, pn - d, pn, cmp);
-		}
-		pm = med3(pl, pm, pn, cmp);
-	}
-	swap(a, pm);
-	pa = pb = (char *) a + es;
-	pc = pd = (char *) a + (n - 1) * es;
-	for (;;)
-	{
-		while (pb <= pc && (r = cmp(pb, a)) <= 0)
-		{
-			if (r == 0)
-			{
-				swap(pa, pb);
-				pa += es;
-			}
-			pb += es;
-		}
-		while (pb <= pc && (r = cmp(pc, a)) >= 0)
-		{
-			if (r == 0)
-			{
-				swap(pc, pd);
-				pd -= es;
-			}
-			pc -= es;
-		}
-		if (pb > pc)
-			break;
-		swap(pb, pc);
-		pb += es;
-		pc -= es;
-	}
-	pn = (char *) a + n * es;
-	d1 = Min(pa - (char *) a, pb - pa);
-	vecswap(a, pb - d1, d1);
-	d1 = Min(pd - pc, pn - pd - es);
-	vecswap(pb, pn - d1, d1);
-	d1 = pb - pa;
-	d2 = pd - pc;
-	if (d1 <= d2)
-	{
-		/* Recurse on left partition, then iterate on right partition */
-		if (d1 > es)
-			pg_qsort(a, d1 / es, es, cmp);
-		if (d2 > es)
-		{
-			/* Iterate rather than recurse to save stack space */
-			/* pg_qsort(pn - d2, d2 / es, es, cmp); */
-			a = pn - d2;
-			n = d2 / es;
-			goto loop;
-		}
-	}
-	else
-	{
-		/* Recurse on right partition, then iterate on left partition */
-		if (d2 > es)
-			pg_qsort(pn - d2, d2 / es, es, cmp);
-		if (d1 > es)
-		{
-			/* Iterate rather than recurse to save stack space */
-			/* pg_qsort(a, d1 / es, es, cmp); */
-			n = d1 / es;
-			goto loop;
-		}
-	}
-}
+#define ST_SORT pg_qsort
+#define ST_ELEMENT_TYPE_VOID
+#define ST_COMPARE_RUNTIME_POINTER
+#define ST_SCOPE
+#define ST_DECLARE
+#define ST_DEFINE
+#include "lib/sort_template.h"
 
 /*
  * qsort comparator wrapper for strcmp.
diff --git a/src/port/qsort_arg.c b/src/port/qsort_arg.c
index 6d54fbc2b4..fa7e11a3b8 100644
--- a/src/port/qsort_arg.c
+++ b/src/port/qsort_arg.c
@@ -1,226 +1,14 @@
 /*
  *	qsort_arg.c: qsort with a passthrough "void *" argument
- *
- *	Modifications from vanilla NetBSD source:
- *	  Add do ... while() macro fix
- *	  Remove __inline, _DIAGASSERTs, __P
- *	  Remove ill-considered "swap_cnt" switch to insertion sort,
- *	  in favor of a simple check for presorted input.
- *	  Take care to recurse on the smaller partition, to bound stack usage.
- *
- *	CAUTION: if you change this file, see also qsort.c, gen_qsort_tuple.pl
- *
- *	src/port/qsort_arg.c
- */
-
-/*	$NetBSD: qsort.c,v 1.13 2003/08/07 16:43:42 agc Exp $	*/
-
-/*-
- * Copyright (c) 1992, 1993
- *	The Regents of the University of California.  All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *	  notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *	  notice, this list of conditions and the following disclaimer in the
- *	  documentation and/or other materials provided with the distribution.
- * 3. Neither the name of the University nor the names of its contributors
- *	  may be used to endorse or promote products derived from this software
- *	  without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
  */
 
 #include "c.h"
 
-
-static char *med3(char *a, char *b, char *c,
-				  qsort_arg_comparator cmp, void *arg);
-static void swapfunc(char *, char *, size_t, int);
-
-/*
- * Qsort routine based on J. L. Bentley and M. D. McIlroy,
- * "Engineering a sort function",
- * Software--Practice and Experience 23 (1993) 1249-1265.
- *
- * We have modified their original by adding a check for already-sorted input,
- * which seems to be a win per discussions on pgsql-hackers around 2006-03-21.
- *
- * Also, we recurse on the smaller partition and iterate on the larger one,
- * which ensures we cannot recurse more than log(N) levels (since the
- * partition recursed to is surely no more than half of the input).  Bentley
- * and McIlroy explicitly rejected doing this on the grounds that it's "not
- * worth the effort", but we have seen crashes in the field due to stack
- * overrun, so that judgment seems wrong.
- */
-
-#define swapcode(TYPE, parmi, parmj, n) \
-do {		\
-	size_t i = (n) / sizeof (TYPE);			\
-	TYPE *pi = (TYPE *)(void *)(parmi);			\
-	TYPE *pj = (TYPE *)(void *)(parmj);			\
-	do {						\
-		TYPE	t = *pi;			\
-		*pi++ = *pj;				\
-		*pj++ = t;				\
-		} while (--i > 0);				\
-} while (0)
-
-#define SWAPINIT(a, es) swaptype = ((char *)(a) - (char *)0) % sizeof(long) || \
-	(es) % sizeof(long) ? 2 : (es) == sizeof(long)? 0 : 1
-
-static void
-swapfunc(char *a, char *b, size_t n, int swaptype)
-{
-	if (swaptype <= 1)
-		swapcode(long, a, b, n);
-	else
-		swapcode(char, a, b, n);
-}
-
-#define swap(a, b)						\
-	if (swaptype == 0) {					\
-		long t = *(long *)(void *)(a);			\
-		*(long *)(void *)(a) = *(long *)(void *)(b);	\
-		*(long *)(void *)(b) = t;			\
-	} else							\
-		swapfunc(a, b, es, swaptype)
-
-#define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
-
-static char *
-med3(char *a, char *b, char *c, qsort_arg_comparator cmp, void *arg)
-{
-	return cmp(a, b, arg) < 0 ?
-		(cmp(b, c, arg) < 0 ? b : (cmp(a, c, arg) < 0 ? c : a))
-		: (cmp(b, c, arg) > 0 ? b : (cmp(a, c, arg) < 0 ? a : c));
-}
-
-void
-qsort_arg(void *a, size_t n, size_t es, qsort_arg_comparator cmp, void *arg)
-{
-	char	   *pa,
-			   *pb,
-			   *pc,
-			   *pd,
-			   *pl,
-			   *pm,
-			   *pn;
-	size_t		d1,
-				d2;
-	int			r,
-				swaptype,
-				presorted;
-
-loop:SWAPINIT(a, es);
-	if (n < 7)
-	{
-		for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
-			for (pl = pm; pl > (char *) a && cmp(pl - es, pl, arg) > 0;
-				 pl -= es)
-				swap(pl, pl - es);
-		return;
-	}
-	presorted = 1;
-	for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
-	{
-		if (cmp(pm - es, pm, arg) > 0)
-		{
-			presorted = 0;
-			break;
-		}
-	}
-	if (presorted)
-		return;
-	pm = (char *) a + (n / 2) * es;
-	if (n > 7)
-	{
-		pl = (char *) a;
-		pn = (char *) a + (n - 1) * es;
-		if (n > 40)
-		{
-			size_t		d = (n / 8) * es;
-
-			pl = med3(pl, pl + d, pl + 2 * d, cmp, arg);
-			pm = med3(pm - d, pm, pm + d, cmp, arg);
-			pn = med3(pn - 2 * d, pn - d, pn, cmp, arg);
-		}
-		pm = med3(pl, pm, pn, cmp, arg);
-	}
-	swap(a, pm);
-	pa = pb = (char *) a + es;
-	pc = pd = (char *) a + (n - 1) * es;
-	for (;;)
-	{
-		while (pb <= pc && (r = cmp(pb, a, arg)) <= 0)
-		{
-			if (r == 0)
-			{
-				swap(pa, pb);
-				pa += es;
-			}
-			pb += es;
-		}
-		while (pb <= pc && (r = cmp(pc, a, arg)) >= 0)
-		{
-			if (r == 0)
-			{
-				swap(pc, pd);
-				pd -= es;
-			}
-			pc -= es;
-		}
-		if (pb > pc)
-			break;
-		swap(pb, pc);
-		pb += es;
-		pc -= es;
-	}
-	pn = (char *) a + n * es;
-	d1 = Min(pa - (char *) a, pb - pa);
-	vecswap(a, pb - d1, d1);
-	d1 = Min(pd - pc, pn - pd - es);
-	vecswap(pb, pn - d1, d1);
-	d1 = pb - pa;
-	d2 = pd - pc;
-	if (d1 <= d2)
-	{
-		/* Recurse on left partition, then iterate on right partition */
-		if (d1 > es)
-			qsort_arg(a, d1 / es, es, cmp, arg);
-		if (d2 > es)
-		{
-			/* Iterate rather than recurse to save stack space */
-			/* qsort_arg(pn - d2, d2 / es, es, cmp, arg); */
-			a = pn - d2;
-			n = d2 / es;
-			goto loop;
-		}
-	}
-	else
-	{
-		/* Recurse on right partition, then iterate on left partition */
-		if (d2 > es)
-			qsort_arg(pn - d2, d2 / es, es, cmp, arg);
-		if (d1 > es)
-		{
-			/* Iterate rather than recurse to save stack space */
-			/* qsort_arg(a, d1 / es, es, cmp, arg); */
-			n = d1 / es;
-			goto loop;
-		}
-	}
-}
+#define ST_SORT qsort_arg
+#define ST_ELEMENT_TYPE_VOID
+#define ST_COMPARATOR_TYPE_NAME qsort_arg_comparator
+#define ST_COMPARE_RUNTIME_POINTER
+#define ST_COMPARE_ARG_TYPE void
+#define ST_SCOPE
+#define ST_DEFINE
+#include "lib/sort_template.h"
-- 
2.30.0

From 53f717b74926bd812acf0985c1ffb42a8e2780ae Mon Sep 17 00:00:00 2001
From: Thomas Munro <[email-masked]>
Date: Wed, 19 Aug 2020 20:25:12 +1200
Subject: [PATCH 3/3] Use sort_template.h for qsort_tuple() and qsort_ssup().

Replace the Perl code the previously generated specialized sort
functions with an instantiation of sort_template.h.
---
 src/backend/Makefile                      |   4 +-
 src/backend/utils/sort/.gitignore         |   1 -
 src/backend/utils/sort/Makefile           |   8 -
 src/backend/utils/sort/gen_qsort_tuple.pl | 272 ----------------------
 src/backend/utils/sort/tuplesort.c        |  21 +-
 src/tools/msvc/Solution.pm                |  10 -
 src/tools/msvc/clean.bat                  |   1 -
 7 files changed, 21 insertions(+), 296 deletions(-)
 delete mode 100644 src/backend/utils/sort/.gitignore
 delete mode 100644 src/backend/utils/sort/gen_qsort_tuple.pl

diff --git a/src/backend/Makefile b/src/backend/Makefile
index 9672e2cb43..0da848b1fd 100644
--- a/src/backend/Makefile
+++ b/src/backend/Makefile
@@ -190,7 +190,6 @@ distprep:
 	$(MAKE) -C utils	distprep
 	$(MAKE) -C utils/adt	jsonpath_gram.c jsonpath_scan.c
 	$(MAKE) -C utils/misc	guc-file.c
-	$(MAKE) -C utils/sort	qsort_tuple.c

 ##########################################################################
@@ -312,8 +311,7 @@ maintainer-clean: distclean
 	      storage/lmgr/lwlocknames.h \
 	      utils/adt/jsonpath_gram.c \
 	      utils/adt/jsonpath_scan.c \
-	      utils/misc/guc-file.c \
-	      utils/sort/qsort_tuple.c
+	      utils/misc/guc-file.c

 ##########################################################################
diff --git a/src/backend/utils/sort/.gitignore b/src/backend/utils/sort/.gitignore
deleted file mode 100644
index f2958633e6..0000000000
--- a/src/backend/utils/sort/.gitignore
+++ /dev/null
@@ -1 +0,0 @@
-/qsort_tuple.c
diff --git a/src/backend/utils/sort/Makefile b/src/backend/utils/sort/Makefile
index 7ac3659261..26f65fcaf7 100644
--- a/src/backend/utils/sort/Makefile
+++ b/src/backend/utils/sort/Makefile
@@ -21,12 +21,4 @@ OBJS = \
 	tuplesort.o \
 	tuplestore.o
 
-tuplesort.o: qsort_tuple.c
-
-qsort_tuple.c: gen_qsort_tuple.pl
-	$(PERL) $(srcdir)/gen_qsort_tuple.pl $< > $@
-
 include $(top_srcdir)/src/backend/common.mk
-
-maintainer-clean:
-	rm -f qsort_tuple.c
diff --git a/src/backend/utils/sort/gen_qsort_tuple.pl b/src/backend/utils/sort/gen_qsort_tuple.pl
deleted file mode 100644
index 4c305806c7..0000000000
--- a/src/backend/utils/sort/gen_qsort_tuple.pl
+++ /dev/null
@@ -1,272 +0,0 @@
-#!/usr/bin/perl
-
-#
-# gen_qsort_tuple.pl
-#
-# This script generates specialized versions of the quicksort algorithm for
-# tuple sorting.  The quicksort code is derived from the NetBSD code.  The
-# code generated by this script runs significantly faster than vanilla qsort
-# when used to sort tuples.  This speedup comes from a number of places.
-# The major effects are (1) inlining simple tuple comparators is much faster
-# than jumping through a function pointer and (2) swap and vecswap operations
-# specialized to the particular data type of interest (in this case, SortTuple)
-# are faster than the generic routines.
-#
-#	Modifications from vanilla NetBSD source:
-#	  Add do ... while() macro fix
-#	  Remove __inline, _DIAGASSERTs, __P
-#	  Remove ill-considered "swap_cnt" switch to insertion sort,
-#	  in favor of a simple check for presorted input.
-#	  Take care to recurse on the smaller partition, to bound stack usage.
-#
-#     Instead of sorting arbitrary objects, we're always sorting SortTuples.
-#     Add CHECK_FOR_INTERRUPTS().
-#
-# CAUTION: if you change this file, see also qsort.c and qsort_arg.c
-#
-
-use strict;
-use warnings;
-
-my $SUFFIX;
-my $EXTRAARGS;
-my $EXTRAPARAMS;
-my $CMPPARAMS;
-
-emit_qsort_boilerplate();
-
-$SUFFIX      = 'tuple';
-$EXTRAARGS   = ', SortTupleComparator cmp_tuple, Tuplesortstate *state';
-$EXTRAPARAMS = ', cmp_tuple, state';
-$CMPPARAMS   = ', state';
-emit_qsort_implementation();
-
-$SUFFIX      = 'ssup';
-$EXTRAARGS   = ', SortSupport ssup';
-$EXTRAPARAMS = ', ssup';
-$CMPPARAMS   = ', ssup';
-print <<'EOM';
-
-#define cmp_ssup(a, b, ssup) \
-	ApplySortComparator((a)->datum1, (a)->isnull1, \
-						(b)->datum1, (b)->isnull1, ssup)
-
-EOM
-emit_qsort_implementation();
-
-sub emit_qsort_boilerplate
-{
-	print <<'EOM';
-/*
- * autogenerated by src/backend/utils/sort/gen_qsort_tuple.pl, do not edit!
- *
- * This file is included by tuplesort.c, rather than compiled separately.
- */
-
-/*	$NetBSD: qsort.c,v 1.13 2003/08/07 16:43:42 agc Exp $	*/
-
-/*-
- * Copyright (c) 1992, 1993
- *	The Regents of the University of California.  All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *	  notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *	  notice, this list of conditions and the following disclaimer in the
- *	  documentation and/or other materials provided with the distribution.
- * 3. Neither the name of the University nor the names of its contributors
- *	  may be used to endorse or promote products derived from this software
- *	  without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
- * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
- * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
- * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- */
-
-/*
- * Qsort routine based on J. L. Bentley and M. D. McIlroy,
- * "Engineering a sort function",
- * Software--Practice and Experience 23 (1993) 1249-1265.
- *
- * We have modified their original by adding a check for already-sorted input,
- * which seems to be a win per discussions on pgsql-hackers around 2006-03-21.
- *
- * Also, we recurse on the smaller partition and iterate on the larger one,
- * which ensures we cannot recurse more than log(N) levels (since the
- * partition recursed to is surely no more than half of the input).  Bentley
- * and McIlroy explicitly rejected doing this on the grounds that it's "not
- * worth the effort", but we have seen crashes in the field due to stack
- * overrun, so that judgment seems wrong.
- */
-
-static void
-swapfunc(SortTuple *a, SortTuple *b, size_t n)
-{
-	do
-	{
-		SortTuple	t = *a;
-
-		*a++ = *b;
-		*b++ = t;
-	} while (--n > 0);
-}
-
-#define swap(a, b)						\
-	do { 								\
-		SortTuple t = *(a);				\
-		*(a) = *(b);					\
-		*(b) = t;						\
-	} while (0)
-
-#define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n)
-
-EOM
-
-	return;
-}
-
-sub emit_qsort_implementation
-{
-	print <<EOM;
-static SortTuple *
-med3_$SUFFIX(SortTuple *a, SortTuple *b, SortTuple *c$EXTRAARGS)
-{
-	return cmp_$SUFFIX(a, b$CMPPARAMS) < 0 ?
-		(cmp_$SUFFIX(b, c$CMPPARAMS) < 0 ? b :
-		 (cmp_$SUFFIX(a, c$CMPPARAMS) < 0 ? c : a))
-		: (cmp_$SUFFIX(b, c$CMPPARAMS) > 0 ? b :
-		   (cmp_$SUFFIX(a, c$CMPPARAMS) < 0 ? a : c));
-}
-
-static void
-qsort_$SUFFIX(SortTuple *a, size_t n$EXTRAARGS)
-{
-	SortTuple  *pa,
-			   *pb,
-			   *pc,
-			   *pd,
-			   *pl,
-			   *pm,
-			   *pn;
-	size_t		d1,
-				d2;
-	int			r,
-				presorted;
-
-loop:
-	CHECK_FOR_INTERRUPTS();
-	if (n < 7)
-	{
-		for (pm = a + 1; pm < a + n; pm++)
-			for (pl = pm; pl > a && cmp_$SUFFIX(pl - 1, pl$CMPPARAMS) > 0; pl--)
-				swap(pl, pl - 1);
-		return;
-	}
-	presorted = 1;
-	for (pm = a + 1; pm < a + n; pm++)
-	{
-		CHECK_FOR_INTERRUPTS();
-		if (cmp_$SUFFIX(pm - 1, pm$CMPPARAMS) > 0)
-		{
-			presorted = 0;
-			break;
-		}
-	}
-	if (presorted)
-		return;
-	pm = a + (n / 2);
-	if (n > 7)
-	{
-		pl = a;
-		pn = a + (n - 1);
-		if (n > 40)
-		{
-			size_t		d = (n / 8);
-
-			pl = med3_$SUFFIX(pl, pl + d, pl + 2 * d$EXTRAPARAMS);
-			pm = med3_$SUFFIX(pm - d, pm, pm + d$EXTRAPARAMS);
-			pn = med3_$SUFFIX(pn - 2 * d, pn - d, pn$EXTRAPARAMS);
-		}
-		pm = med3_$SUFFIX(pl, pm, pn$EXTRAPARAMS);
-	}
-	swap(a, pm);
-	pa = pb = a + 1;
-	pc = pd = a + (n - 1);
-	for (;;)
-	{
-		while (pb <= pc && (r = cmp_$SUFFIX(pb, a$CMPPARAMS)) <= 0)
-		{
-			if (r == 0)
-			{
-				swap(pa, pb);
-				pa++;
-			}
-			pb++;
-			CHECK_FOR_INTERRUPTS();
-		}
-		while (pb <= pc && (r = cmp_$SUFFIX(pc, a$CMPPARAMS)) >= 0)
-		{
-			if (r == 0)
-			{
-				swap(pc, pd);
-				pd--;
-			}
-			pc--;
-			CHECK_FOR_INTERRUPTS();
-		}
-		if (pb > pc)
-			break;
-		swap(pb, pc);
-		pb++;
-		pc--;
-	}
-	pn = a + n;
-	d1 = Min(pa - a, pb - pa);
-	vecswap(a, pb - d1, d1);
-	d1 = Min(pd - pc, pn - pd - 1);
-	vecswap(pb, pn - d1, d1);
-	d1 = pb - pa;
-	d2 = pd - pc;
-	if (d1 <= d2)
-	{
-		/* Recurse on left partition, then iterate on right partition */
-		if (d1 > 1)
-			qsort_$SUFFIX(a, d1$EXTRAPARAMS);
-		if (d2 > 1)
-		{
-			/* Iterate rather than recurse to save stack space */
-			/* qsort_$SUFFIX(pn - d2, d2$EXTRAPARAMS); */
-			a = pn - d2;
-			n = d2;
-			goto loop;
-		}
-	}
-	else
-	{
-		/* Recurse on right partition, then iterate on left partition */
-		if (d2 > 1)
-			qsort_$SUFFIX(pn - d2, d2$EXTRAPARAMS);
-		if (d1 > 1)
-		{
-			/* Iterate rather than recurse to save stack space */
-			/* qsort_$SUFFIX(a, d1$EXTRAPARAMS); */
-			n = d1;
-			goto loop;
-		}
-	}
-}
-EOM
-
-	return;
-}
diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c
index 7d0f96afb7..22972071ff 100644
--- a/src/backend/utils/sort/tuplesort.c
+++ b/src/backend/utils/sort/tuplesort.c
@@ -676,8 +676,27 @@ static void tuplesort_updatemax(Tuplesortstate *state);
  * reduces to ApplySortComparator(), that is single-key MinimalTuple sorts
  * and Datum sorts.
  */
-#include "qsort_tuple.c"
 
+#define ST_SORT qsort_tuple
+#define ST_ELEMENT_TYPE SortTuple
+#define ST_COMPARE_RUNTIME_POINTER
+#define ST_COMPARE_ARG_TYPE Tuplesortstate
+#define ST_CHECK_FOR_INTERRUPTS
+#define ST_SCOPE static
+#define ST_DECLARE
+#define ST_DEFINE
+#include "lib/sort_template.h"
+
+#define ST_SORT qsort_ssup
+#define ST_ELEMENT_TYPE SortTuple
+#define ST_COMPARE(a, b, ssup) \
+	ApplySortComparator((a)->datum1, (a)->isnull1, \
+						(b)->datum1, (b)->isnull1, (ssup))
+#define ST_COMPARE_ARG_TYPE SortSupportData
+#define ST_CHECK_FOR_INTERRUPTS
+#define ST_SCOPE static
+#define ST_DEFINE
+#include "lib/sort_template.h"
 
 /*
  *		tuplesort_begin_xxx
diff --git a/src/tools/msvc/Solution.pm b/src/tools/msvc/Solution.pm
index 2aa062b2c9..69b08591cc 100644
--- a/src/tools/msvc/Solution.pm
+++ b/src/tools/msvc/Solution.pm
@@ -665,16 +665,6 @@ sub GenerateFiles
 		);
 	}
 
-	if (IsNewer(
-			'src/backend/utils/sort/qsort_tuple.c',
-			'src/backend/utils/sort/gen_qsort_tuple.pl'))
-	{
-		print "Generating qsort_tuple.c...\n";
-		system(
-			'perl src/backend/utils/sort/gen_qsort_tuple.pl > src/backend/utils/sort/qsort_tuple.c'
-		);
-	}
-
 	if (IsNewer('src/bin/psql/sql_help.h', 'src/bin/psql/create_help.pl'))
 	{
 		print "Generating sql_help.h...\n";
diff --git a/src/tools/msvc/clean.bat b/src/tools/msvc/clean.bat
index d0d79a0932..0cc91e7d6c 100755
--- a/src/tools/msvc/clean.bat
+++ b/src/tools/msvc/clean.bat
@@ -62,7 +62,6 @@ if %DIST%==1 if exist src\backend\storage\lmgr\lwlocknames.h del /q src\backend\
 if %DIST%==1 if exist src\pl\plpython\spiexceptions.h del /q src\pl\plpython\spiexceptions.h
 if %DIST%==1 if exist src\pl\plpgsql\src\plerrcodes.h del /q src\pl\plpgsql\src\plerrcodes.h
 if %DIST%==1 if exist src\pl\tcl\pltclerrcodes.h del /q src\pl\tcl\pltclerrcodes.h
-if %DIST%==1 if exist src\backend\utils\sort\qsort_tuple.c del /q src\backend\utils\sort\qsort_tuple.c
 if %DIST%==1 if exist src\bin\psql\sql_help.c del /q src\bin\psql\sql_help.c
 if %DIST%==1 if exist src\bin\psql\sql_help.h del /q src\bin\psql\sql_help.h
 if %DIST%==1 if exist src\common\kwlist_d.h del /q src\common\kwlist_d.h
-- 
2.30.0

---

From: Andres Freund <[email-masked]>
Date: Wed, 17 Feb 2021 22:02:22 -0800

Hi,

> worthwhile specialisations for separate proposals; I've heard about

One place that could benefit is the qsort that BufferSync() does at the
start. I tried your patch for that, and it does reduce the sort time
considerably. For 64GB of mostly dirty shared_buffers from ~1.4s to
0.6s.

Now, obviously one can argue that that's not going to be the crucial
spot, and wouldn't be entirely wrong. OTOH, in my AIO branch I see
checkpointer doing ~10GB/s, leading to the sort being a measurable
portion of the overall time.

Greetings,

Andres Freund

---

From: Daniel Gustafsson <[email-masked]>
Date: Tue, 2 Mar 2021 22:25:39 +0100

> On 18 Feb 2021, at 04:09, Thomas Munro <[email-masked]> wrote:

> worthwhile specialisations for separate proposals; I've heard about

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:

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

---

From: Thomas Munro <[email-masked]>
Date: Wed, 3 Mar 2021 17:17:13 +1300

> of magic, moving from the Perl generator makes this slightly less magic IMO so

Thanks for testing and reviewing!

> + *   - ST_COMPARE(a, b, arg) - variant that takes an extra argument

Fixed.  Also ran pgindent.

> sort_template.h for documentation.

I tried adding a comment along the lines "see lib/sort_template.h for
details", but it felt pretty redundant, when the file contains very
little other than #include "lib/sort_template.h" which should already
tell you to go and look there to find out what this is about...

I went ahead and pushed these.

I am sure there are plenty of opportunities to experiment with this
code.  Here are some I recall Peter Geoghegan mentioning:

1.  If you know that elements are unique, you could remove some
branches that deal with equal elements (see "r == 0").
2.  Perhaps you might want to be able to disable the "presorted" check
in some cases?
3.  The parameters 7, 7 and 40 were probably tuned for an ancient Vax
or similar[1].  We see higher insertion sort thesholds such as 27 in
more recent sort algorithms[2] used in eg the JVM.  You could perhaps
speculate that the right answer depends in part on the element size; I
dunno, but if so, here we have that at compile time while traditional
qsort() does not.

As for which cases are actually worth specialising, I've attached the
example that Andres mentioned earlier; it seems like a reasonable
candidate to go ahead and commit too, but I realised that I'd
forgotten to attach it earlier.

It's possible that the existing support sorting tuples could be
further specialised for common sort key data types; I haven't tried
that.

[1] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.14.8162&rep=rep1&type=pdf
[2] https://codeblab.com/wp-content/uploads/2009/09/DualPivotQuicksort.pdf
From 4cec5cb9a2e0c50726b7337fb8221281e155c4cd Mon Sep 17 00:00:00 2001
From: Thomas Munro <[email-masked]>
Date: Thu, 18 Feb 2021 14:47:28 +1300
Subject: [PATCH] Specialize checkpointer sort functions.

When sorting a potentially large number of dirty buffers, the
checkpointer can benefit from a faster sort routine.  One reported
improvement on a large buffer pool system was 1.4s -> 0.6s.

Discussion: https://postgr.es/m/CA%2BhUKGJ2-eaDqAum5bxhpMNhvuJmRDZxB_Tow0n-gse%2BHG0Yig%40mail.gmail.com
---
 src/backend/storage/buffer/bufmgr.c | 37 +++++++++++++++++------------
 1 file changed, 22 insertions(+), 15 deletions(-)

diff --git a/src/backend/storage/buffer/bufmgr.c b/src/backend/storage/buffer/bufmgr.c
index 561c212092..7adec2ddc3 100644
--- a/src/backend/storage/buffer/bufmgr.c
+++ b/src/backend/storage/buffer/bufmgr.c
@@ -488,8 +488,8 @@ static void FindAndDropRelFileNodeBuffers(RelFileNode rnode,
 static void AtProcExit_Buffers(int code, Datum arg);
 static void CheckForBufferLeaks(void);
 static int	rnode_comparator(const void *p1, const void *p2);
-static int	buffertag_comparator(const void *p1, const void *p2);
-static int	ckpt_buforder_comparator(const void *pa, const void *pb);
+static inline int buffertag_comparator(const BufferTag *a, const BufferTag *b);
+static inline int ckpt_buforder_comparator(const CkptSortItem *a, const CkptSortItem *b);
 static int	ts_ckpt_progress_comparator(Datum a, Datum b, void *arg);

@@ -1831,6 +1831,13 @@ UnpinBuffer(BufferDesc *buf, bool fixOwner)
 	}
 }
 
+#define ST_SORT sort_checkpoint_bufferids
+#define ST_ELEMENT_TYPE CkptSortItem
+#define ST_COMPARE(a, b) ckpt_buforder_comparator(a, b)
+#define ST_SCOPE static
+#define ST_DEFINE
+#include <lib/sort_template.h>
+
 /*
  * BufferSync -- Write out all dirty buffers in the pool.
  *
@@ -1931,8 +1938,7 @@ BufferSync(int flags)
 	 * end up writing to the tablespaces one-by-one; possibly overloading the
 	 * underlying system.
 	 */
-	qsort(CkptBufferIds, num_to_scan, sizeof(CkptSortItem),
-		  ckpt_buforder_comparator);
+	sort_checkpoint_bufferids(CkptBufferIds, num_to_scan);
 
 	num_spaces = 0;
 
@@ -4595,11 +4601,9 @@ WaitBufHdrUnlocked(BufferDesc *buf)
 /*
  * BufferTag comparator.
  */
-static int
-buffertag_comparator(const void *a, const void *b)
+static inline int
+buffertag_comparator(const BufferTag *ba, const BufferTag *bb)
 {
-	const BufferTag *ba = (const BufferTag *) a;
-	const BufferTag *bb = (const BufferTag *) b;
 	int			ret;
 
 	ret = rnode_comparator(&ba->rnode, &bb->rnode);
@@ -4626,12 +4630,9 @@ buffertag_comparator(const void *a, const void *b)
  * It is important that tablespaces are compared first, the logic balancing
  * writes between tablespaces relies on it.
  */
-static int
-ckpt_buforder_comparator(const void *pa, const void *pb)
+static inline int
+ckpt_buforder_comparator(const CkptSortItem *a, const CkptSortItem *b)
 {
-	const CkptSortItem *a = (const CkptSortItem *) pa;
-	const CkptSortItem *b = (const CkptSortItem *) pb;
-
 	/* compare tablespace */
 	if (a->tsId < b->tsId)
 		return -1;
@@ -4722,6 +4723,13 @@ ScheduleBufferTagForWriteback(WritebackContext *context, BufferTag *tag)
 		IssuePendingWritebacks(context);
 }
 
+#define ST_SORT sort_pending_writebacks
+#define ST_ELEMENT_TYPE PendingWriteback
+#define ST_COMPARE(a, b) buffertag_comparator(&a->tag, &b->tag)
+#define ST_SCOPE static
+#define ST_DEFINE
+#include <lib/sort_template.h>
+
 /*
  * Issue all pending writeback requests, previously scheduled with
  * ScheduleBufferTagForWriteback, to the OS.
@@ -4741,8 +4749,7 @@ IssuePendingWritebacks(WritebackContext *context)
 	 * Executing the writes in-order can make them a lot faster, and allows to
 	 * merge writeback requests to consecutive blocks into larger writebacks.
 	 */
-	qsort(&context->pending_writebacks, context->nr_pending,
-		  sizeof(PendingWriteback), buffertag_comparator);
+	sort_pending_writebacks(context->pending_writebacks, context->nr_pending);
 
 	/*
 	 * Coalesce neighbouring writes, but nothing else. For that we iterate
-- 
2.30.0

---

From: Andres Freund <[email-masked]>
Date: Thu, 11 Mar 2021 10:58:47 -0800

Hi,

I wish we had the same for bsearch... :)

> Discussion: https://postgr.es/m/CA%2BhUKGJ2-eaDqAum5bxhpMNhvuJmRDZxB_Tow0n-gse%2BHG0Yig%40mail.gmail.com

Looks good to me.

Greetings,

Andres Freund

---

From: Thomas Munro <[email-masked]>
Date: Sat, 13 Mar 2021 15:49:36 +1300

> 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...

[1] https://www.postgresql.org/message-id/flat/CA%2BhUKGLY47Cvu62mFDT53Ya0P95cGggcBN6R6aLpx6%3DGm5j%2B1A%40mail.gmail.com

---

From: Thomas Munro <[email-masked]>
Date: Sun, 14 Mar 2021 15:35:23 +1300

> 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.
From d0fb306d2720d14be2d46f4ae4198b25a33a95fa Mon Sep 17 00:00:00 2001
From: Thomas Munro <[email-masked]>
Date: Sat, 13 Mar 2021 17:29:44 +1300
Subject: [PATCH 1/9] Add bsearch and unique templates to sort_template.h.

Since binary search and uniquify are so closely related to sorting,
let's optionally generate compatible functions at the same time.

Also, optionally support comparators with wider return types.  This will
allow us to do more branchless comparators.

Also, adjust the ST_SORT template to cope with pointer types.
---
 src/include/lib/sort_template.h | 142 ++++++++++++++++++++++++++++----
 1 file changed, 124 insertions(+), 18 deletions(-)

diff --git a/src/include/lib/sort_template.h b/src/include/lib/sort_template.h
index 771c789ced..a6097e1ac5 100644
--- a/src/include/lib/sort_template.h
+++ b/src/include/lib/sort_template.h
@@ -3,7 +3,8 @@
  * sort_template.h
  *
  *	  A template for a sort algorithm that supports varying degrees of
- *	  specialization.
+ *	  specialization.  Also related algorithms for binary search and
+ *	  unique, on sorted arrays.
  *
  * Copyright (c) 2021, PostgreSQL Global Development Group
  * Portions Copyright (c) 1992-1994, Regents of the University of California
@@ -13,7 +14,9 @@
  *	  To generate functions specialized for a type, the following parameter
  *	  macros should be #define'd before this file is included.
  *
- *	  - ST_SORT - the name of a sort function to be generated
+ *	  - ST_SORT - if defined the name of a sort function
+ *	  - ST_UNIQUE - if defined the name of a unique function
+ *	  - ST_SEARCH - if defined the name of a search function
  *	  - ST_ELEMENT_TYPE - type of the referenced elements
  *	  - ST_DECLARE - if defined the functions and types are declared
  *	  - ST_DEFINE - if defined the functions and types are defined
@@ -40,6 +43,10 @@
  *
  *	  - ST_COMPARE_ARG_TYPE - type of extra argument
  *
+ *	  To say that the comparator returns a type other than int, use:
+ *
+ * 	  - ST_COMPARE_TYPE - an integer type
+ *
  *	  The prototype of the generated sort function is:
  *
  *	  void ST_SORT(ST_ELEMENT_TYPE *data, size_t n,
@@ -179,13 +186,35 @@ typedef int (*ST_COMPARATOR_TYPE_NAME) (const ST_ELEMENT_TYPE *,
 										const ST_ELEMENT_TYPE *ST_SORT_PROTO_ARG);
 #endif
 
+#ifdef ST_SORT
 /* Declare the sort function.  Note optional arguments at end. */
-ST_SCOPE void ST_SORT(ST_ELEMENT_TYPE *first, size_t n
+ST_SCOPE void ST_SORT(ST_ELEMENT_TYPE *array,
+					  size_t n
 					  ST_SORT_PROTO_ELEMENT_SIZE
 					  ST_SORT_PROTO_COMPARE
 					  ST_SORT_PROTO_ARG);
+#endif /* ST_SORT */
 
-#endif
+#ifdef ST_SEARCH
+/* Declare the search function. */
+ST_SCOPE ST_ELEMENT_TYPE *ST_SEARCH(ST_ELEMENT_TYPE *value,
+									ST_ELEMENT_TYPE *array,
+									size_t n
+									ST_SORT_PROTO_ELEMENT_SIZE
+									ST_SORT_PROTO_COMPARE
+									ST_SORT_PROTO_ARG);
+#endif /* ST_SEARCH */
+
+#ifdef ST_UNIQUE
+ST_SCOPE size_t
+ST_UNIQUE(ST_ELEMENT_TYPE *array,
+		  size_t n
+		  ST_SORT_PROTO_ELEMENT_SIZE
+		  ST_SORT_PROTO_COMPARE
+		  ST_SORT_PROTO_ARG);
+#endif /* ST_UNIQUE */
+
+#endif /* ST_DECLARE */
 
 #ifdef ST_DEFINE
 
@@ -201,16 +230,20 @@ ST_SCOPE void ST_SORT(ST_ELEMENT_TYPE *first, size_t n
 #define DO_CHECK_FOR_INTERRUPTS()
 #endif
 
+#ifndef ST_COMPARE_TYPE
+#define ST_COMPARE_TYPE int
+#endif
+
 /*
  * Create wrapper macros that know how to invoke compare, med3 and sort with
  * the right arguments.
  */
 #ifdef ST_COMPARE_RUNTIME_POINTER
-#define DO_COMPARE(a_, b_) ST_COMPARE((a_), (b_) ST_SORT_INVOKE_ARG)
+#define DO_COMPARE(a_, b_) ((ST_COMPARE_TYPE) (ST_COMPARE((a_), (b_) ST_SORT_INVOKE_ARG)))
 #elif defined(ST_COMPARE_ARG_TYPE)
-#define DO_COMPARE(a_, b_) ST_COMPARE((a_), (b_), arg)
+#define DO_COMPARE(a_, b_) ((ST_COMPARE_TYPE) (ST_COMPARE((a_), (b_), arg)))
 #else
-#define DO_COMPARE(a_, b_) ST_COMPARE((a_), (b_))
+#define DO_COMPARE(a_, b_) ((ST_COMPARE_TYPE) (ST_COMPARE((a_), (b_))))
 #endif
 #define DO_MED3(a_, b_, c_)												\
 	ST_MED3((a_), (b_), (c_)											\
@@ -239,6 +272,8 @@ ST_SCOPE void ST_SORT(ST_ELEMENT_TYPE *first, size_t n
 #define DO_SWAP(a_, b_) DO_SWAPN((a_), (b_), element_size)
 #endif
 
+#ifdef ST_SORT
+
 /*
  * Find the median of three values.  Currently, performance seems to be best
  * if the the comparator is inlined here, but the med3 function is not inlined
@@ -281,18 +316,18 @@ ST_SORT(ST_ELEMENT_TYPE *data, size_t n
 		ST_SORT_PROTO_COMPARE
 		ST_SORT_PROTO_ARG)
 {
-	ST_POINTER_TYPE *a = (ST_POINTER_TYPE *) data,
-			   *pa,
-			   *pb,
-			   *pc,
-			   *pd,
-			   *pl,
-			   *pm,
-			   *pn;
+	ST_POINTER_TYPE *a = (ST_POINTER_TYPE *) data;
+	ST_POINTER_TYPE *pa;
+	ST_POINTER_TYPE *pb;
+	ST_POINTER_TYPE *pc;
+	ST_POINTER_TYPE *pd;
+	ST_POINTER_TYPE *pl;
+	ST_POINTER_TYPE *pm;
+	ST_POINTER_TYPE *pn;
 	size_t		d1,
 				d2;
-	int			r,
-				presorted;
+	int			presorted;
+	ST_COMPARE_TYPE r;
 
 loop:
 	DO_CHECK_FOR_INTERRUPTS();
@@ -399,7 +434,75 @@ loop:
 		}
 	}
 }
-#endif
+
+#endif /* ST_SORT */
+
+#ifdef ST_SEARCH
+
+/*
+ * Find an element in the array of sorted values that is equal to a given
+ * value, in a sorted array.  Return NULL if there is none.
+ */
+ST_SCOPE ST_ELEMENT_TYPE *
+ST_SEARCH(ST_ELEMENT_TYPE *value,
+		  ST_ELEMENT_TYPE *array,
+		  size_t n
+		  ST_SORT_PROTO_ELEMENT_SIZE
+		  ST_SORT_PROTO_COMPARE
+		  ST_SORT_PROTO_ARG)
+{
+	ssize_t		left = 0,
+				right = n - 1;
+
+	while (left <= right)
+	{
+		size_t		mid = (left + right) / 2;
+		ST_ELEMENT_TYPE *element = &array[mid];
+		ST_COMPARE_TYPE cmp = DO_COMPARE(element, value);
+
+		if (cmp < 0)
+			left = mid + 1;
+		else if (cmp > 0)
+			right = mid - 1;
+		else
+			return element;
+	}
+
+	return NULL;
+}
+
+#endif /* ST_SEARCH */
+
+#ifdef ST_UNIQUE
+
+/*
+ * Remove duplicates from an array.  Return the new size.
+ */
+ST_SCOPE size_t
+ST_UNIQUE(ST_ELEMENT_TYPE *array,
+		  size_t n
+		  ST_SORT_PROTO_ELEMENT_SIZE
+		  ST_SORT_PROTO_COMPARE
+		  ST_SORT_PROTO_ARG)
+{
+	size_t		i,
+				j;
+
+	if (n <= 1)
+		return n;
+
+	for (i = 1, j = 0; i < n; ++i)
+	{
+		if (DO_COMPARE(&array[i], &array[j]) != 0 && ++j != i)
+			array[j] = array[i];
+	}
+
+	return j + 1;
+}
+
+#endif /* ST_UNIQUE */
+
+#endif /* ST_DEFINE */
 
 #undef DO_CHECK_FOR_INTERRUPTS
 #undef DO_COMPARE
@@ -411,6 +514,7 @@ loop:
 #undef ST_COMPARE
 #undef ST_COMPARE_ARG_TYPE
 #undef ST_COMPARE_RUNTIME_POINTER
+#undef ST_COMPARE_TYPE
 #undef ST_ELEMENT_TYPE
 #undef ST_ELEMENT_TYPE_VOID
 #undef ST_MAKE_NAME
@@ -420,6 +524,7 @@ loop:
 #undef ST_POINTER_STEP
 #undef ST_POINTER_TYPE
 #undef ST_SCOPE
+#undef ST_SEARCH
 #undef ST_SORT
 #undef ST_SORT_INVOKE_ARG
 #undef ST_SORT_INVOKE_COMPARE
@@ -429,3 +534,4 @@ loop:
 #undef ST_SORT_PROTO_ELEMENT_SIZE
 #undef ST_SWAP
 #undef ST_SWAPN
+#undef ST_UNIQUE
-- 
2.30.1

From 9a0cb8be6e3146d9cde39c4d9291bf3990604823 Mon Sep 17 00:00:00 2001
From: Thomas Munro <[email-masked]>
Date: Sun, 14 Mar 2021 10:00:25 +1300
Subject: [PATCH 2/9] Supply sort/search specializations for common scalar
 types.

---
 src/backend/utils/sort/Makefile     |  1 +
 src/backend/utils/sort/sortscalar.c | 11 +++++++++++
 src/include/utils/sortscalar.h      | 26 ++++++++++++++++++++++++++
 3 files changed, 38 insertions(+)
 create mode 100644 src/backend/utils/sort/sortscalar.c
 create mode 100644 src/include/utils/sortscalar.h

diff --git a/src/backend/utils/sort/Makefile b/src/backend/utils/sort/Makefile
index 26f65fcaf7..b4dce08614 100644
--- a/src/backend/utils/sort/Makefile
+++ b/src/backend/utils/sort/Makefile
@@ -17,6 +17,7 @@ override CPPFLAGS := -I. -I$(srcdir) $(CPPFLAGS)
 OBJS = \
 	logtape.o \
 	sharedtuplestore.o \
+	sortscalar.o \
 	sortsupport.o \
 	tuplesort.o \
 	tuplestore.o
diff --git a/src/backend/utils/sort/sortscalar.c b/src/backend/utils/sort/sortscalar.c
new file mode 100644
index 0000000000..026e472a1d
--- /dev/null
+++ b/src/backend/utils/sort/sortscalar.c
@@ -0,0 +1,11 @@
+#include "postgres.h"
+
+#include "utils/sortscalar.h"
+
+#define ST_SORT qsort_uint32
+#define ST_ELEMENT_TYPE uint32
+#define ST_COMPARE(a, b) (((int64) *(a)) - ((int64) *(b)))
+#define ST_COMPARE_TYPE int64
+#define ST_SCOPE
+#define ST_DEFINE
+#include "lib/sort_template.h"
diff --git a/src/include/utils/sortscalar.h b/src/include/utils/sortscalar.h
new file mode 100644
index 0000000000..932fe29d42
--- /dev/null
+++ b/src/include/utils/sortscalar.h
@@ -0,0 +1,26 @@
+#ifndef SORTSCALAR_H
+#define SORTSCALAR_H
+
+/* We'll define the sort functions in sortscalar.c (they'd better match). */
+extern void qsort_uint32(uint32 *array, size_t n);
+
+/* The unique and search functions are defined here so they can be inlined. */
+#define ST_UNIQUE unique_uint32
+#define ST_SEARCH bsearch_uint32
+#define ST_ELEMENT_TYPE uint32
+#define ST_COMPARE(a, b) (((int64) *(a)) - ((int64) *(b)))
+#define ST_COMPARE_TYPE int64
+#define ST_SCOPE static inline
+#define ST_DEFINE
+#include "lib/sort_template.h"
+
+/* Provide names for other common types that are currently uint32. */
+#define qsort_oid			qsort_uint32
+#define unique_oid			unique_uint32
+#define bsearch_oid			bsearch_uint32
+
+#define qsort_blocknum		qsort_uint32
+#define unique_blocknum		unique_uint32
+#define bsearch_blocknum	bsearch_uint32
+
+#endif
-- 
2.30.1

From 441563a698a7af06dfb71d0eca1283a1ca7a7cf1 Mon Sep 17 00:00:00 2001
From: Thomas Munro <[email-masked]>
Date: Sun, 14 Mar 2021 11:40:01 +1300
Subject: [PATCH 3/9] Use qsort_oid() and friends in obvious places.

Done mainly for notational advantage over traditional qsort()/bsearch().
There may be some speedup, from inlined branchless comparators.
---
 src/backend/access/nbtree/nbtinsert.c   | 30 +++++--------------------
 src/backend/catalog/pg_enum.c           |  3 ++-
 src/backend/catalog/pg_inherits.c       |  3 ++-
 src/backend/commands/subscriptioncmds.c | 15 ++++++-------
 src/backend/utils/adt/acl.c             |  5 +++--
 src/backend/utils/cache/syscache.c      | 30 +++++--------------------
 6 files changed, 24 insertions(+), 62 deletions(-)

diff --git a/src/backend/access/nbtree/nbtinsert.c b/src/backend/access/nbtree/nbtinsert.c
index 0bc86943eb..09abf342de 100644
--- a/src/backend/access/nbtree/nbtinsert.c
+++ b/src/backend/access/nbtree/nbtinsert.c
@@ -19,11 +19,11 @@
 #include "access/nbtxlog.h"
 #include "access/transam.h"
 #include "access/xloginsert.h"
-#include "lib/qunique.h"
 #include "miscadmin.h"
 #include "storage/lmgr.h"
 #include "storage/predicate.h"
 #include "storage/smgr.h"
+#include "utils/sortscalar.h"
 
 /* Minimum tree height for application of fastpath optimization */
 #define BTREE_FASTPATH_MIN_LEVEL	2
@@ -70,7 +70,6 @@ static void _bt_simpledel_pass(Relation rel, Buffer buffer, Relation heapRel,
 static BlockNumber *_bt_deadblocks(Page page, OffsetNumber *deletable,
 								   int ndeletable, IndexTuple newitem,
 								   int *nblocks);
-static inline int _bt_blk_cmp(const void *arg1, const void *arg2);
 
 /*
  *	_bt_doinsert() -- Handle insertion of a single index tuple in the tree.
@@ -2814,8 +2813,7 @@ _bt_simpledel_pass(Relation rel, Buffer buffer, Relation heapRel,
 		if (!BTreeTupleIsPosting(itup))
 		{
 			tidblock = ItemPointerGetBlockNumber(&itup->t_tid);
-			match = bsearch(&tidblock, deadblocks, ndeadblocks,
-							sizeof(BlockNumber), _bt_blk_cmp);
+			match = bsearch_blocknum(&tidblock, deadblocks, ndeadblocks);
 
 			if (!match)
 			{
@@ -2845,8 +2843,7 @@ _bt_simpledel_pass(Relation rel, Buffer buffer, Relation heapRel,
 				ItemPointer tid = BTreeTupleGetPostingN(itup, p);
 
 				tidblock = ItemPointerGetBlockNumber(tid);
-				match = bsearch(&tidblock, deadblocks, ndeadblocks,
-								sizeof(BlockNumber), _bt_blk_cmp);
+				match = bsearch_blocknum(&tidblock, deadblocks, ndeadblocks);
 
 				if (!match)
 				{
@@ -2966,25 +2963,8 @@ _bt_deadblocks(Page page, OffsetNumber *deletable, int ndeletable,
 		}
 	}
 
-	qsort(tidblocks, ntids, sizeof(BlockNumber), _bt_blk_cmp);
-	*nblocks = qunique(tidblocks, ntids, sizeof(BlockNumber), _bt_blk_cmp);
+	qsort_blocknum(tidblocks, ntids);
+	*nblocks = unique_blocknum(tidblocks, ntids);
 
 	return tidblocks;
 }
-
-/*
- * _bt_blk_cmp() -- qsort comparison function for _bt_simpledel_pass
- */
-static inline int
-_bt_blk_cmp(const void *arg1, const void *arg2)
-{
-	BlockNumber b1 = *((BlockNumber *) arg1);
-	BlockNumber b2 = *((BlockNumber *) arg2);
-
-	if (b1 < b2)
-		return -1;
-	else if (b1 > b2)
-		return 1;
-
-	return 0;
-}
diff --git a/src/backend/catalog/pg_enum.c b/src/backend/catalog/pg_enum.c
index f958f1541d..1d9dacb516 100644
--- a/src/backend/catalog/pg_enum.c
+++ b/src/backend/catalog/pg_enum.c
@@ -30,6 +30,7 @@
 #include "utils/fmgroids.h"
 #include "utils/hsearch.h"
 #include "utils/memutils.h"
+#include "utils/sortscalar.h"
 #include "utils/syscache.h"
 
 /* Potentially set by pg_upgrade_support functions */
@@ -108,7 +109,7 @@ EnumValuesCreate(Oid enumTypeOid, List *vals)
 	}
 
 	/* sort them, just in case OID counter wrapped from high to low */
-	qsort(oids, num_elems, sizeof(Oid), oid_cmp);
+	qsort_oid(oids, num_elems);
 
 	/* and make the entries */
 	memset(nulls, false, sizeof(nulls));
diff --git a/src/backend/catalog/pg_inherits.c b/src/backend/catalog/pg_inherits.c
index 5ab7902827..5cf76b2cad 100644
--- a/src/backend/catalog/pg_inherits.c
+++ b/src/backend/catalog/pg_inherits.c
@@ -29,6 +29,7 @@
 #include "utils/builtins.h"
 #include "utils/fmgroids.h"
 #include "utils/memutils.h"
+#include "utils/sortscalar.h"
 #include "utils/syscache.h"
 
 /*
@@ -111,7 +112,7 @@ find_inheritance_children(Oid parentrelId, LOCKMODE lockmode)
 	 * lock children in the same order to avoid needless deadlocks.
 	 */
 	if (numoids > 1)
-		qsort(oidarr, numoids, sizeof(Oid), oid_cmp);
+		qsort_oid(oidarr, numoids);
 
 	/*
 	 * Acquire locks and build the result list.
diff --git a/src/backend/commands/subscriptioncmds.c b/src/backend/commands/subscriptioncmds.c
index bfd3514546..a24db5dca8 100644
--- a/src/backend/commands/subscriptioncmds.c
+++ b/src/backend/commands/subscriptioncmds.c
@@ -44,6 +44,7 @@
 #include "utils/guc.h"
 #include "utils/lsyscache.h"
 #include "utils/memutils.h"
+#include "utils/sortscalar.h"
 #include "utils/syscache.h"
 
 static List *fetch_table_list(WalReceiverConn *wrconn, List *publications);
@@ -608,8 +609,7 @@ AlterSubscription_refresh(Subscription *sub, bool copy_data)
 
 			subrel_local_oids[off++] = relstate->relid;
 		}
-		qsort(subrel_local_oids, list_length(subrel_states),
-			  sizeof(Oid), oid_cmp);
+		qsort_oid(subrel_local_oids, list_length(subrel_states));
 
 		/*
 		 * Rels that we want to remove from subscription and drop any slots
@@ -640,8 +640,8 @@ AlterSubscription_refresh(Subscription *sub, bool copy_data)
 
 			pubrel_local_oids[off++] = relid;
 
-			if (!bsearch(&relid, subrel_local_oids,
-						 list_length(subrel_states), sizeof(Oid), oid_cmp))
+			if (!bsearch_oid(&relid, subrel_local_oids,
+							 list_length(subrel_states)))
 			{
 				AddSubscriptionRelState(sub->oid, relid,
 										copy_data ? SUBREL_STATE_INIT : SUBREL_STATE_READY,
@@ -656,16 +656,15 @@ AlterSubscription_refresh(Subscription *sub, bool copy_data)
 		 * Next remove state for tables we should not care about anymore using
 		 * the data we collected above
 		 */
-		qsort(pubrel_local_oids, list_length(pubrel_names),
-			  sizeof(Oid), oid_cmp);
+		qsort_oid(pubrel_local_oids, list_length(pubrel_names));
 
 		remove_rel_len = 0;
 		for (off = 0; off < list_length(subrel_states); off++)
 		{
 			Oid			relid = subrel_local_oids[off];
 
-			if (!bsearch(&relid, pubrel_local_oids,
-						 list_length(pubrel_names), sizeof(Oid), oid_cmp))
+			if (!bsearch_oid(&relid, pubrel_local_oids,
+							 list_length(pubrel_names)))
 			{
 				char		state;
 				XLogRecPtr	statelsn;
diff --git a/src/backend/utils/adt/acl.c b/src/backend/utils/adt/acl.c
index c7f029e218..2b90ee4c88 100644
--- a/src/backend/utils/adt/acl.c
+++ b/src/backend/utils/adt/acl.c
@@ -38,6 +38,7 @@
 #include "utils/inval.h"
 #include "utils/lsyscache.h"
 #include "utils/memutils.h"
+#include "utils/sortscalar.h"
 #include "utils/syscache.h"
 #include "utils/varlena.h"
 
@@ -1496,7 +1497,7 @@ aclmembers(const Acl *acl, Oid **roleids)
 	}
 
 	/* Sort the array */
-	qsort(list, j, sizeof(Oid), oid_cmp);
+	qsort_oid(list, j);
 
 	/*
 	 * We could repalloc the array down to minimum size, but it's hardly worth
@@ -1505,7 +1506,7 @@ aclmembers(const Acl *acl, Oid **roleids)
 	*roleids = list;
 
 	/* Remove duplicates from the array */
-	return qunique(list, j, sizeof(Oid), oid_cmp);
+	return unique_oid(list, j);
 }

diff --git a/src/backend/utils/cache/syscache.c b/src/backend/utils/cache/syscache.c
index e4dc4ee34e..26ef27b50d 100644
--- a/src/backend/utils/cache/syscache.c
+++ b/src/backend/utils/cache/syscache.c
@@ -76,6 +76,7 @@
 #include "lib/qunique.h"
 #include "utils/catcache.h"
 #include "utils/rel.h"
+#include "utils/sortscalar.h"
 #include "utils/syscache.h"
 
 /*---------------------------------------------------------------------------
@@ -1006,8 +1007,6 @@ static int	SysCacheRelationOidSize;
 static Oid	SysCacheSupportingRelOid[SysCacheSize * 2];
 static int	SysCacheSupportingRelOidSize;
 
-static int	oid_compare(const void *a, const void *b);
-
 
 /*
  * InitCatalogCache - initialize the caches
@@ -1055,17 +1054,13 @@ InitCatalogCache(void)
 	Assert(SysCacheSupportingRelOidSize <= lengthof(SysCacheSupportingRelOid));
 
 	/* Sort and de-dup OID arrays, so we can use binary search. */
-	pg_qsort(SysCacheRelationOid, SysCacheRelationOidSize,
-			 sizeof(Oid), oid_compare);
+	qsort_oid(SysCacheRelationOid, SysCacheRelationOidSize);
 	SysCacheRelationOidSize =
-		qunique(SysCacheRelationOid, SysCacheRelationOidSize, sizeof(Oid),
-				oid_compare);
+		unique_oid(SysCacheRelationOid, SysCacheRelationOidSize);
 
-	pg_qsort(SysCacheSupportingRelOid, SysCacheSupportingRelOidSize,
-			 sizeof(Oid), oid_compare);
+	qsort_oid(SysCacheSupportingRelOid, SysCacheSupportingRelOidSize);
 	SysCacheSupportingRelOidSize =
-		qunique(SysCacheSupportingRelOid, SysCacheSupportingRelOidSize,
-				sizeof(Oid), oid_compare);
+		unique_oid(SysCacheSupportingRelOid, SysCacheSupportingRelOidSize);
 
 	CacheInitialized = true;
 }
@@ -1548,18 +1543,3 @@ RelationSupportsSysCache(Oid relid)
 
 	return false;
 }
-
-
-/*
- * OID comparator for pg_qsort
- */
-static int
-oid_compare(const void *a, const void *b)
-{
-	Oid			oa = *((const Oid *) a);
-	Oid			ob = *((const Oid *) b);
-
-	if (oa == ob)
-		return 0;
-	return (oa > ob) ? 1 : -1;
-}
-- 
2.30.1

From 7e6091ee0163e0c49abcf99952c493c05baaaab7 Mon Sep 17 00:00:00 2001
From: Thomas Munro <[email-masked]>
Date: Sun, 14 Mar 2021 15:11:22 +1300
Subject: [PATCH 4/9] Supply specialized sort/search routines for ItemPtrData.

---
 src/backend/utils/sort/Makefile      |  1 +
 src/backend/utils/sort/sortitemptr.c | 12 ++++++++++++
 src/include/utils/sortitemptr.h      | 19 +++++++++++++++++++
 3 files changed, 32 insertions(+)
 create mode 100644 src/backend/utils/sort/sortitemptr.c
 create mode 100644 src/include/utils/sortitemptr.h

diff --git a/src/backend/utils/sort/Makefile b/src/backend/utils/sort/Makefile
index b4dce08614..32acbb7f20 100644
--- a/src/backend/utils/sort/Makefile
+++ b/src/backend/utils/sort/Makefile
@@ -17,6 +17,7 @@ override CPPFLAGS := -I. -I$(srcdir) $(CPPFLAGS)
 OBJS = \
 	logtape.o \
 	sharedtuplestore.o \
+	sortitemptr.o \
 	sortscalar.o \
 	sortsupport.o \
 	tuplesort.o \
diff --git a/src/backend/utils/sort/sortitemptr.c b/src/backend/utils/sort/sortitemptr.c
new file mode 100644
index 0000000000..a0db6d6d0d
--- /dev/null
+++ b/src/backend/utils/sort/sortitemptr.c
@@ -0,0 +1,12 @@
+#include "postgres.h"
+
+#include "catalog/index.h"
+#include "utils/sortitemptr.h"
+
+#define ST_SORT qsort_itemptr
+#define ST_SCOPE
+#define ST_ELEMENT_TYPE ItemPointerData
+#define ST_COMPARE(a, b) (itemptr_encode(a) - itemptr_encode(b))
+#define ST_COMPARE_TYPE int64
+#define ST_DEFINE
+#include "lib/sort_template.h"
diff --git a/src/include/utils/sortitemptr.h b/src/include/utils/sortitemptr.h
new file mode 100644
index 0000000000..eb3df25eec
--- /dev/null
+++ b/src/include/utils/sortitemptr.h
@@ -0,0 +1,19 @@
+#ifndef SORTITEMPTR_H
+#define SORTITEMPTR_H
+
+#include "catalog/index.h"
+
+/* Declare sort function, from .c file. */
+extern void qsort_itemptr(ItemPointerData *tids, size_t n);
+
+/* Search and unique functions inline in header. */
+#define ST_SEARCH bsearch_itemptr
+#define ST_UNIQUE unique_itemptr
+#define ST_ELEMENT_TYPE ItemPointerData
+#define ST_COMPARE(a, b) (itemptr_encode(a) - itemptr_encode(b))
+#define ST_COMPARE_TYPE int64
+#define ST_SCOPE static inline
+#define ST_DEFINE
+#include "lib/sort_template.h"
+
+#endif
-- 
2.30.1

From eed4a91d7742166124c26dbdadd41aa4695cc5b8 Mon Sep 17 00:00:00 2001
From: Thomas Munro <[email-masked]>
Date: Sat, 13 Mar 2021 18:48:10 +1300
Subject: [PATCH 5/9] Use qsort_itemptr() and friends in various places.

---
 src/backend/access/heap/vacuumlazy.c | 40 +++-------------------------
 src/backend/executor/nodeTidscan.c   | 32 +++-------------------
 2 files changed, 7 insertions(+), 65 deletions(-)

diff --git a/src/backend/access/heap/vacuumlazy.c b/src/backend/access/heap/vacuumlazy.c
index a65dcbebfa..ef57e88b43 100644
--- a/src/backend/access/heap/vacuumlazy.c
+++ b/src/backend/access/heap/vacuumlazy.c
@@ -79,6 +79,7 @@
 #include "utils/lsyscache.h"
 #include "utils/memutils.h"
 #include "utils/pg_rusage.h"
+#include "utils/sortitemptr.h"
 #include "utils/timestamp.h"

@@ -367,7 +368,6 @@ static void lazy_space_alloc(LVRelStats *vacrelstats, BlockNumber relblocks);
 static void lazy_record_dead_tuple(LVDeadTuples *dead_tuples,
 								   ItemPointer itemptr);
 static bool lazy_tid_reaped(ItemPointer itemptr, void *state);
-static int	vac_cmp_itemptr(const void *left, const void *right);
 static bool heap_page_is_all_visible(Relation rel, Buffer buf,
 									 LVRelStats *vacrelstats,
 									 TransactionId *visibility_cutoff_xid, bool *all_frozen);
@@ -2943,45 +2943,13 @@ lazy_tid_reaped(ItemPointer itemptr, void *state)
 	if (item < litem || item > ritem)
 		return false;
 
-	res = (ItemPointer) bsearch((void *) itemptr,
-								(void *) dead_tuples->itemptrs,
-								dead_tuples->num_tuples,
-								sizeof(ItemPointerData),
-								vac_cmp_itemptr);
+	res = bsearch_itemptr(itemptr,
+						  dead_tuples->itemptrs,
+						  dead_tuples->num_tuples);
 
 	return (res != NULL);
 }
 
-/*
- * Comparator routines for use with qsort() and bsearch().
- */
-static int
-vac_cmp_itemptr(const void *left, const void *right)
-{
-	BlockNumber lblk,
-				rblk;
-	OffsetNumber loff,
-				roff;
-
-	lblk = ItemPointerGetBlockNumber((ItemPointer) left);
-	rblk = ItemPointerGetBlockNumber((ItemPointer) right);
-
-	if (lblk < rblk)
-		return -1;
-	if (lblk > rblk)
-		return 1;
-
-	loff = ItemPointerGetOffsetNumber((ItemPointer) left);
-	roff = ItemPointerGetOffsetNumber((ItemPointer) right);
-
-	if (loff < roff)
-		return -1;
-	if (loff > roff)
-		return 1;
-
-	return 0;
-}
-
 /*
  * Check if every tuple in the given page is visible to all current and future
  * transactions. Also return the visibility_cutoff_xid which is the highest
diff --git a/src/backend/executor/nodeTidscan.c b/src/backend/executor/nodeTidscan.c
index 48c3737da2..ee6bc4ee05 100644
--- a/src/backend/executor/nodeTidscan.c
+++ b/src/backend/executor/nodeTidscan.c
@@ -33,6 +33,7 @@
 #include "storage/bufmgr.h"
 #include "utils/array.h"
 #include "utils/rel.h"
+#include "utils/sortitemptr.h"

 #define IsCTIDVar(node)  \
@@ -51,7 +52,6 @@ typedef struct TidExpr
 
 static void TidExprListCreate(TidScanState *tidstate);
 static void TidListEval(TidScanState *tidstate);
-static int	itemptr_comparator(const void *a, const void *b);
 static TupleTableSlot *TidNext(TidScanState *node);

@@ -263,10 +263,8 @@ TidListEval(TidScanState *tidstate)
 		/* CurrentOfExpr could never appear OR'd with something else */
 		Assert(!tidstate->tss_isCurrentOf);
 
-		qsort((void *) tidList, numTids, sizeof(ItemPointerData),
-			  itemptr_comparator);
-		numTids = qunique(tidList, numTids, sizeof(ItemPointerData),
-						  itemptr_comparator);
+		qsort_itemptr(tidList, numTids);
+		numTids = unique_itemptr(tidList, numTids);
 	}
 
 	tidstate->tss_TidList = tidList;
@@ -274,30 +272,6 @@ TidListEval(TidScanState *tidstate)
 	tidstate->tss_TidPtr = -1;
 }
 
-/*
- * qsort comparator for ItemPointerData items
- */
-static int
-itemptr_comparator(const void *a, const void *b)
-{
-	const ItemPointerData *ipa = (const ItemPointerData *) a;
-	const ItemPointerData *ipb = (const ItemPointerData *) b;
-	BlockNumber ba = ItemPointerGetBlockNumber(ipa);
-	BlockNumber bb = ItemPointerGetBlockNumber(ipb);
-	OffsetNumber oa = ItemPointerGetOffsetNumber(ipa);
-	OffsetNumber ob = ItemPointerGetOffsetNumber(ipb);
-
-	if (ba < bb)
-		return -1;
-	if (ba > bb)
-		return 1;
-	if (oa < ob)
-		return -1;
-	if (oa > ob)
-		return 1;
-	return 0;
-}
-
 /* ----------------------------------------------------------------
  *		TidNext
  *
-- 
2.30.1

From 50bb6dfb24fb68559c87ce4e2785c9a65be9a674 Mon Sep 17 00:00:00 2001
From: Thomas Munro <[email-masked]>
Date: Sat, 13 Mar 2021 17:30:56 +1300
Subject: [PATCH 6/9] Specialize the HeapTuple sort routine for ANALYZE.

Instead of a branching comparator, use "encoded" format, based on 48 bit
integers that can be compared by subtraction.
---
 src/backend/commands/analyze.c | 36 +++++++++-------------------------
 1 file changed, 9 insertions(+), 27 deletions(-)

diff --git a/src/backend/commands/analyze.c b/src/backend/commands/analyze.c
index 3a9f358dd4..e760821ef5 100644
--- a/src/backend/commands/analyze.c
+++ b/src/backend/commands/analyze.c
@@ -98,7 +98,6 @@ static VacAttrStats *examine_attribute(Relation onerel, int attnum,
 static int	acquire_sample_rows(Relation onerel, int elevel,
 								HeapTuple *rows, int targrows,
 								double *totalrows, double *totaldeadrows);
-static int	compare_rows(const void *a, const void *b);
 static int	acquire_inherited_sample_rows(Relation onerel, int elevel,
 										  HeapTuple *rows, int targrows,
 										  double *totalrows, double *totaldeadrows);
@@ -998,6 +997,14 @@ examine_attribute(Relation onerel, int attnum, Node *index_expr)
 	return stats;
 }
 
+#define ST_SORT sort_heaptuples_by_tid
+#define ST_ELEMENT_TYPE HeapTuple
+#define ST_COMPARE(a, b) (itemptr_encode(&((*a)->t_self)) - itemptr_encode(&((*b)->t_self)))
+#define ST_COMPARE_TYPE int64
+#define ST_SCOPE static
+#define ST_DEFINE
+#include "lib/sort_template.h"
+
 /*
  * acquire_sample_rows -- acquire a random sample of rows from the table
  *
@@ -1141,7 +1148,7 @@ acquire_sample_rows(Relation onerel, int elevel,
 	 * tuples are already sorted.
 	 */
 	if (numrows == targrows)
-		qsort((void *) rows, numrows, sizeof(HeapTuple), compare_rows);
+		sort_heaptuples_by_tid(rows, numrows);
 
 	/*
 	 * Estimate total numbers of live and dead rows in relation, extrapolating
@@ -1176,31 +1183,6 @@ acquire_sample_rows(Relation onerel, int elevel,
 	return numrows;
 }
 
-/*
- * qsort comparator for sorting rows[] array
- */
-static int
-compare_rows(const void *a, const void *b)
-{
-	HeapTuple	ha = *(const HeapTuple *) a;
-	HeapTuple	hb = *(const HeapTuple *) b;
-	BlockNumber ba = ItemPointerGetBlockNumber(&ha->t_self);
-	OffsetNumber oa = ItemPointerGetOffsetNumber(&ha->t_self);
-	BlockNumber bb = ItemPointerGetBlockNumber(&hb->t_self);
-	OffsetNumber ob = ItemPointerGetOffsetNumber(&hb->t_self);
-
-	if (ba < bb)
-		return -1;
-	if (ba > bb)
-		return 1;
-	if (oa < ob)
-		return -1;
-	if (oa > ob)
-		return 1;
-	return 0;
-}
-
-
 /*
  * acquire_inherited_sample_rows -- acquire sample rows from inheritance tree
  *
-- 
2.30.1

From 2352ce2f93fe8b9f9f597ef5ffc6a87468d769ac Mon Sep 17 00:00:00 2001
From: Thomas Munro <[email-masked]>
Date: Sun, 14 Mar 2021 13:48:14 +1300
Subject: [PATCH 7/9] Specialize pagetable sort routines in tidbitmap.c.

Provide slightly more efficient routines for sorting the page table.
---
 src/backend/nodes/tidbitmap.c | 73 +++++++++++++----------------------
 1 file changed, 27 insertions(+), 46 deletions(-)

diff --git a/src/backend/nodes/tidbitmap.c b/src/backend/nodes/tidbitmap.c
index c5feacbff4..86d9ff0499 100644
--- a/src/backend/nodes/tidbitmap.c
+++ b/src/backend/nodes/tidbitmap.c
@@ -234,9 +234,6 @@ static PagetableEntry *tbm_get_pageentry(TIDBitmap *tbm, BlockNumber pageno);
 static bool tbm_page_is_lossy(const TIDBitmap *tbm, BlockNumber pageno);
 static void tbm_mark_page_lossy(TIDBitmap *tbm, BlockNumber pageno);
 static void tbm_lossify(TIDBitmap *tbm);
-static int	tbm_comparator(const void *left, const void *right);
-static int	tbm_shared_comparator(const void *left, const void *right,
-								  void *arg);
 
 /* define hashtable mapping block numbers to PagetableEntry's */
 #define SH_USE_NONDEFAULT_ALLOCATOR
@@ -671,6 +668,29 @@ tbm_is_empty(const TIDBitmap *tbm)
 	return (tbm->nentries == 0);
 }
 
+/* An inline sort function to sort PagetableEntry pointers by block. */
+#define ST_SORT qsort_pagetable
+#define ST_ELEMENT_TYPE PagetableEntry *
+#define ST_COMPARE(a, b) (((int64) (*(a))->blockno) - (((int64) (*(b))->blockno)))
+#define ST_COMPARE_TYPE int64
+#define ST_SCOPE static
+#define ST_DEFINE
+#include "lib/sort_template.h"
+
+/*
+ * As above, but this will get index into PagetableEntry array.  Therefore,
+ * it needs to get actual PagetableEntry using the index before comparing the
+ * blockno.
+ */
+#define ST_SORT qsort_pagetable_shared
+#define ST_ELEMENT_TYPE int
+#define ST_COMPARE(a, b, base) ((int64) (base)[*(a)].blockno - ((int64) (base)[*(b)].blockno))
+#define ST_COMPARE_ARG_TYPE PagetableEntry
+#define ST_COMPARE_TYPE int64
+#define ST_SCOPE static
+#define ST_DEFINE
+#include "lib/sort_template.h"
+
 /*
  * tbm_begin_iterate - prepare to iterate through a TIDBitmap
  *
@@ -740,11 +760,9 @@ tbm_begin_iterate(TIDBitmap *tbm)
 		Assert(npages == tbm->npages);
 		Assert(nchunks == tbm->nchunks);
 		if (npages > 1)
-			qsort(tbm->spages, npages, sizeof(PagetableEntry *),
-				  tbm_comparator);
+			qsort_pagetable(tbm->spages, npages);
 		if (nchunks > 1)
-			qsort(tbm->schunks, nchunks, sizeof(PagetableEntry *),
-				  tbm_comparator);
+			qsort_pagetable(tbm->schunks, nchunks);
 	}
 
 	tbm->iterating = TBM_ITERATING_PRIVATE;
@@ -853,11 +871,9 @@ tbm_prepare_shared_iterate(TIDBitmap *tbm)
 		if (ptbase != NULL)
 			pg_atomic_init_u32(&ptbase->refcount, 0);
 		if (npages > 1)
-			qsort_arg((void *) (ptpages->index), npages, sizeof(int),
-					  tbm_shared_comparator, (void *) ptbase->ptentry);
+			qsort_pagetable_shared(ptpages->index, npages, ptbase->ptentry);
 		if (nchunks > 1)
-			qsort_arg((void *) (ptchunks->index), nchunks, sizeof(int),
-					  tbm_shared_comparator, (void *) ptbase->ptentry);
+			qsort_pagetable_shared(ptchunks->index, nchunks, ptbase->ptentry);
 	}
 
 	/*
@@ -1416,41 +1432,6 @@ tbm_lossify(TIDBitmap *tbm)
 		tbm->maxentries = Min(tbm->nentries, (INT_MAX - 1) / 2) * 2;
 }
 
-/*
- * qsort comparator to handle PagetableEntry pointers.
- */
-static int
-tbm_comparator(const void *left, const void *right)
-{
-	BlockNumber l = (*((PagetableEntry *const *) left))->blockno;
-	BlockNumber r = (*((PagetableEntry *const *) right))->blockno;
-
-	if (l < r)
-		return -1;
-	else if (l > r)
-		return 1;
-	return 0;
-}
-
-/*
- * As above, but this will get index into PagetableEntry array.  Therefore,
- * it needs to get actual PagetableEntry using the index before comparing the
- * blockno.
- */
-static int
-tbm_shared_comparator(const void *left, const void *right, void *arg)
-{
-	PagetableEntry *base = (PagetableEntry *) arg;
-	PagetableEntry *lpage = &base[*(int *) left];
-	PagetableEntry *rpage = &base[*(int *) right];
-
-	if (lpage->blockno < rpage->blockno)
-		return -1;
-	else if (lpage->blockno > rpage->blockno)
-		return 1;
-	return 0;
-}
-
 /*
  *	tbm_attach_shared_iterate
  *
-- 
2.30.1

From 2a5676c8b79449bb563d3aa7a489310926e14f25 Mon Sep 17 00:00:00 2001
From: Thomas Munro <[email-masked]>
Date: Sun, 14 Mar 2021 11:02:40 +1300
Subject: [PATCH 8/9] Specialize some sort/search routines in nbtree code.

---
 src/backend/access/nbtree/nbtpage.c  | 29 ++++--------
 src/backend/access/nbtree/nbtutils.c | 68 ++++++++++++++++------------
 2 files changed, 48 insertions(+), 49 deletions(-)

diff --git a/src/backend/access/nbtree/nbtpage.c b/src/backend/access/nbtree/nbtpage.c
index fc744cf9fd..78e04a3e9a 100644
--- a/src/backend/access/nbtree/nbtpage.c
+++ b/src/backend/access/nbtree/nbtpage.c
@@ -1468,24 +1468,16 @@ _bt_delitems_update(BTVacuumPosting *updatable, int nupdatable,
 }
 
 /*
- * Comparator used by _bt_delitems_delete_check() to restore deltids array
- * back to its original leaf-page-wise sort order
+ * Sort used by _bt_delitems_delete_check() to restore deltids array back to
+ * its original leaf-page-wise sort order.  We can safely use a branchless
+ * int-based comparator expression because id is an int16.
  */
-static int
-_bt_delitems_cmp(const void *a, const void *b)
-{
-	TM_IndexDelete *indexdelete1 = (TM_IndexDelete *) a;
-	TM_IndexDelete *indexdelete2 = (TM_IndexDelete *) b;
-
-	if (indexdelete1->id > indexdelete2->id)
-		return 1;
-	if (indexdelete1->id < indexdelete2->id)
-		return -1;
-
-	Assert(false);
-
-	return 0;
-}
+#define ST_SORT qsort_delitems
+#define ST_ELEMENT_TYPE TM_IndexDelete
+#define ST_COMPARE(a, b) ((int) (a)->id - (int) (b)->id)
+#define ST_SCOPE static
+#define ST_DEFINE
+#include "lib/sort_template.h"
 
 /*
  * Try to delete item(s) from a btree leaf page during single-page cleanup.
@@ -1555,8 +1547,7 @@ _bt_delitems_delete_check(Relation rel, Buffer buf, Relation heapRel,
 	 * no entries at all (with bottom-up deletion caller), in which case there
 	 * is nothing left to do.
 	 */
-	qsort(delstate->deltids, delstate->ndeltids, sizeof(TM_IndexDelete),
-		  _bt_delitems_cmp);
+	qsort_delitems(delstate->deltids, delstate->ndeltids);
 	if (delstate->ndeltids == 0)
 	{
 		Assert(delstate->bottomup);
diff --git a/src/backend/access/nbtree/nbtutils.c b/src/backend/access/nbtree/nbtutils.c
index d524310723..3012d9f702 100644
--- a/src/backend/access/nbtree/nbtutils.c
+++ b/src/backend/access/nbtree/nbtutils.c
@@ -22,7 +22,6 @@
 #include "access/relscan.h"
 #include "catalog/catalog.h"
 #include "commands/progress.h"
-#include "lib/qunique.h"
 #include "miscadmin.h"
 #include "utils/array.h"
 #include "utils/datum.h"
@@ -35,7 +34,6 @@ typedef struct BTSortArrayContext
 {
 	FmgrInfo	flinfo;
 	Oid			collation;
-	bool		reverse;
 } BTSortArrayContext;
 
 static Datum _bt_find_extreme_element(IndexScanDesc scan, ScanKey skey,
@@ -44,7 +42,6 @@ static Datum _bt_find_extreme_element(IndexScanDesc scan, ScanKey skey,
 static int	_bt_sort_array_elements(IndexScanDesc scan, ScanKey skey,
 									bool reverse,
 									Datum *elems, int nelems);
-static int	_bt_compare_array_elements(const void *a, const void *b, void *arg);
 static bool _bt_compare_scankey_args(IndexScanDesc scan, ScanKey op,
 									 ScanKey leftarg, ScanKey rightarg,
 									 bool *result);
@@ -429,6 +426,33 @@ _bt_find_extreme_element(IndexScanDesc scan, ScanKey skey,
 	return result;
 }
 
+/* Define a specialized sort function for _bt_sort_array_elements. */
+#define ST_SORT qsort_bt_array_elements
+#define ST_UNIQUE unique_bt_array_elements
+#define ST_ELEMENT_TYPE Datum
+#define ST_COMPARE(a, b, cxt) \
+	DatumGetInt32(FunctionCall2Coll(&cxt->flinfo, cxt->collation, *a, *b))
+#define ST_COMPARE_ARG_TYPE BTSortArrayContext
+#define ST_SCOPE static
+#define ST_DEFINE
+#include "lib/sort_template.h"
+
+/*
+ * Define a reverse sort function for _bt_sort_array_elements.  Note use of
+ * int64 comparator expression, so that we can safely invert even INT_MIN with
+ * simple substraction from zero.
+ */
+#define ST_SORT qsort_bt_array_elements_reverse
+#define ST_UNIQUE unique_bt_array_elements_reverse
+#define ST_ELEMENT_TYPE Datum
+#define ST_COMPARE(a, b, cxt) \
+	(0 - (DatumGetInt32(FunctionCall2Coll(&cxt->flinfo, cxt->collation, *a, *b))))
+#define ST_COMPARE_TYPE int64
+#define ST_COMPARE_ARG_TYPE BTSortArrayContext
+#define ST_SCOPE static
+#define ST_DEFINE
+#include "lib/sort_template.h"
+
 /*
  * _bt_sort_array_elements() -- sort and de-dup array elements
  *
@@ -477,35 +501,19 @@ _bt_sort_array_elements(IndexScanDesc scan, ScanKey skey,
 			 BTORDER_PROC, elemtype, elemtype,
 			 rel->rd_opfamily[skey->sk_attno - 1]);
 
-	/* Sort the array elements */
+	/* Sort the array elements and remove duplicates */
 	fmgr_info(cmp_proc, &cxt.flinfo);
 	cxt.collation = skey->sk_collation;
-	cxt.reverse = reverse;
-	qsort_arg((void *) elems, nelems, sizeof(Datum),
-			  _bt_compare_array_elements, (void *) &cxt);
-
-	/* Now scan the sorted elements and remove duplicates */
-	return qunique_arg(elems, nelems, sizeof(Datum),
-					   _bt_compare_array_elements, &cxt);
-}
-
-/*
- * qsort_arg comparator for sorting array elements
- */
-static int
-_bt_compare_array_elements(const void *a, const void *b, void *arg)
-{
-	Datum		da = *((const Datum *) a);
-	Datum		db = *((const Datum *) b);
-	BTSortArrayContext *cxt = (BTSortArrayContext *) arg;
-	int32		compare;
-
-	compare = DatumGetInt32(FunctionCall2Coll(&cxt->flinfo,
-											  cxt->collation,
-											  da, db));
-	if (cxt->reverse)
-		INVERT_COMPARE_RESULT(compare);
-	return compare;
+	if (reverse)
+	{
+		qsort_bt_array_elements_reverse(elems, nelems, &cxt);
+		return unique_bt_array_elements_reverse(elems, nelems, &cxt);
+	}
+	else
+	{
+		qsort_bt_array_elements(elems, nelems, &cxt);
+		return unique_bt_array_elements(elems, nelems, &cxt);
+	}
 }
 
 /*
-- 
2.30.1

From 2308a8556fecdf3388ec4ac4c2a1588619a62b94 Mon Sep 17 00:00:00 2001
From: Thomas Munro <[email-masked]>
Date: Sun, 14 Mar 2021 14:53:10 +1300
Subject: [PATCH 9/9] Specialize sort routine used by multixact.c.

---
 src/backend/access/transam/multixact.c | 35 +++++++-------------------
 1 file changed, 9 insertions(+), 26 deletions(-)

diff --git a/src/backend/access/transam/multixact.c b/src/backend/access/transam/multixact.c
index 1f9f1a1fa1..97c5120cdd 100644
--- a/src/backend/access/transam/multixact.c
+++ b/src/backend/access/transam/multixact.c
@@ -344,7 +344,6 @@ static void RecordNewMultiXact(MultiXactId multi, MultiXactOffset offset,
 static MultiXactId GetNewMultiXactId(int nmembers, MultiXactOffset *offset);
 
 /* MultiXact cache management */
-static int	mxactMemberComparator(const void *arg1, const void *arg2);
 static MultiXactId mXactCacheGetBySet(int nmembers, MultiXactMember *members);
 static int	mXactCacheGetById(MultiXactId multi, MultiXactMember **members);
 static void mXactCachePut(MultiXactId multi, int nmembers,
@@ -1453,29 +1452,13 @@ retry:
 	return truelength;
 }
 
-/*
- * mxactMemberComparator
- *		qsort comparison function for MultiXactMember
- *
- * We can't use wraparound comparison for XIDs because that does not respect
- * the triangle inequality!  Any old sort order will do.
- */
-static int
-mxactMemberComparator(const void *arg1, const void *arg2)
-{
-	MultiXactMember member1 = *(const MultiXactMember *) arg1;
-	MultiXactMember member2 = *(const MultiXactMember *) arg2;
-
-	if (member1.xid > member2.xid)
-		return 1;
-	if (member1.xid < member2.xid)
-		return -1;
-	if (member1.status > member2.status)
-		return 1;
-	if (member1.status < member2.status)
-		return -1;
-	return 0;
-}
+#define ST_SORT qsort_mxact_members
+#define ST_ELEMENT_TYPE MultiXactMember
+#define ST_COMPARE(a, b) (((((int64) (a)->status) << 8) | (int64) (a)->xid) - ((((int64) (b)->status) << 8) | (int64) (b)->xid))
+#define ST_COMPARE_TYPE int64
+#define ST_SCOPE static
+#define ST_DEFINE
+#include "lib/sort_template.h"
 
 /*
  * mXactCacheGetBySet
@@ -1499,7 +1482,7 @@ mXactCacheGetBySet(int nmembers, MultiXactMember *members)
 				mxid_to_string(InvalidMultiXactId, nmembers, members));
 
 	/* sort the array so comparison is easy */
-	qsort(members, nmembers, sizeof(MultiXactMember), mxactMemberComparator);
+	qsort_mxact_members(members, nmembers);
 
 	dlist_foreach(iter, &MXactCache)
 	{
@@ -1605,7 +1588,7 @@ mXactCachePut(MultiXactId multi, int nmembers, MultiXactMember *members)
 	memcpy(entry->members, members, nmembers * sizeof(MultiXactMember));
 
 	/* mXactCacheGetBySet assumes the entries are sorted, so sort them */
-	qsort(entry->members, nmembers, sizeof(MultiXactMember), mxactMemberComparator);
+	qsort_mxact_members(entry->members, nmembers);
 
 	dlist_push_head(&MXactCache, &entry->node);
 	if (MXactCacheMembers++ >= MAX_CACHE_ENTRIES)
-- 
2.30.1

---

From: Zhihong Yu <[email-masked]>
Date: Sat, 13 Mar 2021 20:06:26 -0800

Hi,

For 0001-Add-bsearch-and-unique-templates-to-sort_template.h.patch :

The array is supposed to be sorted, right ?
The comment should mention this.

Cheers

---

From: Thomas Munro <[email-masked]>
Date: Mon, 15 Mar 2021 13:09:16 +1300

> The comment should mention this.

Good point, will update.  Thanks!

---

From: Thomas Munro <[email-masked]>
Date: Wed, 16 Jun 2021 17:54:48 +1200

> Good point, will update.  Thanks!

Rebased.  Also fixed some formatting problems and updated
typedefs.list so they don't come back.

---

From: Zhihong Yu <[email-masked]>
Date: Wed, 16 Jun 2021 13:18:16 -0700

> typedefs.list so they don't come back.

Hi,
In 0001-Add-bsearch-and-unique-templates-to-sort_template.h.patch :

-                                       const ST_ELEMENT_TYPE *
ST_SORT_PROTO_ARG);
+                                       const ST_ELEMENT_TYPE
*ST_SORT_PROTO_ARG);

It seems there is no real change in the line above. Better keep the
original formation.

Since the ST_COMPARE_TYPE is meant to designate the type of the return
value, maybe ST_COMPARE_RET_TYPE would be better name.
It also goes with ST_COMPARE_ARG_TYPE preceding this.

There doesn't seem to be material change for the above hunk.

+   while (left <= right)
+   {

The computation for midpoint should be left + (right-left)/2.

Cheers

---

From: Thomas Munro <[email-masked]>
Date: Thu, 17 Jun 2021 09:54:21 +1200

Hi Zhihong,

On Thu, Jun 17, 2021 at 8:13 AM Zhihong Yu <[email-masked]> wrote:
> -                                       const ST_ELEMENT_TYPE * ST_SORT_PROTO_ARG);
> +                                       const ST_ELEMENT_TYPE *ST_SORT_PROTO_ARG);
>
> It seems there is no real change in the line above. Better keep the original formation.

Hmm, well it was only recently damaged by commit def5b065, and that's
because I'd forgotten to put ST_ELEMENT_TYPE into typedefs.list, and I
was correcting that in this patch.  (That file is used by
pg_bsd_indent to decide if an identifier is a type or a variable,
which affects whether '*' is formatted like a unary operator/type
syntax or a binary operator.)

> Since the ST_COMPARE_TYPE is meant to designate the type of the return value, maybe ST_COMPARE_RET_TYPE would be better name.

Good idea, will do.

> There doesn't seem to be material change for the above hunk.

In master, you can't write #define ST_ELEMENT_TYPE some_type *, which
seems like it would be quite useful.  You can use pointers as element
types, but only with a typedef name due to C parsing rules.  some_type
**a, *pa, ... declares some_type *pa, but we want some_type **pa.  I
don't want to have to introduce extra typedefs.  The change fixes that
problem by not using C's squirrelly variable declaration list syntax.

> The computation for midpoint should be left + (right-left)/2.

Right, my way can overflow.  Will fix.  Thanks!

---

From: Zhihong Yu <[email-masked]>
Date: Wed, 16 Jun 2021 15:05:24 -0700

> Right, my way can overflow.  Will fix.  Thanks!

Hi,
Thanks for giving me background on typedefs.
The relevant changes look fine to me.

Cheers

---

From: Tom Lane <[email-masked]>
Date: Wed, 16 Jun 2021 19:40:18 -0400

Thomas Munro <[email-masked]> writes:
> was correcting that in this patch.

If ST_ELEMENT_TYPE isn't recognized as a typedef by the buildfarm's
typedef collectors, this sort of manual addition to typedefs.list
is not going to survive the next pgindent run.  No, I will NOT
promise to manually add it back every time.

We do already have special provision for injecting additional typedefs
in the pgindent script, so one possibility is to add it there:

-my @additional = ("bool\n");
+my @additional = ("bool\nST_ELEMENT_TYPE\n");

On the whole I'm not sure that this is a big enough formatting
issue to justify a special hack, though.  Is there any more than
the one line that gets misformatted?

			regards, tom lane

---

From: Thomas Munro <[email-masked]>
Date: Thu, 17 Jun 2021 13:07:38 +1200

> the one line that gets misformatted?

Ohh.  In that case, I won't bother with that hunk and will live with
the extra space.  There are several other lines like this in the tree,
where people use caveman template macrology that is invisible to
whatever analyser is being used for that, and I can see that that's
just going to have to be OK for now.  Perhaps one day we could add a
secondary file, not updated by that mechanism, that holds a manually
maintained list for cases like this.

---

From: Tom Lane <[email-masked]>
Date: Wed, 16 Jun 2021 21:14:25 -0400

Thomas Munro <[email-masked]> writes:
> Perhaps one day we could add a

Yeah, the comments in pgindent already speculate about that.  For
now, those include and exclude lists are short enough that keeping
them inside the script seems a lot easier than building tooling
to get them from somewhere else.

The big problem in my mind, which would not be alleviated in the
slightest by having a separate file, is that it'd be easy to miss
removing entries if they ever become obsolete.

			regards, tom lane

---

From: Thomas Munro <[email-masked]>
Date: Thu, 17 Jun 2021 13:20:44 +1200

> removing entries if they ever become obsolete.

I suppose you could invent some kind of declaration syntax in a
comment near the use of the pseudo-typename in the source tree that is
mechanically extracted.

---

From: John Naylor <[email-masked]>
Date: Mon, 28 Jun 2021 15:13:06 -0400

On Wed, Jun 16, 2021 at 1:55 AM Thomas Munro <[email-masked]> wrote:
[v2 patch]

Hi Thomas,

I plan to do some performance testing with VACUUM, ANALYZE etc soon, to see
if I can detect any significant differences.

I did a quick check of the MacOS/clang binary size (no debug symbols):

master:    8108408
0001-0009: 8125224

Later, I'll drill down into the individual patches and see if anything
stands out.

There were already some comments for v2 upthread about formatting and an
overflow hazard, but I did find a few more things to ask about:

- For my curiosity, there are a lot of calls to qsort/qunique in the tree
-- without having looked exhaustively, do these patches focus on cases
where there are bespoke comparator functions and/or hot code paths?

- Aside from the qsort{_arg} precedence, is there a practical reason for
keeping the new global functions in their own files?

- 0002 / 0004

The functions are pretty small, but is there some advantage for inlining
these?

- 0003

#include "lib/qunique.h" is not needed anymore.

This isn't quite relevant for the current patch perhaps, but I'm wondering
why we don't already call bsearch for RelationHasSysCache() and
RelationSupportsSysCache().

- 0008

This seems like a pretty heavyweight comparison, so I'm not sure inlining
buys us much, but it seems also there are fewer branches this way. I'll
come up with a test and see what happens.

--
John Naylor
EDB: http://www.enterprisedb.com

---

From: Thomas Munro <[email-masked]>
Date: Tue, 29 Jun 2021 12:16:16 +1200

Hi John,

On Tue, Jun 29, 2021 at 7:13 AM John Naylor
<[email-masked]> wrote:
> I plan to do some performance testing with VACUUM, ANALYZE etc soon, to see if I can detect any significant differences.

Thanks!

> I did a quick check of the MacOS/clang binary size (no debug symbols):

Not too bad.

> Later, I'll drill down into the individual patches and see if anything stands out.
>
> There were already some comments for v2 upthread about formatting and an overflow hazard, but I did find a few more things to ask about:

Right, here's an update with fixes discussed earlier with Zhihong and Tom:

* COMPARE_TYPE -> COMPARE_RET_TYPE
* quit fighting with pgindent (I will try to fix this problem generally later)
* fix overflow hazard

> - For my curiosity, there are a lot of calls to qsort/qunique in the tree -- without having looked exhaustively, do these patches focus on cases where there are bespoke comparator functions and/or hot code paths?

Patches 0006-0009 are highly specialised for local usage by a single
module, and require some kind of evidence that they're worth their
bytes, and the onus is on me there of course -- but any ideas and
feedback are welcome.  There are other opportunities like these, maybe
better ones.  That reminds me: I recently had a perf report from
Andres that showed the qsort in compute_scalar_stats() as quite hot.
That's probably a good candidate, and is not yet done in the current
patch set.

The lower numbered patches are all things that are reused in many
places, and in my humble opinion improve the notation and type safety
and code deduplication generally when working with common types
ItemPtr, BlockNumber, Oid, aside from any performance arguments.  At
least the ItemPtr stuff *might* also speed something useful up.

I tried to measure a speedup in vacuum, but so far I have not.  I did
learn some things though:  While doing that with an uncorrelated index
and a lot of deleted tuples, I found that adding more
maintenance_work_mem doesn't help beyond a few MB, because then cache
misses dominate to the point where it's not better than doing multiple
passes (and this is familiar to me from work on hash joins).  If I
turned on huge pages on Linux and set min_dynamic_shared_memory so
that the parallel DSM used by vacuum lives in huge pages, then
parallel vacuum with a large maintenance_work_mem starts to do much
better than non-parallel vacuum by improving the TLB misses (as with
hash joins).  I thought that was quite interesting!  Perhaps
bsearch_itemptr might help with correlated indexes with a lot of
deleted indexes (so not dominated by cache misses), though?

(I wouldn't be suprised if someone comes up with a much better idea
than bsearch for that anyway...  a few ideas have been suggested.)

> - Aside from the qsort{_arg} precedence, is there a practical reason for keeping the new global functions in their own files?

Better idea for layout welcome.  One thing I wondered while trying to
figure out where to put functions that operate on itemptr: why is
itemptr_encode() in src/include/catalog/index.h?!

> The functions are pretty small, but is there some advantage for inlining these?

Glibc's bsearch definition is already in a header for inlining (as is
our qunique), so I thought I should preserve that characteristic on
principle.  I don't have any evidence though.  Other libcs I looked at
didn't have bsearch in a header.  So by doing this we make the
generated code the same across platforms (all other relevant things
being equal).  I don't know if it really makes much difference,
especially since in this case the comparator and size would still be
inlined if we defined it in the .c (unlike standard bsearch)...
Probably only lazy_tid_reaped() calls it enough to potentially show
any difference in a non-microbenchmark workload, if anything does.

> #include "lib/qunique.h" is not needed anymore.

Fixed.

> This isn't quite relevant for the current patch perhaps, but I'm wondering why we don't already call bsearch for RelationHasSysCache() and RelationSupportsSysCache().

Right, I missed that.  Done.  Nice to delete some more code.

> This seems like a pretty heavyweight comparison, so I'm not sure inlining buys us much, but it seems also there are fewer branches this way. I'll come up with a test and see what happens.

I will be very interested to see the results.  Thanks!

---

From: Thomas Munro <[email-masked]>
Date: Tue, 29 Jun 2021 13:11:06 +1200

I spotted a mistake in v3: I didn't rename ST_COMPARE_TYPE to
ST_COMPARE_RET_TYPE in the 0009 patch (well, I did, but forgot to
commit before I ran git format-patch).  I won't send another tarball
just for that, but will correct it next time.

---

From: Thomas Munro <[email-masked]>
Date: Tue, 29 Jun 2021 18:56:07 +1200

> just for that, but will correct it next time.

Here's a version that includes a rather hackish test module that you
might find useful to explore various weird effects.  Testing sorting
routines is really hard, of course... there's a zillion parameters and
things you could do in the data and cache effects etc etc.  One of the
main things that jumps out pretty clearly though with these simple
tests is that sorting 6 byte ItemPointerData objects is *really slow*
compared to more natural object sizes (look at the times and the
MEMORY values in the scripts).  Another is that specialised sort
functions are much faster than traditional qsort (being one of the
goals of this exercise).  Sadly, the 64 bit comparison technique is
not looking too good in the output of this test.

---

From: John Naylor <[email-masked]>
Date: Tue, 29 Jun 2021 12:40:53 -0400

> things you could do in the data and cache effects etc etc.  One of the

That module is incredibly useful!

Yeah, while brushing up on recent findings on sorting, it's clear there's a
huge amount of options with different tradeoffs. I did see your tweet last
year about the "small sort" threshold that was tested on a VAX machine, but
hadn't given it any thought til now. Looking around, I've seen quite a
range, always with the caveat of "it depends". A couple interesting
variations:

Golang uses 12, with an extra tweak:

// Do ShellSort pass with gap 6
// It could be written in this simplified form cause b-a <= 12
for i := a + 6; i < b; i++ {
    if data.Less(i, i-6) {
        data.Swap(i, i-6)
    }
}
insertionSort(data, a, b)

Andrei Alexandrescu gave a couple talks discussing the small-sort part of
quicksort, and demonstrated a ruthlessly-optimized make-heap +
unguarded-insertion-sort, using a threshold of 256. He reported a 6%
speed-up sorting a million doubles, IIRC:

video: https://www.youtube.com/watch?v=FJJTYQYB1JQ
slides:
https://github.com/CppCon/CppCon2019/blob/master/Presentations/speed_is_found_in_the_minds_of_people/speed_is_found_in_the_minds_of_people__andrei_alexandrescu__cppcon_2019.pdf

That might not be workable for us, but it's a fun talk.

> not looking too good in the output of this test.

One of the points of the talk I linked to is "if doing the sensible thing
makes things worse, try something silly instead".

Anyway, I'll play around with the scripts and see if something useful pops
out.

---

From: John Naylor <[email-masked]>
Date: Thu, 1 Jul 2021 12:39:32 -0400

For item pointers, it made sense to try doing math to reduce the number of
branches. That made things worse, so let's try the opposite: Increase the
number of branches so we do less math. In the attached patch (applies on
top of your 0012 and a .txt to avoid confusing the CF bot), I test a new
comparator with this approach, and also try a wider range of thresholds.
The thresholds don't seem to make any noticeable difference with this data
type, but the new comparator (cmp=ids below) gives a nice speedup in this
test:

# SELECT test_sort_itemptr();
NOTICE:  [traditional qsort] order=random, threshold=7, cmp=32, test=0,
time=4.964657
NOTICE:  [traditional qsort] order=random, threshold=7, cmp=32, test=1,
time=5.185384
NOTICE:  [traditional qsort] order=random, threshold=7, cmp=32, test=2,
time=5.058179
NOTICE:  order=random, threshold=7, cmp=std, test=0, time=2.810627
NOTICE:  order=random, threshold=7, cmp=std, test=1, time=2.804940
NOTICE:  order=random, threshold=7, cmp=std, test=2, time=2.800677
NOTICE:  order=random, threshold=7, cmp=ids, test=0, time=1.692711
NOTICE:  order=random, threshold=7, cmp=ids, test=1, time=1.694546
NOTICE:  order=random, threshold=7, cmp=ids, test=2, time=1.692839
NOTICE:  order=random, threshold=12, cmp=std, test=0, time=2.687033
NOTICE:  order=random, threshold=12, cmp=std, test=1, time=2.681974
NOTICE:  order=random, threshold=12, cmp=std, test=2, time=2.687833
NOTICE:  order=random, threshold=12, cmp=ids, test=0, time=1.666418
NOTICE:  order=random, threshold=12, cmp=ids, test=1, time=1.666188
NOTICE:  order=random, threshold=12, cmp=ids, test=2, time=1.664176
NOTICE:  order=random, threshold=16, cmp=std, test=0, time=2.574147
NOTICE:  order=random, threshold=16, cmp=std, test=1, time=2.579981
NOTICE:  order=random, threshold=16, cmp=std, test=2, time=2.572861
NOTICE:  order=random, threshold=16, cmp=ids, test=0, time=1.699432
NOTICE:  order=random, threshold=16, cmp=ids, test=1, time=1.703075
NOTICE:  order=random, threshold=16, cmp=ids, test=2, time=1.697173
NOTICE:  order=random, threshold=32, cmp=std, test=0, time=2.750040
NOTICE:  order=random, threshold=32, cmp=std, test=1, time=2.744138
NOTICE:  order=random, threshold=32, cmp=std, test=2, time=2.748026
NOTICE:  order=random, threshold=32, cmp=ids, test=0, time=1.677414
NOTICE:  order=random, threshold=32, cmp=ids, test=1, time=1.683792
NOTICE:  order=random, threshold=32, cmp=ids, test=2, time=1.701309
NOTICE:  [traditional qsort] order=increasing, threshold=7, cmp=32, test=0,
time=2.543837
NOTICE:  [traditional qsort] order=increasing, threshold=7, cmp=32, test=1,
time=2.290497
NOTICE:  [traditional qsort] order=increasing, threshold=7, cmp=32, test=2,
time=2.262956
NOTICE:  order=increasing, threshold=7, cmp=std, test=0, time=1.033052
NOTICE:  order=increasing, threshold=7, cmp=std, test=1, time=1.032079
NOTICE:  order=increasing, threshold=7, cmp=std, test=2, time=1.041836
NOTICE:  order=increasing, threshold=7, cmp=ids, test=0, time=0.367355
NOTICE:  order=increasing, threshold=7, cmp=ids, test=1, time=0.367428
NOTICE:  order=increasing, threshold=7, cmp=ids, test=2, time=0.367384
NOTICE:  order=increasing, threshold=12, cmp=std, test=0, time=1.004991
NOTICE:  order=increasing, threshold=12, cmp=std, test=1, time=1.008045
NOTICE:  order=increasing, threshold=12, cmp=std, test=2, time=1.010778
NOTICE:  order=increasing, threshold=12, cmp=ids, test=0, time=0.370944
NOTICE:  order=increasing, threshold=12, cmp=ids, test=1, time=0.368669
NOTICE:  order=increasing, threshold=12, cmp=ids, test=2, time=0.370100
NOTICE:  order=increasing, threshold=16, cmp=std, test=0, time=1.023682
NOTICE:  order=increasing, threshold=16, cmp=std, test=1, time=1.025805
NOTICE:  order=increasing, threshold=16, cmp=std, test=2, time=1.022005
NOTICE:  order=increasing, threshold=16, cmp=ids, test=0, time=0.365398
NOTICE:  order=increasing, threshold=16, cmp=ids, test=1, time=0.365586
NOTICE:  order=increasing, threshold=16, cmp=ids, test=2, time=0.364807
NOTICE:  order=increasing, threshold=32, cmp=std, test=0, time=0.950780
NOTICE:  order=increasing, threshold=32, cmp=std, test=1, time=0.949920
NOTICE:  order=increasing, threshold=32, cmp=std, test=2, time=0.953239
NOTICE:  order=increasing, threshold=32, cmp=ids, test=0, time=0.367866
NOTICE:  order=increasing, threshold=32, cmp=ids, test=1, time=0.372179
NOTICE:  order=increasing, threshold=32, cmp=ids, test=2, time=0.371115
NOTICE:  [traditional qsort] order=decreasing, threshold=7, cmp=32, test=0,
time=2.317475
NOTICE:  [traditional qsort] order=decreasing, threshold=7, cmp=32, test=1,
time=2.323446
NOTICE:  [traditional qsort] order=decreasing, threshold=7, cmp=32, test=2,
time=2.326714
NOTICE:  order=decreasing, threshold=7, cmp=std, test=0, time=1.022270
NOTICE:  order=decreasing, threshold=7, cmp=std, test=1, time=1.015133
NOTICE:  order=decreasing, threshold=7, cmp=std, test=2, time=1.016367
NOTICE:  order=decreasing, threshold=7, cmp=ids, test=0, time=0.386884
NOTICE:  order=decreasing, threshold=7, cmp=ids, test=1, time=0.388397
NOTICE:  order=decreasing, threshold=7, cmp=ids, test=2, time=0.386328
NOTICE:  order=decreasing, threshold=12, cmp=std, test=0, time=0.993594
NOTICE:  order=decreasing, threshold=12, cmp=std, test=1, time=0.995031
NOTICE:  order=decreasing, threshold=12, cmp=std, test=2, time=0.995320
NOTICE:  order=decreasing, threshold=12, cmp=ids, test=0, time=0.391243
NOTICE:  order=decreasing, threshold=12, cmp=ids, test=1, time=0.391938
NOTICE:  order=decreasing, threshold=12, cmp=ids, test=2, time=0.392478
NOTICE:  order=decreasing, threshold=16, cmp=std, test=0, time=1.006240
NOTICE:  order=decreasing, threshold=16, cmp=std, test=1, time=1.009817
NOTICE:  order=decreasing, threshold=16, cmp=std, test=2, time=1.010281
NOTICE:  order=decreasing, threshold=16, cmp=ids, test=0, time=0.386388
NOTICE:  order=decreasing, threshold=16, cmp=ids, test=1, time=0.385801
NOTICE:  order=decreasing, threshold=16, cmp=ids, test=2, time=0.384484
NOTICE:  order=decreasing, threshold=32, cmp=std, test=0, time=0.959647
NOTICE:  order=decreasing, threshold=32, cmp=std, test=1, time=0.958833
NOTICE:  order=decreasing, threshold=32, cmp=std, test=2, time=0.960234
NOTICE:  order=decreasing, threshold=32, cmp=ids, test=0, time=0.403014
NOTICE:  order=decreasing, threshold=32, cmp=ids, test=1, time=0.393329
NOTICE:  order=decreasing, threshold=32, cmp=ids, test=2, time=0.395659

---

From: Thomas Munro <[email-masked]>
Date: Fri, 2 Jul 2021 10:09:39 +1200

On Fri, Jul 2, 2021 at 4:39 AM John Naylor <[email-masked]> wrote:
> For item pointers, it made sense to try doing math to reduce the number of branches. That made things worse, so let's try the opposite: Increase the number of branches so we do less math. In the attached patch (applies on top of your 0012 and a .txt to avoid confusing the CF bot), I test a new comparator with this approach, and also try a wider range of thresholds. The thresholds don't seem to make any noticeable difference with this data type, but the new comparator (cmp=ids below) gives a nice speedup in this test:

> NOTICE:  [traditional qsort] order=random, threshold=7, cmp=32, test=0, time=4.964657

> NOTICE:  order=random, threshold=7, cmp=ids, test=0, time=1.692711

Oooh.  So, the awkwardness of the 64 maths with unaligned inputs (even
though we obtain all inputs with 16 bit loads) was hurting, and you
realised the same sort of thing might be happening also with the 32
bit version and went the other way.  (It'd be nice to understand
exactly why.)

I tried your 16 bit comparison version on Intel, AMD and Apple CPUs
and the results were all in the same ballpark.  For random input, I
see something like ~1.7x speedup over traditional qsort from
specialising (cmp=std), and ~2.7x from going 16 bit (cmp=ids).  For
increasing and decreasing input, it's ~2x speedup from specialising
and ~4x speedup from going 16 bit.  Beautiful.

One thing I'm wondering about is whether it's worth having stuff to
support future experimentation like ST_SORT_SMALL_THRESHOLD and
ST_COMPARE_RET_TYPE in the tree, or whether we should pare it back to
the minimal changes that definitely produce results.  I think I'd like
to keep those changes: even if it may be some time, possibly an
infinite amount, before we figure out how to tune the thresholds
profitably, giving them names instead of using magic numbers seems
like progress.

The Alexandrescu talk was extremely entertaining, thanks.

---

From: John Naylor <[email-masked]>
Date: Thu, 1 Jul 2021 22:32:31 -0400

> profitably, giving them names instead of using magic numbers seems

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.

(BTW, I just realized I lied and sent a .patch file after all, oops)

---

From: Thomas Munro <[email-masked]>
Date: Sun, 4 Jul 2021 16:27:21 +1200

On Fri, Jul 2, 2021 at 2:32 PM John Naylor <[email-masked]> 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.
From 62a8acbc745f3b4a90c9a14b6b61989a9d83bece Mon Sep 17 00:00:00 2001
From: Thomas Munro <[email-masked]>
Date: Sat, 3 Jul 2021 19:02:10 +1200
Subject: [PATCH] WIP: Accelerate tuple sorting for common types.

Several data types have their own fast comparator functions that can be
replaced with common binary or signed comparator functions.  These
functions can then be recognized by tuplesort.c and used to dispatch to
corresponding specialized sort functions, to accelerate sorting.

XXX WIP, experiment grade only, many open questions...
---
 src/backend/access/nbtree/nbtcompare.c |  22 ++--
 src/backend/utils/adt/date.c           |  15 +--
 src/backend/utils/adt/timestamp.c      |  11 ++
 src/backend/utils/adt/varlena.c        |  26 +---
 src/backend/utils/sort/tuplesort.c     | 161 ++++++++++++++++++++++++-
 src/include/utils/sortsupport.h        | 115 ++++++++++++++++++
 6 files changed, 295 insertions(+), 55 deletions(-)

diff --git a/src/backend/access/nbtree/nbtcompare.c b/src/backend/access/nbtree/nbtcompare.c
index 7ac73cb8c2..204cf778fb 100644
--- a/src/backend/access/nbtree/nbtcompare.c
+++ b/src/backend/access/nbtree/nbtcompare.c
@@ -119,26 +119,12 @@ btint4cmp(PG_FUNCTION_ARGS)
 		PG_RETURN_INT32(A_LESS_THAN_B);
 }
 
-static int
-btint4fastcmp(Datum x, Datum y, SortSupport ssup)
-{
-	int32		a = DatumGetInt32(x);
-	int32		b = DatumGetInt32(y);
-
-	if (a > b)
-		return A_GREATER_THAN_B;
-	else if (a == b)
-		return 0;
-	else
-		return A_LESS_THAN_B;
-}
-
 Datum
 btint4sortsupport(PG_FUNCTION_ARGS)
 {
 	SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
 
-	ssup->comparator = btint4fastcmp;
+	ssup->comparator = ssup_datum_int32_cmp;
 	PG_RETURN_VOID();
 }
 
@@ -156,6 +142,7 @@ btint8cmp(PG_FUNCTION_ARGS)
 		PG_RETURN_INT32(A_LESS_THAN_B);
 }
 
+#ifndef USE_FLOAT8_BYVAL
 static int
 btint8fastcmp(Datum x, Datum y, SortSupport ssup)
 {
@@ -169,13 +156,18 @@ btint8fastcmp(Datum x, Datum y, SortSupport ssup)
 	else
 		return A_LESS_THAN_B;
 }
+#endif
 
 Datum
 btint8sortsupport(PG_FUNCTION_ARGS)
 {
 	SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
 
+#ifdef USE_FLOAT8_BYVAL
+	ssup->comparator = ssup_datum_signed_cmp;
+#else
 	ssup->comparator = btint8fastcmp;
+#endif
 	PG_RETURN_VOID();
 }
 
diff --git a/src/backend/utils/adt/date.c b/src/backend/utils/adt/date.c
index 0bea16cb67..350c662d50 100644
--- a/src/backend/utils/adt/date.c
+++ b/src/backend/utils/adt/date.c
@@ -438,25 +438,12 @@ date_cmp(PG_FUNCTION_ARGS)
 	PG_RETURN_INT32(0);
 }
 
-static int
-date_fastcmp(Datum x, Datum y, SortSupport ssup)
-{
-	DateADT		a = DatumGetDateADT(x);
-	DateADT		b = DatumGetDateADT(y);
-
-	if (a < b)
-		return -1;
-	else if (a > b)
-		return 1;
-	return 0;
-}
-
 Datum
 date_sortsupport(PG_FUNCTION_ARGS)
 {
 	SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
 
-	ssup->comparator = date_fastcmp;
+	ssup->comparator = ssup_datum_int32_cmp;
 	PG_RETURN_VOID();
 }
 
diff --git a/src/backend/utils/adt/timestamp.c b/src/backend/utils/adt/timestamp.c
index 79761f809c..c678517db6 100644
--- a/src/backend/utils/adt/timestamp.c
+++ b/src/backend/utils/adt/timestamp.c
@@ -37,6 +37,7 @@
 #include "utils/datetime.h"
 #include "utils/float.h"
 #include "utils/numeric.h"
+#include "utils/sortsupport.h"
 
 /*
  * gcc's -ffast-math switch breaks routines that expect exact results from
@@ -2155,6 +2156,7 @@ timestamp_cmp(PG_FUNCTION_ARGS)
 	PG_RETURN_INT32(timestamp_cmp_internal(dt1, dt2));
 }
 
+#ifndef USE_FLOAT8_BYVAL
 /* note: this is used for timestamptz also */
 static int
 timestamp_fastcmp(Datum x, Datum y, SortSupport ssup)
@@ -2164,13 +2166,22 @@ timestamp_fastcmp(Datum x, Datum y, SortSupport ssup)
 
 	return timestamp_cmp_internal(a, b);
 }
+#endif
 
 Datum
 timestamp_sortsupport(PG_FUNCTION_ARGS)
 {
 	SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
 
+#ifdef USE_FLOAT8_BYVAL
+	/*
+	 * If this build has pass-by-value timestamps, then we can use a standard
+	 * comparator function.
+	 */
+	ssup->comparator = ssup_datum_signed_cmp;
+#else
 	ssup->comparator = timestamp_fastcmp;
+#endif
 	PG_RETURN_VOID();
 }
 
diff --git a/src/backend/utils/adt/varlena.c b/src/backend/utils/adt/varlena.c
index d2a11b1b5d..4709d8129e 100644
--- a/src/backend/utils/adt/varlena.c
+++ b/src/backend/utils/adt/varlena.c
@@ -127,7 +127,6 @@ static int	namefastcmp_c(Datum x, Datum y, SortSupport ssup);
 static int	varlenafastcmp_locale(Datum x, Datum y, SortSupport ssup);
 static int	namefastcmp_locale(Datum x, Datum y, SortSupport ssup);
 static int	varstrfastcmp_locale(char *a1p, int len1, char *a2p, int len2, SortSupport ssup);
-static int	varstrcmp_abbrev(Datum x, Datum y, SortSupport ssup);
 static Datum varstr_abbrev_convert(Datum original, SortSupport ssup);
 static bool varstr_abbrev_abort(int memtupcount, SortSupport ssup);
 static int32 text_length(Datum str);
@@ -2175,7 +2174,7 @@ varstr_sortsupport(SortSupport ssup, Oid typid, Oid collid)
 			initHyperLogLog(&sss->abbr_card, 10);
 			initHyperLogLog(&sss->full_card, 10);
 			ssup->abbrev_full_comparator = ssup->comparator;
-			ssup->comparator = varstrcmp_abbrev;
+			ssup->comparator = ssup_datum_binary_cmp;
 			ssup->abbrev_converter = varstr_abbrev_convert;
 			ssup->abbrev_abort = varstr_abbrev_abort;
 		}
@@ -2461,27 +2460,6 @@ varstrfastcmp_locale(char *a1p, int len1, char *a2p, int len2, SortSupport ssup)
 	return result;
 }
 
-/*
- * Abbreviated key comparison func
- */
-static int
-varstrcmp_abbrev(Datum x, Datum y, SortSupport ssup)
-{
-	/*
-	 * When 0 is returned, the core system will call varstrfastcmp_c()
-	 * (bpcharfastcmp_c() in BpChar case) or varlenafastcmp_locale().  Even a
-	 * strcmp() on two non-truncated strxfrm() blobs cannot indicate *equality*
-	 * authoritatively, for the same reason that there is a strcoll()
-	 * tie-breaker call to strcmp() in varstr_cmp().
-	 */
-	if (x > y)
-		return 1;
-	else if (x == y)
-		return 0;
-	else
-		return -1;
-}
-
 /*
  * Conversion routine for sortsupport.  Converts original to abbreviated key
  * representation.  Our encoding strategy is simple -- pack the first 8 bytes
@@ -2710,7 +2688,7 @@ done:
 	/*
 	 * Byteswap on little-endian machines.
 	 *
-	 * This is needed so that varstrcmp_abbrev() (an unsigned integer 3-way
+	 * This is needed so that ssup_datum_binary_cmp() (an unsigned integer 3-way
 	 * comparator) works correctly on all platforms.  If we didn't do this,
 	 * the comparator would have to call memcmp() with a pair of pointers to
 	 * the first byte of each abbreviated key, which is slower.
diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c
index 22972071ff..455bb652b8 100644
--- a/src/backend/utils/sort/tuplesort.c
+++ b/src/backend/utils/sort/tuplesort.c
@@ -669,14 +669,101 @@ static void free_sort_tuple(Tuplesortstate *state, SortTuple *stup);
 static void tuplesort_free(Tuplesortstate *state);
 static void tuplesort_updatemax(Tuplesortstate *state);
 
+/*
+ * Specialized comparators that we can inline into specialized sorts.  The goal
+ * is to try to sort two tuples without having to follow the pointers to the
+ * comparator or the tuple.
+ *
+ * XXX: For now, these fall back to comparator functions that will compare the
+ * leading datum a second time.
+ *
+ * XXX: For now, there is no specialization for cases where datum1 is
+ * authoritative and we don't even need to fall back to a callback at all (that
+ * would be true for types like int4/int8/timestamp/date, but not true for
+ * abbreviations of text or multi-key sorts.  There could be!  Is it worth it?
+ */
+
+/* Used if first key's comparator is ssup_datum_binary_compare */
+static pg_attribute_always_inline int
+qsort_tuple_binary_compare(SortTuple *a, SortTuple *b, Tuplesortstate *state)
+{
+	int			compare;
+
+	compare = ApplyBinarySortComparator(a->datum1, a->isnull1,
+										b->datum1, b->isnull1,
+										&state->sortKeys[0]);
+	if (compare != 0)
+		return compare;
+
+	return state->comparetup(a, b, state);
+}
+
+/* Used if first key's comparator is ssup_datum_signed_compare */
+static pg_attribute_always_inline int
+qsort_tuple_signed_compare(SortTuple *a, SortTuple *b, Tuplesortstate *state)
+{
+	int			compare;
+
+	compare = ApplySignedSortComparator(a->datum1, a->isnull1,
+										b->datum1, b->isnull1,
+										&state->sortKeys[0]);
+	if (compare != 0)
+		return compare;
+
+	return state->comparetup(a, b, state);
+}
+
+/* Used if first key's comparator is ssup_datum_int32_compare */
+static pg_attribute_always_inline int
+qsort_tuple_int32_compare(SortTuple *a, SortTuple *b, Tuplesortstate *state)
+{
+	int			compare;
+
+	compare = ApplyInt32SortComparator(a->datum1, a->isnull1,
+										b->datum1, b->isnull1,
+										&state->sortKeys[0]);
+	if (compare != 0)
+		return compare;
+
+	return state->comparetup(a, b, state);
+}
+
 /*
  * Special versions of qsort just for SortTuple objects.  qsort_tuple() sorts
  * any variant of SortTuples, using the appropriate comparetup function.
  * qsort_ssup() is specialized for the case where the comparetup function
  * reduces to ApplySortComparator(), that is single-key MinimalTuple sorts
- * and Datum sorts.
+ * and Datum sorts.  qsort_tuple_{binary,signed,int32} are specialized for
+ * common comparison functions on pass-by-value leading datums.
  */
 
+#define ST_SORT qsort_tuple_binary
+#define ST_ELEMENT_TYPE SortTuple
+#define ST_COMPARE(a, b, state) qsort_tuple_binary_compare(a, b, state)
+#define ST_COMPARE_ARG_TYPE Tuplesortstate
+#define ST_CHECK_FOR_INTERRUPTS
+#define ST_SCOPE static
+#define ST_DEFINE
+#include "lib/sort_template.h"
+
+#define ST_SORT qsort_tuple_signed
+#define ST_ELEMENT_TYPE SortTuple
+#define ST_COMPARE(a, b, state) qsort_tuple_signed_compare(a, b, state)
+#define ST_COMPARE_ARG_TYPE Tuplesortstate
+#define ST_CHECK_FOR_INTERRUPTS
+#define ST_SCOPE static
+#define ST_DEFINE
+#include "lib/sort_template.h"
+
+#define ST_SORT qsort_tuple_int32
+#define ST_ELEMENT_TYPE SortTuple
+#define ST_COMPARE(a, b, state) qsort_tuple_int32_compare(a, b, state)
+#define ST_COMPARE_ARG_TYPE Tuplesortstate
+#define ST_CHECK_FOR_INTERRUPTS
+#define ST_SCOPE static
+#define ST_DEFINE
+#include "lib/sort_template.h"
+
 #define ST_SORT qsort_tuple
 #define ST_ELEMENT_TYPE SortTuple
 #define ST_COMPARE_RUNTIME_POINTER
@@ -698,6 +785,7 @@ static void tuplesort_updatemax(Tuplesortstate *state);
 #define ST_DEFINE
 #include "lib/sort_template.h"
 
+
 /*
  *		tuplesort_begin_xxx
  *
@@ -3558,15 +3646,40 @@ tuplesort_sort_memtuples(Tuplesortstate *state)
 
 	if (state->memtupcount > 1)
 	{
+		/* Do we have a specialization for the leading column's comparator? */
+		if (state->sortKeys &&
+			state->sortKeys[0].comparator == ssup_datum_binary_cmp)
+		{
+			elog(DEBUG1, "qsort_tuple_binary");
+			qsort_tuple_binary(state->memtuples, state->memtupcount, state);
+		}
+		else if (state->sortKeys &&
+				 state->sortKeys[0].comparator == ssup_datum_signed_cmp)
+		{
+			elog(DEBUG1, "qsort_tuple_signed");
+			qsort_tuple_signed(state->memtuples, state->memtupcount, state);
+		}
+		else if (state->sortKeys &&
+				 state->sortKeys[0].comparator == ssup_datum_int32_cmp)
+		{
+			elog(DEBUG1, "qsort_tuple_int32");
+			qsort_tuple_int32(state->memtuples, state->memtupcount, state);
+		}
 		/* Can we use the single-key sort function? */
-		if (state->onlyKey != NULL)
+		else if (state->onlyKey != NULL)
+		{
+			elog(DEBUG1, "qsort_ssup");
 			qsort_ssup(state->memtuples, state->memtupcount,
 					   state->onlyKey);
+		}
 		else
+		{
+			elog(DEBUG1, "qsort_tuple");
 			qsort_tuple(state->memtuples,
 						state->memtupcount,
 						state->comparetup,
 						state);
+		}
 	}
 }
 
@@ -4776,3 +4889,47 @@ free_sort_tuple(Tuplesortstate *state, SortTuple *stup)
 	FREEMEM(state, GetMemoryChunkSpace(stup->tuple));
 	pfree(stup->tuple);
 }
+
+int
+ssup_datum_binary_cmp(Datum x, Datum y, SortSupport ssup)
+{
+	if (x < y)
+		return -1;
+	else if (x > y)
+		return 1;
+	else
+		return 0;
+}
+
+int
+ssup_datum_signed_cmp(Datum x, Datum y, SortSupport ssup)
+{
+#if SIZEOF_DATUM == 8
+	int64		xx = (int64) x;
+	int64		yy = (int64) y;
+#else
+	int32		xx = (int32) x;
+	int32		yy = (int32) y;
+#endif
+
+	if (xx < yy)
+		return -1;
+	else if (xx > yy)
+		return 1;
+	else
+		return 0;
+}
+
+int
+ssup_datum_int32_cmp(Datum x, Datum y, SortSupport ssup)
+{
+	int32		xx = (int32) x;
+	int32		yy = (int32) y;
+
+	if (xx < yy)
+		return -1;
+	else if (xx > yy)
+		return 1;
+	else
+		return 0;
+}
diff --git a/src/include/utils/sortsupport.h b/src/include/utils/sortsupport.h
index 2f12a8b8eb..8b6a0c5e10 100644
--- a/src/include/utils/sortsupport.h
+++ b/src/include/utils/sortsupport.h
@@ -229,6 +229,112 @@ ApplySortComparator(Datum datum1, bool isNull1,
 	return compare;
 }
 
+static inline int
+ApplyBinarySortComparator(Datum datum1, bool isNull1,
+						  Datum datum2, bool isNull2,
+						  SortSupport ssup)
+{
+	int			compare;
+
+	if (isNull1)
+	{
+		if (isNull2)
+			compare = 0;		/* NULL "=" NULL */
+		else if (ssup->ssup_nulls_first)
+			compare = -1;		/* NULL "<" NOT_NULL */
+		else
+			compare = 1;		/* NULL ">" NOT_NULL */
+	}
+	else if (isNull2)
+	{
+		if (ssup->ssup_nulls_first)
+			compare = 1;		/* NOT_NULL ">" NULL */
+		else
+			compare = -1;		/* NOT_NULL "<" NULL */
+	}
+	else
+	{
+		compare = datum1 < datum2 ? -1 : datum1 > datum2 ? 1 : 0;
+		if (ssup->ssup_reverse)
+			INVERT_COMPARE_RESULT(compare);
+	}
+
+	return compare;
+}
+
+static inline int
+ApplySignedSortComparator(Datum datum1, bool isNull1,
+						  Datum datum2, bool isNull2,
+						  SortSupport ssup)
+{
+	int			compare;
+
+	if (isNull1)
+	{
+		if (isNull2)
+			compare = 0;		/* NULL "=" NULL */
+		else if (ssup->ssup_nulls_first)
+			compare = -1;		/* NULL "<" NOT_NULL */
+		else
+			compare = 1;		/* NULL ">" NOT_NULL */
+	}
+	else if (isNull2)
+	{
+		if (ssup->ssup_nulls_first)
+			compare = 1;		/* NOT_NULL ">" NULL */
+		else
+			compare = -1;		/* NOT_NULL "<" NULL */
+	}
+	else
+	{
+#if SIZEOF_DATUM == 8
+		compare = (int64) datum1 < (int64) datum2 ? -1 :
+			(int64) datum1 > (int64) datum2 ? 1 : 0;
+#else
+		compare = (int32) datum1 < (int32) datum2 ? -1 :
+			(int32) datum1 > (int32) datum2 ? 1 : 0;
+#endif
+		if (ssup->ssup_reverse)
+			INVERT_COMPARE_RESULT(compare);
+	}
+
+	return compare;
+}
+
+static inline int
+ApplyInt32SortComparator(Datum datum1, bool isNull1,
+						 Datum datum2, bool isNull2,
+						 SortSupport ssup)
+{
+	int			compare;
+
+	if (isNull1)
+	{
+		if (isNull2)
+			compare = 0;		/* NULL "=" NULL */
+		else if (ssup->ssup_nulls_first)
+			compare = -1;		/* NULL "<" NOT_NULL */
+		else
+			compare = 1;		/* NULL ">" NOT_NULL */
+	}
+	else if (isNull2)
+	{
+		if (ssup->ssup_nulls_first)
+			compare = 1;		/* NOT_NULL ">" NULL */
+		else
+			compare = -1;		/* NOT_NULL "<" NULL */
+	}
+	else
+	{
+		compare = (int32) datum1 < (int32) datum2 ? -1 :
+			(int32) datum1 > (int32) datum2 ? 1 : 0;
+		if (ssup->ssup_reverse)
+			INVERT_COMPARE_RESULT(compare);
+	}
+
+	return compare;
+}
+
 /*
  * Apply a sort comparator function and return a 3-way comparison using full,
  * authoritative comparator.  This takes care of handling reverse-sort and
@@ -267,6 +373,15 @@ ApplySortAbbrevFullComparator(Datum datum1, bool isNull1,
 	return compare;
 }
 
+/*
+ * Datum comparison functions that we have specialized sort routines for.
+ * Datatypes that install these as their comparator or abbrevated comparator
+ * are eligible for faster sorting.
+ */
+extern int ssup_datum_binary_cmp(Datum x, Datum y, SortSupport ssup);
+extern int ssup_datum_signed_cmp(Datum x, Datum y, SortSupport ssup);
+extern int ssup_datum_int32_cmp(Datum x, Datum y, SortSupport ssup);
+
 /* Other functions in utils/sort/sortsupport.c */
 extern void PrepareSortSupportComparisonShim(Oid cmpFunc, SortSupport ssup);
 extern void PrepareSortSupportFromOrderingOp(Oid orderingOp, SortSupport ssup);
-- 
2.30.2

---

From: vignesh C <[email-masked]>
Date: Thu, 15 Jul 2021 17:19:49 +0530

> special cases for not-null, nulls first, reverse sort, ... to kill all

The patch does not apply on Head anymore, could you rebase and post a
patch. I'm changing the status to "Waiting for Author".

Regards,
Vignesh

---

From: John Naylor <[email-masked]>
Date: Thu, 15 Jul 2021 07:57:54 -0400

> patch. I'm changing the status to "Waiting for Author".

The patch set is fine. The error is my fault since I attached an
experimental addendum and neglected to name it as .txt. I've set it back to
"needs review" and will resume testing shortly.

---

From: Thomas Munro <[email-masked]>
Date: Thu, 22 Jul 2021 19:30:04 +1200

> comment near the use of the pseudo-typename in the source tree that is

What do you think about something like this?
From 8252eb18c19c8a78fa6326ae5de8261d7d793dda Mon Sep 17 00:00:00 2001
From: Thomas Munro <[email-masked]>
Date: Thu, 22 Jul 2021 19:05:15 +1200
Subject: [PATCH] Teach pgindent about special file-local typenames.

Allow source files to declare an extra typename with a special
annotation of the form:

    @pgindent typename XXX@

Use these to fix some whitespace problems in simplehash.h and
sort_template.h.
---
 src/include/lib/simplehash.h    | 110 +++++++++++++++++---------------
 src/include/lib/sort_template.h |  21 +++---
 src/tools/pgindent/pgindent     |  11 +++-
 3 files changed, 79 insertions(+), 63 deletions(-)

diff --git a/src/include/lib/simplehash.h b/src/include/lib/simplehash.h
index da51781e98..3e44c7cc03 100644
--- a/src/include/lib/simplehash.h
+++ b/src/include/lib/simplehash.h
@@ -86,6 +86,12 @@
  *	  presence is relevant to determine whether a lookup needs to continue
  *	  looking or is done - buckets following a deleted element are shifted
  *	  backwards, unless they're empty or already at their optimal position.
+ *
+ * Help pgindent understand our pseudo-typenames:
+ *
+ *	  @pgindent typename SH_ELEMENT_TYPE@
+ *	  @pgindent typename SH_TYPE@
+ *	  @pgindent typename SH_ITERATOR@
  */
 
 #include "port/pg_bitutils.h"
@@ -164,7 +170,7 @@ typedef struct SH_TYPE
 
 	/* user defined data, useful for callbacks */
 	void	   *private_data;
-}			SH_TYPE;
+} SH_TYPE;
 
 typedef enum SH_STATUS
 {
@@ -177,67 +183,67 @@ typedef struct SH_ITERATOR
 	uint32		cur;			/* current element */
 	uint32		end;
 	bool		done;			/* iterator exhausted? */
-}			SH_ITERATOR;
+} SH_ITERATOR;
 
 /* externally visible function prototypes */
 #ifdef SH_RAW_ALLOCATOR
 /* <prefix>_hash <prefix>_create(uint32 nelements, void *private_data) */
-SH_SCOPE	SH_TYPE *SH_CREATE(uint32 nelements, void *private_data);
+SH_SCOPE SH_TYPE *SH_CREATE(uint32 nelements, void *private_data);
 #else
 /*
  * <prefix>_hash <prefix>_create(MemoryContext ctx, uint32 nelements,
  *								 void *private_data)
  */
-SH_SCOPE	SH_TYPE *SH_CREATE(MemoryContext ctx, uint32 nelements,
-							   void *private_data);
+SH_SCOPE SH_TYPE *SH_CREATE(MemoryContext ctx, uint32 nelements,
+							void *private_data);
 #endif
 
 /* void <prefix>_destroy(<prefix>_hash *tb) */
-SH_SCOPE void SH_DESTROY(SH_TYPE * tb);
+SH_SCOPE void SH_DESTROY(SH_TYPE *tb);
 
 /* void <prefix>_reset(<prefix>_hash *tb) */
-SH_SCOPE void SH_RESET(SH_TYPE * tb);
+SH_SCOPE void SH_RESET(SH_TYPE *tb);
 
 /* void <prefix>_grow(<prefix>_hash *tb) */
-SH_SCOPE void SH_GROW(SH_TYPE * tb, uint32 newsize);
+SH_SCOPE void SH_GROW(SH_TYPE *tb, uint32 newsize);
 
 /* <element> *<prefix>_insert(<prefix>_hash *tb, <key> key, bool *found) */
-SH_SCOPE	SH_ELEMENT_TYPE *SH_INSERT(SH_TYPE * tb, SH_KEY_TYPE key, bool *found);
+SH_SCOPE SH_ELEMENT_TYPE *SH_INSERT(SH_TYPE *tb, SH_KEY_TYPE key, bool *found);
 
 /*
  * <element> *<prefix>_insert_hash(<prefix>_hash *tb, <key> key, uint32 hash,
  * 								  bool *found)
  */
-SH_SCOPE	SH_ELEMENT_TYPE *SH_INSERT_HASH(SH_TYPE * tb, SH_KEY_TYPE key,
-											uint32 hash, bool *found);
+SH_SCOPE SH_ELEMENT_TYPE *SH_INSERT_HASH(SH_TYPE *tb, SH_KEY_TYPE key,
+										 uint32 hash, bool *found);
 
 /* <element> *<prefix>_lookup(<prefix>_hash *tb, <key> key) */
-SH_SCOPE	SH_ELEMENT_TYPE *SH_LOOKUP(SH_TYPE * tb, SH_KEY_TYPE key);
+SH_SCOPE SH_ELEMENT_TYPE *SH_LOOKUP(SH_TYPE *tb, SH_KEY_TYPE key);
 
 /* <element> *<prefix>_lookup_hash(<prefix>_hash *tb, <key> key, uint32 hash) */
-SH_SCOPE	SH_ELEMENT_TYPE *SH_LOOKUP_HASH(SH_TYPE * tb, SH_KEY_TYPE key,
-											uint32 hash);
+SH_SCOPE SH_ELEMENT_TYPE *SH_LOOKUP_HASH(SH_TYPE *tb, SH_KEY_TYPE key,
+										 uint32 hash);
 
 /* void <prefix>_delete_item(<prefix>_hash *tb, <element> *entry) */
-SH_SCOPE void SH_DELETE_ITEM(SH_TYPE * tb, SH_ELEMENT_TYPE * entry);
+SH_SCOPE void SH_DELETE_ITEM(SH_TYPE *tb, SH_ELEMENT_TYPE *entry);
 
 /* bool <prefix>_delete(<prefix>_hash *tb, <key> key) */
-SH_SCOPE bool SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key);
+SH_SCOPE bool SH_DELETE(SH_TYPE *tb, SH_KEY_TYPE key);
 
 /* void <prefix>_start_iterate(<prefix>_hash *tb, <prefix>_iterator *iter) */
-SH_SCOPE void SH_START_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter);
+SH_SCOPE void SH_START_ITERATE(SH_TYPE *tb, SH_ITERATOR *iter);
 
 /*
  * void <prefix>_start_iterate_at(<prefix>_hash *tb, <prefix>_iterator *iter,
  *								  uint32 at)
  */
-SH_SCOPE void SH_START_ITERATE_AT(SH_TYPE * tb, SH_ITERATOR * iter, uint32 at);
+SH_SCOPE void SH_START_ITERATE_AT(SH_TYPE *tb, SH_ITERATOR *iter, uint32 at);
 
 /* <element> *<prefix>_iterate(<prefix>_hash *tb, <prefix>_iterator *iter) */
-SH_SCOPE	SH_ELEMENT_TYPE *SH_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter);
+SH_SCOPE SH_ELEMENT_TYPE *SH_ITERATE(SH_TYPE *tb, SH_ITERATOR *iter);
 
 /* void <prefix>_stat(<prefix>_hash *tb */
-SH_SCOPE void SH_STAT(SH_TYPE * tb);
+SH_SCOPE void SH_STAT(SH_TYPE *tb);
 
 #endif							/* SH_DECLARE */
 
@@ -302,7 +308,7 @@ SH_SCOPE void SH_STAT(SH_TYPE * tb);
  * the hashtable.
  */
 static inline void
-SH_COMPUTE_PARAMETERS(SH_TYPE * tb, uint32 newsize)
+SH_COMPUTE_PARAMETERS(SH_TYPE *tb, uint32 newsize)
 {
 	uint64		size;
 
@@ -340,14 +346,14 @@ SH_COMPUTE_PARAMETERS(SH_TYPE * tb, uint32 newsize)
 
 /* return the optimal bucket for the hash */
 static inline uint32
-SH_INITIAL_BUCKET(SH_TYPE * tb, uint32 hash)
+SH_INITIAL_BUCKET(SH_TYPE *tb, uint32 hash)
 {
 	return hash & tb->sizemask;
 }
 
 /* return next bucket after the current, handling wraparound */
 static inline uint32
-SH_NEXT(SH_TYPE * tb, uint32 curelem, uint32 startelem)
+SH_NEXT(SH_TYPE *tb, uint32 curelem, uint32 startelem)
 {
 	curelem = (curelem + 1) & tb->sizemask;
 
@@ -358,7 +364,7 @@ SH_NEXT(SH_TYPE * tb, uint32 curelem, uint32 startelem)
 
 /* return bucket before the current, handling wraparound */
 static inline uint32
-SH_PREV(SH_TYPE * tb, uint32 curelem, uint32 startelem)
+SH_PREV(SH_TYPE *tb, uint32 curelem, uint32 startelem)
 {
 	curelem = (curelem - 1) & tb->sizemask;
 
@@ -369,7 +375,7 @@ SH_PREV(SH_TYPE * tb, uint32 curelem, uint32 startelem)
 
 /* return distance between bucket and its optimal position */
 static inline uint32
-SH_DISTANCE_FROM_OPTIMAL(SH_TYPE * tb, uint32 optimal, uint32 bucket)
+SH_DISTANCE_FROM_OPTIMAL(SH_TYPE *tb, uint32 optimal, uint32 bucket)
 {
 	if (optimal <= bucket)
 		return bucket - optimal;
@@ -378,7 +384,7 @@ SH_DISTANCE_FROM_OPTIMAL(SH_TYPE * tb, uint32 optimal, uint32 bucket)
 }
 
 static inline uint32
-SH_ENTRY_HASH(SH_TYPE * tb, SH_ELEMENT_TYPE * entry)
+SH_ENTRY_HASH(SH_TYPE *tb, SH_ELEMENT_TYPE *entry)
 {
 #ifdef SH_STORE_HASH
 	return SH_GET_HASH(tb, entry);
@@ -388,14 +394,14 @@ SH_ENTRY_HASH(SH_TYPE * tb, SH_ELEMENT_TYPE * entry)
 }
 
 /* default memory allocator function */
-static inline void *SH_ALLOCATE(SH_TYPE * type, Size size);
-static inline void SH_FREE(SH_TYPE * type, void *pointer);
+static inline void *SH_ALLOCATE(SH_TYPE *type, Size size);
+static inline void SH_FREE(SH_TYPE *type, void *pointer);
 
 #ifndef SH_USE_NONDEFAULT_ALLOCATOR
 
 /* default memory allocator function */
 static inline void *
-SH_ALLOCATE(SH_TYPE * type, Size size)
+SH_ALLOCATE(SH_TYPE *type, Size size)
 {
 #ifdef SH_RAW_ALLOCATOR
 	return SH_RAW_ALLOCATOR(size);
@@ -407,7 +413,7 @@ SH_ALLOCATE(SH_TYPE * type, Size size)
 
 /* default memory free function */
 static inline void
-SH_FREE(SH_TYPE * type, void *pointer)
+SH_FREE(SH_TYPE *type, void *pointer)
 {
 	pfree(pointer);
 }
@@ -424,10 +430,10 @@ SH_FREE(SH_TYPE * type, void *pointer)
  * the passed-in context.
  */
 #ifdef SH_RAW_ALLOCATOR
-SH_SCOPE	SH_TYPE *
+SH_SCOPE SH_TYPE *
 SH_CREATE(uint32 nelements, void *private_data)
 #else
-SH_SCOPE	SH_TYPE *
+SH_SCOPE SH_TYPE *
 SH_CREATE(MemoryContext ctx, uint32 nelements, void *private_data)
 #endif
 {
@@ -454,7 +460,7 @@ SH_CREATE(MemoryContext ctx, uint32 nelements, void *private_data)
 
 /* destroy a previously created hash table */
 SH_SCOPE void
-SH_DESTROY(SH_TYPE * tb)
+SH_DESTROY(SH_TYPE *tb)
 {
 	SH_FREE(tb, tb->data);
 	pfree(tb);
@@ -462,7 +468,7 @@ SH_DESTROY(SH_TYPE * tb)
 
 /* reset the contents of a previously created hash table */
 SH_SCOPE void
-SH_RESET(SH_TYPE * tb)
+SH_RESET(SH_TYPE *tb)
 {
 	memset(tb->data, 0, sizeof(SH_ELEMENT_TYPE) * tb->size);
 	tb->members = 0;
@@ -476,7 +482,7 @@ SH_RESET(SH_TYPE * tb)
  * performance-wise, when known at some point.
  */
 SH_SCOPE void
-SH_GROW(SH_TYPE * tb, uint32 newsize)
+SH_GROW(SH_TYPE *tb, uint32 newsize)
 {
 	uint64		oldsize = tb->size;
 	SH_ELEMENT_TYPE *olddata = tb->data;
@@ -586,7 +592,7 @@ SH_GROW(SH_TYPE * tb, uint32 newsize)
  * into its wrapper functions even if SH_SCOPE is extern.
  */
 static inline SH_ELEMENT_TYPE *
-SH_INSERT_HASH_INTERNAL(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash, bool *found)
+SH_INSERT_HASH_INTERNAL(SH_TYPE *tb, SH_KEY_TYPE key, uint32 hash, bool *found)
 {
 	uint32		startelem;
 	uint32		curelem;
@@ -756,8 +762,8 @@ restart:
  * already exists, false otherwise. Returns the hash-table entry in either
  * case.
  */
-SH_SCOPE	SH_ELEMENT_TYPE *
-SH_INSERT(SH_TYPE * tb, SH_KEY_TYPE key, bool *found)
+SH_SCOPE SH_ELEMENT_TYPE *
+SH_INSERT(SH_TYPE *tb, SH_KEY_TYPE key, bool *found)
 {
 	uint32		hash = SH_HASH_KEY(tb, key);
 
@@ -769,8 +775,8 @@ SH_INSERT(SH_TYPE * tb, SH_KEY_TYPE key, bool *found)
  * hash. Set *found to true if the key already exists, false
  * otherwise. Returns the hash-table entry in either case.
  */
-SH_SCOPE	SH_ELEMENT_TYPE *
-SH_INSERT_HASH(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash, bool *found)
+SH_SCOPE SH_ELEMENT_TYPE *
+SH_INSERT_HASH(SH_TYPE *tb, SH_KEY_TYPE key, uint32 hash, bool *found)
 {
 	return SH_INSERT_HASH_INTERNAL(tb, key, hash, found);
 }
@@ -780,7 +786,7 @@ SH_INSERT_HASH(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash, bool *found)
  * into its wrapper functions even if SH_SCOPE is extern.
  */
 static inline SH_ELEMENT_TYPE *
-SH_LOOKUP_HASH_INTERNAL(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash)
+SH_LOOKUP_HASH_INTERNAL(SH_TYPE *tb, SH_KEY_TYPE key, uint32 hash)
 {
 	const uint32 startelem = SH_INITIAL_BUCKET(tb, hash);
 	uint32		curelem = startelem;
@@ -813,8 +819,8 @@ SH_LOOKUP_HASH_INTERNAL(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash)
 /*
  * Lookup up entry in hash table.  Returns NULL if key not present.
  */
-SH_SCOPE	SH_ELEMENT_TYPE *
-SH_LOOKUP(SH_TYPE * tb, SH_KEY_TYPE key)
+SH_SCOPE SH_ELEMENT_TYPE *
+SH_LOOKUP(SH_TYPE *tb, SH_KEY_TYPE key)
 {
 	uint32		hash = SH_HASH_KEY(tb, key);
 
@@ -826,8 +832,8 @@ SH_LOOKUP(SH_TYPE * tb, SH_KEY_TYPE key)
  *
  * Returns NULL if key not present.
  */
-SH_SCOPE	SH_ELEMENT_TYPE *
-SH_LOOKUP_HASH(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash)
+SH_SCOPE SH_ELEMENT_TYPE *
+SH_LOOKUP_HASH(SH_TYPE *tb, SH_KEY_TYPE key, uint32 hash)
 {
 	return SH_LOOKUP_HASH_INTERNAL(tb, key, hash);
 }
@@ -837,7 +843,7 @@ SH_LOOKUP_HASH(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash)
  * present.
  */
 SH_SCOPE bool
-SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key)
+SH_DELETE(SH_TYPE *tb, SH_KEY_TYPE key)
 {
 	uint32		hash = SH_HASH_KEY(tb, key);
 	uint32		startelem = SH_INITIAL_BUCKET(tb, hash);
@@ -908,7 +914,7 @@ SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key)
  * Delete entry from hash table by entry pointer
  */
 SH_SCOPE void
-SH_DELETE_ITEM(SH_TYPE * tb, SH_ELEMENT_TYPE * entry)
+SH_DELETE_ITEM(SH_TYPE *tb, SH_ELEMENT_TYPE *entry)
 {
 	SH_ELEMENT_TYPE *lastentry = entry;
 	uint32		hash = SH_ENTRY_HASH(tb, entry);
@@ -963,7 +969,7 @@ SH_DELETE_ITEM(SH_TYPE * tb, SH_ELEMENT_TYPE * entry)
  * Initialize iterator.
  */
 SH_SCOPE void
-SH_START_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter)
+SH_START_ITERATE(SH_TYPE *tb, SH_ITERATOR *iter)
 {
 	int			i;
 	uint64		startelem = PG_UINT64_MAX;
@@ -1003,7 +1009,7 @@ SH_START_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter)
  * same position.
  */
 SH_SCOPE void
-SH_START_ITERATE_AT(SH_TYPE * tb, SH_ITERATOR * iter, uint32 at)
+SH_START_ITERATE_AT(SH_TYPE *tb, SH_ITERATOR *iter, uint32 at)
 {
 	/*
 	 * Iterate backwards, that allows the current element to be deleted, even
@@ -1024,8 +1030,8 @@ SH_START_ITERATE_AT(SH_TYPE * tb, SH_ITERATOR * iter, uint32 at)
  * deletions), but if so, there's neither a guarantee that all nodes are
  * visited at least once, nor a guarantee that a node is visited at most once.
  */
-SH_SCOPE	SH_ELEMENT_TYPE *
-SH_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter)
+SH_SCOPE SH_ELEMENT_TYPE *
+SH_ITERATE(SH_TYPE *tb, SH_ITERATOR *iter)
 {
 	while (!iter->done)
 	{
@@ -1052,7 +1058,7 @@ SH_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter)
  * debugging/profiling purposes only.
  */
 SH_SCOPE void
-SH_STAT(SH_TYPE * tb)
+SH_STAT(SH_TYPE *tb)
 {
 	uint32		max_chain_length = 0;
 	uint32		total_chain_length = 0;
diff --git a/src/include/lib/sort_template.h b/src/include/lib/sort_template.h
index f52627d8ce..cb9d9bf449 100644
--- a/src/include/lib/sort_template.h
+++ b/src/include/lib/sort_template.h
@@ -52,6 +52,11 @@
  *	  int (*)(const ST_ELEMENT_TYPE *a, const ST_ELEMENT_TYPE *b,
  *			  [ST_COMPARE_ARG_TYPE *arg])
  *
+ * 	  Help pgindent understand our pseudo-typenames:
+ *
+ *		@pgindent typename ST_ELEMENT_TYPE@
+ *		@pgindent typename ST_POINTER_TYPE@
+ *
  * HISTORY
  *
  *	  Modifications from vanilla NetBSD source:
@@ -176,11 +181,11 @@
 
 #ifdef ST_COMPARE_RUNTIME_POINTER
 typedef int (*ST_COMPARATOR_TYPE_NAME) (const ST_ELEMENT_TYPE *,
-										const ST_ELEMENT_TYPE * ST_SORT_PROTO_ARG);
+										const ST_ELEMENT_TYPE *ST_SORT_PROTO_ARG);
 #endif
 
 /* Declare the sort function.  Note optional arguments at end. */
-ST_SCOPE void ST_SORT(ST_ELEMENT_TYPE * first, size_t n
+ST_SCOPE void ST_SORT(ST_ELEMENT_TYPE *first, size_t n
 					  ST_SORT_PROTO_ELEMENT_SIZE
 					  ST_SORT_PROTO_COMPARE
 					  ST_SORT_PROTO_ARG);
@@ -245,9 +250,9 @@ ST_SCOPE void ST_SORT(ST_ELEMENT_TYPE * first, size_t n
  * in the qsort function.
  */
 static pg_noinline ST_ELEMENT_TYPE *
-ST_MED3(ST_ELEMENT_TYPE * a,
-		ST_ELEMENT_TYPE * b,
-		ST_ELEMENT_TYPE * c
+ST_MED3(ST_ELEMENT_TYPE *a,
+		ST_ELEMENT_TYPE *b,
+		ST_ELEMENT_TYPE *c
 		ST_SORT_PROTO_COMPARE
 		ST_SORT_PROTO_ARG)
 {
@@ -257,7 +262,7 @@ ST_MED3(ST_ELEMENT_TYPE * a,
 }
 
 static inline void
-ST_SWAP(ST_POINTER_TYPE * a, ST_POINTER_TYPE * b)
+ST_SWAP(ST_POINTER_TYPE *a, ST_POINTER_TYPE *b)
 {
 	ST_POINTER_TYPE tmp = *a;
 
@@ -266,7 +271,7 @@ ST_SWAP(ST_POINTER_TYPE * a, ST_POINTER_TYPE * b)
 }
 
 static inline void
-ST_SWAPN(ST_POINTER_TYPE * a, ST_POINTER_TYPE * b, size_t n)
+ST_SWAPN(ST_POINTER_TYPE *a, ST_POINTER_TYPE *b, size_t n)
 {
 	for (size_t i = 0; i < n; ++i)
 		ST_SWAP(&a[i], &b[i]);
@@ -276,7 +281,7 @@ ST_SWAPN(ST_POINTER_TYPE * a, ST_POINTER_TYPE * b, size_t n)
  * Sort an array.
  */
 ST_SCOPE void
-ST_SORT(ST_ELEMENT_TYPE * data, size_t n
+ST_SORT(ST_ELEMENT_TYPE *data, size_t n
 		ST_SORT_PROTO_ELEMENT_SIZE
 		ST_SORT_PROTO_COMPARE
 		ST_SORT_PROTO_ARG)
diff --git a/src/tools/pgindent/pgindent b/src/tools/pgindent/pgindent
index f8190b6c35..2d62245648 100755
--- a/src/tools/pgindent/pgindent
+++ b/src/tools/pgindent/pgindent
@@ -56,9 +56,8 @@ $excludes ||= "$code_base/src/tools/pgindent/exclude_file_patterns"
 # some names we want to treat like typedefs, e.g. "bool" (which is a macro
 # according to <stdbool.h>), and may include some names we don't want
 # treated as typedefs, although various headers that some builds include
-# might make them so.  For the moment we just hardwire a list of names
-# to add and a list of names to exclude; eventually this may need to be
-# easier to configure.  Note that the typedefs need trailing newlines.
+# might make them so.  Extra items can be added within individual source files
+# with special annotation comments; see run_indent.
 my @additional = ("bool\n");
 
 my %excluded = map { +"$_\n" => 1 } qw(
@@ -264,6 +263,12 @@ sub run_indent
 
 	my $cmd = "$indent $indent_opts -U" . $filtered_typedefs_fh->filename;
 
+	# add file-local typenames in inline annotations
+	foreach ($source =~ /\@pgindent typename (\w+)\@/g)
+	{
+		$cmd .= " -T'$_'";
+	}
+
 	my $tmp_fh = new File::Temp(TEMPLATE => "pgsrcXXXXX");
 	my $filename = $tmp_fh->filename;
 	print $tmp_fh $source;
-- 
2.30.2

---

From: John Naylor <[email-masked]>
Date: Thu, 29 Jul 2021 20:34:01 -0400

> recognise qualifying users of those and select 3 corresponding sort

I got around to getting a benchmark together to serve as a starting point.
I based it off something I got from the archives, but don't remember where
(I seem to remember Tomas Vondra wrote the original, but not sure). To
start I just used types that were there already -- int, text, numeric. The
latter two won't be helped by this patch, but I wanted to keep something
like that so we can see what kind of noise variation there is. I'll
probably cut text out in the future and just keep numeric for that purpose.

I've attached both the script and a crude spreadsheet. I'll try to figure
out something nicer for future tests, and maybe some graphs. The
"comparison" sheet has the results side by side (min of five). There are 6
distributions of values:
- random
- sorted
- "almost sorted"
- reversed
- organ pipe (first half ascending, second half descending)
- rotated (sorted but then put the smallest at the end)
- random 0s/1s

I included both "select a" and "select *" to make sure we have the recent
datum sort optimization represented. The results look pretty good for ints
-- about the same speed up master gets going from tuple sorts to datum
sorts, and those got faster in turn also.

Next I think I'll run microbenchmarks on int64s with the test harness you
attached earlier, and experiment with the qsort parameters a bit.

I'm also attaching your tuplesort patch so others can see what exactly I'm
comparing.

---

From: Peter Geoghegan <[email-masked]>
Date: Fri, 30 Jul 2021 10:10:49 +0300

On Fri, Jul 30, 2021 at 3:34 AM John Naylor
<[email-masked]> wrote:
> I'm also attaching your tuplesort patch so others can see what exactly I'm comparing.

If you're going to specialize the sort routine for unsigned integer
style abbreviated keys then you might as well cover all relevant
opclasses/types. Almost all abbreviated key schemes produce
conditioned datums that are designed to use simple 3-way unsigned int
comparator. It's not just text. (Actually, the only abbreviated key
scheme that doesn't do it that way is numeric.)

Offhand I know that UUID, macaddr, and inet all have abbreviated keys
that can use your new ssup_datum_binary_cmp() comparator instead of
their own duplicated comparator (which will make them use the
corresponding specialized sort routine inside tuplesort.c).

-- 
Peter Geoghegan

---

From: Ranier Vilela <[email-masked]>
Date: Fri, 30 Jul 2021 08:47:18 -0300

> I'm also attaching your tuplesort patch so others can see what exactly I'm
The patch attached does not apply cleanly,
please can fix it?

error: patch failed: src/backend/utils/sort/tuplesort.c:4776
error: src/backend/utils/sort/tuplesort.c: patch does not apply

regards,
Ranier Vilela

---

From: John Naylor <[email-masked]>
Date: Fri, 30 Jul 2021 10:53:58 -0400

> The patch attached does not apply cleanly,

It applies just fine with "patch", for those wondering.

---

From: Thomas Munro <[email-masked]>
Date: Mon, 2 Aug 2021 12:01:33 +1200

> scheme that doesn't do it that way is numeric.)

Right, that was the plan, but this was just experimenting with an
idea.  Looks like John's also seeing evidence that it may be worth
pursuing.

(Re numeric, I guess it must be possible to rearrange things so it can
use ssup_datum_signed_cmp; maybe something like NaN -> INT64_MAX, +inf
-> INT64_MAX - 1, -inf -> INT64_MIN, and then -1 - (whatever we're
doing now for normal values).)

> corresponding specialized sort routine inside tuplesort.c).

Thanks, I've added these ones, and also gist_bbox_zorder_cmp_abbrev.

I also renamed that function to ssup_datum_unsigned_cmp(), because
"binary" was misleading.
From a1ca8e9ca989de5f61f1b8f067cb9785034ce9cc Mon Sep 17 00:00:00 2001
From: Thomas Munro <[email-masked]>
Date: Sat, 3 Jul 2021 19:02:10 +1200
Subject: [PATCH v3] WIP: Accelerate tuple sorting for common types.

XXX WIP, experiment grade only, many open questions... such as:

XXX Can we avoid repeating the null-handling logic?
XXX Is it worth specializing for reverse sort?
XXX Is it worth specializing for nulls first, nulls last, not null?
XXX Should we have separate cases for "result is authoritative", "need
XXX tiebreaker for atts 1..n (= abbrev case)", "need tie breaker for
XXX atts 2..n"?
XXX If we did all of the above, that'd give:
XXX  {nulls_first, nulls_last, not_null} x
XXX  {asc, desc} x
XXX  {tiebreak_none, tiebreak_first, tiebreak_rest} x
XXX  {unsigned, signed, int32}
XXX  = 54 specializations!  Seems a little over the top.
XXX You could use a smaller SortTuple for some cases.
XXX How should we handle numeric?
---
 src/backend/access/gist/gistproc.c     |  18 +--
 src/backend/access/nbtree/nbtcompare.c |  22 ++--
 src/backend/utils/adt/date.c           |  15 +--
 src/backend/utils/adt/mac.c            |  23 +---
 src/backend/utils/adt/network.c        |  17 +--
 src/backend/utils/adt/timestamp.c      |  11 ++
 src/backend/utils/adt/uuid.c           |  25 +---
 src/backend/utils/adt/varlena.c        |  34 +-----
 src/backend/utils/sort/tuplesort.c     | 160 ++++++++++++++++++++++++-
 src/include/utils/sortsupport.h        | 115 ++++++++++++++++++
 10 files changed, 308 insertions(+), 132 deletions(-)

diff --git a/src/backend/access/gist/gistproc.c b/src/backend/access/gist/gistproc.c
index d474612b77..20135ea0ec 100644
--- a/src/backend/access/gist/gistproc.c
+++ b/src/backend/access/gist/gistproc.c
@@ -37,7 +37,6 @@ static uint64 part_bits32_by2(uint32 x);
 static uint32 ieee_float32_to_uint32(float f);
 static int	gist_bbox_zorder_cmp(Datum a, Datum b, SortSupport ssup);
 static Datum gist_bbox_zorder_abbrev_convert(Datum original, SortSupport ssup);
-static int	gist_bbox_zorder_cmp_abbrev(Datum z1, Datum z2, SortSupport ssup);
 static bool gist_bbox_zorder_abbrev_abort(int memtupcount, SortSupport ssup);

@@ -1726,21 +1725,6 @@ gist_bbox_zorder_abbrev_convert(Datum original, SortSupport ssup)
 #endif
 }
 
-static int
-gist_bbox_zorder_cmp_abbrev(Datum z1, Datum z2, SortSupport ssup)
-{
-	/*
-	 * Compare the pre-computed Z-orders as unsigned integers. Datum is a
-	 * typedef for 'uintptr_t', so no casting is required.
-	 */
-	if (z1 > z2)
-		return 1;
-	else if (z1 < z2)
-		return -1;
-	else
-		return 0;
-}
-
 /*
  * We never consider aborting the abbreviation.
  *
@@ -1764,7 +1748,7 @@ gist_point_sortsupport(PG_FUNCTION_ARGS)
 
 	if (ssup->abbreviate)
 	{
-		ssup->comparator = gist_bbox_zorder_cmp_abbrev;
+		ssup->comparator = ssup_datum_unsigned_cmp;
 		ssup->abbrev_converter = gist_bbox_zorder_abbrev_convert;
 		ssup->abbrev_abort = gist_bbox_zorder_abbrev_abort;
 		ssup->abbrev_full_comparator = gist_bbox_zorder_cmp;
diff --git a/src/backend/access/nbtree/nbtcompare.c b/src/backend/access/nbtree/nbtcompare.c
index 7ac73cb8c2..204cf778fb 100644
--- a/src/backend/access/nbtree/nbtcompare.c
+++ b/src/backend/access/nbtree/nbtcompare.c
@@ -119,26 +119,12 @@ btint4cmp(PG_FUNCTION_ARGS)
 		PG_RETURN_INT32(A_LESS_THAN_B);
 }
 
-static int

 
 
 Datum
 
+#ifdef USE_FLOAT8_BYVAL

-static int

diff --git a/src/backend/utils/adt/mac.c b/src/backend/utils/adt/mac.c
index 844d8814e6..9016c6bf94 100644
--- a/src/backend/utils/adt/mac.c
+++ b/src/backend/utils/adt/mac.c
@@ -44,7 +44,6 @@ typedef struct
 
 static int	macaddr_cmp_internal(macaddr *a1, macaddr *a2);
 static int	macaddr_fast_cmp(Datum x, Datum y, SortSupport ssup);
-static int	macaddr_cmp_abbrev(Datum x, Datum y, SortSupport ssup);
 static bool macaddr_abbrev_abort(int memtupcount, SortSupport ssup);
 static Datum macaddr_abbrev_convert(Datum original, SortSupport ssup);
 
@@ -381,7 +380,7 @@ macaddr_sortsupport(PG_FUNCTION_ARGS)
 
 		ssup->ssup_extra = uss;
 
-		ssup->comparator = macaddr_cmp_abbrev;
+		ssup->comparator = ssup_datum_unsigned_cmp;
 		ssup->abbrev_converter = macaddr_abbrev_convert;
 		ssup->abbrev_abort = macaddr_abbrev_abort;
 		ssup->abbrev_full_comparator = macaddr_fast_cmp;
@@ -405,22 +404,6 @@ macaddr_fast_cmp(Datum x, Datum y, SortSupport ssup)
 	return macaddr_cmp_internal(arg1, arg2);
 }
 
-/*
- * SortSupport abbreviated key comparison function. Compares two MAC addresses
- * quickly by treating them like integers, and without having to go to the
- * heap.
- */
-static int
-macaddr_cmp_abbrev(Datum x, Datum y, SortSupport ssup)
-{
-	if (x > y)
-		return 1;
-	else if (x == y)
-		return 0;
-	else
-		return -1;
-}
-
 /*
  * Callback for estimating effectiveness of abbreviated key optimization.
  *
@@ -537,8 +520,8 @@ macaddr_abbrev_convert(Datum original, SortSupport ssup)
 	/*
 	 * Byteswap on little-endian machines.
 	 *
-	 * This is needed so that macaddr_cmp_abbrev() (an unsigned integer 3-way
-	 * comparator) works correctly on all platforms. Without this, the
+	 * This is needed so that ssup_datum_unsigned_cmp() (an unsigned integer
+	 * 3-way comparator) works correctly on all platforms. Without this, the
 	 * comparator would have to call memcmp() with a pair of pointers to the
 	 * first byte of each abbreviated key, which is slower.
 	 */
diff --git a/src/backend/utils/adt/network.c b/src/backend/utils/adt/network.c
index 0ab54316f8..ea1c7390d0 100644
--- a/src/backend/utils/adt/network.c
+++ b/src/backend/utils/adt/network.c
@@ -53,7 +53,6 @@ typedef struct
 
 static int32 network_cmp_internal(inet *a1, inet *a2);
 static int	network_fast_cmp(Datum x, Datum y, SortSupport ssup);
-static int	network_cmp_abbrev(Datum x, Datum y, SortSupport ssup);
 static bool network_abbrev_abort(int memtupcount, SortSupport ssup);
 static Datum network_abbrev_convert(Datum original, SortSupport ssup);
 static List *match_network_function(Node *leftop,
@@ -456,7 +455,7 @@ network_sortsupport(PG_FUNCTION_ARGS)
 
 		ssup->ssup_extra = uss;
 
-		ssup->comparator = network_cmp_abbrev;
+		ssup->comparator = ssup_datum_unsigned_cmp;
 		ssup->abbrev_converter = network_abbrev_convert;
 		ssup->abbrev_abort = network_abbrev_abort;
 		ssup->abbrev_full_comparator = network_fast_cmp;
@@ -479,20 +478,6 @@ network_fast_cmp(Datum x, Datum y, SortSupport ssup)
 	return network_cmp_internal(arg1, arg2);
 }
 
-/*
- * Abbreviated key comparison func
- */
-static int
-network_cmp_abbrev(Datum x, Datum y, SortSupport ssup)
-{
-	if (x > y)
-		return 1;
-	else if (x == y)
-		return 0;
-	else
-		return -1;
-}
-
 /*
  * Callback for estimating effectiveness of abbreviated key optimization.
  *
diff --git a/src/backend/utils/adt/timestamp.c b/src/backend/utils/adt/timestamp.c
index 1c0bf0aa5c..410b39b44e 100644
--- a/src/backend/utils/adt/timestamp.c
+++ b/src/backend/utils/adt/timestamp.c
@@ -37,6 +37,7 @@
 #include "utils/datetime.h"
 #include "utils/float.h"
 #include "utils/numeric.h"
+#include "utils/sortsupport.h"
 
 /*

 
 Datum
 
+#ifdef USE_FLOAT8_BYVAL
+	/*
 
diff --git a/src/backend/utils/adt/uuid.c b/src/backend/utils/adt/uuid.c
index b02c9fcf98..eaf0a6bbdf 100644
--- a/src/backend/utils/adt/uuid.c
+++ b/src/backend/utils/adt/uuid.c
@@ -34,7 +34,6 @@ typedef struct
 static void string_to_uuid(const char *source, pg_uuid_t *uuid);
 static int	uuid_internal_cmp(const pg_uuid_t *arg1, const pg_uuid_t *arg2);
 static int	uuid_fast_cmp(Datum x, Datum y, SortSupport ssup);
-static int	uuid_cmp_abbrev(Datum x, Datum y, SortSupport ssup);
 static bool uuid_abbrev_abort(int memtupcount, SortSupport ssup);
 static Datum uuid_abbrev_convert(Datum original, SortSupport ssup);
 
@@ -255,7 +254,7 @@ uuid_sortsupport(PG_FUNCTION_ARGS)
 
 		ssup->ssup_extra = uss;
 
-		ssup->comparator = uuid_cmp_abbrev;
+		ssup->comparator = ssup_datum_unsigned_cmp;
 		ssup->abbrev_converter = uuid_abbrev_convert;
 		ssup->abbrev_abort = uuid_abbrev_abort;
 		ssup->abbrev_full_comparator = uuid_fast_cmp;
@@ -278,20 +277,6 @@ uuid_fast_cmp(Datum x, Datum y, SortSupport ssup)
 	return uuid_internal_cmp(arg1, arg2);
 }
 
-/*
- * Abbreviated key comparison func
- */
-static int
-uuid_cmp_abbrev(Datum x, Datum y, SortSupport ssup)
-{
-	if (x > y)
-		return 1;
-	else if (x == y)
-		return 0;
-	else
-		return -1;
-}
-
 /*
  * Callback for estimating effectiveness of abbreviated key optimization.
  *
@@ -390,10 +375,10 @@ uuid_abbrev_convert(Datum original, SortSupport ssup)
 	/*
 	 * Byteswap on little-endian machines.
 	 *
-	 * This is needed so that uuid_cmp_abbrev() (an unsigned integer 3-way
-	 * comparator) works correctly on all platforms.  If we didn't do this,
-	 * the comparator would have to call memcmp() with a pair of pointers to
-	 * the first byte of each abbreviated key, which is slower.
+	 * This is needed so that ssup_datum_unsigned_cmp() (an unsigned integer
+	 * 3-way comparator) works correctly on all platforms.  If we didn't do
+	 * this, the comparator would have to call memcmp() with a pair of pointers
+	 * to the first byte of each abbreviated key, which is slower.
 	 */
 	res = DatumBigEndianToNative(res);
 
index d2a11b1b5d..0a91de6992 100644
+			ssup->comparator = ssup_datum_unsigned_cmp;
 
-/*
- * Abbreviated key comparison func
- */
-static int
-varstrcmp_abbrev(Datum x, Datum y, SortSupport ssup)
-{
-	/*
-	 * When 0 is returned, the core system will call varstrfastcmp_c()
-	 * (bpcharfastcmp_c() in BpChar case) or varlenafastcmp_locale().  Even a
-	 * strcmp() on two non-truncated strxfrm() blobs cannot indicate *equality*
-	 * authoritatively, for the same reason that there is a strcoll()
-	 * tie-breaker call to strcmp() in varstr_cmp().
-	 */
-	if (x > y)
-		return 1;
-	else if (x == y)
-		return 0;
-	else
-		return -1;
-}
-
 /*
  * Conversion routine for sortsupport.  Converts original to abbreviated key
  * representation.  Our encoding strategy is simple -- pack the first 8 bytes
@@ -2520,7 +2498,7 @@ varstr_abbrev_convert(Datum original, SortSupport ssup)
 	 * strings may contain NUL bytes.  Besides, this should be faster, too.
 	 *
 	 * More generally, it's okay that bytea callers can have NUL bytes in
-	 * strings because varstrcmp_abbrev() need not make a distinction between
+	 * strings because abbreviated cmp need not make a distinction between
 	 * terminating NUL bytes, and NUL bytes representing actual NULs in the
 	 * authoritative representation.  Hopefully a comparison at or past one
 	 * abbreviated key's terminating NUL byte will resolve the comparison
@@ -2710,10 +2688,10 @@ done:
 	/*
 	 * Byteswap on little-endian machines.
 	 *
-	 * This is needed so that varstrcmp_abbrev() (an unsigned integer 3-way
-	 * comparator) works correctly on all platforms.  If we didn't do this,
-	 * the comparator would have to call memcmp() with a pair of pointers to
-	 * the first byte of each abbreviated key, which is slower.
+	 * This is needed so that ssup_datum_unsigned_cmp() (an unsigned integer
+	 * 3-way comparator) works correctly on all platforms.  If we didn't do
+	 * this, the comparator would have to call memcmp() with a pair of pointers
+	 * to the first byte of each abbreviated key, which is slower.
 	 */
 	res = DatumBigEndianToNative(res);
 
index b17347b214..32cd072c82 100644
 
+/*
+/* Used if first key's comparator is ssup_datum_unsigned_compare */
+qsort_tuple_unsigned_compare(SortTuple *a, SortTuple *b, Tuplesortstate *state)
+	compare = ApplyUnsignedSortComparator(a->datum1, a->isnull1,
+ * and Datum sorts.  qsort_tuple_{unsigned,signed,int32} are specialized for
 
+#define ST_SORT qsort_tuple_unsigned
+#define ST_ELEMENT_TYPE SortTuple
+#define ST_COMPARE(a, b, state) qsort_tuple_unsigned_compare(a, b, state)
+#define ST_COMPARE_ARG_TYPE Tuplesortstate
+#define ST_CHECK_FOR_INTERRUPTS
+#define ST_SCOPE static
+#define ST_DEFINE
+#include "lib/sort_template.h"
+
+#define ST_SORT qsort_tuple_signed
+#define ST_ELEMENT_TYPE SortTuple
+#define ST_COMPARE(a, b, state) qsort_tuple_signed_compare(a, b, state)
+#define ST_COMPARE_ARG_TYPE Tuplesortstate
+#define ST_CHECK_FOR_INTERRUPTS
+#define ST_SCOPE static
+#define ST_DEFINE
+#include "lib/sort_template.h"
+
+#define ST_SORT qsort_tuple_int32
+#define ST_ELEMENT_TYPE SortTuple
+#define ST_COMPARE(a, b, state) qsort_tuple_int32_compare(a, b, state)
+#define ST_COMPARE_ARG_TYPE Tuplesortstate
+#define ST_CHECK_FOR_INTERRUPTS
+#define ST_SCOPE static
+#define ST_DEFINE
+#include "lib/sort_template.h"
+
 #define ST_SORT qsort_tuple
 #define ST_ELEMENT_TYPE SortTuple
 #define ST_COMPARE_RUNTIME_POINTER
@@ -3558,15 +3645,40 @@ tuplesort_sort_memtuples(Tuplesortstate *state)
 
+			state->sortKeys[0].comparator == ssup_datum_unsigned_cmp)
+			elog(DEBUG1, "qsort_tuple_unsigned");
+			qsort_tuple_unsigned(state->memtuples, state->memtupcount, state);
 
@@ -4780,3 +4892,47 @@ free_sort_tuple(Tuplesortstate *state, SortTuple *stup)
 		stup->tuple = NULL;
 	}
 }
+
+int
+ssup_datum_unsigned_cmp(Datum x, Datum y, SortSupport ssup)
+{
+	if (x < y)
+		return -1;
+	else if (x > y)
+		return 1;
+	else
+		return 0;
+}
+
+int
+ssup_datum_signed_cmp(Datum x, Datum y, SortSupport ssup)
+{
+#if SIZEOF_DATUM == 8
+	int64		xx = (int64) x;
+	int64		yy = (int64) y;
+#else
+	int32		xx = (int32) x;
+	int32		yy = (int32) y;
+#endif
+
+	if (xx < yy)
+		return -1;
+	else if (xx > yy)
+		return 1;
+	else
+		return 0;
+}
+
+int
+ssup_datum_int32_cmp(Datum x, Datum y, SortSupport ssup)
+{
+	int32		xx = (int32) x;
+	int32		yy = (int32) y;
+
+	if (xx < yy)
+		return -1;
+	else if (xx > yy)
+		return 1;
+	else
+		return 0;
+}
diff --git a/src/include/utils/sortsupport.h b/src/include/utils/sortsupport.h
index 2f12a8b8eb..99eac089b3 100644
--- a/src/include/utils/sortsupport.h
+++ b/src/include/utils/sortsupport.h
@@ -229,6 +229,112 @@ ApplySortComparator(Datum datum1, bool isNull1,
 	return compare;
 }
 
+static inline int
+ApplyUnsignedSortComparator(Datum datum1, bool isNull1,
 
+/*
+extern int ssup_datum_unsigned_cmp(Datum x, Datum y, SortSupport ssup);

---

From: Thomas Munro <[email-masked]>
Date: Mon, 2 Aug 2021 12:40:32 +1200

On Fri, Jul 30, 2021 at 12:34 PM John Naylor
<[email-masked]> wrote:
> I got around to getting a benchmark together to serve as a starting point. I based it off something I got from the archives, but don't remember where (I seem to remember Tomas Vondra wrote the original, but not sure). To start I just used types that were there already -- int, text, numeric. The latter two won't be helped by this patch, but I wanted to keep something like that so we can see what kind of noise variation there is. I'll probably cut text out in the future and just keep numeric for that purpose.

Thanks, that's very useful.

> I've attached both the script and a crude spreadsheet. I'll try to figure out something nicer for future tests, and maybe some graphs. The "comparison" sheet has the results side by side (min of five). There are 6 distributions of values:
> - random
> - sorted
> - "almost sorted"
> - reversed
> I included both "select a" and "select *" to make sure we have the recent datum sort optimization represented. The results look pretty good for ints -- about the same speed up master gets going from tuple sorts to datum sorts, and those got faster in turn also.

Great!  I saw similar sorts of numbers.  It's really just a few
crumbs, nothing compared to the gains David just found over in the
thread "Use generation context to speed up tuplesorts", but on the
bright side, these crumbs will be magnified by that work.

> Next I think I'll run microbenchmarks on int64s with the test harness you attached earlier, and experiment with the qsort parameters a bit.

Cool.  I haven't had much luck experimenting with that yet, though I
consider the promotion from magic numbers to names as an improvement
in any case.

> I'm also attaching your tuplesort patch so others can see what exactly I'm comparing.

We've been bouncing around quite a few different ideas and patches in
this thread; soon I'll try to bring it back to one patch set with the
ideas that are looking good so far in a more tidied up form.  For the
tupesort.c part, I added some TODO notes in
v3-0001-WIP-Accelerate-tuple-sorting-for-common-types.patch's commit
message (see reply to Peter).

---

From: Thomas Munro <[email-masked]>
Date: Mon, 2 Aug 2021 12:42:54 +1200

> bright side, these crumbs will be magnified by that work.

(Hmm, that also makes me wonder about using a smaller SortTuple when
possible...)

---

From: Peter Geoghegan <[email-masked]>
Date: Thu, 5 Aug 2021 16:18:41 -0700

> Thanks, that's very useful.

If somebody wants to get a sense of what the size hit is from all of
these specializations, I can recommend the diff feature of bloaty:

https://github.com/google/bloaty/blob/master/doc/using.md#size-diffs

Obviously you'd approach this by building postgres without the patch,
and diffing that baseline to postgres with the patch. And possibly
variations of the patch, with less or more sort specializations.

-- 
Peter Geoghegan

---

From: John Naylor <[email-masked]>
Date: Thu, 31 Mar 2022 17:09:15 +0700

In a couple days I'm going to commit the v3 patch "accelerate tuple
sorting for common types" as-is after giving it one more look, barring
objections.

I started towards incorporating the change in insertion sort threshold
(part of 0010), but that caused regression test failures, so that will
have to wait for a bit of analysis and retesting. (My earlier tests
were done in a separate module.)

The rest in this series that I looked at closely were either
refactoring or could use some minor tweaks so likely v16 material.

---

From: Thomas Munro <[email-masked]>
Date: Fri, 1 Apr 2022 10:42:59 +1300

Hi John,

Thanks so much for all the work you've done here!  I feel bad that I
lobbed so many experimental patches in here and then ran away due to
lack of cycles.  That particular patch (the one cfbot has been chewing
on all this time) does indeed seem committable, despite the
deficiencies/opportunities listed in comments.  It's nice to reduce
code duplication, it gives the right answers, and it goes faster.

> refactoring or could use some minor tweaks so likely v16 material.

Looking forward to it.