Changeset: 8635e919383a for MonetDB
URL: https://dev.monetdb.org/hg/MonetDB/rev/8635e919383a
Modified Files:
gdk/gdk_string.c
Branch: string-dedup
Log Message:
Don't use linear hashing to grow string hash; better estimate for initial size.
Now loading data (tpc-h copy into) is only slightly slower.
diffs (truncated from 477 to 300 lines):
diff --git a/gdk/gdk_string.c b/gdk/gdk_string.c
--- a/gdk/gdk_string.c
+++ b/gdk/gdk_string.c
@@ -23,6 +23,16 @@
* can be between one and four bytes long.
*/
+#ifdef __GNUC__
+/* __builtin_expect returns its first argument; it is expected to be
+ * equal to the second argument */
+#define unlikely(expr) __builtin_expect((expr) != 0, 0)
+#define likely(expr) __builtin_expect((expr) != 0, 1)
+#else
+#define unlikely(expr) (expr)
+#define likely(expr) (expr)
+#endif
+
/* some of these macros are duplicates from gdk_atoms.c */
#define num08(x) ((x) >= '0' && (x) <= '7')
#define base08(x) ((x) - '0')
@@ -38,7 +48,7 @@
GDKfree(*dst); \
*len = (size); \
*dst = GDKmalloc(*len); \
- if (*dst == NULL) { \
+ if (unlikely(*dst == NULL)) { \
*len = 0; \
return -1; \
} \
@@ -48,11 +58,9 @@
const char str_nil[2] = { '\200', 0 };
struct hash {
- BUN mask1;
- BUN mask2;
- BUN nbucket;
+ BUN mask;
BUN nentries;
- BUN growlim;
+ BUN limit;
uint64_t *buckets;
Heap heap;
};
@@ -64,16 +72,15 @@ struct hash {
#define PSLSHIFT 40
#define PSLMASK ((UINT64_C(1) << PSLSHIFT) - 1)
+/* calculate the hash for `value', given `hs' */
static inline BUN
-hash_str(struct hash *h, const char *value)
+hash_str(const struct hash *hs, const char *value)
{
- BUN hsh = strHash(value);
- hsh &= h->mask2;
- if (hsh >= h->nbucket)
- hsh &= h->mask1;
- return hsh;
+ return strHash(value) & hs->mask;
}
+/* enter the string `value' into the vheap and return its position or
+ * ((var_t) -1) on failure */
static inline var_t
str_enter(BAT *b, const char *value)
{
@@ -84,7 +91,7 @@ str_enter(BAT *b, const char *value)
do {
newsize += 64 * 1024;
} while (pos + len > newsize);
- if (HEAPgrow(&b->theaplock, &b->tvheap, newsize, true) !=
GDK_SUCCEED)
+ if (unlikely(HEAPgrow(&b->theaplock, &b->tvheap, newsize, true)
!= GDK_SUCCEED))
return (var_t) -1;
}
memcpy(b->tvheap->base + pos, value, len);
@@ -93,20 +100,21 @@ str_enter(BAT *b, const char *value)
return pos;
}
+/* add the value `pos' with hash `hsh' to the hash table */
static inline void
-str_reinsert(struct hash *h, BUN hsh, var_t pos)
+str_reinsert(struct hash *hs, BUN hsh, var_t pos)
{
uint64_t psl = 0;
uint64_t swp = EMPTY;
for (;;) {
- uint64_t bkt = h->buckets[hsh];
+ uint64_t bkt = hs->buckets[hsh];
if (bkt == EMPTY) {
/* found an empty slot */
if (swp == EMPTY) {
swp = (uint64_t) pos;
}
- h->buckets[hsh] = swp | psl << PSLSHIFT;
+ hs->buckets[hsh] = swp | psl << PSLSHIFT;
return;
}
uint64_t psl2 = bkt >> PSLSHIFT;
@@ -114,129 +122,78 @@ str_reinsert(struct hash *h, BUN hsh, va
if (swp == EMPTY) {
swp = (uint64_t) pos;
}
- h->buckets[hsh] = swp | psl << PSLSHIFT;
+ hs->buckets[hsh] = swp | psl << PSLSHIFT;
swp = bkt & PSLMASK;
psl = psl2;
}
- if (++hsh == h->nbucket)
+ if (hsh++ == hs->mask)
hsh = 0;
psl++;
}
}
-static inline void
-str_remove(struct hash *h, BUN pos)
+/* double the size of the hash table */
+static gdk_return
+str_growhash(BAT *b, struct hash *hs)
{
- h->buckets[pos] = EMPTY;
- for (;;) {
- BUN hsh = pos + 1;
- if (hsh >= h->nbucket)
- hsh = 0;
- uint64_t p = h->buckets[hsh];
- if (p == EMPTY)
- break;
- uint64_t psl = p >> PSLSHIFT;
- if (psl == 0)
- break;
- h->buckets[pos] = (p & PSLMASK) | (psl - 1) << PSLSHIFT;
- h->buckets[hsh] = EMPTY;
- pos = hsh;
- }
-}
-
-static inline void
-str_incPSL(struct hash *h)
-{
- uint64_t hsh = 0;
- for (;;) {
- uint64_t bkt = h->buckets[hsh];
- if (bkt == EMPTY)
- break;
- uint64_t psl = bkt >> PSLSHIFT;
- if (psl <= hsh)
- break;
- h->buckets[hsh] = (bkt & PSLMASK) | (psl + 1) << PSLSHIFT;
- if (++hsh == h->nbucket)
- break;
- }
-}
-
-static inline gdk_return
-str_growhash(BAT *b, struct hash *h)
-{
- BUN oldmask1 = h->mask1;
- BUN oldnbucket = h->nbucket;
+ HEAPfree(&hs->heap, true);
+ hs->mask = hs->mask << 1 | 1;
+ hs->limit <<= 1;
+ if (unlikely(HEAPalloc(&hs->heap, hs->mask + 1 + OFFSET,
sizeof(uint64_t), 0) != GDK_SUCCEED))
+ return GDK_FAIL;
- if ((h->nbucket + OFFSET) * sizeof(uint64_t) >= h->heap.size) {
- if (HEAPextend(&h->heap, h->heap.size + 64 * 1024, true) !=
GDK_SUCCEED)
- return GDK_FAIL;
- h->buckets = (uint64_t *) h->heap.base + OFFSET;
- }
- if (h->nbucket == h->mask2) {
- h->mask1 = h->mask2;
- h->mask2 |= h->mask2 << 1; /* extend with one bit */
+ hs->heap.free = (hs->mask + 1 + OFFSET) * sizeof(uint64_t);
+ *(uint64_t *) hs->heap.base = STRHASH_VERSION;
+ hs->buckets = (uint64_t *) (hs->heap.base + OFFSET);
+ memset(hs->buckets, -1, (hs->mask + 1) * sizeof(uint64_t));
+#ifndef NDEBUG
+ BUN nentries = 0;
+#endif
+ Heap *hp = b->tvheap;
+ const char *v = hp->base;
+ for (var_t pos = 0, free = (var_t) hp->free; pos < free;) {
+ size_t len = strlen(v) + 1;
+ BUN hsh = hash_str(hs, v);
+ str_reinsert(hs, hsh, pos);
+#ifndef NDEBUG
+ nentries++;
+#endif
+ pos += len;
+ v += len;
}
- h->nbucket++;
- h->heap.free = (h->nbucket + OFFSET) * sizeof(uint64_t);
- h->growlim = (BUN) (h->nbucket * (0.75 - (h->nbucket & h->mask1) / (2.0
* h->mask2)));
- assert(h->mask1 < h->nbucket && h->nbucket <= h->mask2);
-
- str_incPSL(h);
- str_remove(h, h->nbucket - 1);
-
- BUN hsh = oldnbucket & oldmask1;
- uint64_t psl = 0;
-
- for (;;) {
- uint64_t bkt = h->buckets[hsh];
- if (bkt == EMPTY)
- break;
- uint64_t psl2 = bkt >> PSLSHIFT;
- if (psl2 < psl)
- break;
- if (psl2 == psl) {
- bkt &= PSLMASK;
- const char *v = b->tvheap->base + bkt;
- BUN c = strHash(v);
- if ((c & h->mask2) == oldnbucket) {
- /* this one should be moved */
- str_remove(h, hsh);
- str_reinsert(h, oldnbucket, (var_t) bkt);
- continue;
- }
- }
- if (++hsh == oldnbucket)
- hsh = 0;
- psl++;
- }
+ assert(hs->nentries == nentries);
return GDK_SUCCEED;
}
+/* insert a new string into the bat's vheap, using the hash table,
+ * return the position (if a duplicate, returns the position of the
+ * duplicated string), returns (var_t)-1 on error */
static var_t
-str_insert(BAT *b, struct hash *h, const char *value)
+str_insert(BAT *b, struct hash *hs, const char *value)
{
- BUN hsh = hash_str(h, value);
+ BUN hsh = hash_str(hs, value);
uint64_t psl = 0; /* probe sequence length */
uint64_t swp = EMPTY; /* swapped entry */
var_t new = (var_t) -1; /* new entry */
for (;;) {
- uint64_t bkt = h->buckets[hsh];
+ uint64_t bkt = hs->buckets[hsh];
if (bkt == EMPTY) {
/* found an empty slot */
if (swp == EMPTY) {
assert(new == (var_t) -1);
/* didn't enter value yet, so do it now */
new = str_enter(b, value);
- if (new == (var_t) -1)
+ if (unlikely(new == (var_t) -1))
return (var_t) -1;
swp = (uint64_t) new;
- h->nentries++;
+ hs->nentries++;
+ b->tunique_est = (double) hs->nentries;
}
assert(new != (var_t) -1);
- h->buckets[hsh] = swp | psl << PSLSHIFT;
- while (h->nentries >= h->growlim)
- if (str_growhash(b, h) != GDK_SUCCEED)
+ hs->buckets[hsh] = swp | psl << PSLSHIFT;
+ while (hs->nentries >= hs->limit)
+ if (unlikely(str_growhash(b, hs) !=
GDK_SUCCEED))
return (var_t) -1;
return new;
}
@@ -255,31 +212,37 @@ str_insert(BAT *b, struct hash *h, const
if (swp == EMPTY) {
assert(new == (var_t) -1);
new = str_enter(b, value);
- if (new == (var_t) -1)
+ if (unlikely(new == (var_t) -1))
return (var_t) -1;
swp = (uint64_t) new;
- h->nentries++;
+ hs->nentries++;
+ b->tunique_est = (double) hs->nentries;
}
- h->buckets[hsh] = swp | psl << PSLSHIFT;
+ hs->buckets[hsh] = swp | psl << PSLSHIFT;
swp = bkt;
psl = psl2;
}
- if (++hsh == h->nbucket)
+ if (hsh++ == hs->mask)
hsh = 0;
psl++;
}
}
+/* allocate, initialize and return a hash table */
static struct hash *
str_hashinit(BAT *b)
{
struct hash *hs = GDKmalloc(sizeof(struct hash));
- if (hs == NULL)
_______________________________________________
checkin-list mailing list
[email protected]
https://www.monetdb.org/mailman/listinfo/checkin-list
