On Tue, Jan 14, 2025 at 4:22 PM Andrey Borodin <x4...@yandex-team.ru> wrote: > > Looks good to me. > Nice stats for some cleaning up 34 insertions(+), 48 deletions(-).
Great, I've attached v11 with a draft commit message. It also adds a comment for the comparator arg and removes ST_DECLARE since we have a hand-written declaration in the header. I plan to commit this next week unless there are objections. -- John Naylor Amazon Web Services -- John Naylor Amazon Web Services
From 868506ebef1cd20aee053e4767aac22cd40b1da0 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 v11] 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 unique-ifying step. Testing showed no regressions in always calling qunique(). 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 <x4...@yandex-team.ru> Discussion: https://postgr.es/m/098a3e67-e4a6-4086-9c66-b1eaeb1df...@yandex-team.ru --- 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..0d0cdc289c 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); -} -- 2.48.1
