diff options
Diffstat (limited to 'src/backend/utils')
| -rw-r--r-- | src/backend/utils/sort/gen_qsort_tuple.pl | 86 |
1 files changed, 60 insertions, 26 deletions
diff --git a/src/backend/utils/sort/gen_qsort_tuple.pl b/src/backend/utils/sort/gen_qsort_tuple.pl index 18dd751b382..6186d0a5bab 100644 --- a/src/backend/utils/sort/gen_qsort_tuple.pl +++ b/src/backend/utils/sort/gen_qsort_tuple.pl @@ -14,11 +14,13 @@ # # 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() +# 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 # @@ -43,9 +45,11 @@ $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(); @@ -53,7 +57,8 @@ sub emit_qsort_boilerplate { print <<'EOM'; /* - * autogenerated by src/backend/utils/sort/gen_qsort_tuple.pl, do not edit + * autogenerated by src/backend/utils/sort/gen_qsort_tuple.pl, do not edit! + * * This file is included by tuplesort.c, rather than compiled separately. */ @@ -78,7 +83,7 @@ sub emit_qsort_boilerplate * 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 + * 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) @@ -92,8 +97,16 @@ sub emit_qsort_boilerplate * 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 @@ -114,7 +127,8 @@ swapfunc(SortTuple *a, SortTuple *b, size_t n) *(b) = t; \ } while (0); -#define vecswap(a, b, n) if ((n) > 0) swapfunc((a), (b), (size_t)(n)) +#define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n) + EOM } @@ -141,8 +155,9 @@ qsort_$SUFFIX(SortTuple *a, size_t n$EXTRAARGS) *pl, *pm, *pn; - int d, - r, + size_t d1, + d2; + int r, presorted; loop: @@ -173,7 +188,8 @@ loop: pn = a + (n - 1); if (n > 40) { - d = (n / 8); + 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); @@ -187,23 +203,23 @@ loop: { while (pb <= pc && (r = cmp_$SUFFIX(pb, a$CMPPARAMS)) <= 0) { - CHECK_FOR_INTERRUPTS(); if (r == 0) { swap(pa, pb); pa++; } pb++; + CHECK_FOR_INTERRUPTS(); } while (pb <= pc && (r = cmp_$SUFFIX(pc, a$CMPPARAMS)) >= 0) { - CHECK_FOR_INTERRUPTS(); if (r == 0) { swap(pc, pd); pd--; } pc--; + CHECK_FOR_INTERRUPTS(); } if (pb > pc) break; @@ -212,21 +228,39 @@ loop: pc--; } pn = a + n; - r = Min(pa - a, pb - pa); - vecswap(a, pb - r, r); - r = Min(pd - pc, pn - pd - 1); - vecswap(pb, pn - r, r); - if ((r = pb - pa) > 1) - qsort_$SUFFIX(a, r$EXTRAPARAMS); - if ((r = pd - pc) > 1) + 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) { - /* Iterate rather than recurse to save stack space */ - a = pn - r; - n = r; - goto loop; + /* 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; + } } -/* qsort_$SUFFIX(pn - r, r$EXTRAPARAMS);*/ } - EOM } |