On 21 November 2011 22:55, Robert Haas <robertmh...@gmail.com> wrote:
> Results on my machine, for what they're worth:
I was curious as to how much of an improvement I'd made to sorting in
isolation. I've adding simple sort timing instrumentation to the code
in a revised patch, attached, for the convenience of reviewers.
This patch adds an int8 specialisation, but it also supports fast path
sorting of timestamps by using that same int8 specialisation (for
HAVE_INT64_TIMESTAMP builds at least - didn't know if it was worth
handling the NaN crud for the other case). ISTM that various different
types with identical internal representations can share
specialisations like this, which I hope will alleviate some earlier
concerns about both the limited applicability of this optimisation and
the possible proliferation of specialisations.
Here's some raw qsort figures in seconds for the query "select * from
orderlines order by test" (where test is a timestamptz column I added
and updated with some data, executing repeatedly on the same machine
as before):
Before:
DEBUG: elapsed: 0.031738
DEBUG: elapsed: 0.031595
DEBUG: elapsed: 0.031502
DEBUG: elapsed: 0.031378
DEBUG: elapsed: 0.031359
DEBUG: elapsed: 0.031413
DEBUG: elapsed: 0.031499
DEBUG: elapsed: 0.031394
DEBUG: elapsed: 0.031368
After:
DEBUG: elapsed: 0.013341
DEBUG: elapsed: 0.014608
DEBUG: elapsed: 0.013809
DEBUG: elapsed: 0.013244
DEBUG: elapsed: 0.014307
DEBUG: elapsed: 0.013207
DEBUG: elapsed: 0.013227
DEBUG: elapsed: 0.013264
DEBUG: elapsed: 0.013143
DEBUG: elapsed: 0.013455
DEBUG: elapsed: 0.013447
I wonder, is it worth qualifying that the "Sort Method" was a
"quicksort (fast path)" sort within explain analyze output? This is a
rather large improvement, so It might actually be something that
people look out for, as it might be tricky to remember the exact
circumstances under which the optimisation kicks in by the time we're
done here.
I haven't had as much time as I'd like to polish this patch, or to get
clearer answers. I expect to spend more time on it over the weekend.
--
Peter Geoghegan http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training and Services
From 687779e799eb0d0064f86192cc74ea473ff9a607 Mon Sep 17 00:00:00 2001
From: peter2ndQuadrant <pe...@2ndquadrant.com>
Date: Sun, 20 Nov 2011 20:36:25 +0000
Subject: [PATCH] Initial commit of optimization
Stop directly using oid
Added int8 quicksort fast path specialisation, which can also be used in
place of F_TIMESTAMP_CMP for HAVE_INT64_TIMESTAMP builds.
Rebased, revised patch for -hackers, with timestamp and int8 fast path
sorting using the same int8 specialization.
Remove unneeded line
Rebase for -hackers
---
src/backend/utils/sort/tuplesort.c | 105 +++++++++++++++-
src/include/utils/template_qsort_arg.h | 217 ++++++++++++++++++++++++++++++++
2 files changed, 316 insertions(+), 6 deletions(-)
create mode 100644 src/include/utils/template_qsort_arg.h
diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c
index 3505236..4962973 100644
--- a/src/backend/utils/sort/tuplesort.c
+++ b/src/backend/utils/sort/tuplesort.c
@@ -107,11 +107,13 @@
#include "miscadmin.h"
#include "pg_trace.h"
#include "utils/datum.h"
+#include "utils/fmgroids.h"
#include "utils/logtape.h"
#include "utils/lsyscache.h"
#include "utils/memutils.h"
#include "utils/pg_rusage.h"
#include "utils/rel.h"
+#include "utils/template_qsort_arg.h"
#include "utils/tuplesort.h"
@@ -1225,12 +1227,60 @@ puttuple_common(Tuplesortstate *state, SortTuple *tuple)
}
/*
- * All tuples have been provided; finish the sort.
+ * Manufacture type specific sorting specialisations
+ * with inline comparators
+ */
+static inline int
+compare_int4(Datum first, Datum second)
+{
+ int32 first_int = DatumGetInt32(first);
+ int32 second_int = DatumGetInt32(second);
+
+ if (first_int > second_int)
+ return 1;
+ else if (first_int == second_int)
+ return 0;
+ else
+ return -1;
+}
+
+static inline int
+compare_int8(Datum first, Datum second)
+{
+ int64 first_int = DatumGetInt64(first);
+ int64 second_int = DatumGetInt64(second);
+
+ if (first_int > second_int)
+ return 1;
+ else if (first_int == second_int)
+ return 0;
+ else
+ return -1;
+}
+
+TEMPLATE_QSORT_ARG(int4, compare_int4);
+TEMPLATE_QSORT_ARG(int8, compare_int8);
+
+double timeval_subtract(struct timeval *x, struct timeval *y);
+double timeval_subtract(struct timeval *x, struct timeval *y)
+{
+ struct timeval result;
+ /* Compute the time remaining to wait. tv_usec is certainly positive. */
+ result.tv_sec = x->tv_sec - y->tv_sec;
+ result.tv_usec = x->tv_usec - y->tv_usec;
+
+ /* return difference in seconds */
+ return result.tv_sec + ((double) result.tv_usec / 1000000);
+}
+
+/*
+ * All tuples have been provided; perform the sort.
*/
void
tuplesort_performsort(Tuplesortstate *state)
{
MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
+ struct timeval begin, end;
#ifdef TRACE_SORT
if (trace_sort)
@@ -1247,11 +1297,51 @@ tuplesort_performsort(Tuplesortstate *state)
* amount of memory. Just qsort 'em and we're done.
*/
if (state->memtupcount > 1)
- qsort_arg((void *) state->memtuples,
- state->memtupcount,
- sizeof(SortTuple),
- (qsort_arg_comparator) state->comparetup,
- (void *) state);
+ {
+ /*
+ * Choose between various type-specific qsort variants.
+ * Do so to avail of per-type compiler optimizations, in
+ * particular, inlining of comparators.
+ */
+ gettimeofday(&begin, NULL);
+ if (state->scanKeys && state->scanKeys->sk_func.fn_oid == F_BTINT4CMP &&
+ state->comparetup == &comparetup_heap)
+ {
+ int4_qsort_arg((void *) state->memtuples,
+ state->memtupcount,
+ sizeof(SortTuple),
+ (void *) state);
+ }
+ else if (state->scanKeys &&
+ (
+ /* Some comparison that has an underlying int8 representation */
+ state->scanKeys->sk_func.fn_oid == F_BTINT8CMP
+#ifdef HAVE_INT64_TIMESTAMP
+ || state->scanKeys->sk_func.fn_oid == F_TIMESTAMP_CMP
+#endif
+ )
+ && state->comparetup == &comparetup_heap)
+ {
+ int8_qsort_arg((void *) state->memtuples,
+ state->memtupcount,
+ sizeof(SortTuple),
+ (void *) state);
+ }
+ else
+ {
+ /*
+ * Finally, fall back on type-neutral qsort with
+ * function-pointer comparator
+ */
+ qsort_arg((void *) state->memtuples,
+ state->memtupcount,
+ sizeof(SortTuple),
+ (qsort_arg_comparator) state->comparetup,
+ (void *) state);
+ }
+ gettimeofday(&end, NULL);
+ elog(DEBUG1, "elapsed: %f", timeval_subtract(&end, &begin));
+ }
state->current = 0;
state->eof_reached = false;
state->markpos_offset = 0;
@@ -2657,6 +2747,9 @@ myFunctionCall2Coll(FmgrInfo *flinfo, Oid collation, Datum arg1, Datum arg2)
* and return a 3-way comparison result. This takes care of handling
* reverse-sort and NULLs-ordering properly. We assume that DESC and
* NULLS_FIRST options are encoded in sk_flags the same way btree does it.
+ *
+ * Note that this logic is more-or-less duplicated in template_qsort_arg.h,
+ * and "instantiated" per-type there.
*/
static inline int32
inlineApplySortFunction(FmgrInfo *sortFunction, int sk_flags, Oid collation,
diff --git a/src/include/utils/template_qsort_arg.h b/src/include/utils/template_qsort_arg.h
new file mode 100644
index 0000000..41f8237
--- /dev/null
+++ b/src/include/utils/template_qsort_arg.h
@@ -0,0 +1,217 @@
+/*-------------------------------------------------------------------------
+ * template_qsort_arg.h: "template" version of qsort_arg.c
+ *
+ * This version of qsort_arg is exclusively used within tuplesort.c to
+ * more efficiently sort common types such as integers and floats. In
+ * providing this version, we seek to take advantage of compile-time
+ * optimisations for specific types, in particular, the inlining of
+ * comparators, as well as reducing the overhead of comparisons that
+ * the general SQL-callable-function API imposes.
+ *
+ * It is assumed that any types that use this infrastructure have at
+ * most one element in their ScanKeys array.
+ *
+ * CAUTION: if you change this file, see also qsort_arg.c as well as
+ * qsort.c. qsort_arg.c should be considered authoratative.
+ *
+ * Portions Copyright (c) 1996-2011, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * src/include/utils/template_qsort_arg.h
+ *-------------------------------------------------------------------------
+ */
+
+#include "c.h"
+
+#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;
+
+#define thistype_vecswap(TYPE, a, b, n) if ((n) > 0) TYPE##_swapfunc((a), (b), (size_t)(n), swaptype)
+
+#define thistype_swap(TYPE, a, b) \
+if (swaptype == 0) { \
+ long t = *(long *)(void *)(a); \
+ *(long *)(void *)(a) = *(long *)(void *)(b); \
+ *(long *)(void *)(b) = t; \
+ } else \
+ TYPE##_swapfunc(a, b, es, swaptype)
+
+/*
+ * This macro manufactures a type-specific implementation of qsort_arg with
+ * the comparator, COMPAR, known at compile time. COMPAR is typically an
+ * inline function.
+ *
+ * COMPAR should take as its arguments two Datums, and return an int, in
+ * line with standard qsort convention.
+ *
+ * We have void* parameters for TYPE##AppSort just to shut up the compiler.
+ * They could be SortTuple pointers instead, but that would make it more
+ * difficult to keep template_qsort_arg.h consistent with qsort_arg.c.
+ *
+ */
+
+#define TEMPLATE_QSORT_ARG(TYPE, COMPAR) \
+void TYPE##_qsort_arg(void *a, size_t n, size_t es, void *arg); \
+ \
+static inline int32 \
+TYPE##AppSort(const void *a, const void *b, Tuplesortstate *state) \
+{ \
+ int32 compare; \
+ const SortTuple* aT = a; \
+ const SortTuple* bT = b; \
+ /* Allow interrupting long sorts */ \
+ CHECK_FOR_INTERRUPTS(); \
+ \
+ Assert(state->nKeys == 1); \
+ Assert(state->scanKeys); \
+ \
+ if ( aT->isnull1) \
+ { \
+ if (bT->isnull1) \
+ compare = 0; /* NULL "=" NULL */ \
+ else if (state->scanKeys->sk_flags & SK_BT_NULLS_FIRST) \
+ compare = -1; /* NULL "<" NOT_NULL */ \
+ else \
+ compare = 1; /* NULL ">" NOT_NULL */ \
+ } \
+ else if (bT->isnull1) \
+ { \
+ if (state->scanKeys->sk_flags & SK_BT_NULLS_FIRST) \
+ compare = 1; /* NOT_NULL ">" NULL */ \
+ else \
+ compare = -1; /* NOT_NULL "<" NULL */ \
+ } \
+ else \
+ { \
+ compare = COMPAR(aT->datum1, bT->datum1); \
+ \
+ if (state->scanKeys->sk_flags & SK_BT_DESC) \
+ compare = -compare; \
+ } \
+ \
+ return compare; \
+} \
+ \
+static inline void \
+TYPE##_swapfunc(char *a, char *b, size_t n, int swaptype) \
+{ \
+ if (swaptype <= 1) \
+ swapcode(long, a, b, n); \
+ else \
+ swapcode(char, a, b, n); \
+} \
+ \
+static inline char * \
+TYPE##_med3(char *a, char *b, char *c, void *arg) \
+{ \
+ return TYPE##AppSort(a, b, arg) < 0 ? \
+ (TYPE##AppSort(b, c, arg) < 0 ? b : (TYPE##AppSort(a, c, arg) < 0 ? c : a)) \
+ : (TYPE##AppSort(b, c, arg) > 0 ? b : (TYPE##AppSort(a, c, arg) < 0 ? a : c)); \
+} \
+ \
+void \
+TYPE##_qsort_arg(void *a, size_t n, size_t es, void *arg) \
+{ \
+ char *pa, \
+ *pb, \
+ *pc, \
+ *pd, \
+ *pl, \
+ *pm, \
+ *pn; \
+ int d, \
+ 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 && TYPE##AppSort(pl - es, pl, arg) > 0; \
+ pl -= es) \
+ thistype_swap(TYPE, pl, pl - es); \
+ return; \
+ } \
+ presorted = 1; \
+ for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es) \
+ { \
+ if (TYPE##AppSort(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) \
+ { \
+ d = (n / 8) * es; \
+ pl = TYPE##_med3(pl, pl + d, pl + 2 * d, arg); \
+ pm = TYPE##_med3(pm - d, pm, pm + d, arg); \
+ pn = TYPE##_med3(pn - 2 * d, pn - d, pn, arg); \
+ } \
+ pm = TYPE##_med3(pl, pm, pn, arg); \
+ } \
+ thistype_swap(TYPE, a, pm); \
+ pa = pb = (char *) a + es; \
+ pc = pd = (char *) a + (n - 1) * es; \
+ for (;;) \
+ { \
+ while (pb <= pc && (r = TYPE##AppSort(pb, a, arg)) <= 0) \
+ { \
+ if (r == 0) \
+ { \
+ thistype_swap(TYPE, pa, pb); \
+ pa += es; \
+ } \
+ pb += es; \
+ } \
+ while (pb <= pc && (r = TYPE##AppSort(pc, a, arg)) >= 0) \
+ { \
+ if (r == 0) \
+ { \
+ thistype_swap(TYPE, pc, pd); \
+ pd -= es; \
+ } \
+ pc -= es; \
+ } \
+ if (pb > pc) \
+ break; \
+ thistype_swap(TYPE, pb, pc); \
+ pb += es; \
+ pc -= es; \
+ } \
+ pn = (char *) a + n * es; \
+ r = Min(pa - (char *) a, pb - pa); \
+ thistype_vecswap(TYPE, a, pb - r, r); \
+ r = Min(pd - pc, pn - pd - es); \
+ thistype_vecswap(TYPE, pb, pn - r, r); \
+ if ((r = pb - pa) > es) \
+ TYPE##_qsort_arg(a, r / es, es, arg); \
+ if ((r = pd - pc) > es) \
+ { \
+ /* Iterate rather than recurse to save stack space */ \
+ a = pn - r; \
+ n = r / es; \
+ goto loop; \
+ } \
+} \
+
--
1.7.7.3
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
