Changeset: 96510139b5fa for MonetDB
URL: https://dev.monetdb.org/hg/MonetDB/rev/96510139b5fa
Modified Files:
gdk/gdk_cand.c
gdk/gdk_sample.c
Branch: default
Log Message:
Let BATsample return masked candidate lists in certain cases.
If the sample is at least one eighth the size of the bat, use a masked
candidate list since its size will be smaller than the size of an
ordinary candidate list. In addition, creating such a candidate list is
way more efficient than creating the oid-based candidate list.
diffs (130 lines):
diff --git a/gdk/gdk_cand.c b/gdk/gdk_cand.c
--- a/gdk/gdk_cand.c
+++ b/gdk/gdk_cand.c
@@ -701,7 +701,9 @@ canditer_init(struct canditer *ci, BAT *
cnt -= 32;
}
}
- ci->ncand = count_mask_bits(ci, 0, cnt);
+ ci->ncand = s->ttype == TYPE_msk
+ ? s->batCount
+ : count_mask_bits(ci, 0, cnt);
return;
default:
MT_UNREACHABLE();
diff --git a/gdk/gdk_sample.c b/gdk/gdk_sample.c
--- a/gdk/gdk_sample.c
+++ b/gdk/gdk_sample.c
@@ -113,6 +113,73 @@ do_batsample(oid hseq, BUN cnt, BUN n, r
/* sample size is larger than the input BAT, return
* all oids */
bn = BATdense(0, hseq, cnt);
+ } else if (cnt > n / 8) {
+ bn = COLnew(0, TYPE_void, 0, TRANSIENT);
+ Heap *msks = GDKmalloc(sizeof(Heap));
+ if (bn == NULL || msks == NULL) {
+ GDKfree(msks);
+ BBPreclaim(bn);
+ return NULL;
+ }
+ *msks = (Heap) {
+ .farmid = BBPselectfarm(TRANSIENT, TYPE_void, varheap),
+ .parentid = bn->batCacheid,
+ .dirty = true,
+ .refs = ATOMIC_VAR_INIT(1),
+ };
+ strtconcat(msks->filename, sizeof(msks->filename),
+ BBP_physical(bn->batCacheid), ".theap", NULL);
+ BUN nmask = (cnt + 31) / 32;
+ if (msks->farmid < 0 ||
+ HEAPalloc(msks,
+ nmask + sizeof(ccand_t) / sizeof(uint32_t),
+ sizeof(uint32_t)) != GDK_SUCCEED) {
+ GDKfree(msks);
+ BBPreclaim(bn);
+ return NULL;
+ }
+ ccand_t *c = (ccand_t *) msks->base;
+ *c = (ccand_t) {
+ .type = CAND_MSK,
+ .firstbit = cnt, /* too large, will be reduced */
+ };
+ msks->free = sizeof(ccand_t) + nmask * sizeof(uint32_t);
+ uint32_t *r = (uint32_t *) (msks->base + sizeof(ccand_t));
+ BATsetcount(bn, n);
+ bn->tunique_est = (double) n;
+ if (n <= cnt / 2) {
+ memset(r, 0, nmask * sizeof(uint32_t));
+ for (rescnt = 0; rescnt < n; rescnt++) {
+ BUN i;
+ do {
+ i = next(rse) % cnt;
+ } while ((r[i / 32] & (1U << (i % 32))) != 0);
+ r[i / 32] |= 1U << (i % 32);
+ if (i < c->firstbit)
+ c->firstbit = i;
+ }
+ } else {
+ memset(r, 0xFF, nmask * sizeof(uint32_t));
+ /* clear last few bits */
+ if (cnt % 32 != 0)
+ r[nmask - 1] &= (1U << (cnt % 32)) - 1;
+ n = cnt - n;
+ for (rescnt = 0; rescnt < n; rescnt++) {
+ BUN i;
+ do {
+ i = next(rse) % cnt;
+ } while ((r[i / 32] & (1U << (i % 32))) == 0);
+ r[i / 32] &= ~(1U << (i % 32));
+ }
+ for (rescnt = 0; rescnt < nmask; rescnt++) {
+ if (r[rescnt] != 0) {
+ c->firstbit = candmask_lobit(r[rescnt])
+ rescnt * 32;
+ break;
+ }
+ }
+ }
+ bn->tvheap = msks;
+ BATtseqbase(bn, hseq + c->firstbit);
} else {
oid minoid = hseq;
oid maxoid = hseq + cnt;
@@ -186,12 +253,15 @@ BAT *
BATsample_with_seed(BAT *b, BUN n, uint64_t seed)
{
random_state_engine rse;
+ lng t0 = 0;
+ TRC_DEBUG_IF(ALGO) t0 = GDKusec();
init_random_state_engine(rse, seed);
BAT *bn = do_batsample(b->hseqbase, BATcount(b), n, rse, NULL);
- TRC_DEBUG(ALGO, ALGOBATFMT "," BUNFMT " -> " ALGOOPTBATFMT "\n",
- ALGOBATPAR(b), n, ALGOOPTBATPAR(bn));
+ TRC_DEBUG(ALGO, ALGOBATFMT "," BUNFMT " -> " ALGOOPTBATFMT
+ " (" LLFMT " usec)\n",
+ ALGOBATPAR(b), n, ALGOOPTBATPAR(bn), GDKusec() - t0);
return bn;
}
@@ -200,7 +270,9 @@ BAT *
BATsample(BAT *b, BUN n)
{
static random_state_engine rse;
+ lng t0 = 0;
+ TRC_DEBUG_IF(ALGO) t0 = GDKusec();
MT_lock_set(&b->theaplock);
BUN batcount = BATcount(b);
MT_lock_unset(&b->theaplock);
@@ -209,7 +281,8 @@ BATsample(BAT *b, BUN n)
init_random_state_engine(rse, (uint64_t) GDKusec());
MT_lock_unset(&rse_lock);
BAT *bn = do_batsample(b->hseqbase, batcount, n, rse, &rse_lock);
- TRC_DEBUG(ALGO, ALGOBATFMT "," BUNFMT " -> " ALGOOPTBATFMT "\n",
- ALGOBATPAR(b), n, ALGOOPTBATPAR(bn));
+ TRC_DEBUG(ALGO, ALGOBATFMT "," BUNFMT " -> " ALGOOPTBATFMT
+ " (" LLFMT " usec)\n",
+ ALGOBATPAR(b), n, ALGOOPTBATPAR(bn), GDKusec() - t0);
return bn;
}
_______________________________________________
checkin-list mailing list -- [email protected]
To unsubscribe send an email to [email protected]
