Changeset: 348dd5aaf7f3 for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=348dd5aaf7f3
Modified Files:
gdk/gdk_select.c
Branch: Oct2012
Log Message:
gdk_select.c: aligned with Feb2013 (and thus default):
basically back-ported functionality and performance fixes,
i.e., changesets
a2fb7cee717e fec77f0724dd 74b1a90a5246 863e6e7c4b9f 9188bb6aecfe
f23abbc6e142 dd907dde5444 01f48e7688a6 ac64b6abe064 97a90e8d2a30
854fa96bd7a2 f3c7044d813f a08f1e1d5db3 5765b45a182c 9e3e0b102c5f
diffs (truncated from 984 to 300 lines):
diff --git a/gdk/gdk_select.c b/gdk/gdk_select.c
--- a/gdk/gdk_select.c
+++ b/gdk/gdk_select.c
@@ -21,6 +21,21 @@
#include "gdk.h"
#include "gdk_private.h"
+#define buninsfix(B,C,A,I,T,V,G,M,R) \
+ do { \
+ if ((I) == BATcapacity((B))) { \
+ BATsetcount((B), (I)); \
+ if (BATextend((B), \
+ MIN(BATcapacity((B)) + (G), \
+ (M))) == NULL) { \
+ BBPreclaim((B)); \
+ return (R); \
+ } \
+ A = (T *) C##loc((B), BUNfirst((B))); \
+ } \
+ A[(I)] = (V); \
+ } while (0)
+
static BAT *
newempty(void)
{
@@ -92,23 +107,17 @@ BATslice2(BAT *b, BUN l1, BUN h1, BUN l2
return NULL;
}
-/*
- * @- Value Selections
- * The string search is optimized for the degenerated case that th =
- * tl, and double elimination in the string heap.
- *
- * We allow value selections on the nil atom. This is formally not
- * correct, as in MIL (nil = nil) != true. However, we do need an
- * implementation for selecting nil (in MIL, this is done through is
- * the "isnil" predicate). So we implement it here.
- */
static BAT *
-BAT_hashselect(BAT *b, BAT *s, BAT *bn, const void *tl)
+BAT_hashselect(BAT *b, BAT *s, BAT *bn, const void *tl, BUN maximum)
{
BATiter bi;
- BUN i;
- oid o;
- oid off;
+ BUN i, cnt;
+ oid o, *dst;
+ /* off must be signed as it can be negative,
+ * e.g., if b->hseqbase == 0 and b->U->first > 0;
+ * instead of wrd, we could also use ssize_t or int/lng with
+ * 32/64-bit OIDs */
+ wrd off;
assert(bn->htype == TYPE_void);
assert(bn->ttype == TYPE_oid);
@@ -120,20 +129,30 @@ BAT_hashselect(BAT *b, BAT *s, BAT *bn,
return NULL;
}
bi = bat_iterator(b);
+ dst = (oid*) Tloc(bn, BUNfirst(bn));
+ cnt = 0;
if (s) {
assert(s->tsorted);
s = BATmirror(s); /* SORTfnd works on HEAD column */
HASHloop(bi, b->H->hash, i, tl) {
o = (oid) i + off;
- if (SORTfnd(s, &o) != BUN_NONE)
- bunfastins(bn, NULL, &o);
+ if (SORTfnd(s, &o) != BUN_NONE) {
+ buninsfix(bn, T, dst, cnt, oid, o,
+ maximum - BATcapacity(bn),
+ maximum, NULL);
+ cnt++;
+ }
}
} else {
HASHloop(bi, b->H->hash, i, tl) {
o = (oid) i + off;
- bunfastins(bn, NULL, &o);
+ buninsfix(bn, T, dst, cnt, oid, o,
+ maximum - BATcapacity(bn),
+ maximum, NULL);
+ cnt++;
}
}
+ BATsetcount(bn, cnt);
bn->tkey = 1;
bn->tdense = bn->tsorted = bn->trevsorted = bn->U->count <= 1;
if (bn->U->count == 1)
@@ -148,56 +167,227 @@ BAT_hashselect(BAT *b, BAT *s, BAT *bn,
bn->hsorted = 1;
bn->hrevsorted = bn->U->count <= 1;
return bn;
-
- bunins_failed:
- BBPreclaim(bn);
- return NULL;
}
-/* scan select loop with candidates */
-#define candscanloop(TEST) \
- do { \
- ALGODEBUG fprintf(stderr, \
- "#BATsubselect(b=%s#"BUNFMT",s=%s,anti=%d): " \
- "scanselect %s\n", BATgetId(b), BATcount(b), \
- s ? BATgetId(s) : "NULL", anti, #TEST); \
+
+/* core scan select loop with & without candidates */
+#define scanloop(CAND,READ,TEST) \
+do { \
+ ALGODEBUG fprintf(stderr, \
+ "#BATsubselect(b=%s#"BUNFMT",s=%s,anti=%d): " \
+ "scanselect %s\n", BATgetId(b), BATcount(b), \
+ s ? BATgetId(s) : "NULL", anti, #TEST); \
+ if (BATcapacity(bn) < maximum) { \
while (p < q) { \
- o = *candlist++; \
- r = (BUN) (o - off); \
- v = BUNtail(bi, r); \
- if (TEST) \
- bunfastins(bn, NULL, &o); \
+ CAND; \
+ READ; \
+ buninsfix(bn, T, dst, cnt, oid, o, \
+ (BUN) ((dbl) cnt / (dbl) (p-r) \
+ * (dbl) (q-p) * 1.1), \
+ maximum, BUN_NONE); \
+ cnt += (TEST); \
p++; \
} \
- } while (0)
-
-/* scan select loop without candidates */
-#define scanloop(TEST) \
- do { \
- ALGODEBUG fprintf(stderr, \
- "#BATsubselect(b=%s#"BUNFMT",s=%s,anti=%d): " \
- "scanselect %s\n", BATgetId(b), BATcount(b), \
- s ? BATgetId(s) : "NULL", anti, #TEST); \
+ } else { \
while (p < q) { \
- v = BUNtail(bi, p); \
- if (TEST) { \
- o = (oid) p + off; \
- bunfastins(bn, NULL, &o); \
- } \
+ CAND; \
+ READ; \
+ dst[cnt] = o; \
+ cnt += (TEST); \
p++; \
} \
- } while (0)
+ } \
+} while (0)
+
+/* scan select predicate switch */
+#define scantest(CAND,READ,COMP,NIL1,NIL2)
\
+do {
\
+ if (equi ) {
\
+ scanloop(CAND,READ, COMP(v,==,vl) );
\
+ } else
\
+ if ( anti && b->T->nonil && lval && !li && hval && !hi) {
\
+ scanloop(CAND,READ,(COMP(v,<=,vl) || COMP(v,>=,vh)) );
\
+ } else
\
+ if ( anti && b->T->nonil && lval && !li && hval && hi) {
\
+ scanloop(CAND,READ,(COMP(v,<=,vl) || COMP(v,> ,vh)) );
\
+ } else
\
+ if ( anti && b->T->nonil && lval && li && hval && !hi) {
\
+ scanloop(CAND,READ,(COMP(v,< ,vl) || COMP(v,>=,vh)) );
\
+ } else
\
+ if ( anti && b->T->nonil && lval && li && hval && hi) {
\
+ scanloop(CAND,READ,(COMP(v,< ,vl) || COMP(v,> ,vh)) );
\
+ } else
\
+ if ( anti && b->T->nonil && lval && !li && !hval ) {
\
+ scanloop(CAND,READ,(COMP(v,<=,vl) ) );
\
+ } else
\
+ if ( anti && b->T->nonil && lval && li && !hval ) {
\
+ scanloop(CAND,READ,(COMP(v,< ,vl) ) );
\
+ } else
\
+ if ( anti && b->T->nonil && !lval && hval && !hi) {
\
+ scanloop(CAND,READ,( COMP(v,>=,vh)) );
\
+ } else
\
+ if ( anti && b->T->nonil && !lval && hval && hi) {
\
+ scanloop(CAND,READ,( COMP(v,> ,vh)) );
\
+ } else
\
+ if ( anti && !b->T->nonil && lval && !li && hval && !hi) {
\
+ scanloop(CAND,READ,(COMP(v,<=,vl) || COMP(v,>=,vh)) NIL1(v));
\
+ } else
\
+ if ( anti && !b->T->nonil && lval && !li && hval && hi) {
\
+ scanloop(CAND,READ,(COMP(v,<=,vl) || COMP(v,> ,vh)) NIL1(v));
\
+ } else
\
+ if ( anti && !b->T->nonil && lval && li && hval && !hi) {
\
+ scanloop(CAND,READ,(COMP(v,< ,vl) || COMP(v,>=,vh)) NIL1(v));
\
+ } else
\
+ if ( anti && !b->T->nonil && lval && li && hval && hi) {
\
+ scanloop(CAND,READ,(COMP(v,< ,vl) || COMP(v,> ,vh)) NIL1(v));
\
+ } else
\
+ if ( anti && !b->T->nonil && lval && !li && !hval ) {
\
+ scanloop(CAND,READ,(COMP(v,<=,vl) ) NIL1(v));
\
+ } else
\
+ if ( anti && !b->T->nonil && lval && li && !hval ) {
\
+ scanloop(CAND,READ,(COMP(v,< ,vl) ) NIL1(v));
\
+ } else
\
+ if ( anti && !b->T->nonil && !lval && hval && !hi) {
\
+ scanloop(CAND,READ,( COMP(v,>=,vh)) NIL2(v));
\
+ } else
\
+ if ( anti && !b->T->nonil && !lval && hval && hi) {
\
+ scanloop(CAND,READ,( COMP(v,> ,vh)) NIL2(v));
\
+ } else
\
+ if (!anti && b->T->nonil && lval && !li && hval && !hi) {
\
+ scanloop(CAND,READ,(COMP(v,> ,vl) && COMP(v,< ,vh)) );
\
+ } else
\
+ if (!anti && b->T->nonil && lval && !li && hval && hi) {
\
+ scanloop(CAND,READ,(COMP(v,> ,vl) && COMP(v,<=,vh)) );
\
+ } else
\
+ if (!anti && b->T->nonil && lval && li && hval && !hi) {
\
+ scanloop(CAND,READ,(COMP(v,>=,vl) && COMP(v,< ,vh)) );
\
+ } else
\
+ if (!anti && b->T->nonil && lval && li && hval && hi) {
\
+ scanloop(CAND,READ,(COMP(v,>=,vl) && COMP(v,<=,vh)) );
\
+ } else
\
+ if (!anti && b->T->nonil && lval && !li && !hval ) {
\
+ scanloop(CAND,READ,(COMP(v,> ,vl) ) );
\
+ } else
\
+ if (!anti && b->T->nonil && lval && li && !hval ) {
\
+ scanloop(CAND,READ,(COMP(v,>=,vl) ) );
\
+ } else
\
+ if (!anti && b->T->nonil && !lval && hval && !hi) {
\
+ scanloop(CAND,READ,( COMP(v,< ,vh)) );
\
+ } else
\
+ if (!anti && b->T->nonil && !lval && hval && hi) {
\
+ scanloop(CAND,READ,( COMP(v,<=,vh)) );
\
+ } else
\
+ if (!anti && !b->T->nonil && lval && !li && hval && !hi) {
\
+ scanloop(CAND,READ,(COMP(v,> ,vl) && COMP(v,< ,vh)) NIL2(v));
\
+ } else
\
+ if (!anti && !b->T->nonil && lval && !li && hval && hi) {
\
+ scanloop(CAND,READ,(COMP(v,> ,vl) && COMP(v,<=,vh)) NIL2(v));
\
+ } else
\
+ if (!anti && !b->T->nonil && lval && li && hval && !hi) {
\
+ scanloop(CAND,READ,(COMP(v,>=,vl) && COMP(v,< ,vh)) NIL2(v));
\
+ } else
\
+ if (!anti && !b->T->nonil && lval && li && hval && hi) {
\
+ scanloop(CAND,READ,(COMP(v,>=,vl) && COMP(v,<=,vh)) NIL2(v));
\
+ } else
\
+ if (!anti && !b->T->nonil && lval && !li && !hval ) {
\
+ scanloop(CAND,READ,(COMP(v,> ,vl) ) NIL2(v));
\
+ } else
\
+ if (!anti && !b->T->nonil && lval && li && !hval ) {
\
+ scanloop(CAND,READ,(COMP(v,>=,vl) ) NIL2(v));
\
+ } else
\
+ if (!anti && !b->T->nonil && !lval && hval && !hi) {
\
+ scanloop(CAND,READ,( COMP(v,< ,vh)) NIL1(v));
\
+ } else
\
+ if (!anti && !b->T->nonil && !lval && hval && hi) {
\
+ scanloop(CAND,READ,( COMP(v,<=,vh)) NIL1(v));
\
+ } else
\
+ if (!anti && !b->T->nonil && !lval && !hval ) {
\
+ scanloop(CAND,READ, COMP(v,!=,nil) );
\
+ } else
\
+ assert(0);
\
+} while (0)
+
+/* local variables for known fixed-width types */
+#define scaninit_fix(TYPE) \
+ TYPE vl = *(TYPE *) tl; \
+ TYPE vh = *(TYPE *) th; \
+ TYPE v; \
+ TYPE nil = TYPE##_nil; \
+ const TYPE *src = (const TYPE *) Tloc(b, 0);
+
+/* local variables for generic types */
+#define scaninit_var(TYPE) \
+ const void *vl = tl; \
+ const void *vh = th; \
+ const void *v; \
+ const void *nil = ATOMnilptr(b->ttype); \
+ int (*cmp)(const void *, const void *) = BATatoms[b->ttype].atomCmp;\
+ BATiter bi = bat_iterator(b); \
+
+/* various comparison calls for known fixed-width types */
+#define scancomp_fix(l,o,r) (l) o (r)
+#define scannil1_fix(v) && scancomp_fix(v,!=,nil)
+#define scannil2_fix(v)
+
+/* various comparison calls for generic types */
+#define scancomp_var(l,o,r) (*cmp)((l),(r)) o 0
+#define scannil1_var(v) && scancomp_var(v,!=,nil)
+#define scannil2_var(v) scannil1_var(v)
+
+/* argument list for type-specific core scan select function call */
+#define scanargs \
+ b, s, bn, tl, th, li, hi, equi, anti, lval, hval, \
+ p, q, cnt, off, dst, candlist, maximum
+
+/* definition of type-specific core scan select function */
+#define scanfunc(NAME,WHAT,TYPE,CAND,READ) \
_______________________________________________
checkin-list mailing list
[email protected]
http://mail.monetdb.org/mailman/listinfo/checkin-list
