pg.ddx.io pgsql-hackers@postgresql.org mailing list archive help / color / mirror / Atom feed From: Kefan Yang <starordust@gmail.com>
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Cc: Andrey Borodin <x4mmm@yandex-team.ru>
Cc: Peter Geoghegan <pg@bowt.ie>
Cc: alvherre@2ndquadrant.com <alvherre@2ndquadrant.com>
Cc: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Subject: RE: GSOC 2018 Project - A New Sorting Routine
Date: Mon, 23 Jul 2018 15:21:01 -0700
Message-ID: <5b5654cc.1c69fb81.5ea44.d698@mx.google.com> (raw )
In-Reply-To: <58417882-04e3-b23e-b53e-7d0720558335@2ndquadrant.com >
References: <CAF448YLZz5cD+w5qYQGMcfFPY9zAu2mkkiCtOPSBJmwbjuPNig@mail.gmail.com >
<57ae7691-6dc8-d6d0-361a-a7269e656273@2ndquadrant.com >
<CAF448YKLbmmSPbb_AFEaTKozjnFOEfT+s2eiSjfH=us34VNr4w@mail.gmail.com >
<CAF448YK0xhqK6mg3EeP-dt4j9V-VxkG8Vswmrt3t90OYSrNSsQ@mail.gmail.com >
<CAH2-Wzmj2XstMK58tJ0yEr+0MwpqMU8rfUB0j7GVe=p+yW5rTg@mail.gmail.com >
<00147235-69d3-d4f0-36c1-198d630af7ad@2ndquadrant.com >
<1C5B17F1-D37F-4730-A2E4-EB7288C6DC09@yandex-team.ru >
<78b9c822-e127-5250-a01c-4c51a50c82bd@2ndquadrant.com >
<5b4fad82.1c69fb81.7a6f6.d32b@mx.google.com >
<58417882-04e3-b23e-b53e-7d0720558335@2ndquadrant.com >
Hi Tomas!
I did a few tests on my own Linux machine, but the problem is that my resources on AWS(CPU, RAM and even Disk space) are very limited. I considered establishing virtual machine on my own PC but the performance is even worse.
My original patch has two main optimizations: (1) switch to heap sort when depth limit exceeded (2) check whether the array is presorted only once at the beginning. Now I want to test these optimizations separately. On AWS EC2 instance, regressions on CREATE INDEX cases seems to be less significant if we use (1) only, but I can only test up to 100000 records and 512MB memory using your scripts.
So would you mind re-running the tests using the two patches I provided in the attachment? That will be very helpful
Regards,
Kefan
From: Tomas Vondra
Sent: July 18, 2018 2:26 PM
To: Kefan Yang
Cc: Andrey Borodin; Peter Geoghegan; PostgreSQL Hackers
Subject: Re: GSOC 2018 Project - A New Sorting Routine
I don't have any script for that - load the files into a spreadsheet,
create pivot tables and you're done.
regards
On 07/18/2018 11:13 PM, Kefan Yang wrote:
> Hey Tomas!
>
>
>
> I am trying to reproduce the results on my machine. Could you please
> share the script to generate .ods files?
>
>
>
> Regards,
>
> Kefan
>
>
>
> *From: *Tomas Vondra <mailto:tomas.vondra@2ndquadrant.com>
> *Sent: *July 18, 2018 2:05 AM
> *To: *Andrey Borodin <mailto:x4mmm@yandex-team.ru >
> *Cc: *Peter Geoghegan <mailto:pg@bowt.ie>; Kefan Yang
> <mailto:starordust@gmail.com>; PostgreSQL Hackers
> <mailto:pgsql-hackers@lists.postgresql.org >
> *Subject: *Re: GSOC 2018 Project - A New Sorting Routine
>
>
>
>
>
>
>
> On 07/18/2018 07:06 AM, Andrey Borodin wrote:
>
>> Hi, Tomas!
>
>>
>
>>> 15 июля 2018 г., в 1:20, Tomas Vondra <tomas.vondra@2ndquadrant.com
>
>>> <mailto:tomas.vondra@2ndquadrant.com>> написал(а):
>
>>>
>
>>> So I doubt it's this, but I've tweaked the scripts to also set this GUC
>
>>> and restarted the tests on both machines. Let's see what that does.
>
>>
>
>> Do you observe any different results?
>
>>
>
>
>
> It did change the CREATE INDEX results, depending on the scale. The full
>
> data is available at [1] and [2], attached is a spreadsheet summary from
>
> the Xeon box.
>
>
>
> For the largest scale (1M rows) the regressions for CREATE INDEX queries
>
> mostly disappeared. For 10k rows it still affects CREATE INDEX with a
>
> text column, and the 100k case behaves just like before (so significant
>
> regressions for CREATE INDEX).
>
>
>
> I don't have time to investigate this further at the moment, but I'm
>
> still of the opinion that there's little to gain by replacing our
>
> current sort algorithm with this.
>
>
>
>
>
> [1] https://bitbucket.org/tvondra/sort-intro-sort-xeon/src/master/
>
> [2] https://bitbucket.org/tvondra/sort-intro-sort-i5/src/master/
>
>
>
> regards
>
>
>
> --
>
> Tomas Vondra http://www.2ndQuadrant.com
>
> PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
>
>
>
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
Attachments:
[application/octet-stream] check_once.diff (9.7K, ../5b5654cc.1c69fb81.5ea44.d698@mx.google.com/3-check_once.diff)
download | inline diff:
diff --git a/src/backend/utils/sort/gen_qsort_tuple.pl b/src/backend/utils/sort/gen_qsort_tuple.pl
index 6186d0a..20d7fb4 100644
--- a/src/backend/utils/sort/gen_qsort_tuple.pl
+++ b/src/backend/utils/sort/gen_qsort_tuple.pl
@@ -108,6 +108,8 @@ sub emit_qsort_boilerplate
* worth the effort", but we have seen crashes in the field due to stack
* overrun, so that judgment seems wrong.
*/
+
+#include <math.h>
static void
swapfunc(SortTuple *a, SortTuple *b, size_t n)
@@ -146,7 +148,7 @@ med3_$SUFFIX(SortTuple *a, SortTuple *b, SortTuple *c$EXTRAARGS)
}
static void
-qsort_$SUFFIX(SortTuple *a, size_t n$EXTRAARGS)
+qsort_recursive_$SUFFIX(SortTuple *a, size_t n$EXTRAARGS)
{
SortTuple *pa,
*pb,
@@ -157,8 +159,7 @@ qsort_$SUFFIX(SortTuple *a, size_t n$EXTRAARGS)
*pn;
size_t d1,
d2;
- int r,
- presorted;
+ int r;
loop:
CHECK_FOR_INTERRUPTS();
@@ -169,18 +170,7 @@ loop:
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)
{
@@ -238,11 +228,11 @@ loop:
{
/* Recurse on left partition, then iterate on right partition */
if (d1 > 1)
- qsort_$SUFFIX(a, d1$EXTRAPARAMS);
+ qsort_recursive_$SUFFIX(a, d1$EXTRAPARAMS);
if (d2 > 1)
{
/* Iterate rather than recurse to save stack space */
- /* qsort_$SUFFIX(pn - d2, d2$EXTRAPARAMS); */
+ /* qsort_recursive_$SUFFIX(pn - d2, d2$EXTRAPARAMS); */
a = pn - d2;
n = d2;
goto loop;
@@ -252,15 +242,35 @@ loop:
{
/* Recurse on right partition, then iterate on left partition */
if (d2 > 1)
- qsort_$SUFFIX(pn - d2, d2$EXTRAPARAMS);
+ qsort_recursive_$SUFFIX(pn - d2, d2$EXTRAPARAMS);
if (d1 > 1)
{
/* Iterate rather than recurse to save stack space */
- /* qsort_$SUFFIX(a, d1$EXTRAPARAMS); */
+ /* qsort_recursive_$SUFFIX(a, d1$EXTRAPARAMS); */
n = d1;
goto loop;
}
}
}
+
+static void
+qsort_$SUFFIX(SortTuple *a, size_t n$EXTRAARGS)
+{
+ int presorted = 1;
+ SortTuple* pm;
+ 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;
+ qsort_recursive_$SUFFIX(a, n$EXTRAPARAMS);
+}
+
EOM
}
diff --git a/src/port/qsort.c b/src/port/qsort.c
index 1a8ee08..7341aed 100644
--- a/src/port/qsort.c
+++ b/src/port/qsort.c
@@ -44,6 +44,8 @@
* SUCH DAMAGE.
*/
+
+#include <math.h>
#include "c.h"
@@ -109,47 +111,35 @@ med3(char *a, char *b, char *c, int (*cmp) (const void *, const void *))
: (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 *))
+static void
+pg_qsort_recursive(void *a, size_t n, int swaptype, size_t es, int(*cmp) (const void *, const void *))
{
char *pa,
- *pb,
- *pc,
- *pd,
- *pl,
- *pm,
- *pn;
+ *pb,
+ *pc,
+ *pd,
+ *pl,
+ *pm,
+ *pn;
size_t d1,
- d2;
- int r,
- swaptype,
- presorted;
+ d2;
+ int r;
-loop:SWAPINIT(a, es);
+loop:
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)
+ 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;
+
+ pm = (char *)a + (n / 2) * es;
if (n > 7)
{
- pl = (char *) a;
- pn = (char *) a + (n - 1) * es;
+ pl = (char *)a;
+ pn = (char *)a + (n - 1) * es;
if (n > 40)
{
size_t d = (n / 8) * es;
@@ -161,8 +151,8 @@ loop:SWAPINIT(a, es);
pm = med3(pl, pm, pn, cmp);
}
swap(a, pm);
- pa = pb = (char *) a + es;
- pc = pd = (char *) a + (n - 1) * es;
+ pa = pb = (char *)a + es;
+ pc = pd = (char *)a + (n - 1) * es;
for (;;)
{
while (pb <= pc && (r = cmp(pb, a)) <= 0)
@@ -189,8 +179,8 @@ loop:SWAPINIT(a, es);
pb += es;
pc -= es;
}
- pn = (char *) a + n * es;
- d1 = Min(pa - (char *) a, pb - pa);
+ 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);
@@ -200,11 +190,11 @@ loop:SWAPINIT(a, es);
{
/* Recurse on left partition, then iterate on right partition */
if (d1 > es)
- pg_qsort(a, d1 / es, es, cmp);
+ pg_qsort_recursive(a, d1 / es, swaptype, es, cmp);
if (d2 > es)
{
/* Iterate rather than recurse to save stack space */
- /* pg_qsort(pn - d2, d2 / es, es, cmp); */
+ /* pg_qsort_recursive(pn - d2, d2 / es, es, cmp); */
a = pn - d2;
n = d2 / es;
goto loop;
@@ -214,17 +204,36 @@ loop:SWAPINIT(a, es);
{
/* Recurse on right partition, then iterate on left partition */
if (d2 > es)
- pg_qsort(pn - d2, d2 / es, es, cmp);
+ pg_qsort_recursive(pn - d2, d2 / es, swaptype, es, cmp);
if (d1 > es)
{
/* Iterate rather than recurse to save stack space */
- /* pg_qsort(a, d1 / es, es, cmp); */
+ /* pg_qsort_recursive(a, d1 / es, es, cmp); */
n = d1 / es;
goto loop;
}
}
}
+
+void
+pg_qsort(void *a, const size_t size, const size_t es, int(*cmp) (const void *, const void *)) {
+ int swaptype, presorted = 1;
+ char* pm;
+ for (pm = (char *)a + es; pm < (char *)a + size * es; pm += es)
+ {
+ if (cmp(pm - es, pm) > 0)
+ {
+ presorted = 0;
+ break;
+ }
+ }
+ if (presorted)
+ return;
+ SWAPINIT(a, es);
+ pg_qsort_recursive(a, size, swaptype, es, cmp);
+};
+
/*
* qsort comparator wrapper for strcmp.
*/
diff --git a/src/port/qsort_arg.c b/src/port/qsort_arg.c
index 24acd2c..7de3167 100644
--- a/src/port/qsort_arg.c
+++ b/src/port/qsort_arg.c
@@ -44,6 +44,8 @@
* SUCH DAMAGE.
*/
+
+#include <math.h>
#include "c.h"
@@ -102,54 +104,42 @@ swapfunc(char *a, char *b, size_t n, int 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)
+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));
+ (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)
+static void
+pg_qsort_arg_recursive(void *a, size_t n, int swaptype, size_t es, qsort_arg_comparator cmp, void* arg)
{
char *pa,
- *pb,
- *pc,
- *pd,
- *pl,
- *pm,
- *pn;
+ *pb,
+ *pc,
+ *pd,
+ *pl,
+ *pm,
+ *pn;
size_t d1,
- d2;
- int r,
- swaptype,
- presorted;
+ d2;
+ int r;
-loop:SWAPINIT(a, es);
+loop:
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)
+ 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;
+
+ pm = (char *)a + (n / 2) * es;
if (n > 7)
{
- pl = (char *) a;
- pn = (char *) a + (n - 1) * es;
+ pl = (char *)a;
+ pn = (char *)a + (n - 1) * es;
if (n > 40)
{
size_t d = (n / 8) * es;
@@ -161,8 +151,8 @@ loop:SWAPINIT(a, es);
pm = med3(pl, pm, pn, cmp, arg);
}
swap(a, pm);
- pa = pb = (char *) a + es;
- pc = pd = (char *) a + (n - 1) * es;
+ pa = pb = (char *)a + es;
+ pc = pd = (char *)a + (n - 1) * es;
for (;;)
{
while (pb <= pc && (r = cmp(pb, a, arg)) <= 0)
@@ -189,8 +179,8 @@ loop:SWAPINIT(a, es);
pb += es;
pc -= es;
}
- pn = (char *) a + n * es;
- d1 = Min(pa - (char *) a, pb - pa);
+ 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);
@@ -200,11 +190,11 @@ loop:SWAPINIT(a, es);
{
/* Recurse on left partition, then iterate on right partition */
if (d1 > es)
- qsort_arg(a, d1 / es, es, cmp, arg);
+ pg_qsort_arg_recursive(a, d1 / es, swaptype, es, cmp, arg);
if (d2 > es)
{
/* Iterate rather than recurse to save stack space */
- /* qsort_arg(pn - d2, d2 / es, es, cmp, arg); */
+ /* pg_qsort_arg_recursive(pn - d2, d2 / es, es, cmp, arg); */
a = pn - d2;
n = d2 / es;
goto loop;
@@ -214,13 +204,33 @@ loop:SWAPINIT(a, es);
{
/* Recurse on right partition, then iterate on left partition */
if (d2 > es)
- qsort_arg(pn - d2, d2 / es, es, cmp, arg);
+ pg_qsort_arg_recursive(pn - d2, d2 / es, swaptype, es, cmp, arg);
if (d1 > es)
{
/* Iterate rather than recurse to save stack space */
- /* qsort_arg(a, d1 / es, es, cmp, arg); */
+ /* pg_qsort_arg_recursive(a, d1 / es, es, cmp, arg); */
n = d1 / es;
goto loop;
}
}
}
+
+
+void
+qsort_arg(void *a, const size_t size, const size_t es, qsort_arg_comparator cmp, void* arg) {
+ int swaptype, presorted = 1;
+ char* pm;
+ for (pm = (char *)a + es; pm < (char *)a + size * es; pm += es)
+ {
+ if (cmp(pm - es, pm, arg) > 0)
+ {
+ presorted = 0;
+ break;
+ }
+ }
+ if (presorted)
+ return;
+ SWAPINIT(a, es);
+ pg_qsort_arg_recursive(a, size, swaptype, es, cmp, arg);
+};
+
[application/octet-stream] use_heap.diff (13.2K, ../5b5654cc.1c69fb81.5ea44.d698@mx.google.com/4-use_heap.diff)
download | inline diff:
diff --git a/src/backend/utils/sort/gen_qsort_tuple.pl b/src/backend/utils/sort/gen_qsort_tuple.pl
index 6186d0a..a9ae496 100644
--- a/src/backend/utils/sort/gen_qsort_tuple.pl
+++ b/src/backend/utils/sort/gen_qsort_tuple.pl
@@ -108,6 +108,8 @@ sub emit_qsort_boilerplate
* worth the effort", but we have seen crashes in the field due to stack
* overrun, so that judgment seems wrong.
*/
+
+#include <math.h>
static void
swapfunc(SortTuple *a, SortTuple *b, size_t n)
@@ -145,8 +147,63 @@ med3_$SUFFIX(SortTuple *a, SortTuple *b, SortTuple *c$EXTRAARGS)
(cmp_$SUFFIX(a, c$CMPPARAMS) < 0 ? a : c));
}
+/* heap sort: based on wikipedia */
+
+static inline void
+heap_shift_down_$SUFFIX(SortTuple *a, const size_t start, const size_t end$EXTRAARGS) {
+ size_t child, root = start;
+
+ while ((root << 1) + 1 <= end) {
+ CHECK_FOR_INTERRUPTS();
+
+ child = (root << 1) + 1;
+
+ if ((child < end) && cmp_$SUFFIX(a + child, a + (child + 1)$CMPPARAMS) < 0) {
+ child++;
+ }
+
+ if (cmp_$SUFFIX(a + root, a + child$CMPPARAMS) < 0) {
+ swap(a + root, a + child);
+ root = child;
+ }
+ else {
+ return;
+ }
+ }
+}
+
+static inline void
+heap_sort_$SUFFIX(SortTuple *a, const size_t size$EXTRAARGS) {
+
+ size_t start, end;
+ /* don't bother sorting an array of size <= 1 */
+ if (size <= 1) {
+ return;
+ }
+
+ end = size - 1;
+
+ /* heapify */
+ start = (end - 1) >> 1;
+ while (1) {
+ heap_shift_down_$SUFFIX(a, start, end$EXTRAPARAMS);
+
+ if (start == 0) {
+ break;
+ }
+
+ start--;
+ }
+
+ while (end > 0) {
+ swap(a + end, a);
+ heap_shift_down_$SUFFIX(a, 0, end - 1$EXTRAPARAMS);
+ end--;
+ }
+}
+
static void
-qsort_$SUFFIX(SortTuple *a, size_t n$EXTRAARGS)
+qsort_recursive_$SUFFIX(SortTuple *a, size_t n, size_t depth$EXTRAARGS)
{
SortTuple *pa,
*pb,
@@ -158,7 +215,7 @@ qsort_$SUFFIX(SortTuple *a, size_t n$EXTRAARGS)
size_t d1,
d2;
int r,
- presorted;
+ presorted;
loop:
CHECK_FOR_INTERRUPTS();
@@ -169,8 +226,9 @@ loop:
swap(pl, pl - 1);
return;
}
- presorted = 1;
- for (pm = a + 1; pm < a + n; pm++)
+
+ presorted = 1;
+ for (pm = a + 1; pm < a + n; pm++)
{
CHECK_FOR_INTERRUPTS();
if (cmp_$SUFFIX(pm - 1, pm$CMPPARAMS) > 0)
@@ -181,6 +239,13 @@ loop:
}
if (presorted)
return;
+
+ /* convert to heap sort if exceed depth limit */
+ if (!depth) {
+ heap_sort_$SUFFIX(a, n$EXTRAPARAMS);
+ return;
+ }
+
pm = a + (n / 2);
if (n > 7)
{
@@ -238,13 +303,14 @@ loop:
{
/* Recurse on left partition, then iterate on right partition */
if (d1 > 1)
- qsort_$SUFFIX(a, d1$EXTRAPARAMS);
+ qsort_recursive_$SUFFIX(a, d1, depth - 1$EXTRAPARAMS);
if (d2 > 1)
{
/* Iterate rather than recurse to save stack space */
- /* qsort_$SUFFIX(pn - d2, d2$EXTRAPARAMS); */
+ /* qsort_recursive_$SUFFIX(pn - d2, d2, depth - 1$EXTRAPARAMS); */
a = pn - d2;
n = d2;
+ depth--;
goto loop;
}
}
@@ -252,15 +318,23 @@ loop:
{
/* Recurse on right partition, then iterate on left partition */
if (d2 > 1)
- qsort_$SUFFIX(pn - d2, d2$EXTRAPARAMS);
+ qsort_recursive_$SUFFIX(pn - d2, d2, depth - 1$EXTRAPARAMS);
if (d1 > 1)
{
/* Iterate rather than recurse to save stack space */
- /* qsort_$SUFFIX(a, d1$EXTRAPARAMS); */
+ /* qsort_recursive_$SUFFIX(a, d1, depth - 1$EXTRAPARAMS); */
n = d1;
+ depth--;
goto loop;
}
}
}
+
+static void
+qsort_$SUFFIX(SortTuple *a, size_t n$EXTRAARGS)
+{
+ qsort_recursive_$SUFFIX(a, n, 2 * log(n)$EXTRAPARAMS);
+}
+
EOM
}
diff --git a/src/port/qsort.c b/src/port/qsort.c
index 1a8ee08..49175a7 100644
--- a/src/port/qsort.c
+++ b/src/port/qsort.c
@@ -44,6 +44,8 @@
* SUCH DAMAGE.
*/
+
+#include <math.h>
#include "c.h"
@@ -109,32 +111,85 @@ med3(char *a, char *b, char *c, int (*cmp) (const void *, const void *))
: (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 *))
+/* heap sort: based on wikipedia */
+
+static inline void
+heap_shift_down(void *a, const size_t start, const size_t end,
+ int swaptype, const size_t es, int(*cmp) (const void *, const void *)) {
+ size_t root = start;
+
+ while ((root << 1) + 1 <= end) {
+ size_t child = (root << 1) + 1;
+
+ if ((child < end) && cmp((char*)a + child * es, (char*)a + (child + 1)*es) < 0) {
+ child++;
+ }
+
+ if (cmp((char*)a + root * es, (char*)a + child * es) < 0) {
+ swap((char*)a + root * es, (char*)a + child * es);
+ root = child;
+ }
+ else {
+ return;
+ }
+ }
+}
+
+static inline void
+heap_sort(void *a, const size_t size, int swaptype, const size_t es, int(*cmp) (const void *, const void *)) {
+
+ size_t start, end;
+ /* don't bother sorting an array of size <= 1 */
+ if (size <= 1) {
+ return;
+ }
+
+ end = size - 1;
+
+ /* heapify */
+ start = (end - 1) >> 1;
+ while (1) {
+ heap_shift_down(a, start, end, swaptype, es, cmp);
+
+ if (start == 0) {
+ break;
+ }
+
+ start--;
+ }
+
+ while (end > 0) {
+ swap((char*)a + end * es, (char*)a);
+ heap_shift_down(a, 0, end - 1, swaptype, es, cmp);
+ end--;
+ }
+}
+
+static void
+pg_qsort_recursive(void *a, size_t n, size_t depth, int swaptype, size_t es, int(*cmp) (const void *, const void *))
{
char *pa,
- *pb,
- *pc,
- *pd,
- *pl,
- *pm,
- *pn;
+ *pb,
+ *pc,
+ *pd,
+ *pl,
+ *pm,
+ *pn;
size_t d1,
- d2;
+ d2;
int r,
- swaptype,
- presorted;
+ presorted;
-loop:SWAPINIT(a, es);
+loop:
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)
+ 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;
+ presorted = 1;
for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
{
if (cmp(pm - es, pm) > 0)
@@ -145,11 +200,18 @@ loop:SWAPINIT(a, es);
}
if (presorted)
return;
- pm = (char *) a + (n / 2) * es;
+
+ /* convert to heap sort if exceed depth limit */
+ if (!depth) {
+ heap_sort(a, n, swaptype, es, cmp);
+ return;
+ }
+
+ pm = (char *)a + (n / 2) * es;
if (n > 7)
{
- pl = (char *) a;
- pn = (char *) a + (n - 1) * es;
+ pl = (char *)a;
+ pn = (char *)a + (n - 1) * es;
if (n > 40)
{
size_t d = (n / 8) * es;
@@ -161,8 +223,8 @@ loop:SWAPINIT(a, es);
pm = med3(pl, pm, pn, cmp);
}
swap(a, pm);
- pa = pb = (char *) a + es;
- pc = pd = (char *) a + (n - 1) * es;
+ pa = pb = (char *)a + es;
+ pc = pd = (char *)a + (n - 1) * es;
for (;;)
{
while (pb <= pc && (r = cmp(pb, a)) <= 0)
@@ -189,8 +251,8 @@ loop:SWAPINIT(a, es);
pb += es;
pc -= es;
}
- pn = (char *) a + n * es;
- d1 = Min(pa - (char *) a, pb - pa);
+ 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);
@@ -200,13 +262,14 @@ loop:SWAPINIT(a, es);
{
/* Recurse on left partition, then iterate on right partition */
if (d1 > es)
- pg_qsort(a, d1 / es, es, cmp);
+ pg_qsort_recursive(a, d1 / es, depth - 1, swaptype, es, cmp);
if (d2 > es)
{
/* Iterate rather than recurse to save stack space */
- /* pg_qsort(pn - d2, d2 / es, es, cmp); */
+ /* pg_qsort_recursive(pn - d2, d2 / es, depth - 1, es, cmp); */
a = pn - d2;
n = d2 / es;
+ depth--;
goto loop;
}
}
@@ -214,17 +277,26 @@ loop:SWAPINIT(a, es);
{
/* Recurse on right partition, then iterate on left partition */
if (d2 > es)
- pg_qsort(pn - d2, d2 / es, es, cmp);
+ pg_qsort_recursive(pn - d2, d2 / es, depth - 1, swaptype, es, cmp);
if (d1 > es)
{
/* Iterate rather than recurse to save stack space */
- /* pg_qsort(a, d1 / es, es, cmp); */
+ /* pg_qsort_recursive(a, d1 / es, depth - 1, es, cmp); */
n = d1 / es;
+ depth--;
goto loop;
}
}
}
+
+void
+pg_qsort(void *a, const size_t size, const size_t es, int(*cmp) (const void *, const void *)) {
+ int swaptype;
+ SWAPINIT(a, es);
+ pg_qsort_recursive(a, size, 2 * log(size), swaptype, es, cmp);
+};
+
/*
* qsort comparator wrapper for strcmp.
*/
diff --git a/src/port/qsort_arg.c b/src/port/qsort_arg.c
index 24acd2c..b785778 100644
--- a/src/port/qsort_arg.c
+++ b/src/port/qsort_arg.c
@@ -44,6 +44,8 @@
* SUCH DAMAGE.
*/
+
+#include <math.h>
#include "c.h"
@@ -102,39 +104,94 @@ swapfunc(char *a, char *b, size_t n, int 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)
+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));
+ (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)
+
+/* heap sort: based on wikipedia */
+
+static inline void
+heap_shift_down(void *a, const size_t start, const size_t end,
+ int swaptype, const size_t es, qsort_arg_comparator cmp, void* arg) {
+ size_t root = start;
+
+ while ((root << 1) + 1 <= end) {
+ size_t child = (root << 1) + 1;
+
+ if ((child < end) && cmp((char*)a + child * es, (char*)a + (child + 1)*es, arg) < 0) {
+ child++;
+ }
+
+ if (cmp((char*)a + root * es, (char*)a + child * es, arg) < 0) {
+ swap((char*)a + root * es, (char*)a + child * es);
+ root = child;
+ }
+ else {
+ return;
+ }
+ }
+}
+
+static inline void
+heap_sort(void *a, const size_t size, int swaptype, const size_t es, qsort_arg_comparator cmp, void* arg) {
+
+ size_t start, end;
+ /* don't bother sorting an array of size <= 1 */
+ if (size <= 1) {
+ return;
+ }
+
+ end = size - 1;
+
+ /* heapify */
+ start = (end - 1) >> 1;
+ while (1) {
+ heap_shift_down(a, start, end, swaptype, es, cmp, arg);
+
+ if (start == 0) {
+ break;
+ }
+
+ start--;
+ }
+
+ while (end > 0) {
+ swap((char*)a + end * es, (char*)a);
+ heap_shift_down(a, 0, end - 1, swaptype, es, cmp, arg);
+ end--;
+ }
+}
+
+static void
+pg_qsort_arg_recursive(void *a, size_t n, size_t depth, int swaptype, size_t es, qsort_arg_comparator cmp, void* arg)
{
char *pa,
- *pb,
- *pc,
- *pd,
- *pl,
- *pm,
- *pn;
+ *pb,
+ *pc,
+ *pd,
+ *pl,
+ *pm,
+ *pn;
size_t d1,
- d2;
+ d2;
int r,
- swaptype,
- presorted;
+ presorted;
-loop:SWAPINIT(a, es);
+loop:
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)
+ 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;
+
+ presorted = 1;
for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
{
if (cmp(pm - es, pm, arg) > 0)
@@ -145,11 +202,18 @@ loop:SWAPINIT(a, es);
}
if (presorted)
return;
- pm = (char *) a + (n / 2) * es;
+
+ /* convert to heap sort if exceed depth limit */
+ if (!depth) {
+ heap_sort(a, n, swaptype, es, cmp, arg);
+ return;
+ }
+
+ pm = (char *)a + (n / 2) * es;
if (n > 7)
{
- pl = (char *) a;
- pn = (char *) a + (n - 1) * es;
+ pl = (char *)a;
+ pn = (char *)a + (n - 1) * es;
if (n > 40)
{
size_t d = (n / 8) * es;
@@ -161,8 +225,8 @@ loop:SWAPINIT(a, es);
pm = med3(pl, pm, pn, cmp, arg);
}
swap(a, pm);
- pa = pb = (char *) a + es;
- pc = pd = (char *) a + (n - 1) * es;
+ pa = pb = (char *)a + es;
+ pc = pd = (char *)a + (n - 1) * es;
for (;;)
{
while (pb <= pc && (r = cmp(pb, a, arg)) <= 0)
@@ -189,8 +253,8 @@ loop:SWAPINIT(a, es);
pb += es;
pc -= es;
}
- pn = (char *) a + n * es;
- d1 = Min(pa - (char *) a, pb - pa);
+ 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);
@@ -200,13 +264,14 @@ loop:SWAPINIT(a, es);
{
/* Recurse on left partition, then iterate on right partition */
if (d1 > es)
- qsort_arg(a, d1 / es, es, cmp, arg);
+ pg_qsort_arg_recursive(a, d1 / es, depth - 1, swaptype, es, cmp, arg);
if (d2 > es)
{
/* Iterate rather than recurse to save stack space */
- /* qsort_arg(pn - d2, d2 / es, es, cmp, arg); */
+ /* pg_qsort_arg_recursive(pn - d2, d2 / es, depth - 1, es, cmp, arg); */
a = pn - d2;
n = d2 / es;
+ depth--;
goto loop;
}
}
@@ -214,13 +279,23 @@ loop:SWAPINIT(a, es);
{
/* Recurse on right partition, then iterate on left partition */
if (d2 > es)
- qsort_arg(pn - d2, d2 / es, es, cmp, arg);
+ pg_qsort_arg_recursive(pn - d2, d2 / es, depth - 1, swaptype, es, cmp, arg);
if (d1 > es)
{
/* Iterate rather than recurse to save stack space */
- /* qsort_arg(a, d1 / es, es, cmp, arg); */
+ /* pg_qsort_arg_recursive(a, d1 / es, depth - 1, es, cmp, arg); */
n = d1 / es;
+ depth--;
goto loop;
}
}
}
+
+
+void
+qsort_arg(void *a, const size_t size, const size_t es, qsort_arg_comparator cmp, void* arg) {
+ int swaptype;
+ SWAPINIT(a, es);
+ pg_qsort_arg_recursive(a, size, 2 * log(size), swaptype, es, cmp, arg);
+};
+
view thread (15+ messages) latest in thread
Message-ID: <5b5654cc.1c69fb81.5ea44.d698@mx.google.com>
Permalink: ../5b5654cc.1c69fb81.5ea44.d698@mx.google.com/
Also on: postgresql.org/message-id/5b5654cc.1c69fb81.5ea44.d698@mx.google.com
copy link · copy postgr.es · copy git am
reply Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: starordust@gmail.com, tomas.vondra@2ndquadrant.com, x4mmm@yandex-team.ru, pg@bowt.ie, alvherre@2ndquadrant.com, pgsql-hackers@lists.postgresql.org
Subject: RE: GSOC 2018 Project - A New Sorting Routine
In-Reply-To: <5b5654cc.1c69fb81.5ea44.d698@mx.google.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox