Changeset: 68612f3aea8f for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=68612f3aea8f
Added Files:
gdk/gdk_qsort.c
gdk/gdk_qsort_impl.h
Removed Files:
gdk/gdk_qsort.mx
Modified Files:
gdk/Makefile.ag
Branch: default
Log Message:
De-MX gdk_qsort.
There are some quite significant changes to how qsort is implemented.
Instead of working with pointers into the array being sorted (and
calculating the pointers into the "tail" array), we use indexes.
I also added comments to help understand what is going on.
This version has type-specific code for the usual types: bte, sht,
int, lng, flt, dbl. However, unlike the old version, the generic code
is also used for what was called there the type-specific "offset"
implementation. This may affect the efficiency of refine in group.mx.
diffs (truncated from 1023 to 300 lines):
diff --git a/gdk/Makefile.ag b/gdk/Makefile.ag
--- a/gdk/Makefile.ag
+++ b/gdk/Makefile.ag
@@ -37,7 +37,8 @@ lib_gdk = {
gdk_scanselect.mx gdk.h gdk_batop.mx \
gdk_search.mx gdk_tm.c gdk_align.c gdk_bbp.mx \
gdk_heap.c gdk_setop.mx gdk_utils.c gdk_utils.h gdk_atoms.c
gdk_atoms.h \
- gdk_qsort.mx gdk_ssort.c gdk_ssort_impl.h gdk_storage.c
gdk_bat.c gdk_bat.h \
+ gdk_qsort.c gdk_qsort_impl.h gdk_ssort.c gdk_ssort_impl.h \
+ gdk_storage.c gdk_bat.c gdk_bat.h \
gdk_delta.c gdk_relop.mx gdk_system.c gdk_value.c \
gdk_rangejoin.mx \
gdk_posix.c gdk_logger.c gdk_sample.c \
diff --git a/gdk/gdk_qsort.mx b/gdk/gdk_qsort.c
rename from gdk/gdk_qsort.mx
rename to gdk/gdk_qsort.c
--- a/gdk/gdk_qsort.mx
+++ b/gdk/gdk_qsort.c
@@ -1,509 +1,349 @@
-@/
-The contents of this file are subject to the MonetDB Public License
-Version 1.1 (the "License"); you may not use this file except in
-compliance with the License. You may obtain a copy of the License at
-http://www.monetdb.org/Legal/MonetDBLicense
+/*
+ * The contents of this file are subject to the MonetDB Public License
+ * Version 1.1 (the "License"); you may not use this file except in
+ * compliance with the License. You may obtain a copy of the License at
+ * http://www.monetdb.org/Legal/MonetDBLicense
+ *
+ * Software distributed under the License is distributed on an "AS IS"
+ * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the
+ * License for the specific language governing rights and limitations
+ * under the License.
+ *
+ * The Original Code is the MonetDB Database System.
+ *
+ * The Initial Developer of the Original Code is CWI.
+ * Portions created by CWI are Copyright (C) 1997-July 2008 CWI.
+ * Copyright August 2008-2012 MonetDB B.V.
+ * All Rights Reserved.
+ */
-Software distributed under the License is distributed on an "AS IS"
-basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the
-License for the specific language governing rights and limitations
-under the License.
-
-The Original Code is the MonetDB Database System.
-
-The Initial Developer of the Original Code is CWI.
-Portions created by CWI are Copyright (C) 1997-July 2008 CWI.
-Copyright August 2008-2012 MonetDB B.V.
-All Rights Reserved.
-@
-
-@f gdk_qsort
-
-@c
-/*
- * @a Peter Boncz, Niels Nes et al
- * @* Qsort
- * There were two problems with the OS provided qsort() library routine:
- * @table @samp
- * @item unreliable
- * on certain OSs (e.g. SunOS), the qsort somehow degenerates
- * if there are a very small number of different values (on
- * 132K elements with 7 values, I never saw it return).
- * This is a serious bug.
- * @item atom format
- * when comparing GDK atoms (e.g. in BATs) it was not
- * possible to use qsort on varsized atoms (as monet stores them
- * as integer offsets from a global base pointer that qsort does
- * not know about), nor if the values were not placed at the start
- * of the record (e.g. if the column is the tail column of a BAT).
- * @end table
- *
- * Both these problems are fixed in the new GDKqsort function, that
- * is based on the standard Berkeley qsort (see copyright notice below).
- *
- * The routine was "monet"-ified with macro code expansions for the specific
- * data types to obtain extra speed (we know more about our data than the
stdlib
- * qsort() ever can).
- */
#include "monetdb_config.h"
#include "gdk.h"
#include "gdk_private.h"
-/*-
- * Copyright (c) 1992, 1993
- * The Regents of the University of California. All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the distribution.
- * 3. All advertising materials mentioning features or use of this software
- * must display the following acknowledgement:
- * This product includes software developed by the University of
- * California, Berkeley and its contributors.
- * 4. Neither the name of the University nor the names of its contributors
- * may be used to endorse or promote products derived from this software
- * without specific prior written permission.
- *
- * 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
- * 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)
- * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
- * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
- * SUCH DAMAGE.
- */
+struct qsort_t {
+ unsigned int hs;
+ unsigned int ts;
+ int (*cmp)(const void *, const void *);
+ char *base;
+};
-/*
- * @-
- * Record containing all data-specific info.
- * Introduced to reduce number of qsort parameters
- */
-typedef struct {
- int (*cmp)(const void *, const void *); /* routine that compares two
atoms */
- char *offst; /* NULL or start of varsized heap */
- int hshift; /* log2 of hs */
- int tshift; /* log2 of hs */
- int vshift; /* shift to be applied on var_ offsets */
- unsigned hs; /* width of head record */
- unsigned ts; /* width of tail record */
- void *h; /* start of head buns */
- void *t; /* start of tail buns */
-} buf_t;
+#if SIZEOF_VAR_T == 8
+#define OFF(b, i) (buf->base + \
+ (buf->hs == 1 ? ((unsigned char *) b)[i] + GDK_VAROFFSET : \
+ (buf->hs == 2 ? ((unsigned short *) b)[i] + GDK_VAROFFSET : \
+ (buf->hs == 4 ? ((unsigned int *) b)[i] : \
+ ((var_t *) b)[i]))))
+#else
+#define OFF(b, i) (buf->base + \
+ (buf->hs == 1 ? ((unsigned char *) b)[i] + GDK_VAROFFSET : \
+ (buf->hs == 2 ? ((unsigned short *) b)[i] + GDK_VAROFFSET : \
+ ((var_t *) b)[i])))
+#endif
+#define VAL(i) (buf->base ? OFF(b, (i)) : b + (i) * buf->hs)
-/* fast arithmetic on the record width */
-#define MULT_WIDTH(d) ((d) << buf->hshift)
-#define DIV_WIDTH(d) ((d) >> buf->hshift)
-#define MULT_TS(d) ((d) << buf->tshift)
+/* return index of middle value at indexes a, b, and c */
+#define MED3(a, b, c) (LT(a, b) ? \
+ (LT(b, c) ? (b) : (LT(a, c) ? (c) : (a))) : \
+ (LT(c, b) ? (b) : (LT(a, c) ? (a) : (c))))
-@= register_swap
-/* fast record swapping */
-#define @1_SWAP(TYPE, a, b, s) \
+/* generic swap: swap w bytes starting at indexes i and j with each
+ * other from the array given by b */
+#define SWAP1(i, j, b, w) \
do { \
- @1 *_pa = (@1 *) (a); \
- @1 *_pb = (@1 *) (b); \
- @1 _tmp = *_pa; \
- *_pa = *_pb; \
- *_pb = _tmp; \
+ char _tmp; \
+ size_t _z; \
+ size_t _i = (i), _j = (j); \
+ for (_z = (w); _z > 0; _z--) { \
+ _tmp = b[_i]; \
+ b[_i++] = b[_j]; \
+ b[_j++] = _tmp; \
+ } \
} while (0)
-#define direct_@1_SWAP(TYPE, a, b, s) \
- @1_SWAP(TYPE, a, b, s)
-
-#define offset_@1_SWAP(TYPE, a, b, s) offset_any_SWAP(TYPE, a, b, s)
-
-#define @1_multi_SWAP(TYPE, a, b, n, nt, s) \
- tpe_SWAP(TYPE, a, b, n)
-
-#define direct_@1_multi_SWAP(TYPE, a, b, n, nt, s) \
- tpe_SWAP(TYPE, a, b, n)
-
-#define offset_@1_multi_SWAP(TYPE, a, b, n, nt, s) offset_any_multi_SWAP(TYPE,
a, b, n, nt, s)
-
-@
-@c
-@:register_swap(bte)@
-@:register_swap(sht)@
-@:register_swap(int)@
-@:register_swap(lng)@
-@:register_swap(flt)@
-@:register_swap(dbl)@
-
-#define iterate_SWAP(TYPE, a, b, s) tpe_SWAP(bte, a, b, s)
-#define direct_any_SWAP(TYPE, a, b, s) tpe_SWAP(bte, a, b, s)
-#define offset_any_SWAP(TYPE, a, b, s) \
- do { \
- switch (s) { \
- case 1: bte_SWAP(TYPE, a, b, s); break; \
- case 2: sht_SWAP(TYPE, a, b, s); break; \
- case 4: int_SWAP(TYPE, a, b, s); break; \
- case 8: lng_SWAP(TYPE, a, b, s); break; \
- default: assert(0); \
- } \
- } while (0)
-#define iterate_multi_SWAP(TYPE, a, b, n, nt, s) tpe_SWAP(bte, a, b, nt)
-#define direct_any_multi_SWAP(TYPE, a, b, n, nt, s) tpe_SWAP(bte, a, b, nt)
-#define offset_any_multi_SWAP(TYPE, a, b, n, nt, s) \
- do { \
- switch (s) { \
- case 1: tpe_SWAP(bte, a, b, (nt)); break; \
- case 2: tpe_SWAP(sht, a, b, (nt)>>1); break; \
- case 4: tpe_SWAP(int, a, b, (nt)>>2); break; \
- case 8: tpe_SWAP(lng, a, b, (nt)>>3); break; \
- default: assert(0); \
- } \
+/* swap n items from both h and t arrays starting at indexes i and j */
+#define multi_SWAP(i, j, n) \
+ do { \
+ SWAP1((i) * buf->hs, (j) * buf->hs, h, n * buf->hs); \
+ if (t && buf->ts) \
+ SWAP1((i) * buf->ts, (j) * buf->ts, t, n * buf->ts); \
} while (0)
-/* no swapping for voids */
-#define void_SWAP(TYPE, a, b, s)
-#define void_multi_SWAP(TYPE, a, b, n, nt, s)
+/* From here we define and redefine tokens and include the
+ * implementation file multiple times to get versions for different
+ * types and to get both ascending and descending (reverse) sort.
+ * Note that for reverse sort, the LE (less or equal) and LT (less
+ * than) macros are in fact greater or equal and greater than. */
-#define tpe_SWAP(TYPE, a, b, n) \
- do { \
- ssize_t _i = (ssize_t) (n); \
- TYPE *_pa = (TYPE*)(a); \
- TYPE *_pb = (TYPE*)(b); \
- while (--_i >= 0) { \
- TYPE _tmp = *_pa; \
- *_pa++ = *_pb; \
- *_pb++ = _tmp; \
- } \
+#define SWAP(i, j) \
+ do { \
+ bte _t = ((bte *) h)[i]; \
+ ((bte *) h)[i] = ((bte *) h)[j]; \
+ ((bte *) h)[j] = _t; \
+ if (t && buf->ts) \
+ SWAP1((i) * buf->ts, (j) * buf->ts, t, buf->ts); \
} while (0)
+#define GDKqsort_impl GDKqsort_impl_bte
+#define EQ(i, j) (((bte *) h)[i] == ((bte *) h)[j])
+#define LE(i, j) (((bte *) h)[i] <= ((bte *) h)[j])
+#define LT(i, j) (((bte *) h)[i] < ((bte *) h)[j])
+#include "gdk_qsort_impl.h"
+#undef GDKqsort_impl
+#undef LE
+#undef LT
-/*
- * @-
- * qsort is macro expanded in four dimensions:
- * @table @samp
- * @item direction:2
- * L: from lesser to greater is standard.
- * G: from greater to lesser is the _rev version of quicksort.
- * @item type:7
- * in order to factor out a type-specific check, or a function call for
each
- * value comparison, we separate different qsort implementations by the
comparison
- * type, of which each has the comparison hard-coded. We factor out the
types
- * @{bte,sht,int,wrd,flt,lng,dbl,any@} (the latter uses an adt function
call).
- * @item storage:2
- * denoted @{direct,offset@}, means whether the array to be sorted
contains the
- * (fixed-width) values itself, or whether it contains integer
byte-offsets, that point
- * into some heap. Note that we support byte-offset qsort also on
fixed-size types,
- * as this is handy in many cases.
- * @item swapmethod:2
- * qsort sorts an array by continually swapping entries. To do this, two
- * implementations of the swap action are supported: @{iterate,register@}.
- * The default implementation takes the comparison type and does the
swapping by
- * iterating a number of times per entry, copying one comparison value per
iteration.
- * One often-occurring special case is when the entry width is 8 (two
integers). These
- * can be copied by one long integer load and store; without the loop
overhead.
_______________________________________________
Checkin-list mailing list
[email protected]
http://mail.monetdb.org/mailman/listinfo/checkin-list
