From: Daniel Gustafsson <daniel@yesql.se>
Message-Id: <0F9ECBA9-1DF2-4C38-BB58-B17EEE6C7B3A@yesql.se>
Content-Type: multipart/mixed;
	boundary="Apple-Mail=_EE7C281A-2743-43FA-A5BE-956125888AA8"
Mime-Version: 1.0 (Mac OS X Mail 12.4 \(3445.104.17\))
Subject: Re: A qsort template
Date: Tue, 2 Mar 2021 22:25:39 +0100
In-Reply-To: 
 <CA+hUKGJ2-eaDqAum5bxhpMNhvuJmRDZxB_Tow0n-gse+HG0Yig@mail.gmail.com>
Cc: pgsql-hackers <pgsql-hackers@postgresql.org>
To: Thomas Munro <thomas.munro@gmail.com>
References: 
 <CA+hUKGJ2-eaDqAum5bxhpMNhvuJmRDZxB_Tow0n-gse+HG0Yig@mail.gmail.com>
Precedence: bulk


--Apple-Mail=_EE7C281A-2743-43FA-A5BE-956125888AA8
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
	charset=us-ascii

> On 18 Feb 2021, at 04:09, Thomas Munro <thomas.munro@gmail.com> wrote:

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

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:

+ *       - ST_COMPARE(a, b) - a simple comparison expression
+ *   - ST_COMPARE(a, b, arg) - variant that takes an extra argument
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


--Apple-Mail=_EE7C281A-2743-43FA-A5BE-956125888AA8
Content-Disposition: attachment;
	filename=qsort_tmpl_strcmp-patch
Content-Type: application/octet-stream;
	x-unix-mode=0644;
	name="qsort_tmpl_strcmp-patch"
Content-Transfer-Encoding: 7bit

diff --git a/src/backend/tsearch/ts_utils.c b/src/backend/tsearch/ts_utils.c
index ed16a2e25a..920fbaafc4 100644
--- a/src/backend/tsearch/ts_utils.c
+++ b/src/backend/tsearch/ts_utils.c
@@ -134,7 +134,16 @@ readstoplist(const char *fname, StopList *s, char *(*wordop) (const char *))

        /* Sort to allow binary searching */
        if (s->stop && s->len > 0)
-               qsort(s->stop, s->len, sizeof(char *), pg_qsort_strcmp);
+               qsort_strcmp(s->stop, s->len, sizeof(char *));
+}
+
+/*
+ * qsort comparator wrapper for strcmp.
+ */
+static int
+strcmp_cmp(const void *a, const void *b)
+{
+       return strcmp(*(const char *const *) a, *(const char *const *) b);
 }

 bool
@@ -142,5 +151,5 @@ searchstoplist(StopList *s, char *key)
 {
        return (s->stop && s->len > 0 &&
                        bsearch(&key, s->stop, s->len,
-                                       sizeof(char *), pg_qsort_strcmp)) ? true : false;
+                                       sizeof(char *), strcmp_cmp)) ? true : false;
 }
diff --git a/src/backend/utils/misc/guc-file.l b/src/backend/utils/misc/guc-file.l
index 7885a169bb..7f0719b64c 100644
--- a/src/backend/utils/misc/guc-file.l
+++ b/src/backend/utils/misc/guc-file.l
@@ -1072,7 +1072,7 @@ ParseConfigDirectory(const char *includedir,
        {
                int                     i;

-               qsort(filenames, num_filenames, sizeof(char *), pg_qsort_strcmp);
+               qsort_strcmp(filenames, num_filenames, sizeof(char *));
                for (i = 0; i < num_filenames; i++)
                {
                        if (!ParseConfigFile(filenames[i], true,
diff --git a/src/include/port.h b/src/include/port.h
index 6486db9fdd..441f0c485d 100644
--- a/src/include/port.h
+++ b/src/include/port.h
@@ -496,9 +496,10 @@ extern int pqGethostbyname(const char *name,
                                                        struct hostent **result,
                                                        int *herrno);

+/* port/qsort.c */
 extern void pg_qsort(void *base, size_t nel, size_t elsize,
                                         int (*cmp) (const void *, const void *));
-extern int     pg_qsort_strcmp(const void *a, const void *b);
+extern void qsort_strcmp(void *base, size_t nel, size_t elsize);

 #define qsort(a,b,c,d) pg_qsort(a,b,c,d)

diff --git a/src/port/qsort.c b/src/port/qsort.c
index 7879e6cd56..ca30df5bc6 100644
--- a/src/port/qsort.c
+++ b/src/port/qsort.c
@@ -12,11 +12,11 @@
 #define ST_DEFINE
 #include "lib/sort_template.h"

-/*
- * qsort comparator wrapper for strcmp.
- */
-int
-pg_qsort_strcmp(const void *a, const void *b)
-{
-       return strcmp(*(const char *const *) a, *(const char *const *) b);
-}
+#define ST_SORT qsort_strcmp
+#define ST_ELEMENT_TYPE_VOID
+#define ST_COMPARE(a, b) \
+       strcmp(*(const char *const *) (a), *(const char *const *) (b))
+#define ST_SCOPE extern
+#define ST_DECLARE
+#define ST_DEFINE
+#include "lib/sort_template.h"

--Apple-Mail=_EE7C281A-2743-43FA-A5BE-956125888AA8--