Changeset: 3c856e031b5d for MonetDB URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=3c856e031b5d Modified Files: gdk/gdk_group.c Branch: Feb2013 Log Message:
Merge
diffs (truncated from 384 to 300 lines):
diff --git a/gdk/gdk_group.c b/gdk/gdk_group.c
--- a/gdk/gdk_group.c
+++ b/gdk/gdk_group.c
@@ -70,38 +70,86 @@
* At the MAL level, the multigroup function would perform the dynamic
* optimization.
*/
+#define GRPnotfound \
+ do { \
+ /* no equal found: start new group */ \
+ if (ngrp == maxgrps) { \
+ /* we need to extend extents \
+ * and histo bats, do it at \
+ * most once */ \
+ maxgrps = BATcount(b); \
+ if (extents) { \
+ BATsetcount(en, ngrp); \
+ en = BATextend(en, maxgrps); \
+ exts = (oid *) Tloc(en, BUNfirst(en)); \
+ } \
+ if (histo) { \
+ BATsetcount(hn, ngrp); \
+ hn = BATextend(hn, maxgrps); \
+ cnts = (wrd *) Tloc(hn, BUNfirst(hn)); \
+ } \
+ } \
+ if (extents) \
+ exts[ngrp] = b->hseqbase + (oid) (p - r); \
+ if (histo) \
+ cnts[ngrp] = 1; \
+ ngrps[p - r] = ngrp; \
+ ngrp++; \
+ } while (0)
+
#define GRPhashloop(TYPE) \
do { \
- v = BUNtail(bi, p); \
- if (grps) { \
- BUN hv = hash_##TYPE(hs, v); \
- BUN hg = hash_oid(hs, &grps[p-r]); \
- prb = (hv ^ (hv << bits1) ^ \
- hg ^ (hg << bits2)) & hs->mask; \
- for (hb = hs->hash[prb]; \
- hb != BUN_NONE; \
- hb = hs->link[hb]) { \
- if (grps[hb - r] == grps[p - r] && \
- *(TYPE *) v == *(TYPE *) BUNtail(bi, hb)){ \
- ngrps[p - r] = ngrps[hb - r]; \
- if (histo) \
- cnts[ngrps[hb - r]]++; \
- break; \
- } \
- } \
- } else { \
- prb = hash_##TYPE(hs, v); \
- for (hb = hs->hash[prb]; \
- hb != BUN_NONE; \
- hb = hs->link[hb]) { \
- if (*(TYPE *) v == *(TYPE *) BUNtail(bi, hb)){ \
- ngrps[p - r] = ngrps[hb - r]; \
- if (histo) \
- cnts[ngrps[hb - r]]++; \
- break; \
- } \
- } \
- } \
+ TYPE *w = (TYPE *) Tloc(b, 0);
\
+ for (r = BUNfirst(b), p = r, q = r + BATcount(b); p < q; p++) {
\
+ if (gc) {
\
+ prb = hash_##TYPE(hs, &w[p]);
\
+ for (hb = hs->hash[prb];
\
+ hb != BUN_NONE &&
\
+ grps[hb - r] == grps[p - r];
\
+ hb = hs->link[hb]) {
\
+ if (w[p] == w[hb]) {
\
+ ngrps[p - r] = ngrps[hb - r];
\
+ if (histo)
\
+ cnts[ngrps[hb - r]]++;
\
+ break;
\
+ }
\
+ }
\
+ } else if (grps) {
\
+ BUN hv = hash_##TYPE(hs, &w[p]);
\
+ BUN hg = hash_oid(hs, &grps[p-r]);
\
+ prb = ((hv << bits) ^ hg) & hs->mask;
\
+ for (hb = hs->hash[prb];
\
+ hb != BUN_NONE;
\
+ hb = hs->link[hb]) {
\
+ if (grps[hb - r] == grps[p - r] &&
\
+ w[p] == w[hb]) {
\
+ ngrps[p - r] = ngrps[hb - r];
\
+ if (histo)
\
+ cnts[ngrps[hb - r]]++;
\
+ break;
\
+ }
\
+ }
\
+ } else {
\
+ prb = hash_##TYPE(hs, &w[p]);
\
+ for (hb = hs->hash[prb];
\
+ hb != BUN_NONE;
\
+ hb = hs->link[hb]) {
\
+ if (w[p] == w[hb]) {
\
+ ngrps[p - r] = ngrps[hb - r];
\
+ if (histo)
\
+ cnts[ngrps[hb - r]]++;
\
+ break;
\
+ }
\
+ }
\
+ }
\
+ if (hb == BUN_NONE ||
\
+ (gc && grps[hb - r] != grps[p - r])) {
\
+ GRPnotfound;
\
+ /* enter new group into hash table */
\
+ hs->link[p] = hs->hash[prb];
\
+ hs->hash[prb] = p;
\
+ }
\
+ }
\
} while (0)
gdk_return
@@ -424,17 +472,20 @@ BATgroup_internal(BAT **groups, BAT **ex
ngrp++;
}
} else if (b->T->hash) {
- /* we already have a hash table on b */
+ bit gc = g && (g->tsorted || g->trevsorted);
+
+ /* we already have a hash table on b;
+ * we also exploit if g is clustered */
ALGODEBUG fprintf(stderr, "#BATgroup(b=%s#" BUNFMT ","
"g=%s#" BUNFMT ","
"e=%s#" BUNFMT ","
"h=%s#" BUNFMT ",subsorted=%d): "
- "use existing hash table\n",
+ "use existing hash table%s\n",
BATgetId(b), BATcount(b),
g ? BATgetId(g) : "NULL", g ? BATcount(g) : 0,
e ? BATgetId(e) : "NULL", e ? BATcount(e) : 0,
h ? BATgetId(h) : "NULL", h ? BATcount(h) : 0,
- subsorted);
+ subsorted, gc ? " (g clustered)" : "");
hs = b->T->hash;
for (r = BUNfirst(b), p = r, q = r + BATcount(b); p < q; p++) {
v = BUNtail(bi, p);
@@ -442,79 +493,85 @@ BATgroup_internal(BAT **groups, BAT **ex
* HASHloop: the difference is that we only
* consider BUNs smaller than the one we're
* looking up (p), and that we also consider
- * the input groups */
+ * the input groups;
+ * we also exploit if g is clustered */
+ /* skip irrelevant BUNs after the current BUNs;
+ * exploit that hash-table links backwards through BAT
*/
for (hb = hs->hash[HASHprobe(hs, v)];
- hb != BUN_NONE;
- hb = hs->link[hb]) {
- if (hb < p &&
- (grps == NULL ||
- grps[hb - r] == grps[p - r]) &&
- cmp(v, BUNtail(bi, hb)) == 0) {
- ngrps[p - r] = ngrps[hb - r];
- if (histo)
- cnts[ngrps[hb - r]]++;
- break;
+ hb != BUN_NONE && hb >= p;
+ hb = hs->link[hb]) {}
+ if (gc) {
+ for (;
+ hb != BUN_NONE && grps[hb - r] == grps[p -
r];
+ hb = hs->link[hb]) {
+ if (cmp(v, BUNtail(bi, hb)) == 0) {
+ ngrps[p - r] = ngrps[hb - r];
+ if (histo)
+ cnts[ngrps[hb - r]]++;
+ break;
+ }
+ }
+ } else if (grps) {
+ for (;
+ hb != BUN_NONE;
+ hb = hs->link[hb]) {
+ if (grps[hb - r] == grps[p - r] &&
+ cmp(v, BUNtail(bi, hb)) == 0) {
+ ngrps[p - r] = ngrps[hb - r];
+ if (histo)
+ cnts[ngrps[hb - r]]++;
+ break;
+ }
+ }
+ } else {
+ for (;
+ hb != BUN_NONE;
+ hb = hs->link[hb]) {
+ if (cmp(v, BUNtail(bi, hb)) == 0) {
+ ngrps[p - r] = ngrps[hb - r];
+ if (histo)
+ cnts[ngrps[hb - r]]++;
+ break;
+ }
}
}
- if (hb == BUN_NONE) {
- /* no equal found: start new group */
- if (ngrp == maxgrps) {
- /* we need to extend extents
- * and histo bats, do it
- * once */
- maxgrps = BATcount(b);
- if (extents) {
- BATsetcount(en, ngrp);
- en = BATextend(en, maxgrps);
- exts = (oid *) Tloc(en,
BUNfirst(en));
- }
- if (histo) {
- BATsetcount(hn, ngrp);
- hn = BATextend(hn, maxgrps);
- cnts = (wrd *) Tloc(hn,
BUNfirst(hn));
- }
- }
- if (extents)
- exts[ngrp] = b->hseqbase + (oid) (p -
r);
- if (histo)
- cnts[ngrp] = 1;
- ngrps[p - r] = ngrp;
- ngrp++;
+ if (hb == BUN_NONE || (gc && grps[hb - r] != grps[p -
r])) {
+ GRPnotfound;
}
}
gn->tsorted = BATcount(gn) <= 1;
} else {
+ bit gc = g && (g->tsorted || g->trevsorted);
const char *nme;
size_t nmelen;
Heap *hp = NULL;
BUN prb;
BUN mask = HASHmask(b->batCount) >> 3;
- int bits1 = 3, bits2;
+ int bits = 3;
/* when combining value and group-id hashes,
- * left-shift them by, respectively,
- * 1/3 & 2/3 of the hash-mask width
- * to better spread bits and use entire hash-mask,
+ * we left-shift one of them by half the hash-mask width
+ * to better spread bits and use the entire hash-mask,
* and thus reduce collisions */
while (mask>>=1)
- bits1++;
- bits1 /= 3;
- bits2 = 2 * bits1;
+ bits++;
+ bits /= 2;
/* not sorted, and no pre-existing hash table: we'll
* build an incomplete hash table on the fly--also see
* BATassertHeadProps and BATderiveHeadProps for
- * similar code */
+ * similar code;
+ * we also exploit if g is clustered */
ALGODEBUG fprintf(stderr, "#BATgroup(b=%s#" BUNFMT ","
"g=%s#" BUNFMT ","
"e=%s#" BUNFMT ","
"h=%s#" BUNFMT ",subsorted=%d): "
- "create partial hash table\n",
+ "create partial hash table%s\n",
BATgetId(b), BATcount(b),
g ? BATgetId(g) : "NULL", g ? BATcount(g) : 0,
e ? BATgetId(e) : "NULL", e ? BATcount(e) : 0,
h ? BATgetId(h) : "NULL", h ? BATcount(h) : 0,
- subsorted);
+ subsorted, gc ? " (g clustered)" : "");
nme = BBP_physical(b->batCacheid);
nmelen = strlen(nme);
if ((hp = GDKzalloc(sizeof(Heap))) == NULL ||
@@ -537,33 +594,44 @@ BATgroup_internal(BAT **groups, BAT **ex
goto error;
}
- for (r = BUNfirst(b), p = r, q = r + BATcount(b); p < q; p++) {
- switch (ATOMstorage(hs->type)) {
- case TYPE_bte:
- GRPhashloop(bte);
- break;
- case TYPE_sht:
- GRPhashloop(sht);
- break;
- case TYPE_int:
- GRPhashloop(int);
- break;
- case TYPE_lng:
- GRPhashloop(lng);
- break;
- case TYPE_flt:
- GRPhashloop(flt);
- break;
- case TYPE_dbl:
- GRPhashloop(dbl);
- break;
- default:
_______________________________________________
checkin-list mailing list
[email protected]
http://mail.monetdb.org/mailman/listinfo/checkin-list
