|
| 1 | +#!/usr/bin/perl -w |
| 2 | + |
| 3 | +# |
| 4 | +# gen_qsort_tuple.pl |
| 5 | +# |
| 6 | +# This script generates specialized versions of the quicksort algorithm for |
| 7 | +# tuple sorting. The quicksort code is derived from the NetBSD code. The |
| 8 | +# code generated by this script runs significantly faster than vanilla qsort |
| 9 | +# when used to sort tuples. This speedup comes from a number of places. |
| 10 | +# The major effects are (1) inlining simple tuple comparators is much faster |
| 11 | +# than jumping through a function pointer and (2) swap and vecswap operations |
| 12 | +# specialized to the particular data type of interest (in this case, SortTuple) |
| 13 | +# are faster than the generic routines. |
| 14 | +# |
| 15 | +#Modifications from vanilla NetBSD source: |
| 16 | +# Add do ... while() macro fix |
| 17 | +# Remove __inline, _DIAGASSERTs, __P |
| 18 | +# Remove ill-considered "swap_cnt" switch to insertion sort, |
| 19 | +# in favor of a simple check for presorted input. |
| 20 | +# Instead of sorting arbitrary objects, we're always sorting SortTuples |
| 21 | +# Add CHECK_FOR_INTERRUPTS() |
| 22 | +# |
| 23 | +# CAUTION: if you change this file, see also qsort.c and qsort_arg.c |
| 24 | +# |
| 25 | + |
| 26 | +use strict; |
| 27 | + |
| 28 | +my$SUFFIX; |
| 29 | +my$EXTRAARGS; |
| 30 | +my$EXTRAPARAMS; |
| 31 | +my$CMPPARAMS; |
| 32 | + |
| 33 | +emit_qsort_boilerplate(); |
| 34 | + |
| 35 | +$SUFFIX ='tuple'; |
| 36 | +$EXTRAARGS =', SortTupleComparator cmp_tuple, Tuplesortstate *state'; |
| 37 | +$EXTRAPARAMS =', cmp_tuple, state'; |
| 38 | +$CMPPARAMS =', state'; |
| 39 | +emit_qsort_implementation(); |
| 40 | + |
| 41 | +$SUFFIX ='ssup'; |
| 42 | +$EXTRAARGS =', SortSupport ssup'; |
| 43 | +$EXTRAPARAMS =', ssup'; |
| 44 | +$CMPPARAMS =', ssup'; |
| 45 | +print<<'EOM'; |
| 46 | +#define cmp_ssup(a, b, ssup) \ |
| 47 | +ApplySortComparator((a)->datum1, (a)->isnull1, \ |
| 48 | +(b)->datum1, (b)->isnull1, ssup) |
| 49 | +EOM |
| 50 | +emit_qsort_implementation(); |
| 51 | + |
| 52 | +subemit_qsort_boilerplate |
| 53 | +{ |
| 54 | +print<<'EOM'; |
| 55 | +/* |
| 56 | + * autogenerated by src/backend/utils/sort/gen_qsort_tuple.pl, do not edit |
| 57 | + * This file is included by tuplesort.c, rather than compiled separately. |
| 58 | + */ |
| 59 | +
|
| 60 | +/*$NetBSD: qsort.c,v 1.13 2003/08/07 16:43:42 agc Exp $*/ |
| 61 | +
|
| 62 | +/*- |
| 63 | + * Copyright (c) 1992, 1993 |
| 64 | + *The Regents of the University of California. All rights reserved. |
| 65 | + * |
| 66 | + * Redistribution and use in source and binary forms, with or without |
| 67 | + * modification, are permitted provided that the following conditions |
| 68 | + * are met: |
| 69 | + * 1. Redistributions of source code must retain the above copyright |
| 70 | + * notice, this list of conditions and the following disclaimer. |
| 71 | + * 2. Redistributions in binary form must reproduce the above copyright |
| 72 | + * notice, this list of conditions and the following disclaimer in the |
| 73 | + * documentation and/or other materials provided with the distribution. |
| 74 | + * 3. Neither the name of the University nor the names of its contributors |
| 75 | + * may be used to endorse or promote products derived from this software |
| 76 | + * without specific prior written permission. |
| 77 | + * |
| 78 | + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND |
| 79 | + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
| 80 | + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
| 81 | + * ARE DISCLAIMED.IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE |
| 82 | + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
| 83 | + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
| 84 | + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
| 85 | + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
| 86 | + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
| 87 | + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
| 88 | + * SUCH DAMAGE. |
| 89 | + */ |
| 90 | +
|
| 91 | +/* |
| 92 | + * Qsort routine based on J. L. Bentley and M. D. McIlroy, |
| 93 | + * "Engineering a sort function", |
| 94 | + * Software--Practice and Experience 23 (1993) 1249-1265. |
| 95 | + * We have modified their original by adding a check for already-sorted input, |
| 96 | + * which seems to be a win per discussions on pgsql-hackers around 2006-03-21. |
| 97 | + */ |
| 98 | +
|
| 99 | +static void |
| 100 | +swapfunc(SortTuple *a, SortTuple *b, size_t n) |
| 101 | +{ |
| 102 | +do |
| 103 | +{ |
| 104 | +SortTuple t = *a; |
| 105 | +*a++ = *b; |
| 106 | +*b++ = t; |
| 107 | +} while (--n > 0); |
| 108 | +} |
| 109 | +
|
| 110 | +#define swap(a, b)\ |
| 111 | +do { \ |
| 112 | +SortTuple t = *(a);\ |
| 113 | +*(a) = *(b);\ |
| 114 | +*(b) = t;\ |
| 115 | +} while (0); |
| 116 | +
|
| 117 | +#define vecswap(a, b, n) if ((n) > 0) swapfunc((a), (b), (size_t)(n)) |
| 118 | +EOM |
| 119 | +} |
| 120 | + |
| 121 | +subemit_qsort_implementation |
| 122 | +{ |
| 123 | +print<<EOM; |
| 124 | +static SortTuple * |
| 125 | +med3_$SUFFIX(SortTuple *a, SortTuple *b, SortTuple *c$EXTRAARGS) |
| 126 | +{ |
| 127 | +return cmp_$SUFFIX(a, b$CMPPARAMS) < 0 ? |
| 128 | +(cmp_$SUFFIX(b, c$CMPPARAMS) < 0 ? b : |
| 129 | +(cmp_$SUFFIX(a, c$CMPPARAMS) < 0 ? c : a)) |
| 130 | +: (cmp_$SUFFIX(b, c$CMPPARAMS) > 0 ? b : |
| 131 | +(cmp_$SUFFIX(a, c$CMPPARAMS) < 0 ? a : c)); |
| 132 | +} |
| 133 | +
|
| 134 | +static void |
| 135 | +qsort_$SUFFIX(SortTuple *a, size_t n$EXTRAARGS) |
| 136 | +{ |
| 137 | +SortTuple *pa, |
| 138 | + *pb, |
| 139 | + *pc, |
| 140 | + *pd, |
| 141 | + *pl, |
| 142 | + *pm, |
| 143 | + *pn; |
| 144 | +intd, |
| 145 | +r, |
| 146 | +presorted; |
| 147 | +
|
| 148 | +loop: |
| 149 | +CHECK_FOR_INTERRUPTS(); |
| 150 | +if (n < 7) |
| 151 | +{ |
| 152 | +for (pm = a + 1; pm < a + n; pm++) |
| 153 | +for (pl = pm; pl > a && cmp_$SUFFIX(pl - 1, pl$CMPPARAMS) > 0; pl--) |
| 154 | +swap(pl, pl - 1); |
| 155 | +return; |
| 156 | +} |
| 157 | +presorted = 1; |
| 158 | +for (pm = a + 1; pm < a + n; pm++) |
| 159 | +{ |
| 160 | +CHECK_FOR_INTERRUPTS(); |
| 161 | +if (cmp_$SUFFIX(pm - 1, pm$CMPPARAMS) > 0) |
| 162 | +{ |
| 163 | +presorted = 0; |
| 164 | +break; |
| 165 | +} |
| 166 | +} |
| 167 | +if (presorted) |
| 168 | +return; |
| 169 | +pm = a + (n / 2); |
| 170 | +if (n > 7) |
| 171 | +{ |
| 172 | +pl = a; |
| 173 | +pn = a + (n - 1); |
| 174 | +if (n > 40) |
| 175 | +{ |
| 176 | +d = (n / 8); |
| 177 | +pl = med3_$SUFFIX(pl, pl + d, pl + 2 * d$EXTRAPARAMS); |
| 178 | +pm = med3_$SUFFIX(pm - d, pm, pm + d$EXTRAPARAMS); |
| 179 | +pn = med3_$SUFFIX(pn - 2 * d, pn - d, pn$EXTRAPARAMS); |
| 180 | +} |
| 181 | +pm = med3_$SUFFIX(pl, pm, pn$EXTRAPARAMS); |
| 182 | +} |
| 183 | +swap(a, pm); |
| 184 | +pa = pb = a + 1; |
| 185 | +pc = pd = a + (n - 1); |
| 186 | +for (;;) |
| 187 | +{ |
| 188 | +while (pb <= pc && (r = cmp_$SUFFIX(pb, a$CMPPARAMS)) <= 0) |
| 189 | +{ |
| 190 | +CHECK_FOR_INTERRUPTS(); |
| 191 | +if (r == 0) |
| 192 | +{ |
| 193 | +swap(pa, pb); |
| 194 | +pa++; |
| 195 | +} |
| 196 | +pb++; |
| 197 | +} |
| 198 | +while (pb <= pc && (r = cmp_$SUFFIX(pc, a$CMPPARAMS)) >= 0) |
| 199 | +{ |
| 200 | +CHECK_FOR_INTERRUPTS(); |
| 201 | +if (r == 0) |
| 202 | +{ |
| 203 | +swap(pc, pd); |
| 204 | +pd--; |
| 205 | +} |
| 206 | +pc--; |
| 207 | +} |
| 208 | +if (pb > pc) |
| 209 | +break; |
| 210 | +swap(pb, pc); |
| 211 | +pb++; |
| 212 | +pc--; |
| 213 | +} |
| 214 | +pn = a + n; |
| 215 | +r = Min(pa - a, pb - pa); |
| 216 | +vecswap(a, pb - r, r); |
| 217 | +r = Min(pd - pc, pn - pd - 1); |
| 218 | +vecswap(pb, pn - r, r); |
| 219 | +if ((r = pb - pa) > 1) |
| 220 | +qsort_$SUFFIX(a, r$EXTRAPARAMS); |
| 221 | +if ((r = pd - pc) > 1) |
| 222 | +{ |
| 223 | +/* Iterate rather than recurse to save stack space */ |
| 224 | +a = pn - r; |
| 225 | +n = r; |
| 226 | +goto loop; |
| 227 | +} |
| 228 | +/*qsort_$SUFFIX(pn - r, r$EXTRAPARAMS);*/ |
| 229 | +} |
| 230 | +
|
| 231 | +EOM |
| 232 | +} |