Changeset: 027a4a9710f7 for MonetDB
URL: https://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=027a4a9710f7
Modified Files:
gdk/gdk_qsort.c
gdk/gdk_qsort_impl.h
sql/backends/monet5/vaults/bam/Tests/query2.2.sql
sql/backends/monet5/vaults/bam/Tests/query2.2.stable.out
sql/backends/monet5/vaults/bam/Tests/query2.2.stable.out.int128
sql/backends/monet5/vaults/bam/Tests/query2.6.sql
sql/backends/monet5/vaults/bam/Tests/query2.6.stable.out
sql/test/SQLite_regress/sqllogictest/Tests/select3.test.stable.out
sql/test/SQLite_regress/sqllogictest/Tests/select3.test.stable.out.int128
sql/test/Tests/rank.stable.out
sql/test/rank.sql
Branch: default
Log Message:
Tweaks to qsort code.
Switch to insertion sort earlier (unit test shows its faster).
This has consequences for sort order, so fix and approve some tests.
diffs (truncated from 3847 to 300 lines):
diff --git a/gdk/gdk_qsort.c b/gdk/gdk_qsort.c
--- a/gdk/gdk_qsort.c
+++ b/gdk/gdk_qsort.c
@@ -39,7 +39,7 @@ struct qsort_t {
#define multi_SWAP(i, j, n) \
do { \
SWAP1((i) * buf->hs, (j) * buf->hs, h, n * buf->hs); \
- if (t && buf->ts) \
+ if (t) \
SWAP1((i) * buf->ts, (j) * buf->ts, t, n * buf->ts); \
} while (0)
@@ -54,7 +54,7 @@ struct qsort_t {
bte _t = ((bte *) h)[i]; \
((bte *) h)[i] = ((bte *) h)[j]; \
((bte *) h)[j] = _t; \
- if (t && buf->ts) \
+ if (t) \
SWAP1((i) * buf->ts, (j) * buf->ts, t, buf->ts); \
} while (0)
#define GDKqsort_impl GDKqsort_impl_bte
@@ -81,7 +81,7 @@ struct qsort_t {
sht _t = ((sht *) h)[i]; \
((sht *) h)[i] = ((sht *) h)[j]; \
((sht *) h)[j] = _t; \
- if (t && buf->ts) \
+ if (t) \
SWAP1((i) * buf->ts, (j) * buf->ts, t, buf->ts); \
} while (0)
#define GDKqsort_impl GDKqsort_impl_sht
@@ -108,7 +108,7 @@ struct qsort_t {
int _t = ((int *) h)[i]; \
((int *) h)[i] = ((int *) h)[j]; \
((int *) h)[j] = _t; \
- if (t && buf->ts) \
+ if (t) \
SWAP1((i) * buf->ts, (j) * buf->ts, t, buf->ts); \
} while (0)
#define GDKqsort_impl GDKqsort_impl_int
@@ -135,7 +135,7 @@ struct qsort_t {
lng _t = ((lng *) h)[i]; \
((lng *) h)[i] = ((lng *) h)[j]; \
((lng *) h)[j] = _t; \
- if (t && buf->ts) \
+ if (t) \
SWAP1((i) * buf->ts, (j) * buf->ts, t, buf->ts); \
} while (0)
#define GDKqsort_impl GDKqsort_impl_lng
@@ -163,7 +163,7 @@ struct qsort_t {
hge _t = ((hge *) h)[i]; \
((hge *) h)[i] = ((hge *) h)[j]; \
((hge *) h)[j] = _t; \
- if (t && buf->ts) \
+ if (t) \
SWAP1((i) * buf->ts, (j) * buf->ts, t, buf->ts); \
} while (0)
#define GDKqsort_impl GDKqsort_impl_hge
@@ -191,7 +191,7 @@ struct qsort_t {
flt _t = ((flt *) h)[i]; \
((flt *) h)[i] = ((flt *) h)[j]; \
((flt *) h)[j] = _t; \
- if (t && buf->ts) \
+ if (t) \
SWAP1((i) * buf->ts, (j) * buf->ts, t, buf->ts); \
} while (0)
#define GDKqsort_impl GDKqsort_impl_flt
@@ -218,7 +218,7 @@ struct qsort_t {
dbl _t = ((dbl *) h)[i]; \
((dbl *) h)[i] = ((dbl *) h)[j]; \
((dbl *) h)[j] = _t; \
- if (t && buf->ts) \
+ if (t) \
SWAP1((i) * buf->ts, (j) * buf->ts, t, buf->ts); \
} while (0)
#define GDKqsort_impl GDKqsort_impl_dbl
@@ -243,7 +243,7 @@ struct qsort_t {
#define SWAP(i, j) \
do { \
SWAP1((i) * buf->hs, (j) * buf->hs, h, buf->hs); \
- if (t && buf->ts) \
+ if (t) \
SWAP1((i) * buf->ts, (j) * buf->ts, t, buf->ts); \
} while (0)
@@ -304,6 +304,10 @@ GDKqsort(void *restrict h, void *restric
assert(hs > 0);
assert(ts >= 0);
assert(tpe != TYPE_void);
+ assert((ts == 0) == (t == NULL));
+
+ if (n <= 1)
+ return;
buf.hs = (unsigned int) hs;
buf.ts = (unsigned int) ts;
@@ -357,6 +361,10 @@ GDKqsort_rev(void *restrict h, void *res
assert(hs > 0);
assert(ts >= 0);
assert(tpe != TYPE_void);
+ assert((ts == 0) == (t == NULL));
+
+ if (n <= 1)
+ return;
buf.hs = (unsigned int) hs;
buf.ts = (unsigned int) ts;
diff --git a/gdk/gdk_qsort_impl.h b/gdk/gdk_qsort_impl.h
--- a/gdk/gdk_qsort_impl.h
+++ b/gdk/gdk_qsort_impl.h
@@ -49,19 +49,24 @@
* SUCH DAMAGE.
*/
+/* when to switch to insertion sort */
+#ifndef INSERTSORT
+#define INSERTSORT 60 /* the original algorithm used 7 */
+#endif
+
static void
GDKqsort_impl(const struct qsort_t *restrict buf,
char *restrict h, char *restrict t, size_t n)
{
size_t a, b, c, d;
size_t r;
- int swap_cnt;
+ bool swap_cnt;
#ifdef INITIALIZER
INITIALIZER;
#endif
loop:
- if (n < 7) {
+ if (n < INSERTSORT) {
/* insertion sort for very small chunks */
for (b = 1; b < n; b++) {
for (a = b; a > 0 && LT(a, a - 1); a--) {
@@ -73,12 +78,18 @@ GDKqsort_impl(const struct qsort_t *rest
/* determine pivot */
b = n >> 1; /* small arrays: middle element */
- if (n > 7) {
+#if INSERTSORT <= 7
+ if (n > 7)
+#endif
+ {
/* for larger arrays, take the middle value from the
* first, middle, and last */
a = 0;
c = n - 1;
- if (n > 40) {
+#if INSERTSORT <= 40
+ if (n > 40)
+#endif
+ {
/* for even larger arrays, take the middle
* value of three middle values */
d = n >> 3;
@@ -96,11 +107,17 @@ GDKqsort_impl(const struct qsort_t *rest
* National Flag Problem */
a = b = 1;
c = d = n - 1;
- swap_cnt = 0;
+ swap_cnt = false;
for (;;) {
+ /* loop invariant:
+ * [0..a): values equal to pivot (cannot be empty)
+ * [a..b): values less than pivot (can be empty)
+ * [c+1..d+1): values greater than pivot (can be empty)
+ * [d+1..n): values equal to pivot (can be empty)
+ */
while (b <= c && LE(b, 0)) {
if (EQ(b, 0)) {
- swap_cnt = 1;
+ swap_cnt = true;
SWAP(a, b);
a++;
}
@@ -108,7 +125,7 @@ GDKqsort_impl(const struct qsort_t *rest
}
while (b <= c && LE(0, c)) {
if (EQ(0, c)) {
- swap_cnt = 1;
+ swap_cnt = true;
SWAP(c, d);
d--;
}
@@ -117,16 +134,12 @@ GDKqsort_impl(const struct qsort_t *rest
if (b > c)
break;
SWAP(b, c);
- swap_cnt = 1;
+ swap_cnt = true;
b++;
c--;
}
- /* at this point we have:
+ /* in addition to the loop invariant we have:
* b == c + 1
- * [0..a): values equal to pivot (cannot be empty)
- * [a..b): values less than pivot (can be empty)
- * [b..d+1): values greater than pivot (can be empty)
- * [d+1..n): values equal to pivot (can be empty)
* i.e., there are b-a values less than the pivot and d-c
* values greater than the pivot
*/
diff --git a/sql/backends/monet5/vaults/bam/Tests/query2.2.sql
b/sql/backends/monet5/vaults/bam/Tests/query2.2.sql
--- a/sql/backends/monet5/vaults/bam/Tests/query2.2.sql
+++ b/sql/backends/monet5/vaults/bam/Tests/query2.2.sql
@@ -32,7 +32,7 @@ FROM (
ON l.qname = r.qname
AND l.rname = r.rname
GROUP BY distance
-ORDER BY nr_alignments DESC;
+ORDER BY nr_alignments DESC, distance;
SELECT
CASE WHEN l_pos < r_pos
@@ -43,4 +43,4 @@ SELECT
FROM bam.paired_primary_alignments_3
WHERE l_rname = r_rname
GROUP BY distance
-ORDER BY nr_alignments DESC;
+ORDER BY nr_alignments DESC, distance;
diff --git a/sql/backends/monet5/vaults/bam/Tests/query2.2.stable.out
b/sql/backends/monet5/vaults/bam/Tests/query2.2.stable.out
--- a/sql/backends/monet5/vaults/bam/Tests/query2.2.stable.out
+++ b/sql/backends/monet5/vaults/bam/Tests/query2.2.stable.out
@@ -44,16 +44,16 @@ Ready.
[ 112, 3 ]
[ 93, 2 ]
[ 91, 1 ]
+[ 101, 1 ]
+[ 113, 1 ]
+[ 114, 1 ]
+[ 124, 1 ]
[ 127, 1 ]
-[ 101, 1 ]
-[ 153, 1 ]
-[ 124, 1 ]
[ 130, 1 ]
-[ 113, 1 ]
+[ 135, 1 ]
[ 140, 1 ]
-[ 135, 1 ]
[ 145, 1 ]
-[ 114, 1 ]
+[ 153, 1 ]
#SELECT
# CASE WHEN l_pos < r_pos
# THEN r_pos - (l_pos + bam.seq_length(l_cigar))
@@ -71,17 +71,17 @@ Ready.
[ 108, 5 ]
[ 112, 3 ]
[ 93, 2 ]
+[ 91, 1 ]
+[ 101, 1 ]
[ 113, 1 ]
+[ 114, 1 ]
+[ 124, 1 ]
[ 127, 1 ]
+[ 130, 1 ]
+[ 135, 1 ]
+[ 140, 1 ]
[ 145, 1 ]
-[ 130, 1 ]
-[ 101, 1 ]
[ 153, 1 ]
-[ 114, 1 ]
-[ 140, 1 ]
-[ 124, 1 ]
-[ 91, 1 ]
-[ 135, 1 ]
# 10:22:42 >
# 10:22:42 > "Done."
diff --git a/sql/backends/monet5/vaults/bam/Tests/query2.2.stable.out.int128
b/sql/backends/monet5/vaults/bam/Tests/query2.2.stable.out.int128
--- a/sql/backends/monet5/vaults/bam/Tests/query2.2.stable.out.int128
+++ b/sql/backends/monet5/vaults/bam/Tests/query2.2.stable.out.int128
@@ -44,16 +44,16 @@ Ready.
[ 112, 3 ]
[ 93, 2 ]
[ 91, 1 ]
+[ 101, 1 ]
+[ 113, 1 ]
+[ 114, 1 ]
+[ 124, 1 ]
[ 127, 1 ]
-[ 101, 1 ]
-[ 153, 1 ]
-[ 124, 1 ]
[ 130, 1 ]
-[ 113, 1 ]
+[ 135, 1 ]
[ 140, 1 ]
-[ 135, 1 ]
[ 145, 1 ]
-[ 114, 1 ]
+[ 153, 1 ]
#SELECT
# CASE WHEN l_pos < r_pos
# THEN r_pos - (l_pos + bam.seq_length(l_cigar))
_______________________________________________
checkin-list mailing list
[email protected]
https://www.monetdb.org/mailman/listinfo/checkin-list
