Specialize intarray sorting

There is at least one report in the field of storing millions of
integers in arrays, so it seems like a good time to specialize
intarray's qsort function. In doing so, streamline the comparators:
Previously there were three, two for each direction for sorting
and one passed to qunique_arg. To preserve the early exit in the
case of descending input, pass the direction as an argument to
the comparator. This requires giving up duplicate detection, which
previously allowed skipping the qunique_arg() call. Testing showed
no regressions this way.

In passing, get rid of nearby checks that the input has at least
two elements, since preserving them would make some macros less
readable. These are not necessary for correctness, and seem like
premature optimizations.

Author: Andrey M. Borodin <x4mmm@yandex-team.ru>
Discussion: https://postgr.es/m/098A3E67-E4A6-4086-9C66-B1EAEB1DFE1C@yandex-team.ru

1 files changed, 26 insertions, 36 deletions

diff --git a/contrib/intarray/_int_tool.c b/contrib/intarray/_int_tool.c
index c85280c8422..0d0cdc289cd 100644
--- a/contrib/intarray/_int_tool.c
+++ b/contrib/intarray/_int_tool.c
@@ -186,36 +186,38 @@ rt__int_size(ArrayType *a, float *size)
 	*size = (float) ARRNELEMS(a);
 }
 
-/* qsort_arg comparison function for isort() */
-static int
+/* comparison function for isort() and _int_unique() */
+static inline int
 isort_cmp(const void *a, const void *b, void *arg)
 {
 	int32		aval = *((const int32 *) a);
 	int32		bval = *((const int32 *) b);
 
-	if (aval < bval)
-		return -1;
-	if (aval > bval)
-		return 1;
-
-	/*
-	 * Report if we have any duplicates.  If there are equal keys, qsort must
-	 * compare them at some point, else it wouldn't know whether one should go
-	 * before or after the other.
-	 */
-	*((bool *) arg) = true;
+	if (*((bool *) arg))
+	{
+		/* compare for ascending order */
+		if (aval < bval)
+			return -1;
+		if (aval > bval)
+			return 1;
+	}
+	else
+	{
+		if (aval > bval)
+			return -1;
+		if (aval < bval)
+			return 1;
+	}
 	return 0;
 }
 
-/* Sort the given data (len >= 2).  Return true if any duplicates found */
-bool
-isort(int32 *a, int len)
-{
-	bool		r = false;
-
-	qsort_arg(a, len, sizeof(int32), isort_cmp, &r);
-	return r;
-}
+#define ST_SORT isort
+#define ST_ELEMENT_TYPE int32
+#define ST_COMPARE(a, b, ascending) isort_cmp(a, b, ascending)
+#define ST_COMPARE_ARG_TYPE void
+#define ST_SCOPE
+#define ST_DEFINE
+#include "lib/sort_template.h"
 
 /* Create a new int array with room for "num" elements */
 ArrayType *
@@ -311,10 +313,10 @@ ArrayType *
 _int_unique(ArrayType *r)
 {
 	int			num = ARRNELEMS(r);
-	bool		duplicates_found;	/* not used */
+	bool		ascending = true;
 
 	num = qunique_arg(ARRPTR(r), num, sizeof(int), isort_cmp,
-					  &duplicates_found);
+					  &ascending);
 
 	return resize_intArrayType(r, num);
 }
@@ -393,15 +395,3 @@ int_to_intset(int32 elem)
 	aa[0] = elem;
 	return result;
 }
-
-int
-compASC(const void *a, const void *b)
-{
-	return pg_cmp_s32(*(const int32 *) a, *(const int32 *) b);
-}
-
-int
-compDESC(const void *a, const void *b)
-{
-	return pg_cmp_s32(*(const int32 *) b, *(const int32 *) a);
-}