From 853ffc1723cc90958ab224005c7020a6f7e9d512 Mon Sep 17 00:00:00 2001 From: Robert Haas Date: Tue, 14 Feb 2012 16:31:19 -0500 Subject: [PATCH] Generate qsort_tuple.c --- src/backend/Makefile | 4 +- src/backend/utils/sort/.gitignore | 1 + src/backend/utils/sort/Makefile | 8 ++ .../{qsort_tuple.c => gen_qsort_tuple.pl} | 111 +++++++++++++----- src/backend/utils/sort/tuplesort.c | 14 ++- src/port/qsort.c | 2 +- src/port/qsort_arg.c | 2 +- 7 files changed, 105 insertions(+), 37 deletions(-) create mode 100644 src/backend/utils/sort/.gitignore rename src/backend/utils/sort/{qsort_tuple.c => gen_qsort_tuple.pl} (55%) mode change 100644 => 100755 diff --git a/src/backend/Makefile b/src/backend/Makefile index 0c763dd375..461257ce58 100644 --- a/src/backend/Makefile +++ b/src/backend/Makefile @@ -202,6 +202,7 @@ distprep: $(MAKE) -C replication repl_gram.c repl_scanner.c $(MAKE) -C utils fmgrtab.c fmgroids.h errcodes.h $(MAKE) -C utils/misc guc-file.c + $(MAKE) -C utils/sort qsort_tuple.c ########################################################################## @@ -315,7 +316,8 @@ maintainer-clean: distclean utils/fmgroids.h \ utils/fmgrtab.c \ utils/errcodes.h \ - utils/misc/guc-file.c + utils/misc/guc-file.c \ + utils/sort/qsort_tuple.c ########################################################################## diff --git a/src/backend/utils/sort/.gitignore b/src/backend/utils/sort/.gitignore new file mode 100644 index 0000000000..f2958633e6 --- /dev/null +++ b/src/backend/utils/sort/.gitignore @@ -0,0 +1 @@ +/qsort_tuple.c diff --git a/src/backend/utils/sort/Makefile b/src/backend/utils/sort/Makefile index 2ef4965ee6..f46ce41610 100644 --- a/src/backend/utils/sort/Makefile +++ b/src/backend/utils/sort/Makefile @@ -14,4 +14,12 @@ include $(top_builddir)/src/Makefile.global OBJS = logtape.o sortsupport.o 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/qsort_tuple.c b/src/backend/utils/sort/gen_qsort_tuple.pl old mode 100644 new mode 100755 similarity index 55% rename from src/backend/utils/sort/qsort_tuple.c rename to src/backend/utils/sort/gen_qsort_tuple.pl index c7857fa020..9a39b1ee6d --- a/src/backend/utils/sort/qsort_tuple.c +++ b/src/backend/utils/sort/gen_qsort_tuple.pl @@ -1,17 +1,60 @@ +#!/usr/bin/perl -w + +# +# 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. +# 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; + +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'; /* - * qsort_tuple.c: specialized version of qsort, for SortTuple objects - * - * This file is included by tuplesort.c, rather than compiled separately. - * - * 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. - * - * CAUTION: if you change this file, see also qsort.c and qsort_arg.c - * - * src/backend/utils/sort/qsort_tuple.c + * autogenerated by src/backend/utils/sort/gen_qsort.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 $ */ @@ -72,19 +115,24 @@ swapfunc(SortTuple *a, SortTuple *b, size_t n) } while (0); #define vecswap(a, b, n) if ((n) > 0) swapfunc((a), (b), (size_t)(n)) +EOM +} +sub emit_qsort_implementation +{ + print < 0 ? b : (cmp(a, c, state) < 0 ? a : c)); + 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_tuple(SortTuple *a, size_t n, SortTupleComparator cmp, - Tuplesortstate *state) +qsort_$SUFFIX(SortTuple *a, size_t n$EXTRAARGS) { SortTuple *pa, *pb, @@ -102,7 +150,7 @@ loop: if (n < 7) { for (pm = a + 1; pm < a + n; pm++) - for (pl = pm; pl > a && cmp(pl - 1, pl, state) > 0; pl--) + for (pl = pm; pl > a && cmp_$SUFFIX(pl - 1, pl$CMPPARAMS) > 0; pl--) swap(pl, pl - 1); return; } @@ -110,7 +158,7 @@ loop: for (pm = a + 1; pm < a + n; pm++) { CHECK_FOR_INTERRUPTS(); - if (cmp(pm - 1, pm, state) > 0) + if (cmp_$SUFFIX(pm - 1, pm$CMPPARAMS) > 0) { presorted = 0; break; @@ -126,18 +174,18 @@ loop: if (n > 40) { d = (n / 8); - pl = med3_tuple(pl, pl + d, pl + 2 * d, cmp, state); - pm = med3_tuple(pm - d, pm, pm + d, cmp, state); - pn = med3_tuple(pn - 2 * d, pn - d, pn, cmp, state); + 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_tuple(pl, pm, pn, cmp, state); + 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(pb, a, state)) <= 0) + while (pb <= pc && (r = cmp_$SUFFIX(pb, a$CMPPARAMS)) <= 0) { CHECK_FOR_INTERRUPTS(); if (r == 0) @@ -147,7 +195,7 @@ loop: } pb++; } - while (pb <= pc && (r = cmp(pc, a, state)) >= 0) + while (pb <= pc && (r = cmp_$SUFFIX(pc, a$CMPPARAMS)) >= 0) { CHECK_FOR_INTERRUPTS(); if (r == 0) @@ -169,7 +217,7 @@ loop: r = Min(pd - pc, pn - pd - 1); vecswap(pb, pn - r, r); if ((r = pb - pa) > 1) - qsort_tuple(a, r, cmp, state); + qsort_$SUFFIX(a, r$EXTRAPARAMS); if ((r = pd - pc) > 1) { /* Iterate rather than recurse to save stack space */ @@ -177,5 +225,8 @@ loop: n = r; goto loop; } -/* qsort_tuple(pn - r, r, cmp, state);*/ +/* qsort_tuple(pn - r, r$EXTRAPARAMS);*/ +} + +EOM } diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c index 0dfe9fb9f1..6c7fa062ae 100644 --- a/src/backend/utils/sort/tuplesort.c +++ b/src/backend/utils/sort/tuplesort.c @@ -1229,10 +1229,16 @@ tuplesort_performsort(Tuplesortstate *state) * amount of memory. Just qsort 'em and we're done. */ if (state->memtupcount > 1) - qsort_tuple(state->memtuples, - state->memtupcount, - state->comparetup, - state); + { + if (state->comparetup == comparetup_heap && state->nKeys == 1) + qsort_ssup(state->memtuples, state->memtupcount, + state->sortKeys); + else + qsort_tuple(state->memtuples, + state->memtupcount, + state->comparetup, + state); + } state->current = 0; state->eof_reached = false; state->markpos_offset = 0; diff --git a/src/port/qsort.c b/src/port/qsort.c index 8e2c6d92c2..49d8fa7ab6 100644 --- a/src/port/qsort.c +++ b/src/port/qsort.c @@ -7,7 +7,7 @@ * Remove ill-considered "swap_cnt" switch to insertion sort, * in favor of a simple check for presorted input. * - * CAUTION: if you change this file, see also qsort_arg.c + * CAUTION: if you change this file, see also qsort_arg.c, gen_qsort_tuple.pl * * src/port/qsort.c */ diff --git a/src/port/qsort_arg.c b/src/port/qsort_arg.c index 28d1894992..3091eb09ea 100644 --- a/src/port/qsort_arg.c +++ b/src/port/qsort_arg.c @@ -7,7 +7,7 @@ * Remove ill-considered "swap_cnt" switch to insertion sort, * in favor of a simple check for presorted input. * - * CAUTION: if you change this file, see also qsort.c + * CAUTION: if you change this file, see also qsort.c, gen_qsort_tuple.pl * * src/port/qsort_arg.c */ -- 2.39.5