Changeset: a7ca138a5812 for MonetDB URL: https://dev.monetdb.org/hg/MonetDB/rev/a7ca138a5812 Modified Files: gdk/gdk_batop.c Branch: Jul2021 Log Message:
Don't copy vheap at all cost. diffs (241 lines): diff --git a/gdk/gdk_batop.c b/gdk/gdk_batop.c --- a/gdk/gdk_batop.c +++ b/gdk/gdk_batop.c @@ -61,13 +61,13 @@ insert_string_bat(BAT *b, BAT *n, struct BATiter ni; /* iterator */ size_t toff = ~(size_t) 0; /* tail offset */ BUN p, r; /* loop variables */ - const void *tp; /* tail value pointer */ + const void *tp = NULL; /* tail value pointer */ unsigned char tbv; /* tail value-as-bte */ unsigned short tsv; /* tail value-as-sht */ #if SIZEOF_VAR_T == 8 unsigned int tiv; /* tail value-as-int */ #endif - var_t v = GDK_VAROFFSET; /* value */ + var_t v; /* value */ size_t off; /* offset within n's string heap */ BUN cnt = ci->ncand; BUN oldcnt = BATcount(b); @@ -80,146 +80,89 @@ insert_string_bat(BAT *b, BAT *n, struct if (cnt == 0) return GDK_SUCCEED; ni = bat_iterator(n); - tp = NULL; - if (oldcnt == 0 || (!GDK_ELIMDOUBLES(b->tvheap) && - !GDK_ELIMDOUBLES(ni.vh) && - b->tvheap->hashash == ni.vh->hashash)) { - if (b->batRole == TRANSIENT || b->tvheap == ni.vh) { - /* If b is in the transient farm (i.e. b will - * never become persistent), we try some - * clever tricks to avoid copying: - * - if b is empty, we just let it share the - * string heap with n; - * - otherwise, if b's string heap and n's - * string heap are the same (i.e. shared), - * we leave it that way (this includes the - * case that b is persistent and n shares - * its string heap with b); - * - otherwise, if b shares its string heap - * with some other bat, we materialize it - * and we will have to copy strings. - */ - bat bid = b->batCacheid; - /* if candidates are not dense, there is no - * wholesale copying of n's offset heap, but - * we may still be able to share the string - * heap */ - if (mayshare && - oldcnt == 0 && - b->tvheap != ni.vh && - ci->tpe == cand_dense) { - /* make sure locking happens in a - * predictable order: lowest id - * first */ - MT_thread_setalgorithm("share vheap, copy heap"); - MT_lock_set(&b->theaplock); - if (b->tvheap->parentid != bid) - BBPunshare(b->tvheap->parentid); - HEAPdecref(b->tvheap, true); - HEAPincref(ni.vh); - b->tvheap = ni.vh; - BBPshare(ni.vh->parentid); - b->batDirtydesc = true; - MT_lock_unset(&b->theaplock); - toff = 0; - v = ni.width == 1 ? GDK_VAROFFSET + 1 : - ni.width == 2 ? GDK_VAROFFSET + (1 << 9) : -#if SIZEOF_VAR_T == 8 - ni.width != 4 ? (var_t) 1 << 33 : -#endif - (var_t) 1 << 17; - } else if (b->tvheap->parentid == ni.vh->parentid && - ci->tpe == cand_dense) { - MT_thread_setalgorithm("copy heap"); - toff = 0; - } else if (b->tvheap->parentid != bid && - unshare_varsized_heap(b) != GDK_SUCCEED) { - bat_iterator_end(&ni); - return GDK_FAIL; - } - } else if (oldcnt == 0) { - v = ni.width == 1 ? GDK_VAROFFSET + 1 : - ni.width == 2 ? GDK_VAROFFSET + (1 << 9) : -#if SIZEOF_VAR_T == 8 - ni.width != 4 ? (var_t) 1 << 33 : -#endif - (var_t) 1 << 17; - MT_thread_setalgorithm("copy vheap, copy heap"); - if (b->tvheap->size < ni.vh->free) { - if (HEAPgrow(&b->theaplock, &b->tvheap, ni.vh->free, force) != GDK_SUCCEED) { - bat_iterator_end(&ni); - return GDK_FAIL; - } - } - memcpy(b->tvheap->base, ni.vh->base, ni.vh->free); - b->tvheap->free = ni.vh->free; - toff = 0; + if (b->tvheap == ni.vh) { + /* vheaps are already shared, continue doing so: we just + * need to append the offsets */ + toff = 0; + MT_thread_setalgorithm("shared vheap"); + } else if (mayshare && b->batRole == TRANSIENT && oldcnt == 0) { + /* we can share the vheaps, so we then only need to + * append the offsets */ + MT_lock_set(&b->theaplock); + if (b->tvheap->parentid != b->batCacheid) + BBPunshare(b->tvheap->parentid); + HEAPdecref(b->tvheap, b->tvheap->parentid == b->batCacheid); + HEAPincref(ni.vh); + b->tvheap = ni.vh; + BBPshare(ni.vh->parentid); + b->batDirtydesc = true; + MT_lock_unset(&b->theaplock); + toff = 0; + MT_thread_setalgorithm("share vheap"); + } else { + /* no heap sharing, so also make sure the heap isn't + * shared currently (we're not allowed to write in + * another bat's heap) */ + if (b->tvheap->parentid != b->batCacheid && + unshare_varsized_heap(b) != GDK_SUCCEED) { + bat_iterator_end(&ni); + return GDK_FAIL; } - if (toff == ~(size_t) 0 && cnt > 1024 && b->tvheap->free >= ni.vh->free) { - /* If b and n aren't sharing their string - * heaps, we try to determine whether to copy - * n's whole string heap to the end of b's, or - * whether we will insert each string from n - * individually. We do this by testing a - * sample of n's strings and extrapolating - * from that sample whether n uses a - * significant part of its string heap for its - * strings (i.e. whether there are many unused - * strings in n's string heap). If n doesn't - * have many strings in the first place, we - * skip this and just insert them all - * individually. We also check whether a - * significant number of n's strings happen to - * have the same offset in b. In the latter - * case we also want to insert strings - * individually, but reusing the string in b's - * string heap. */ - int match = 0, i; - size_t len = b->tvheap->hashash ? 1024 * EXTRALEN : 0; - for (i = 0; i < 1024; i++) { + if (oldcnt == 0 || (!GDK_ELIMDOUBLES(b->tvheap) && + !GDK_ELIMDOUBLES(ni.vh) && + b->tvheap->hashash == ni.vh->hashash)) { + /* we'll consider copying the string heap completely + * + * we first estimate how much space the string heap + * should occupy, given the number of rows we need to + * insert, then, if that is way smaller than the actual + * space occupied, we will skip the copy and just insert + * one by one */ + size_t len = 0; + for (int i = 0; i < 1024; i++) { p = (BUN) (((double) rand() / RAND_MAX) * (cnt - 1)); p = canditer_idx(ci, p) - n->hseqbase; - off = BUNtvaroff(ni, p); - if (off < b->tvheap->free && - strcmp(b->tvheap->base + off, ni.vh->base + off) == 0 && - (!b->tvheap->hashash || - ((BUN *) (b->tvheap->base + off))[-1] == (ni.vh->hashash ? ((BUN *) (ni.vh->base + off))[-1] : strHash(ni.vh->base + off)))) - match++; - len += (strlen(ni.vh->base + off) + 8) & ~7; + len += strlen(BUNtvar(ni, p)) + 1; } - if (match < 768 && (size_t) (ni.count * (double) len / 1024) >= ni.vh->free / 2) { - /* append string heaps */ - toff = oldcnt == 0 ? 0 : b->tvheap->free; - /* make sure we get alignment right */ - toff = (toff + GDK_VARALIGN - 1) & ~(GDK_VARALIGN - 1); - /* if in "force" mode, the heap may be - * shared when memory mapped */ + len = (len + 512) / 1024; /* rounded average length */ + r = (GDK_ELIMLIMIT - GDK_STRHASHSIZE) / (len + 12); + /* r is estimate of number of strings in + * double-eliminated area */ + if (r < ci->ncand) + len = GDK_ELIMLIMIT + (ci->ncand - r) * len; + else + len = GDK_STRHASHSIZE + ci->ncand * (len + 12); + /* len is total estimated expected size of vheap */ + + if (len > ni.vh->free / 2) { + /* we copy the string heap, perhaps appending */ + if (oldcnt == 0) { + toff = 0; + MT_thread_setalgorithm("copy vheap"); + } else { + toff = (b->tvheap->free + GDK_VARALIGN - 1) & ~(GDK_VARALIGN - 1); + MT_thread_setalgorithm("append vheap"); + } + if (HEAPgrow(&b->theaplock, &b->tvheap, toff + ni.vh->size, force) != GDK_SUCCEED) { bat_iterator_end(&ni); return GDK_FAIL; } - MT_thread_setalgorithm("append vheap"); memcpy(b->tvheap->base + toff, ni.vh->base, ni.vh->free); b->tvheap->free = toff + ni.vh->free; - if (toff > 0) { - /* flush double-elimination - * hash table */ - memset(b->tvheap->base, 0, - GDK_STRHASHSIZE); - } - /* make sure b is wide enough */ - v = b->tvheap->free; } } - } else if (b->tvheap != ni.vh && - unshare_varsized_heap(b) != GDK_SUCCEED) { - bat_iterator_end(&ni); - return GDK_FAIL; } + /* if toff has the initial value of ~0, we insert strings + * individually, otherwise we only copy (insert) offsets */ + if (toff == ~(size_t) 0) + v = GDK_VAROFFSET; + else + v = b->tvheap->free - 1; /* make sure there is (vertical) space in the offset heap, we - * may also widen if v was set to some limit above */ + * may also widen thanks to v, set above */ if (GDKupgradevarheap(b, v, oldcnt + cnt < b->batCapacity ? b->batCapacity : oldcnt + cnt, b->batCount) != GDK_SUCCEED) { bat_iterator_end(&ni); return GDK_FAIL; @@ -228,6 +171,7 @@ insert_string_bat(BAT *b, BAT *n, struct if (toff == 0 && ni.width == b->twidth && ci->tpe == cand_dense) { /* we don't need to do any translation of offset * values, so we can use fast memcpy */ + MT_thread_setalgorithm("memcpy offsets"); memcpy(Tloc(b, BUNlast(b)), (const char *) ni.base + ((ci->seq - n->hseqbase) << ni.shift), cnt << ni.shift); } else if (toff != ~(size_t) 0) { /* we don't need to insert any actual strings since we _______________________________________________ checkin-list mailing list checkin-list@monetdb.org https://www.monetdb.org/mailman/listinfo/checkin-list