Optimising compactify_tuples()
Hi,
With [1]https://commitfest.postgresql.org/29/2669/ applied so that you can get crash recovery to be CPU bound
with a pgbench workload, we spend an awful lot of time in qsort(),
called from compactify_tuples(). I tried replacing that with a
specialised sort, and I got my test crash recovery time from ~55.5s
down to ~49.5s quite consistently.
I've attached a draft patch. The sort_utils.h thing (which I've
proposed before in another context where it didn't turn out to be
needed) probably needs better naming, and a few more parameterisations
so that it could entirely replace the existing copies of the algorithm
rather than adding yet one more. The header also contains some more
related algorithms that don't have a user right now; maybe I should
remove them.
While writing this email, I checked the archives and discovered that a
couple of other people have complained about this hot spot before and
proposed faster sorts already[2]/messages/by-id/3c6ff1d3a2ff429ee80d0031e6c69cb7@postgrespro.ru[3]/messages/by-id/546B89DE.7030906@vmware.com, and then there was a wide ranging
discussion of various options which ultimately seemed to conclude that
we should do what I'm now proposing ... and then it stalled. The
present work is independent; I wrote this for some other sorting
problem, and then tried it out here when perf told me that it was the
next thing to fix to make recovery go faster. So I guess what I'm
really providing here is the compelling workload and numbers that were
perhaps missing from that earlier thread, but I'm open to other
solutions too.
[1]: https://commitfest.postgresql.org/29/2669/
[2]: /messages/by-id/3c6ff1d3a2ff429ee80d0031e6c69cb7@postgrespro.ru
[3]: /messages/by-id/546B89DE.7030906@vmware.com
Attachments:
0001-Add-parameterized-sorting-searching-support.patchtext/x-patch; charset=US-ASCII; name=0001-Add-parameterized-sorting-searching-support.patchDownload
From 4f3e6ccab72b3241da9afebac311eb32400eaa61 Mon Sep 17 00:00:00 2001
From: Thomas Munro <thomas.munro@gmail.com>
Date: Mon, 17 Aug 2020 21:31:56 +1200
Subject: [PATCH 1/2] Add parameterized sorting/searching support.
Provide some simple sorting and searching algorithms for working with
sorted arrays, allowing for inlining of comparisons and object sizes.
---
src/include/lib/sort_utils.h | 322 +++++++++++++++++++++++++++++++++++
1 file changed, 322 insertions(+)
create mode 100644 src/include/lib/sort_utils.h
diff --git a/src/include/lib/sort_utils.h b/src/include/lib/sort_utils.h
new file mode 100644
index 0000000000..8b92e00273
--- /dev/null
+++ b/src/include/lib/sort_utils.h
@@ -0,0 +1,322 @@
+/*-------------------------------------------------------------------------
+ *
+ * sort_utils.h
+ *
+ * Simple sorting-related algorithms specialized for arrays of
+ * paramaterized type, using inlined comparators.
+ *
+ * Copyright (c) 2020, PostgreSQL Global Development Group
+ *
+ * Usage notes:
+ *
+ * To generate functions specialized for a type, the following parameter
+ * macros should be #define'd before this file is included.
+ *
+ * - SA_PREFIX - prefix for all symbol names generated.
+ * - SA_ELEMENT_TYPE - type of the referenced elements
+ * - SA_DECLARE - if defined the functions and types are declared
+ * - SA_DEFINE - if defined the functions and types are defined
+ * - SA_SCOPE - scope (e.g. extern, static inline) for functions
+ *
+ * The following macros should be #define'd to enable functions:
+ *
+ * - SA_ENABLE_SORT - a PREFIX_sort function
+ * - SA_ENABLE_UNIQUE - a PREFIX_unique function
+ * - SA_ENABLE_BINARY_SEARCH - a PREFIX_binary_search function
+ * - SA_ENABLE_LOWER_BOUND - a PREFIX_lower_bound function
+ *
+ * The following are relevant only when SA_DEFINE is defined:
+ *
+ * - SA_COMPARE(a, b) - an expression to compare pointers to two values
+ *
+ * IDENTIFICATION
+ * src/include/lib/sort_utils.h
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#define SA_MAKE_PREFIX(a) CppConcat(a,_)
+#define SA_MAKE_NAME(name) SA_MAKE_NAME_(SA_MAKE_PREFIX(SA_PREFIX),name)
+#define SA_MAKE_NAME_(a,b) CppConcat(a,b)
+
+/* function declarations */
+#define SA_SORT SA_MAKE_NAME(sort)
+#define SA_UNIQUE SA_MAKE_NAME(unique)
+#define SA_BINARY_SEARCH SA_MAKE_NAME(binary_search)
+#define SA_LOWER_BOUND SA_MAKE_NAME(lower_bound)
+
+#ifdef SA_DECLARE
+
+SA_SCOPE void SA_SORT(SA_ELEMENT_TYPE *first, size_t n);
+SA_SCOPE SA_ELEMENT_TYPE *SA_UNIQUE(SA_ELEMENT_TYPE *first,
+ SA_ELEMENT_TYPE *last);
+SA_SCOPE SA_ELEMENT_TYPE *SA_BINARY_SEARCH(SA_ELEMENT_TYPE *first,
+ SA_ELEMENT_TYPE *last,
+ SA_ELEMENT_TYPE *value);
+SA_SCOPE SA_ELEMENT_TYPE *SA_LOWER_BOUND(SA_ELEMENT_TYPE *first,
+ SA_ELEMENT_TYPE *last,
+ SA_ELEMENT_TYPE *value);
+
+#endif
+
+#ifdef SA_DEFINE
+
+#ifdef SA_ENABLE_SORT
+
+/* helper functions */
+#define SA_MED3 SA_MAKE_NAME(med3)
+#define SA_SWAP SA_MAKE_NAME(swap)
+#define SA_SWAPN SA_MAKE_NAME(swapn)
+
+static inline SA_ELEMENT_TYPE *
+SA_MED3(SA_ELEMENT_TYPE *a,
+ SA_ELEMENT_TYPE *b,
+ SA_ELEMENT_TYPE *c)
+{
+ return SA_COMPARE(a, b) < 0 ?
+ (SA_COMPARE(b, c) < 0 ? b : (SA_COMPARE(a, c) < 0 ? c : a))
+ : (SA_COMPARE(b, c) > 0 ? b : (SA_COMPARE(a, c) < 0 ? a : c));
+}
+
+static inline void
+SA_SWAP(SA_ELEMENT_TYPE *a, SA_ELEMENT_TYPE *b)
+{
+ SA_ELEMENT_TYPE tmp = *a;
+
+ *a = *b;
+ *b = tmp;
+}
+
+static inline void
+SA_SWAPN(SA_ELEMENT_TYPE *a, SA_ELEMENT_TYPE *b, size_t n)
+{
+ size_t i;
+
+ for (i = 0; i < n; ++i)
+ SA_SWAP(&a[i], &b[i]);
+}
+
+/*
+ * Sort an array [first, last). This is the same algorithm as
+ * src/port/qsort.c, parameterized at compile-time for comparison and element
+ * type.
+ */
+SA_SCOPE void
+SA_SORT(SA_ELEMENT_TYPE *first, size_t n)
+{
+ SA_ELEMENT_TYPE *a = first,
+ *pa,
+ *pb,
+ *pc,
+ *pd,
+ *pl,
+ *pm,
+ *pn;
+ size_t d1,
+ d2;
+ int r,
+ presorted;
+
+loop:
+ if (n < 7)
+ {
+ for (pm = a + 1; pm < a + n; ++pm)
+ for (pl = pm; pl > a && SA_COMPARE(pl - 1, pl) > 0; --pl)
+ SA_SWAP(pl, pl - 1);
+ return;
+ }
+ presorted = 1;
+ for (pm = a + 1; pm < a + n; ++pm)
+ {
+ if (SA_COMPARE(pm - 1, pm) > 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 = SA_MED3(pl, pl + d, pl + 2 * d);
+ pm = SA_MED3(pm - d, pm, pm + d);
+ pn = SA_MED3(pn - 2 * d, pn - d, pn);
+ }
+ pm = SA_MED3(pl, pm, pn);
+ }
+ SA_SWAP(a, pm);
+ pa = pb = a + 1;
+ pc = pd = a + (n - 1);
+ for (;;)
+ {
+ while (pb <= pc && (r = SA_COMPARE(pb, a)) <= 0)
+ {
+ if (r == 0)
+ {
+ SA_SWAP(pa, pb);
+ ++pa;
+ }
+ ++pb;
+ }
+ while (pb <= pc && (r = SA_COMPARE(pc, a)) >= 0)
+ {
+ if (r == 0)
+ {
+ SA_SWAP(pc, pd);
+ --pd;
+ }
+ --pc;
+ }
+ if (pb > pc)
+ break;
+ SA_SWAP(pb, pc);
+ ++pb;
+ --pc;
+ }
+ pn = a + n;
+ d1 = Min(pa - a, pb - pa);
+ SA_SWAPN(a, pb - d1, d1);
+ d1 = Min(pd - pc, pn - pd - 1);
+ SA_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 > 1)
+ SA_SORT(a, d1);
+ if (d2 > 1)
+ {
+ /* Iterate rather than recurse to save stack space */
+ /* SA_SORT(pn - d2, d2) */
+ a = pn - d2;
+ n = d2;
+ goto loop;
+ }
+ }
+ else
+ {
+ /* Recurse on right partition, then iterate on left partition */
+ if (d2 > 1)
+ SA_SORT(pn - d2, d2);
+ if (d1 > 1)
+ {
+ /* Iterate rather than recurse to save stack space */
+ /* SA_SORT(a, d1) */
+ n = d1;
+ goto loop;
+ }
+ }
+}
+#endif
+
+#ifdef SA_ENABLE_UNIQUE
+/*
+ * Remove duplicates from an array. Return the new size.
+ */
+SA_SCOPE size_t
+SA_UNIQUE(SA_ELEMENT_TYPE *first, size_t n)
+{
+ SA_ELEMENT_TYPE *write_head;
+ SA_ELEMENT_TYPE *read_head;
+ SA_ELEMENT_TYPE *end = first + n;
+
+ if (n <= 1)
+ return n;
+
+ write_head = first;
+ read_head = first + 1;
+
+ while (read_head < end)
+ {
+ if (SA_COMPARE(read_head, write_head) != 0)
+ *++write_head = *read_head;
+ ++read_head;
+ }
+ return (write_head - first) + 1;
+}
+#endif
+
+#ifdef SA_ENABLE_BINARY_SEARCH
+/*
+ * Find an element in the array of sorted values that is equal to a given
+ * value. Return NULL if there is none.
+ */
+SA_SCOPE SA_ELEMENT_TYPE *
+SA_BINARY_SEARCH(SA_ELEMENT_TYPE *first, size_t n, SA_ELEMENT_TYPE *value)
+{
+ SA_ELEMENT_TYPE *lower = first;
+ SA_ELEMENT_TYPE *upper = first + n - 1;
+
+ while (lower <= upper)
+ {
+ SA_ELEMENT_TYPE *mid;
+ int cmp;
+
+ mid = lower + (upper - lower) / 2;
+ cmp = SA_COMPARE(mid, value);
+ if (cmp < 0)
+ lower = mid + 1;
+ else if (cmp > 0)
+ upper = mid - 1;
+ else
+ return mid;
+ }
+
+ return NULL;
+}
+#endif
+
+#ifdef SA_ENABLE_LOWER_BOUND
+/*
+ * Find the first element in a sorted array that is not less than *value.
+ */
+SA_SCOPE SA_ELEMENT_TYPE *
+SA_LOWER_BOUND(SA_ELEMENT_TYPE *first, size_t n, SA_ELEMENT_TYPE *value)
+{
+ ptrdiff_t count;
+
+ count = n;
+ while (count > 0)
+ {
+ SA_ELEMENT_TYPE *iter = first;
+ ptrdiff_t step = count / 2;
+
+ iter += step;
+ if (SA_COMPARE(iter, value) < 0)
+ {
+ first = ++iter;
+ count -= step + 1;
+ }
+ else
+ count = step;
+ }
+ return first;
+}
+#endif
+
+#endif
+
+#undef SA_BINARY_SEARCH
+#undef SA_DECLARE
+#undef SA_DEFINE
+#undef SA_ENABLE_BINARY_SEARCH
+#undef SA_ENABLE_LOWER_BOUND
+#undef SA_ENABLE_SORT
+#undef SA_ENABLE_UNIQUE
+#undef SA_LOWER_BOUND
+#undef SA_MAKE_NAME
+#undef SA_MAKE_NAME
+#undef SA_MAKE_NAME_
+#undef SA_MAKE_PREFIX
+#undef SA_MED3
+#undef SA_SORT
+#undef SA_SWAP
+#undef SA_UNIQUE
--
2.20.1
0002-Use-specialized-sort-in-compactify_tuples.patchtext/x-patch; charset=US-ASCII; name=0002-Use-specialized-sort-in-compactify_tuples.patchDownload
From ffe50d5901a8f9e76200abf2c6ef43e250cc25f7 Mon Sep 17 00:00:00 2001
From: Thomas Munro <thomas.munro@gmail.com>
Date: Mon, 17 Aug 2020 20:59:32 +1200
Subject: [PATCH 2/2] Use specialized sort in compactify_tuples().
Micro-optimization: by using a sort function with inlined comparison
and size we can improve page compaction performance.
---
src/backend/storage/page/bufpage.c | 21 ++++++++++++---------
1 file changed, 12 insertions(+), 9 deletions(-)
diff --git a/src/backend/storage/page/bufpage.c b/src/backend/storage/page/bufpage.c
index d708117a40..33d783e5f6 100644
--- a/src/backend/storage/page/bufpage.c
+++ b/src/backend/storage/page/bufpage.c
@@ -421,13 +421,17 @@ typedef struct itemIdSortData
} itemIdSortData;
typedef itemIdSortData *itemIdSort;
-static int
-itemoffcompare(const void *itemidp1, const void *itemidp2)
-{
- /* Sort in decreasing itemoff order */
- return ((itemIdSort) itemidp2)->itemoff -
- ((itemIdSort) itemidp1)->itemoff;
-}
+/*
+ * Instantiate a fast itemid_sort() function that sorts in decreasing offset
+ * order.
+ */
+#define SA_PREFIX itemid
+#define SA_ELEMENT_TYPE itemIdSortData
+#define SA_DEFINE
+#define SA_SCOPE static
+#define SA_ENABLE_SORT
+#define SA_COMPARE(a, b) ((b)->itemoff - (a)->itemoff)
+#include "lib/sort_utils.h"
/*
* After removing or marking some line pointers unused, move the tuples to
@@ -441,8 +445,7 @@ compactify_tuples(itemIdSort itemidbase, int nitems, Page page)
int i;
/* sort itemIdSortData array into decreasing itemoff order */
- qsort((char *) itemidbase, nitems, sizeof(itemIdSortData),
- itemoffcompare);
+ itemid_sort(itemidbase, nitems);
upper = phdr->pd_special;
for (i = 0; i < nitems; i++)
--
2.20.1
On Mon, Aug 17, 2020 at 4:01 AM Thomas Munro <thomas.munro@gmail.com> wrote:
While writing this email, I checked the archives and discovered that a
couple of other people have complained about this hot spot before and
proposed faster sorts already[2][3], and then there was a wide ranging
discussion of various options which ultimately seemed to conclude that
we should do what I'm now proposing ... and then it stalled.
I saw compactify_tuples() feature prominently in profiles when testing
the deduplication patch. We changed the relevant nbtdedup.c logic to
use a temp page rather than incrementally rewriting the authoritative
page in shared memory, which sidestepped the problem.
I definitely think that we should have something like this, though.
It's a relatively easy win. There are plenty of workloads that spend
lots of time on pruning.
--
Peter Geoghegan
On Tue, Aug 18, 2020 at 6:53 AM Peter Geoghegan <pg@bowt.ie> wrote:
I definitely think that we should have something like this, though.
It's a relatively easy win. There are plenty of workloads that spend
lots of time on pruning.
Alright then, here's an attempt to flesh the idea out a bit more, and
replace the three other copies of qsort() while I'm at it.
Attachments:
0003-Use-sort_template.h-for-qsort-and-qsort_arg.patchtext/x-patch; charset=US-ASCII; name=0003-Use-sort_template.h-for-qsort-and-qsort_arg.patchDownload
From 66e33fbeb329bffe9d8dd2ef2c8594d20e1ad662 Mon Sep 17 00:00:00 2001
From: Thomas Munro <thomas.munro@gmail.com>
Date: Wed, 19 Aug 2020 19:34:45 +1200
Subject: [PATCH 3/4] 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.20.1
0004-Use-sort_template.h-for-qsort_tuple-and-qsort_ssup.patchtext/x-patch; charset=US-ASCII; name=0004-Use-sort_template.h-for-qsort_tuple-and-qsort_ssup.patchDownload
From 6a767c0e5ebf72aac2cf0883b1333a839a87567a Mon Sep 17 00:00:00 2001
From: Thomas Munro <thomas.munro@gmail.com>
Date: Wed, 19 Aug 2020 20:25:12 +1200
Subject: [PATCH 4/4] 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/utils/sort/.gitignore | 1 -
src/backend/utils/sort/Makefile | 3 -
src/backend/utils/sort/gen_qsort_tuple.pl | 271 ----------------------
src/backend/utils/sort/tuplesort.c | 21 +-
4 files changed, 20 insertions(+), 276 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/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..39f132ef68 100644
--- a/src/backend/utils/sort/Makefile
+++ b/src/backend/utils/sort/Makefile
@@ -23,9 +23,6 @@ OBJS = \
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:
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 eb0f7c5814..0000000000
--- a/src/backend/utils/sort/gen_qsort_tuple.pl
+++ /dev/null
@@ -1,271 +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 3c49476483..8119c41328 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
--
2.20.1
0001-Add-sort_template.h-for-making-fast-sort-functions.patchtext/x-patch; charset=US-ASCII; name=0001-Add-sort_template.h-for-making-fast-sort-functions.patchDownload
From 8d0b569fcf6141b622c63fc4bc102c762f01ca9e Mon Sep 17 00:00:00 2001
From: Thomas Munro <thomas.munro@gmail.com>
Date: Mon, 17 Aug 2020 21:31:56 +1200
Subject: [PATCH 1/4] 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.
Discussion: https://postgr.es/m/CA%2BhUKGKMQFVpjr106gRhwk6R-nXv0qOcTreZuQzxgpHESAL6dw%40mail.gmail.com
---
src/include/lib/sort_template.h | 428 ++++++++++++++++++++++++++++++++
1 file changed, 428 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..a279bcf959
--- /dev/null
+++ b/src/include/lib/sort_template.h
@@ -0,0 +1,428 @@
+/*-------------------------------------------------------------------------
+ *
+ * sort_template.h
+ *
+ * A template for a sort algorithm that supports varying degrees of
+ * specialization.
+ *
+ * Copyright (c) 2020, PostgreSQL Global Development Group
+ *
+ * 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_SIZE , size_t element_size
+#define ST_SORT_INVOKE_SIZE , element_size
+#else
+#define ST_SORT_PROTO_SIZE
+#define ST_SORT_INVOKE_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_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_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_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_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_SORT
+#undef ST_SORT_INVOKE_ARG
+#undef ST_SORT_INVOKE_COMPARE
+#undef ST_SORT_INVOKE_SIZE
+#undef ST_SORT_PROTO_ARG
+#undef ST_SORT_PROTO_COMPARE
+#undef ST_SORT_PROTO_SIZE
+#undef ST_SWAP
+#undef ST_SWAPN
--
2.20.1
0002-Use-sort_template.h-for-compactify_tuples.patchtext/x-patch; charset=US-ASCII; name=0002-Use-sort_template.h-for-compactify_tuples.patchDownload
From fc58e1ad97a1eaad7bd1277a9d493af239cc77ef Mon Sep 17 00:00:00 2001
From: Thomas Munro <thomas.munro@gmail.com>
Date: Mon, 17 Aug 2020 20:59:32 +1200
Subject: [PATCH 2/4] Use sort_template.h for compactify_tuples().
Since compactify_tuples() is called often, a specialized sort function
for sorting tuple offsets can give measurable speed-up.
Discussion: https://postgr.es/m/CA%2BhUKGKMQFVpjr106gRhwk6R-nXv0qOcTreZuQzxgpHESAL6dw%40mail.gmail.com
---
src/backend/storage/page/bufpage.c | 17 ++++++++---------
1 file changed, 8 insertions(+), 9 deletions(-)
diff --git a/src/backend/storage/page/bufpage.c b/src/backend/storage/page/bufpage.c
index d708117a40..f81fa8cf3d 100644
--- a/src/backend/storage/page/bufpage.c
+++ b/src/backend/storage/page/bufpage.c
@@ -421,13 +421,13 @@ typedef struct itemIdSortData
} itemIdSortData;
typedef itemIdSortData *itemIdSort;
-static int
-itemoffcompare(const void *itemidp1, const void *itemidp2)
-{
- /* Sort in decreasing itemoff order */
- return ((itemIdSort) itemidp2)->itemoff -
- ((itemIdSort) itemidp1)->itemoff;
-}
+/* Create a specialized sort function for descending offset order. */
+#define ST_SORT qsort_itemoff
+#define ST_ELEMENT_TYPE itemIdSortData
+#define ST_COMPARE(a, b) ((b)->itemoff - (a)->itemoff)
+#define ST_SCOPE static
+#define ST_DEFINE
+#include "lib/sort_template.h"
/*
* After removing or marking some line pointers unused, move the tuples to
@@ -441,8 +441,7 @@ compactify_tuples(itemIdSort itemidbase, int nitems, Page page)
int i;
/* sort itemIdSortData array into decreasing itemoff order */
- qsort((char *) itemidbase, nitems, sizeof(itemIdSortData),
- itemoffcompare);
+ qsort_itemoff(itemidbase, nitems);
upper = phdr->pd_special;
for (i = 0; i < nitems; i++)
--
2.20.1
On Wed, Aug 19, 2020 at 11:41 PM Thomas Munro <thomas.munro@gmail.com> wrote:
On Tue, Aug 18, 2020 at 6:53 AM Peter Geoghegan <pg@bowt.ie> wrote:
I definitely think that we should have something like this, though.
It's a relatively easy win. There are plenty of workloads that spend
lots of time on pruning.Alright then, here's an attempt to flesh the idea out a bit more, and
replace the three other copies of qsort() while I'm at it.
I fixed up the copyright messages, and removed some stray bits of
build scripting relating to the Perl-generated file. Added to
commitfest.
Attachments:
v2-0001-Add-sort_template.h-for-making-fast-sort-function.patchtext/x-patch; charset=US-ASCII; name=v2-0001-Add-sort_template.h-for-making-fast-sort-function.patchDownload
From 940100ea1b2021e434976f6ce10aae75dd265d26 Mon Sep 17 00:00:00 2001
From: Thomas Munro <thomas.munro@gmail.com>
Date: Mon, 17 Aug 2020 21:31:56 +1200
Subject: [PATCH v2 1/5] 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.
Discussion: https://postgr.es/m/CA%2BhUKGKMQFVpjr106gRhwk6R-nXv0qOcTreZuQzxgpHESAL6dw%40mail.gmail.com
---
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..0e163d4d8a
--- /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) 2020, 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.20.1
v2-0002-Use-sort_template.h-for-compactify_tuples.patchtext/x-patch; charset=US-ASCII; name=v2-0002-Use-sort_template.h-for-compactify_tuples.patchDownload
From 9290693b090ec69bf837f2a2f53e1f1663bdc8ef Mon Sep 17 00:00:00 2001
From: Thomas Munro <thomas.munro@gmail.com>
Date: Mon, 17 Aug 2020 20:59:32 +1200
Subject: [PATCH v2 2/5] Use sort_template.h for compactify_tuples().
Since compactify_tuples() is called often, a specialized sort function
for sorting tuple offsets can give measurable speed-up.
Discussion: https://postgr.es/m/CA%2BhUKGKMQFVpjr106gRhwk6R-nXv0qOcTreZuQzxgpHESAL6dw%40mail.gmail.com
---
src/backend/storage/page/bufpage.c | 17 ++++++++---------
1 file changed, 8 insertions(+), 9 deletions(-)
diff --git a/src/backend/storage/page/bufpage.c b/src/backend/storage/page/bufpage.c
index d708117a40..f81fa8cf3d 100644
--- a/src/backend/storage/page/bufpage.c
+++ b/src/backend/storage/page/bufpage.c
@@ -421,13 +421,13 @@ typedef struct itemIdSortData
} itemIdSortData;
typedef itemIdSortData *itemIdSort;
-static int
-itemoffcompare(const void *itemidp1, const void *itemidp2)
-{
- /* Sort in decreasing itemoff order */
- return ((itemIdSort) itemidp2)->itemoff -
- ((itemIdSort) itemidp1)->itemoff;
-}
+/* Create a specialized sort function for descending offset order. */
+#define ST_SORT qsort_itemoff
+#define ST_ELEMENT_TYPE itemIdSortData
+#define ST_COMPARE(a, b) ((b)->itemoff - (a)->itemoff)
+#define ST_SCOPE static
+#define ST_DEFINE
+#include "lib/sort_template.h"
/*
* After removing or marking some line pointers unused, move the tuples to
@@ -441,8 +441,7 @@ compactify_tuples(itemIdSort itemidbase, int nitems, Page page)
int i;
/* sort itemIdSortData array into decreasing itemoff order */
- qsort((char *) itemidbase, nitems, sizeof(itemIdSortData),
- itemoffcompare);
+ qsort_itemoff(itemidbase, nitems);
upper = phdr->pd_special;
for (i = 0; i < nitems; i++)
--
2.20.1
v2-0003-Use-sort_template.h-for-qsort-and-qsort_arg.patchtext/x-patch; charset=US-ASCII; name=v2-0003-Use-sort_template.h-for-qsort-and-qsort_arg.patchDownload
From c4f01775f54a9942d9cd7e90206438233d1f4e6a Mon Sep 17 00:00:00 2001
From: Thomas Munro <thomas.munro@gmail.com>
Date: Wed, 19 Aug 2020 19:34:45 +1200
Subject: [PATCH v2 3/5] 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.20.1
v2-0004-Use-sort_template.h-for-qsort_tuple-and-qsort_ssu.patchtext/x-patch; charset=US-ASCII; name=v2-0004-Use-sort_template.h-for-qsort_tuple-and-qsort_ssu.patchDownload
From ad98b873695ce84dbf7c4ce1b23337db66eef76d Mon Sep 17 00:00:00 2001
From: Thomas Munro <thomas.munro@gmail.com>
Date: Wed, 19 Aug 2020 20:25:12 +1200
Subject: [PATCH v2 4/5] 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 | 271 ----------------------
src/backend/utils/sort/tuplesort.c | 21 +-
src/tools/msvc/Solution.pm | 10 -
src/tools/msvc/clean.bat | 1 -
7 files changed, 21 insertions(+), 295 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 9706a95848..5a9858e35e 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 eb0f7c5814..0000000000
--- a/src/backend/utils/sort/gen_qsort_tuple.pl
+++ /dev/null
@@ -1,271 +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 3c49476483..8119c41328 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 bc8904732f..ca2e3f6329 100644
--- a/src/tools/msvc/Solution.pm
+++ b/src/tools/msvc/Solution.pm
@@ -662,16 +662,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 672bb2d650..5b6b796ff9 100755
--- a/src/tools/msvc/clean.bat
+++ b/src/tools/msvc/clean.bat
@@ -61,7 +61,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.20.1
On Thu, 20 Aug 2020 at 11:28, Thomas Munro <thomas.munro@gmail.com> wrote:
I fixed up the copyright messages, and removed some stray bits of
build scripting relating to the Perl-generated file. Added to
commitfest.
I'm starting to look at this. So far I've only just done a quick
performance test on it. With the workload I ran, using 0001+0002.
The test replayed ~2.2 GB of WAL. master took 148.581 seconds and
master+0001+0002 took 115.588 seconds. That's about 28% faster. Pretty
nice!
I found running a lower heap fillfactor will cause quite a few more
heap cleanups to occur. Perhaps that's one of the reasons the speedup
I got was more than the 12% you reported.
More details of the test:
Setup:
drowley@amd3990x:~$ cat recoverbench.sh
#!/bin/bash
pg_ctl stop -D pgdata -m smart
pg_ctl start -D pgdata -l pg.log -w
psql -c "drop table if exists t1;" postgres > /dev/null
psql -c "create table t1 (a int primary key, b int not null) with
(fillfactor = 85);" postgres > /dev/null
psql -c "insert into t1 select x,0 from generate_series(1,10000000)
x;" postgres > /dev/null
psql -c "drop table if exists log_wal;" postgres > /dev/null
psql -c "create table log_wal (lsn pg_lsn not null);" postgres > /dev/null
psql -c "insert into log_wal values(pg_current_wal_lsn());" postgres > /dev/null
pgbench -n -f update.sql -t 60000 -c 200 -j 200 -M prepared postgres > /dev/null
psql -c "select 'Used ' ||
pg_size_pretty(pg_wal_lsn_diff(pg_current_wal_lsn(), lsn)) || ' of
WAL' from log_wal limit 1;" postgres
pg_ctl stop -D pgdata -m immediate -w
echo Starting Postgres...
pg_ctl start -D pgdata -l pg.log
drowley@amd3990x:~$ cat update.sql
\set i random(1,10000000)
update t1 set b = b+1 where a = :i;
Results:
master
Recovery times are indicated in the postgresql log:
2020-09-06 22:38:58.992 NZST [6487] LOG: redo starts at 3/16E4A988
2020-09-06 22:41:27.570 NZST [6487] LOG: invalid record length at
3/F67F8B48: wanted 24, got 0
2020-09-06 22:41:27.573 NZST [6487] LOG: redo done at 3/F67F8B20
recovery duration = 00:02:28.581
drowley@amd3990x:~$ ./recoverbench.sh
waiting for server to shut down.... done
server stopped
waiting for server to start.... done
server started
?column?
---------------------
Used 2333 MB of WAL
(1 row)
waiting for server to shut down.... done
server stopped
Starting Postgres...
recovery profile:
28.79% postgres postgres [.] pg_qsort
13.58% postgres postgres [.] itemoffcompare
12.27% postgres postgres [.] PageRepairFragmentation
8.26% postgres libc-2.31.so [.] 0x000000000018e48f
5.90% postgres postgres [.] swapfunc
4.86% postgres postgres [.] hash_search_with_hash_value
2.95% postgres postgres [.] XLogReadBufferExtended
1.83% postgres postgres [.] PinBuffer
1.80% postgres postgres [.] compactify_tuples
1.71% postgres postgres [.] med3
0.99% postgres postgres [.] hash_bytes
0.90% postgres libc-2.31.so [.] 0x000000000018e470
0.89% postgres postgres [.] StartupXLOG
0.84% postgres postgres [.] XLogReadRecord
0.72% postgres postgres [.] LWLockRelease
0.71% postgres postgres [.] PageGetHeapFreeSpace
0.61% postgres libc-2.31.so [.] 0x000000000018e499
0.50% postgres postgres [.] heap_xlog_update
0.50% postgres postgres [.] DecodeXLogRecord
0.50% postgres postgres [.] pg_comp_crc32c_sse42
0.45% postgres postgres [.] LWLockAttemptLock
0.40% postgres postgres [.] ReadBuffer_common
0.40% postgres [kernel.kallsyms] [k] copy_user_generic_string
0.36% postgres libc-2.31.so [.] 0x000000000018e49f
0.33% postgres postgres [.] SlruSelectLRUPage
0.32% postgres postgres [.] PageAddItemExtended
0.31% postgres postgres [.] ReadPageInternal
Patched v2-0001 + v2-0002:
Recovery times are indicated in the postgresql log:
2020-09-06 22:54:25.532 NZST [13252] LOG: redo starts at 3/F67F8C70
2020-09-06 22:56:21.120 NZST [13252] LOG: invalid record length at
4/D633FCD0: wanted 24, got 0
2020-09-06 22:56:21.120 NZST [13252] LOG: redo done at 4/D633FCA8
recovery duration = 00:01:55.588
drowley@amd3990x:~$ ./recoverbench.sh
waiting for server to shut down.... done
server stopped
waiting for server to start.... done
server started
?column?
---------------------
Used 2335 MB of WAL
(1 row)
waiting for server to shut down.... done
server stopped
Starting Postgres...
recovery profile:
32.29% postgres postgres [.] qsort_itemoff
17.73% postgres postgres [.] PageRepairFragmentation
10.98% postgres libc-2.31.so [.] 0x000000000018e48f
5.54% postgres postgres [.] hash_search_with_hash_value
3.60% postgres postgres [.] XLogReadBufferExtended
2.32% postgres postgres [.] compactify_tuples
2.14% postgres postgres [.] PinBuffer
1.39% postgres postgres [.] PageGetHeapFreeSpace
1.38% postgres postgres [.] hash_bytes
1.36% postgres postgres [.] qsort_itemoff_med3
0.94% postgres libc-2.31.so [.] 0x000000000018e499
0.89% postgres postgres [.] XLogReadRecord
0.74% postgres postgres [.] LWLockRelease
0.74% postgres postgres [.] DecodeXLogRecord
0.73% postgres postgres [.] heap_xlog_update
0.66% postgres postgres [.] LWLockAttemptLock
0.65% postgres libc-2.31.so [.] 0x000000000018e470
0.64% postgres postgres [.] pg_comp_crc32c_sse42
0.63% postgres postgres [.] StartupXLOG
0.61% postgres [kernel.kallsyms] [k] copy_user_generic_string
0.60% postgres postgres [.] PageAddItemExtended
0.60% postgres libc-2.31.so [.] 0x000000000018e49f
0.56% postgres libc-2.31.so [.] 0x000000000018e495
0.54% postgres postgres [.] ReadBuffer_common
Settings:
shared_buffers = 10GB
checkpoint_timeout = 1 hour
max_wal_size = 100GB
Hardware:
AMD 3990x
Samsung 970 EVO SSD
64GB DDR4 3600MHz
I'll spend some time looking at the code soon.
David
On Sun, 6 Sep 2020 at 23:37, David Rowley <dgrowleyml@gmail.com> wrote:
The test replayed ~2.2 GB of WAL. master took 148.581 seconds and
master+0001+0002 took 115.588 seconds. That's about 28% faster. Pretty
nice!
I was wondering today if we could just get rid of the sort in
compactify_tuples() completely. It seems to me that the existing sort
is there just so that the memmove() is done in order of tuple at the
end of the page first. We seem to be just shunting all the tuples to
the end of the page so we need to sort the line items in reverse
offset so as not to overwrite memory for other tuples during the copy.
I wondered if we could get around that just by having another buffer
somewhere and memcpy the tuples into that first then copy the tuples
out that buffer back into the page. No need to worry about the order
we do that in as there's no chance to overwrite memory belonging to
other tuples.
Doing that gives me 79.166 seconds in the same recovery test. Or about
46% faster, instead of 22% (I mistakenly wrote 28% yesterday)
The top of perf report says:
24.19% postgres postgres [.] PageRepairFragmentation
8.37% postgres postgres [.] hash_search_with_hash_value
7.40% postgres libc-2.31.so [.] 0x000000000018e74b
5.59% postgres libc-2.31.so [.] 0x000000000018e741
5.49% postgres postgres [.] XLogReadBufferExtended
4.05% postgres postgres [.] compactify_tuples
3.27% postgres postgres [.] PinBuffer
2.88% postgres libc-2.31.so [.] 0x000000000018e470
2.02% postgres postgres [.] hash_bytes
(I'll need to figure out why libc's debug symbols are not working)
I was thinking that there might be a crossover point to where this
method becomes faster than the sort method. e.g sorting 1 tuple is
pretty cheap, but copying the memory for the entire tuple space might
be expensive as that includes the tuples we might be getting rid of.
So if we did go down that path we might need some heuristics to decide
which method is likely best. Maybe that's based on the number of
tuples, I'm not really sure. I've not made any attempt to try to give
it a worst-case workload to see if there is a crossover point that's
worth worrying about.
The attached patch is what I used to test this. It kinda goes and
sticks a page-sized variable on the stack, which is not exactly ideal.
I think we'd likely want to figure some other way to do that, but I
just don't know what that would look like yet. I just put the attached
together quickly to test out the idea.
(I don't want to derail the sort improvements here. I happen to think
those are quite important improvements, so I'll continue to review
that patch still. Longer term, we might just end up with something
slightly different for compactify_tuples)
David
Attachments:
compactify_tuples_dgr.patch.txttext/plain; charset=US-ASCII; name=compactify_tuples_dgr.patch.txtDownload
diff --git a/src/backend/storage/page/bufpage.c b/src/backend/storage/page/bufpage.c
index d708117a40..5bf35aff37 100644
--- a/src/backend/storage/page/bufpage.c
+++ b/src/backend/storage/page/bufpage.c
@@ -440,22 +440,53 @@ compactify_tuples(itemIdSort itemidbase, int nitems, Page page)
Offset upper;
int i;
- /* sort itemIdSortData array into decreasing itemoff order */
- qsort((char *) itemidbase, nitems, sizeof(itemIdSortData),
- itemoffcompare);
+ if (nitems > MaxHeapTuplesPerPage / 2)
+ {
+ char buffer[BLCKSZ + MAXIMUM_ALIGNOF];
+ char *bufp = (char *) MAXALIGN(&buffer);
+
+ /*
+ * Make a temp copy of the tuple data so that we can rearange
+ * the tuples freely without having to worry about stomping
+ * on the memory of other tuples.
+ */
+ memcpy(bufp + phdr->pd_upper,
+ page + phdr->pd_upper,
+ phdr->pd_special - phdr->pd_upper);
- upper = phdr->pd_special;
- for (i = 0; i < nitems; i++)
+ upper = phdr->pd_special;
+ for (i = 0; i < nitems; i++)
+ {
+ itemIdSort itemidptr = &itemidbase[i];
+ ItemId lp;
+
+ lp = PageGetItemId(page, itemidptr->offsetindex + 1);
+ upper -= itemidptr->alignedlen;
+ memcpy((char *) page + upper,
+ bufp + itemidptr->itemoff,
+ itemidptr->alignedlen);
+ lp->lp_off = upper;
+ }
+ }
+ else
{
- itemIdSort itemidptr = &itemidbase[i];
- ItemId lp;
-
- lp = PageGetItemId(page, itemidptr->offsetindex + 1);
- upper -= itemidptr->alignedlen;
- memmove((char *) page + upper,
- (char *) page + itemidptr->itemoff,
- itemidptr->alignedlen);
- lp->lp_off = upper;
+ /* sort itemIdSortData array into decreasing itemoff order */
+ qsort((char *) itemidbase, nitems, sizeof(itemIdSortData),
+ itemoffcompare);
+
+ upper = phdr->pd_special;
+ for (i = 0; i < nitems; i++)
+ {
+ itemIdSort itemidptr = &itemidbase[i];
+ ItemId lp;
+
+ lp = PageGetItemId(page, itemidptr->offsetindex + 1);
+ upper -= itemidptr->alignedlen;
+ memmove((char *) page + upper,
+ (char *) page + itemidptr->itemoff,
+ itemidptr->alignedlen);
+ lp->lp_off = upper;
+ }
}
phdr->pd_upper = upper;
On Mon, Sep 7, 2020 at 7:48 PM David Rowley <dgrowleyml@gmail.com> wrote:
I was wondering today if we could just get rid of the sort in
compactify_tuples() completely. It seems to me that the existing sort
is there just so that the memmove() is done in order of tuple at the
end of the page first. We seem to be just shunting all the tuples to
the end of the page so we need to sort the line items in reverse
offset so as not to overwrite memory for other tuples during the copy.I wondered if we could get around that just by having another buffer
somewhere and memcpy the tuples into that first then copy the tuples
out that buffer back into the page. No need to worry about the order
we do that in as there's no chance to overwrite memory belonging to
other tuples.Doing that gives me 79.166 seconds in the same recovery test. Or about
46% faster, instead of 22% (I mistakenly wrote 28% yesterday)
Wow.
One thought is that if we're going to copy everything out and back in
again, we might want to consider doing it in a
memory-prefetcher-friendly order. Would it be a good idea to
rearrange the tuples to match line pointer order, so that the copying
work and also later sequential scans are in a forward direction? The
copying could also perhaps be done with single memcpy() for ranges of
adjacent tuples. Another thought is that it might be possible to
identify some easy cases that it can handle with an alternative
in-place shifting algorithm without having to go to the
copy-out-and-back-in path. For example, when the offset order already
matches line pointer order but some dead tuples just need to be
squeezed out by shifting ranges of adjacent tuples, and maybe some
slightly more complicated cases, but nothing requiring hard work like
sorting.
(I don't want to derail the sort improvements here. I happen to think
those are quite important improvements, so I'll continue to review
that patch still. Longer term, we might just end up with something
slightly different for compactify_tuples)
Yeah. Perhaps qsort specialisation needs to come back in a new thread
with a new use case.
On Tue, 8 Sep 2020 at 12:08, Thomas Munro <thomas.munro@gmail.com> wrote:
One thought is that if we're going to copy everything out and back in
again, we might want to consider doing it in a
memory-prefetcher-friendly order. Would it be a good idea to
rearrange the tuples to match line pointer order, so that the copying
work and also later sequential scans are in a forward direction?
That's an interesting idea but wouldn't that require both the copy to
the separate buffer *and* a qsort? That's the worst of both
implementations. We'd need some other data structure too in order to
get the index of the sorted array by reverse lineitem point, which
might require an additional array and an additional sort.
The
copying could also perhaps be done with single memcpy() for ranges of
adjacent tuples.
I wonder if the additional code required to check for that would be
cheaper than the additional function call. If it was then it might be
worth trying, but since the tuples can be in any random order then
it's perhaps not likely to pay off that often. I'm not really sure
how often adjacent line items will also be neighbouring tuples for
pages we call compactify_tuples() for. It's certainly going to be
common with INSERT only tables, but if we're calling
compactify_tuples() then it's not read-only.
Another thought is that it might be possible to
identify some easy cases that it can handle with an alternative
in-place shifting algorithm without having to go to the
copy-out-and-back-in path. For example, when the offset order already
matches line pointer order but some dead tuples just need to be
squeezed out by shifting ranges of adjacent tuples, and maybe some
slightly more complicated cases, but nothing requiring hard work like
sorting.
It's likely worth experimenting. The only thing is that the workload
I'm using seems to end up with the tuples with line items not in the
same order as the tuple offset. So adding a precheck to check the
ordering will regress the test I'm doing. We'd need to see if there is
any other workload that would keep the tuples more in order then
determine how likely that is to occur in the real world.
(I don't want to derail the sort improvements here. I happen to think
those are quite important improvements, so I'll continue to review
that patch still. Longer term, we might just end up with something
slightly different for compactify_tuples)Yeah. Perhaps qsort specialisation needs to come back in a new thread
with a new use case.
hmm, yeah, perhaps that's a better way given the subject here is about
compactify_tuples()
David
On Mon, 7 Sep 2020 at 19:47, David Rowley <dgrowleyml@gmail.com> wrote:
I wondered if we could get around that just by having another buffer
somewhere and memcpy the tuples into that first then copy the tuples
out that buffer back into the page. No need to worry about the order
we do that in as there's no chance to overwrite memory belonging to
other tuples.Doing that gives me 79.166 seconds in the same recovery test. Or about
46% faster, instead of 22% (I mistakenly wrote 28% yesterday)
I did some more thinking about this and considered if there's a way to
just get rid of the sorting version of compactify_tuples() completely.
In the version from yesterday, I fell back on the sort version for
when more than half the tuples from the page were being pruned. I'd
thought that in this case copying out *all* of the page from pd_upper
up to the pd_special (the tuple portion of the page) would maybe be
more costly since that would include (needlessly) copying all the
pruned tuples too. The sort also becomes cheaper in that case since
the number of items to sort is less, hence I thought it was a good
idea to keep the old version for some cases. However, I now think we
can just fix this by conditionally copying all tuples when in 1 big
memcpy when not many tuples have been pruned and when more tuples are
pruned we can just do individual memcpys into the separate buffer.
I wrote a little .c program to try to figure out of there's some good
cut off point to where one method becomes better than the other and I
find that generally if we're pruning away about 75% of tuples then
doing a memcpy() per non-pruned tuple is faster, otherwise, it seems
better just to copy the entire tuple area of the page. See attached
compact_test.c
I ran this and charted the cut off at (nitems < totaltups / 4) and
(nitems < totaltups / 2), and nitems < 16)
./compact_test 32 192
./compact_test 64 96
./compact_test 128 48
./compact_test 256 24
./compact_test 512 12
The / 4 one gives me the graphs with the smallest step when the method
switches. See attached 48_tuples_per_page.png for comparison.
I've so far come up with the attached
compactify_tuples_dgr_v2.patch.txt. Thomas pointed out to me off-list
that using PGAlignedBlock is the general way to allocate a page-sized
data on the stack. I'm still classing this patch as PoC grade. I'll
need to look a bit harder at the correctness of it all.
I did spend quite a bit of time trying to find a case where this is
slower than master's version. I can't find a case where there's any
noticeable slowdown. Using the same script from [1]/messages/by-id/CAApHDvoKwqAzhiuxEt8jSquPJKDpH8DNUZDFUSX9P7DXrJdc3Q@mail.gmail.com I tried a few
variations of the t1 table by adding an additional column to pad out
the tuple to make it wider. Obviously a wider tuple means fewer
tuples on the page so less tuples for master's qsort to sort during
compactify_tuples(). I did manage to squeeze a bit more performance
out of the test cases. Yesterday I got 79.166 seconds. This version
gets me 76.623 seconds.
Here are the results of the various tuple widths:
narrow width row test: insert into t1 select x,0 from
generate_series(1,10000000) x; (32 byte tuples)
patched: 76.623
master: 137.593
medium width row test: insert into t1 select x,0,md5(x::text) ||
md5((x+1)::Text) from generate_series(1,10000000) x; (about 64 byte
tuples)
patched: 64.411
master: 95.576
wide row test: insert into t1 select x,0,(select
string_agg(md5(y::text),'') from generate_Series(x,x+30) y) from
generate_series(1,1000000)x; (1024 byte tuples)
patched: 88.653
master: 90.077
Changing the test so instead of having 10 million rows in the table
and updating a random row 12 million times. I put just 10 rows in the
table and updated them 12 million times. This results in
compactify_tuples() pruning all but 1 row (since autovac can't keep up
with this, each row does end up on a page by itself). I wanted to
ensure I didn't regress a workload that master's qsort() version would
have done very well at. qsorting 1 element is pretty fast.
10-row narrow test:
patched: 10.633 <--- small regression
master: 10.366
I could special case this and do a memmove without copying the tuple
to another buffer, but I don't think the slowdown is enough to warrant
having such a special case.
Another thing I tried was to instead of compacting the page in
compactify_tuples(), I just get rid of that function and did the
compacting in the existing loop in PageRepairFragmentation(). This
does require changing the ERROR check to a PANIC since we may have
already started shuffling tuples around when we find the corrupted
line pointer. However, I was just unable to make this faster than the
attached version. I'm still surprised at this as I can completely get
rid of the itemidbase array. The best run-time I got with this method
out the original test was 86 seconds, so 10 seconds slower than what
the attached can do. So I threw that idea away.
David
[1]: /messages/by-id/CAApHDvoKwqAzhiuxEt8jSquPJKDpH8DNUZDFUSX9P7DXrJdc3Q@mail.gmail.com
Attachments:
48_tuples_per_page.pngimage/png; name=48_tuples_per_page.pngDownload
�PNG
IHDR � GA3 sRGB ��� gAMA ���a pHYs % %IR$� ��IDATx^��wpwz&~���r�|U�-��:����~%�]l�}.S"�W%��JZQZi����I� A0'0�$���3H0'0� &�A� �������|��$����SS(LwOOw����@3�+1��K1��K1��K1��K1��K1��K1��K1��K1��K1��K1��K1��K�dT�r��o[]�v�j�Q$A7�f�����>����?�|��Q6l���V)��
��>TXX�!O2�$��'�����+Wb�uQ��
KG ��Pb�P����z�==�+��T���'��2L���B�E +���cQ���a��$����t�R�St��~�p���]
n�������z��U)JMM��#F�}��=�Q������l��
=����
V ����\V�t�`�<_S���bdV�Q��o/jkkQ�?V#"�g�����N�U:X�~�� ��������V�I�������*��P(4o�<� ��o��(-q�+d�l����T���~���^y����1.+V���������X�-Z�E�jDDR�LTU@��z����D�/���6�M����t�������VBC��1��{`����/'N�����F=�Q5E�>�J�V��}k�������O[�R���srr�Y�'"����ZWW7z�h����h����Z1�_�>*��c=h�S*��1��K������9���CV�%9������/#�r��S ��Q����#F��{���(5�l/�={���)S��q1yIw�*~[/Z�+�i���]�6�����q"�u:(b��(1FUr��G�b�;v��^��OfT
���jOq��
�D���}kr��3g�4M�j����J��,hV#"��Q���CX��3M���+++���������<6�h���g;�FQ�������v[��9�X�n��#�&_}�����+**bOHHU1��avv�_|�n����Y�f]�r%�Y
Xe?~<//O�4�Jy������V�����n��<y��j�*�}0<��a����^�/�b�w���G�c��9|���E<iLX�p��LL=t�'??���,[9�?UUU�������q�����W�V[At����g�S^�x��1_�|y��8g6��c�rrrTi�]K�,�� +j�R0J��>c�`��qG��-��Q�
���>��p��{�ba�[%T@��Xgee�3@�(����������!���dOj��O�~����~��u�,V�R�F�-��z�q�����]�iT�QT[������������0:���$V�X��w���
����vs�"�������
V:X��V�UV4�h����\U�A����tz�^;G�~TE�.**j�� �iu�*����3*�EAO��nL���J9�0}���O\�m���Wc���~�-�*���C��0���_��)��|?GMCSou�
}��y��<;!=�]�l��,7`����WE�(��;T��__�������[h�=w���u���JM�(��Z__?i�$�EG��w��m����U�Zu�`�1en���|�c4�z����q' +���Y��! 3����PD-X�e���N�d,zX �}�a,1��w�+Lu�R\�����FuE�EuPJ�$��c��8vyQb��$��MU����w��/""�I?�b�6m�4�k����6��W=
��X)������H�����2��y�@\�k���o�����!9?~���� ��:N�����Ok���=����K�6$��Y]�R����;b��
�&��LVm��� ��������F�j�����:�M����JB�c�s�����/�l�qyyy�d5_��G�c�:��jOT��Y%??_���Y������"����^dG�t1�b��|�����Yg����`L��3����+�����������_JNXl����+�6�;�����w��qW,6�6nTM}�?��ZMaA[�f
[�l�W�6l�:���V]�MUW�
.��A�V#"�'��jo�����t�������������~���X}[�Z��gls�n�\��V�v����@b�jjj����2
V�7o��>o���Tm��gXw_�tI��}>���[U�D��}����5
�U����B�&�n�:�Qb�tPf���vA�����c�s�ig;������D���8/fW��9��� �:a�J�C+�!�L����*�Zk�:�V�w���k������;8�m�,|d����3����\�b������*XH_���9H6{f�������YB�� ���b�+��@a���:����A:{�����9w9g����k�������T�&>g|��~�zU)�2�L�z�)v*����h��u6���e5)��3._���#�w�u2�����K��aP1��>�wW�^�K|`����s����b�CV�����P�zM!n�6�ED)U��.���NE�0��'�}�S�M1zbM��S�M�#�����`���+t���b��K����A#����$ ��'��������������j�
_���m��m�[ 5������M��?���!v����0���$g��3�=$�Q�K��*jT������MMM*R����>�=���8�h���.
mW',���Xq�����j{��������}��r��� !,v\�]�����{� '�����;f5m�>�P��}c�+��@a�����H'V�6X���+���Y�E?�c�yC�)QS���3���R��b�O$*f����;w��'���H6������{�j�El��w�[�W�a���_G�'�b��|��Q�J���c�j�������U�
����T�����q���~_�@�DU�Wx�*2���>��E���j��������$cW�q��h���F�����������Rq�|�[ql���R
��(j��&;��W�M���;u���r�������C�N�Q,{:D��a����G�^�tI��u�gu���-Y��j�6����t*� �����7��dG��s������f�[�]�&�.���M*�����nw76�h����JQ�1�!n���O���={V�x�s�N���U�v�A���l��%���&�Ye��5�Di�����=Le�O����Ij;FY��=�;����U���/��B��m��=�CW�r�&��������W?S�}il/��Lh�?�H�.GU�k�.]�u6�Q��D�#u� �������d�����hb�m5j�/�W�6W���-���C�6;9�Q[; a{�;P���� ���}p6���W�\I�Dd�M��M�(�'��;�8�%�4�4&l@]]���'W�\��"�g��dOv���m�����;�����Q�����q�s��Y�n]lC���n;�����E� ��>E
m���Z8p �����(��W������#{��k���s�^�B������s(>����D%��B��m���F�4Lq���"~*L�>����)����?��R<"���"J����u9��������M�u��1���.��j������
�_�\���+nP�d�@�"j���Mn_��]0�����-
��}��T��W'�hQ��F6�-w���(� �^�����������=n���v����)l�c��(Q??���w�������j2F5T]��I&WW�* j��9
~NL�4)������\U�FI������R��������[���q')���;�vMS\�?�������(������{c�X�D���W��(�3H���<��QU�4Sa��n���n���4�$��X�:�W�q{wW�Z ���j$J�B5�G��TD���a@�1c��]�N��au��FQ�*5��H2�)Jc�b&��$&�?�0~�����# �L�<���=�qk
�����F1#���w<��J#�f�s����?_��tB��fu�|;�B]�f���� ����=U1'��������.^�����555������j�h���XA�T�w�]�&,��������;��h�xR�]��;�)�u�}&I�Q�^i�cT��[������q5���v���F�5�Z��\���:��+W�TgpB*;�����X�9�:N��9��:�T��5�)�����fC��/F�t�p��������_&��H�f�.�����|V��:?w:����P����D�<5�$�WzQ��1{���:u�}��,�'i�WU�;IS9@]]������fHu�c��E���Z�&T�5��+qk���?�������1:]:��s�%��+q�:� ����"��k��{I���������Dmw�}�Q�u�8�@j%q�P���qnz��(v�JtqC�`�����`;�3.{:$�NH]WagS{��R�D��7E]���!�����={Vu�d_�bo��p��eU���D3a��3[��i�)��qgE����q����Q
�OL���6�h��nFU���z�8���JEO�R�NR{�z�/��������[�F
m�5u�Sls�G�9a�����'WUU��m'��gS�_����DHE�q����o3"��.G�$���<��+���`_V���7�v7����>���R�G��������>�n~�T��M����}�L]�������{�v"�����W��VcO
{����/_V�9�q��=���S]�����Q�yS!��:��������`��G���k����'D��a*�:01�5*�V�b����
�Ng5Y�����C��@t`�&I��@����3c������-�@�KKK� G�{"q'�=<q�|��T�^��db�*�=�*���M����C�W`�1��V�uu���n����+�D�)*� ~"�����U�&��K���<�������
�|��E�{qce���h} 1{����<eoG+\l���\���=�kX��@Zpl ��<y��O������W�n~�}�����P������={����Y�T���j����[����Q��5�h���`�t |�N|�����U;Z ��;8�>����
ws���NX������s�
��c�s0�Y�G�7� � ���,�}{�=>���SU�g��+W���>�~}a&�������ml4��s���,8G�� �lg,������(�:���?�W8��J��t)��������:r?�?�@UY�O�����A�`t��u�Qb�$]�h�$%�G �a��$��}.Z����_�l�83\�5{����=G[0�*��Y#���q�t�Gsu��������!�!��.��*���+��VOt�"����*�2X���@BB.��N����`�|�����bQ��u���-���5��6�=
�b�*�����X�` �����-P�����r�}{[����e����<�m�8Ler~u���TW',BU��5qa0����S��p�SoUvI���+K5�q�KbZ��-6���9lq��}S�`�������B�����z0�"���s��� ������c(��T�Le����z������t�9��.����7����U��US_�Q�S-���K�D�<_�;b��X�)�����H�>��-Z7(�#�O�v�cH�{��b�
�eu��Im�1H�����c����L]c�����X�P����t����B�p���i�$��eJ��g�(--����P��E�Di�����Y���;��Jc�:t(n�������v<� }��c������ ���0�l��9�#
rI����s�s��Ul4���b��l�V��@1��~`�0���=U3s�������S\�{���<k :���dY�;&�����&B�y���jB���Q]�)bn�:D�vR��U�*�����T�Gr�i�Q�T���]Q��fL����BDB�]T�+�\�2k�,��k�Q�Fa���L���+W�u.��7n�Z���� l�a��I�^�;���v�3++k���q�*��G��|�avv6�W
��q����g�u|�B�3 L�ld���(�rn�0�kLR|o~~~���_m�=�0 ��4Q�mH2�I�1a���[*��=o���v�;���)���hbw�,�
��`����*��SH'G����"t�~����S�j�w��NggY���Y��K�����h������Vm�����MQ����fx��i,�=5�7o�LT�j�`��a����m�D�B�%K��K
ffLm�l�?Z��������FMQ;���+����Y���z�(�:�����f~|6�����U0A.�{�G�]6{����KD�'�j��t]�fI�G��� ��Tbbwy� u*d*�a�,7/�=E]
�9��A�HFUF���V�g�&��g�PhQ��|{pP\��b�HG}LBT�b�t��&"�UU{^LX�������g�������.��-T�;�zk���n^A�S<U����p9�T#"�UU{^L�[��4����)����f�B2���#����X��X�r/"�<FUF���7���_�/��u���{�
��;���Wy;����:�y �������l�F�u��.E?�zc�����M8&�pT�B�r���9*BDAtT%""""7cT%""""�bT%""""�bT%""""�bT%""""�bT%""""�bT%""""�bT%""""�bT%""""�bT%""""�bT%""""�bT%""""�bT%""""�bT%""""�bT%""""�bT%""""�bT%""""�bT%""""�bT%""""�bT%""""��������a������j��\^^�������[-Z%oKDDDD�.��jmm��A�T���Q��DgM������� ��*R)�&B������,P;�v�-�AG����A����Z��WP�}�&���KdpTE�6l��3h�����>��z���u]O��zODDDD�-S�*2%��
�6�|�����:��0��l���{""""�o�U�!{g�,,,D E����U�y��z�$�O �����F���7)3]�pK������G��7�u,w�aT�uv�Tg���Q�����Z��C��a�f�!�c�R?N�7�u,�4�Uc�����*n"�"�"}Z�x ��]Da�bv���&��U���M�Wu]�����%�av����E�[�> ��� �V�UG�����T���0���r��"
�-Mf���NPb��3�v�-y ��(,�@�.����x��*���]Da�bv����Q����E�[ fQXniU���]Da�bv����Q����E�[ fQXniU���]Da�bv����Q����E�[ fQXniU���]Da�bv����Q����E�[ fQX�^r�>b��2���}�.���1���r��=��,8zm��<m�h�;�*�*y��(,�@�.����d���U�f�0�����7��oZ��
�*y��(,�@�.�����t'����b���M�^�~7�WeT%�cv����E�;u�Zd[Y0{M���ZT*�_/O��6%B��sU�� ��(,�@�.�����6Ev�
��k~�(����k�W�����x���J���"
�-��(,w��[���M�����=�������s7���2�*y��(,�@�.�����G\��i|��?xLt$u�^���o1J+B��d*���}�.���1��"���5�u�[n,��=*�F��-��l3��k2��~�U���]Da�bTET�k�"O�V��Mxd�(�/g�c��3/��2��~�U���]Da�bT�����H��P���i ��>���v�����^��SU���]Da�bT���>[���|A���?X�����1T���J�FU�>fQXn�UE�R�����3�[�l\����M�'om�(*��Eu�*y��(,�@���x��G*C7C����'r��U�u���M���&��J���"
�-��(�[���������O���7�g�MO� �*y��(,�@���d\��|��R��Yq��������/�>��)FU�>fQXn�UE��r�Fd������n��t}�����bT%�cv���QU��;i>x)4bu �!R��i�w����0���1���r��*�k�]~+<y�����SQ��h���] E�5-���}�.���1����r_�
�:����v����qNE�����l�Z�SzU���]Da�bT����DN\
-?h�]�uA������#f����=�Q����E�[ FUQ����H�����3��;�/���MJ�~���)Z���OE�a���}�.���1�����>[���6'�NS�5x���}������9���0���1���r��*Jo��He(wc �����/�h�]�/�c�\U�1��FU�>fQXn�UE��r���=��#�?�>6N{�?o���x�lU�w��/���}�.���1����r7���'��,�sg~��b�������(�-U���]Da�bT%�r�4FV6?*�?4*:��5d���:��lP7�P]�Q����E�[ FUQb��7��}�����;��U��WC���S��f��L�� Z����K!�G�J���}�.���1��Q|�|m��W�6�b���D�gc��g*�����wgn0�fFU�>fQXn�U%���#V�Bg�^�����Wjx�~�aT%�cv���Q�����_���^�C�i��i/O�������������ky��;��G��F����U���]Da�bT���������O��9�����z7|�!����
��J���"
�-��W�����vH8�W|�d��aT%�cv�������6F~]�~���)ZEu�i�,�4���}�.���1�x��k�'r������������Q����E�[ f/A ]���v�������;<�����Q����E�[ f�h�#�.n����������b��aT%�cv�����*���Mj?��e���s�?�-
�*y��(,�@�.P|�8�
�g���v8���rK��J���"
�-�KF���l�s���wb��aT%�cv����%s]�
�6���T_,�7vvW�[FU�>fQXn��]\�lUx�Nc�c��@���WE��
����F��k��O�}->�����-
�*y��(,�@�.n�`�=S�|�Vv=d��3,�4���}�.���1���������0����\mh���t��9z���}���g��aT%�cv���������R����J�������=���/����*��7��w#qo>�U,�4���}�.���1��3�����C����;�P�k�{�-
�*y��(,�@�.}�zm����W��|�v�j�'�v�-
�*y��(,�@�.}l����1VH�����.�l�M,�4���}�.���1��_ ����WP=2�W|4�;L� �[FU�>fQXn��]�F������+�^��_���SSc���0���1���r�������y{��FY!�����G��Fc��aT%�cv�����W�4D���~�����~J��XniU���]Da�bv�=%B��k?��q������������Q����E�[ f��p�.��*`�T�R|Foc���HT-//�����T�Z
6L�u�E��m�K�]Da�bv�Y���������T��V?\A�-��*R&�&�3�:���������0���r���#"������.h?-U�F�
\�;��rK���������3���%%%i�%�av�������DW1_��~N�z�7O?x�?������&��*���>X\\��vT���4h�z�&����0���r����z-2{��Dn��:`���~����rK��Q�>E��'��z� ������Z��C�]Da�bvI���p������ �G��&l
����k��c������NQU�B��gIII�}t9h������m���!�.���1�t�������8*^O�j{���!Ua������`j�KFUJ��E�[ ��e�����5�^���9K�`��s��@�fc�.c��8<x)Tv#t�&\�i�Gv�
�37�������G�@����1�J��Q5*n�ATmll��ADD��6�9��)w��fz�W'�l�`����QD+��I�FU$K��X*n��F���&jk�����ge�Z����:�[ Tu��x���uQq3�����;���z�i����1����Q����� d���U������H�8��x����W�u8v�������U��������&����O��_�s���)��'j?���q�k]zi�$���2�\U�� �WH��I����0���r����D�o8��zf���\��[��U��fT���<���-y��(,�@�.��L����:aS ��j-��4�������I4y[�fQXn�<�]j#_/�� ��f�g�2��}�`T��#Q�( fQXn�<�]"�-�9���3��1�E�� cj+FUiU���]Da��Rv�v7u����.|TcT��Q����E�[ od3�<{�10�=�>=A�V&���DU�aT%�cv��(��KMCd����S����5f]�����q0�J��J���"
�-P&f��\Z��b�:=�I�/O�O_Y�QFUiU���]Da�����4��
��.�;�����}��A���U�aT%�cv�������1��Xp����;�w���������E��cT��Q����E�[ f����bh�#�i���+�+Rl�=&�.`T��Q����E�[���.�M�C�B{���5�JM�i��Z����b�G;���K���E�E���7O���*
�*y��(,�@��]L����]}�5[���8Z2x��ncT��Q����E�[�^�.�n������}����Z����s�F����I���0���1���r�����L�d8s�������G���L�j�1�7W67��:,���*��v7\�a6�U���0���1���r��������g��+*5�����*
�*y��(,�@=�]j"�,��!/�EC�5���4���}�.���u?������w�|��<m�9^�F���0���1���r���r�f��t��|7Z�;S]�QUFU�>fQXn���.M���
�m!�_��/��O]�QUFU�>fQXn���.[��OO��S��QUFU�>fQXn���]n����Oe*FUiU���]Da��4���"�n�w� .�o������?����2��4���}�.���9�K�������c����+o���I�8~^>��U�aT%�cv���f��������{��� #i�������|*#1�J��J���"
�-Bj*��������k��[N�n�j��'5�1�J��J���"
��y�p��c����!u���[M}��?y����YZ�z7l�4T�aT��Q����E���V2���!�>3Q�������V�u���0���1���r{�l ���u�C����f0��"�-
�*y��(,����KK��O�R����"�*�.����0���1���r{��l^|�|��@)�^���;u�v��E�[FU�>fQXn��������!u���DtHU�]Da��aT%�cv���hG*C��C�E���'�]���"
�-
�*y��(,w� ��{�����*^/M�����vS�.����0���1���rg�F1������t�����4}kY0�����]Da��aT%�cv��v���H�Q��E��lj�>[�GH��N
��(,�4���}�.����t�^���|�@�M���e�
�8��<���E�[FU�>fQXnW��"svo�����z==A�!p�R��:]�.����0���1���r�
��|�>r�*\r!��xp�>3o�1|e���W����\ �|��;|6�=��0���rK��J���"
��{V1�_�q�6xlt�L���\}�~�JM�;�v��(,�4���}�.������h���Sy=���6C�z��m��]�q0���rK��J���"
����`����3���^F�����1K�t������FQ���t���PEu��������E�[FU�>fQX��7��0�����������Kw�u�>��)`v����Q����E���4#�h��d����4U�t*��;J���E�[FU�>fQX������'�G���.�
��(,�4���}�.���ih�G��6��0�!Uav����Q����E��K�������!�������RfQXniU���]Da�ST�Ef�0��P�zq���T�����.����0���1���rw
!u�v#�6�jOj$s��:1���rK��J���"
��D��:-�C���"
�-
�*y��(,w\�S�����KS��e�w�?��(,�4���}�.���Q�=��I��}��������"
�-
�*y��(,�M�I�
�o��w�z%�Z�]Da��aT%�cv����!�����r/����"
�-
�*y��(����:%&��3W�1du�E�.����0���1��"��w"'��6�f� 8�
�%�RfQXniU��UE�p����;�C��y��/���L�����zo�~���C���"
�-
�*y��(�)��;�-�������������>M�z���)!Uav����Q���QU�L/wMCd�~����Kc_����6C�z��6��UY!Uav����Q���QU�-�/)>j~��C�^OO�����\(�cl9,�����O���E�[FU�>FUQ2��{��<~B�p�?o����y�b��N8��;M� fQXniU��UE��rG��O^��x||�3P�������M�]�*fQXniU��UEqy���
��i<�'��:]������:��1���rK��J���*�;�]��,-5���s���|m���m&��1���rK��Q�����6YYYV�6���>��j;l�0]�����%/aT�m�>y5��:00;:�>=A��l�]�0�1���rK��Q�TM�3q:���z[�FUQ\R�&d�a�����Q��F�
��xK����"
�-M�FU�5�{R�?�������$���1����{����]��S�>]��W�k�{��(,�4�9WA�������
B U���$y[�FUQ���~�y���[��w�>>^�����������E�[�DU]��
������j�kaa�j� ������Z��CUE��r_���l}Q?b��A��0���rK��QU�}����
�=�6�Q�M���{�FUQ���f�y[Y����w�8�7�8p��F�;�.����d|Tu^ eg�������X6(]�pA��H�4�]r�:C]�^�W�{,�)*�>3�q��������R_A�Qw�
y��{u���&�9WUeVu���*"��C������C��Cg�^F��M�3c��#Vo��2�j�������a�y�j���{��R�h�!�K��n�co&�������[y�T�C�Qw�
y�-M�FU�g4��(U�����w ��QU��=s���,���kt���$/�rfQXni25��p���F���U*n��7��l����0���i��v��[y��#�2��(,�4|���N�����[-Z9��'oK��*J�rC��v�j���n�^u���3��(,�4�}��:
@����<����%���$*w���G������M�fQXni<uYQ\�����;j93��3��9��Z�L�fQXniU��UE�*w���A�}�pg��0���rK��J���*�]�`�y��;S5�;S���E�[FU�>FUQT��v���-,1C����"
�-
�*y��({OU�Xr��x�5[�R���e�.����0���1�z^U]�������!�4gH}8�W��2�z��(,�4���}�������:�!�����~�>S�t�)UfQXniU��U������]��s�=���)w�7�� �.����0���1�f�����C�K���F�R���4=o�Qr!t��-�[fQXniU��U3T0���d��3�@}z�6bu ��4��(����E�[FU�>f�������OM�s�#c|�-������Ce�bv����Q����%�����m6�G��;s�Y;�cWBVw���1���rK��J�����n��[��x�^��k+���\"�r��"
�-
�*y���E"�{���}B����me�p���r��"
�-
�*y��;��UG�_L�>!��B��K��O����E�[FU�>f���Ef�2��!���2��b����1���rK��J�����n����>y5�����3��W������������E�[FU�>f�^�����gn����.�gN�d|�"����S�!9��z�^C�i�v��� �
�-��(,�4���}�.���)������d8M�:I[~�k�������E�[FU�>f���u��-�GE���'r��f���V&o56�
Z��,�@�.����t7����4���V�-,,t�%rf���b��U���^?���9K�l������FQ���t�he��:\����S�r��"
�-M��*r�<�������&YYYhh���;f��!f�]�n<�}�)�L�8s#��J��[ fQXni�����6��S�EC�BV#�~����u�9��'G'�A�}���\�{S���r��"
�-M�Q���v��A����{�@�����z_d�!��9�K
�{����/��������E�[��F���,��2��{0�t��1R|�����������L��3o��MO� �-��(,�4�:WU���co�0n�%��.�\�^��|gn�N=1^���8w����c�bv����[QU�Xm����R%Wav�� :s����8 u������V��b����1���rK�����W�+��Jn���H���P�f��Iq�D�6zm��RF/������1���rK�Q���$g�����<��&���8 u�$m������g0�
��"
�-
�*y���r�n����w�y�>{WF���
FU��]Da����
kkk����;��/i���V��qB��s�E�MDX�;�bT��E�[�nEUu��SAEUu��VE�!'���|q���?.��<l�4x�R��1���rK������"�����Z��U��H�./�~3?:�~��_Q��}��Ubv���&���������~U��.���=��o��p��#[�}ZyG\HUUbv����W�j�VEn����4o9|���Q��e�
x�l��Ubv�����O �_4��U�=<�]�P��c��t���C�|#�����
��@�.����t+����`���M �=<�]�����g�:����}c�2����QU fQXni�U�fU
�����6� z�k���#Wj��n��_ ��q&��Dp�a������p���<h*wc �zG�Ubv�����*���0���zmF�G�����) ��S]��*��(,�4���}��.�@d����J�5y�Q������@�.����t7�fee��P���9 �*��.;����� ������KS�_���_��|����Qk6�m7��5�J�������=���/���R;��*��(,�4����bUKJJTNU�W�;7d������H}�"P���Ubv���&���x���r��_]��lnuJ���7��#�K�����������!�5�4FU��]Da��I?�:���0U4�# �=�1���
�1������}3vF�jK��QU fQXni�U�i��L����9���{�Kv����M��Q�;S]��T�`T��E�[�n��j_Gj7�}�*�U%������\�y��'�k��y^j�`T��E�[�nEUuZ*���x*u&