I wrote:
> On Tue, Jan 7, 2025 at 12:59 PM Andrey M. Borodin <x4...@yandex-team.ru>
> wrote:
> > And one more case.
> > BTW for pre-sorted desc arrays desc sorting is slower:
>
> Right, that's because the sort template special-cases pre-sorted input, and
> that only works for descending input if the comparator is wired for
> descending output. I'm still not in favor of having two separate
> specializations because that's kind of a brute force approach, and even if
> that's okay this is a strange place to set that precedent [*]. The principled
> way to avoid this regression is to add a one-time check for descending input
> in the template, which would be more widely beneficial. I suspect (and I
> think the archives show others wondering the same) we could make the
> ascending pre-check a one-time operation as well, but I'd need to test.
That's not as clear-cut as I thought. To avoid regressions, I've gone
back to an earlier idea to pass the direction to the comparator, but
this time keep it simple by using the same comparator for sort and
unique, similar to v9.
--
John Naylor
Amazon Web Services
From cf2f6056c92380fc2aa9538f6bf80536c1a30a5c Mon Sep 17 00:00:00 2001
From: "Andrey M. Borodin" <x4mmm@night.local>
Date: Sat, 18 May 2024 23:02:50 +0500
Subject: [PATCH v10] Use specialized sort facilities
---
contrib/intarray/_int.h | 20 +++++-------
contrib/intarray/_int_tool.c | 62 +++++++++++++++---------------------
2 files changed, 34 insertions(+), 48 deletions(-)
diff --git a/contrib/intarray/_int.h b/contrib/intarray/_int.h
index 0352cbd368..c92ef13f8e 100644
--- a/contrib/intarray/_int.h
+++ b/contrib/intarray/_int.h
@@ -41,17 +41,17 @@ typedef struct
#define SORT(x) \
do { \
int _nelems_ = ARRNELEMS(x); \
- if (_nelems_ > 1) \
- isort(ARRPTR(x), _nelems_); \
+ bool _asc = true; \
+ isort(ARRPTR(x), _nelems_, &_asc); \
} while(0)
/* sort the elements of the array and remove duplicates */
#define PREPAREARR(x) \
do { \
int _nelems_ = ARRNELEMS(x); \
- if (_nelems_ > 1) \
- if (isort(ARRPTR(x), _nelems_)) \
- (x) = _int_unique(x); \
+ bool _asc = true; \
+ isort(ARRPTR(x), _nelems_, &_asc); \
+ (x) = _int_unique(x); \
} while(0)
/* "wish" function */
@@ -109,7 +109,7 @@ typedef struct
/*
* useful functions
*/
-bool isort(int32 *a, int len);
+void isort(int32 *a, size_t len, void *arg);
ArrayType *new_intArrayType(int num);
ArrayType *copy_intArrayType(ArrayType *a);
ArrayType *resize_intArrayType(ArrayType *a, int num);
@@ -176,16 +176,12 @@ bool execconsistent(QUERYTYPE *query, ArrayType *array, bool calcnot);
bool gin_bool_consistent(QUERYTYPE *query, bool *check);
bool query_has_required_values(QUERYTYPE *query);
-int compASC(const void *a, const void *b);
-int compDESC(const void *a, const void *b);
-
/* sort, either ascending or descending */
#define QSORT(a, direction) \
do { \
int _nelems_ = ARRNELEMS(a); \
- if (_nelems_ > 1) \
- qsort((void*) ARRPTR(a), _nelems_, sizeof(int32), \
- (direction) ? compASC : compDESC ); \
+ bool _asc = (direction) ? true : false; \
+ isort(ARRPTR(a), _nelems_, &_asc); \
} while(0)
#endif /* ___INT_H__ */
diff --git a/contrib/intarray/_int_tool.c b/contrib/intarray/_int_tool.c
index c85280c842..6ea189515b 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))
+ {
+ 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_DECLARE
+#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);
-}
--
2.47.1
