Changeset: 944af0425760 for MonetDB
URL: https://dev.monetdb.org/hg/MonetDB/rev/944af0425760
Modified Files:
gdk/gdk_group.c
Branch: dict
Log Message:
Some (speed) improvements to grouping small valued bats.
Prefer array-based grouping over checking consecutive values; special
code for dense (or no) candidate lists.
diffs (202 lines):
diff --git a/gdk/gdk_group.c b/gdk/gdk_group.c
--- a/gdk/gdk_group.c
+++ b/gdk/gdk_group.c
@@ -598,6 +598,57 @@ ctz(oid x)
/* EQUAL */ cmp(v, BUNtail(bi, hb)) == 0 \
)
+#define GRP_small_values(BG, BV, GV) \
+ do { \
+ uint##BG##_t *restrict sgrps = GDKmalloc((1 << BG) *
sizeof(uint##BG##_t)); \
+ const uint##BV##_t *restrict w = (const uint##BV##_t *)
bi.base; \
+ uint##BG##_t v; \
+ if (sgrps == NULL) \
+ goto error1; \
+ memset(sgrps, 0xFF, (1 << BG) * sizeof(uint##BG##_t)); \
+ if (histo) \
+ memset(cnts, 0, maxgrps * sizeof(lng)); \
+ ngrp = 0; \
+ gn->tsorted = true; \
+ if (ci.tpe == cand_dense) { \
+ TIMEOUT_LOOP_IDX(r, cnt, timeoffset) { \
+ oid o = canditer_next_dense(&ci); \
+ p = o - b->hseqbase; \
+ uint##BG##_t x = GV; \
+ if ((v = sgrps[x]) == (uint##BG##_t) ~0 && ngrp
< (1 << BG)) { \
+ sgrps[x] = v = (uint##BG##_t) ngrp++; \
+ maxgrppos = r; \
+ if (extents) \
+ exts[v] = o; \
+ } \
+ ngrps[r] = v; \
+ if (r > 0 && v < ngrps[r - 1]) \
+ gn->tsorted = false; \
+ if (histo) \
+ cnts[v]++; \
+ } \
+ } else { \
+ TIMEOUT_LOOP_IDX(r, cnt, timeoffset) { \
+ oid o = canditer_next(&ci); \
+ p = o - b->hseqbase; \
+ uint##BG##_t x = GV; \
+ if ((v = sgrps[x]) == (uint##BG##_t) ~0 && ngrp
< (1 << BG)) { \
+ sgrps[x] = v = (uint##BG##_t) ngrp++; \
+ maxgrppos = r; \
+ if (extents) \
+ exts[v] = o; \
+ } \
+ ngrps[r] = v; \
+ if (r > 0 && v < ngrps[r - 1]) \
+ gn->tsorted = false; \
+ if (histo) \
+ cnts[v]++; \
+ } \
+ } \
+ TIMEOUT_CHECK(timeoffset, \
+ GOTO_LABEL_TIMEOUT_HANDLER(error)); \
+ GDKfree(sgrps); \
+ } while (0)
gdk_return
BATgroup_internal(BAT **groups, BAT **extents, BAT **histo,
@@ -862,7 +913,26 @@ BATgroup_internal(BAT **groups, BAT **ex
}
}
- if (subsorted ||
+ if (g == NULL && t == TYPE_bte) {
+ /* byte-sized values, use 256 entry array to keep
+ * track of doled out group ids; note that we can't
+ * possibly have more than 256 groups, so the group id
+ * fits in a uint8_t */
+ GRP_small_values(8, 8, w[p]);
+ } else if (t == TYPE_bte && maxgrp < 256) {
+ /* subgrouping byte-sized values with a limited number
+ * of groups, use 65536 entry array to keep track of
+ * doled out group ids; note that we can't possibly have
+ * more than 65536 goups, so the group id fits in a
+ * uint16_t */
+ GRP_small_values(16, 8, (uint16_t) (w[p] | (grps[p] << 8)));
+ } else if (g == NULL && t == TYPE_sht) {
+ /* short-sized values, use 65536 entry array to keep
+ * track of doled out group ids; note that we can't
+ * possibly have more than 65536 groups, so the group
+ * id fits in a uint16_t */
+ GRP_small_values(16, 16, w[p]);
+ } else if (subsorted ||
((BATordered(b) || BATordered_rev(b)) &&
(g == NULL || BATordered(g) || BATordered_rev(g)))) {
/* we only need to compare each entry with the previous */
@@ -963,112 +1033,6 @@ BATgroup_internal(BAT **groups, BAT **ex
}
GDKfree(pgrp);
- } else if (g == NULL && t == TYPE_bte) {
- /* byte-sized values, use 256 entry array to keep
- * track of doled out group ids; note that we can't
- * possibly have more than 256 groups, so the group id
- * fits in a uint8_t */
- uint8_t *restrict bgrps = GDKmalloc(256);
- const uint8_t *restrict w = (const uint8_t *) bi.base;
- uint8_t v;
-
- algomsg = "byte-sized groups -- ";
- if (bgrps == NULL)
- goto error1;
- memset(bgrps, 0xFF, 256);
- if (histo)
- memset(cnts, 0, maxgrps * sizeof(lng));
- ngrp = 0;
- gn->tsorted = true;
- TIMEOUT_LOOP_IDX(r, cnt, timeoffset) {
- oid o = canditer_next(&ci);
- p = o - b->hseqbase;
- if ((v = bgrps[w[p]]) == 0xFF && ngrp < 256) {
- bgrps[w[p]] = v = (uint8_t) ngrp++;
- maxgrppos = r;
- if (extents)
- exts[v] = o;
- }
- ngrps[r] = v;
- if (r > 0 && v < ngrps[r - 1])
- gn->tsorted = false;
- if (histo)
- cnts[v]++;
- }
- TIMEOUT_CHECK(timeoffset,
- GOTO_LABEL_TIMEOUT_HANDLER(error));
- GDKfree(bgrps);
- } else if (t == TYPE_bte && maxgrp < 256) {
- /* byte-sized values with a limited number of groups,
- * use 65536 entry array to keep track of doled out
- * group ids; note that we can't possibly have more than
- * 65536 goups, so the group id fits in a uint16_t */
- uint16_t *restrict sgrps = GDKmalloc(65536 * sizeof(uint16_t));
- const uint8_t *restrict w = (const uint8_t *) bi.base;
- uint16_t v;
-
- algomsg = "short-sized subgroups -- ";
- if (sgrps == NULL)
- goto error1;
- memset(sgrps, 0xFF, 65536 * sizeof(uint16_t));
- if (histo)
- memset(cnts, 0, maxgrps * sizeof(lng));
- ngrp = 0;
- gn->tsorted = true;
- TIMEOUT_LOOP_IDX(r, cnt, timeoffset) {
- oid o = canditer_next(&ci);
- p = o - b->hseqbase;
- uint16_t x = (uint16_t) (w[p] | (grps[p] << 8));
- if ((v = sgrps[x]) == 0xFFFF && ngrp < 65536) {
- sgrps[x] = v = (uint16_t) ngrp++;
- maxgrppos = r;
- if (extents)
- exts[v] = o;
- }
- ngrps[r] = v;
- if (r > 0 && v < ngrps[r - 1])
- gn->tsorted = false;
- if (histo)
- cnts[v]++;
- }
- TIMEOUT_CHECK(timeoffset,
- GOTO_LABEL_TIMEOUT_HANDLER(error));
- GDKfree(sgrps);
- } else if (g == NULL && t == TYPE_sht) {
- /* short-sized values, use 65536 entry array to keep
- * track of doled out group ids; note that we can't
- * possibly have more than 65536 groups, so the group
- * id fits in a uint16_t */
- uint16_t *restrict sgrps = GDKmalloc(65536 * sizeof(uint16_t));
- const uint16_t *restrict w = (const uint16_t *) bi.base;
- uint16_t v;
-
- algomsg = "short-sized groups -- ";
- if (sgrps == NULL)
- goto error1;
- memset(sgrps, 0xFF, 65536 * sizeof(uint16_t));
- if (histo)
- memset(cnts, 0, maxgrps * sizeof(lng));
- ngrp = 0;
- gn->tsorted = true;
- TIMEOUT_LOOP_IDX(r, cnt, timeoffset) {
- oid o = canditer_next(&ci);
- p = o - b->hseqbase;
- if ((v = sgrps[w[p]]) == 0xFFFF && ngrp < 65536) {
- sgrps[w[p]] = v = (uint16_t) ngrp++;
- maxgrppos = r;
- if (extents)
- exts[v] = o;
- }
- ngrps[r] = v;
- if (r > 0 && v < ngrps[r - 1])
- gn->tsorted = false;
- if (histo)
- cnts[v]++;
- }
- TIMEOUT_CHECK(timeoffset,
- GOTO_LABEL_TIMEOUT_HANDLER(error));
- GDKfree(sgrps);
} else if (g == NULL &&
(BATcheckhash(b) ||
(!b->batTransient &&
_______________________________________________
checkin-list mailing list
[email protected]
https://www.monetdb.org/mailman/listinfo/checkin-list
