Changeset: beb7298583cc for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=beb7298583cc
Modified Files:
gdk/gdk_search.c
Branch: Oct2014
Log Message:
BAThash(): avoid potential 4x over allocation for dynamic hash mask
In case we choose to set the hash mask size dynamically accoding to the
number of hash collisions, the old code could (and did in case of TPCH)
overallocate a hash mask by (up to) 4x.
This happend (theoretically) in 1/3 of all cases, i.e., whenever
HASHmask() chooses a hash mask that is (just) smaller than cnt.
Then, HASHmask(cnt>>6) is (just) smaller than cnt/64,
and quadrupeling the mask 3 times (4*4*4=64) would still be (just) < cnt,
leading to a 4th quadrupeling, and thus a mask that is just smaller then 4*cnt.
We now start with mask = HASHmask(cnt)>>6, and ensure the mask does not
exceed HASHmask(cnt).
OPEN / TODO:
In case of "too many" (?) collisions with HASHmask(cnt) < cnt,
should we consider growing the mask size to 2*HASHmask(cnt),
i.e., HASHmask(cnt) < cnt < 2*HASHmask(cnt) < 2*cnt ?
diffs (38 lines):
diff --git a/gdk/gdk_search.c b/gdk/gdk_search.c
--- a/gdk/gdk_search.c
+++ b/gdk/gdk_search.c
@@ -252,7 +252,7 @@ BAThash(BAT *b, BUN masksize)
if (b->H->hash == NULL) {
unsigned int tpe = ATOMbasetype(b->htype);
BUN cnt = BATcount(b);
- BUN mask;
+ BUN mask, maxmask = 0;
BUN p = BUNfirst(b), q = BUNlast(b), r;
Hash *h = NULL;
Heap *hp = NULL;
@@ -287,11 +287,12 @@ BAThash(BAT *b, BUN masksize)
mask = HASHmask(cnt);
} else {
/* dynamic hash: we start with
- * HASHmask(cnt/64); if there are too many
- * collisions we try HASHmask(cnt/16), then
- * HASHmask(cnt/4), and finally
+ * HASHmask(cnt)/64; if there are too many
+ * collisions we try HASHmask(cnt)/16, then
+ * HASHmask(cnt)/4, and finally
* HASHmask(cnt). */
- mask = HASHmask(cnt >> 6);
+ maxmask = HASHmask(cnt);
+ mask = maxmask >> 6;
p += (cnt >> 2); /* try out on first 25% of b */
if (p > q)
p = q;
@@ -368,7 +369,7 @@ BAThash(BAT *b, BUN masksize)
}
break;
}
- } while (r < p && mask < cnt && (mask <<= 2));
+ } while (r < p && mask < maxmask && (mask <<= 2));
/* finish the hashtable with the current mask */
p = r;
_______________________________________________
checkin-list mailing list
checkin-list@monetdb.org
https://www.monetdb.org/mailman/listinfo/checkin-list
