Changeset: bfeeeecb69ff for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=bfeeeecb69ff
Modified Files:
gdk/gdk_atoms.c
gdk/gdk_bat.c
gdk/gdk_group.c
gdk/gdk_search.c
gdk/gdk_search.h
gdk/gdk_select.c
gdk/gdk_unique.c
Branch: default
Log Message:
Update of hash handling.
- the "hash" function for bte and sht are now the identity function;
- the hash mask is at least 1<<16 for anything larger than bte;
- removed unused cruft;
- in gdk_select and gdk_unique, make use of the knowledge that some
"hash" functions are perfect (i.e. no collisions).
diffs (truncated from 410 to 300 lines):
diff --git a/gdk/gdk_atoms.c b/gdk/gdk_atoms.c
--- a/gdk/gdk_atoms.c
+++ b/gdk/gdk_atoms.c
@@ -82,7 +82,7 @@ bteHash(const bte *v)
static BUN
shtHash(const sht *v)
{
- return (BUN) mix_sht(*(const unsigned short *) v);
+ return (BUN) *(const unsigned short *) v;
}
static BUN
diff --git a/gdk/gdk_bat.c b/gdk/gdk_bat.c
--- a/gdk/gdk_bat.c
+++ b/gdk/gdk_bat.c
@@ -2879,6 +2879,7 @@ BATassertHeadProps(BAT *b)
size_t nmelen = strlen(nme);
Heap *hp;
Hash *hs = NULL;
+ BUN mask;
if ((hp = GDKzalloc(sizeof(Heap))) == NULL ||
(hp->filename = GDKmalloc(nmelen + 30)) == NULL) {
@@ -2892,10 +2893,16 @@ BATassertHeadProps(BAT *b)
snprintf(hp->filename, nmelen + 30,
"%s.hash" SZFMT, nme, MT_getpid());
ext = GDKstrdup(hp->filename + nmelen + 1);
+ if (ATOMsize(b->htype) == 1)
+ mask = 1 << 8;
+ else if (ATOMsize(b->htype) == 2)
+ mask = 1 << 16;
+ else
+ mask = HASHmask(b->batCount);
if ((hp->farmid = BBPselectfarm(TRANSIENT, b->htype,
hashheap)) < 0 ||
(hs = HASHnew(hp, b->htype, BUNlast(b),
- HASHmask(b->batCount))) == NULL) {
+ mask)) == NULL) {
GDKfree(ext);
GDKfree(hp->filename);
GDKfree(hp);
@@ -3093,16 +3100,23 @@ BATderiveHeadProps(BAT *b, int expensive
b->H->nodense = 0;
}
if (expensive) {
+ BUN mask;
+
nme = BBP_physical(b->batCacheid);
nmelen = strlen(nme);
+ if (ATOMsize(b->htype) == 1)
+ mask = 1 << 8;
+ else if (ATOMsize(b->htype) == 2)
+ mask = 1 << 16;
+ else
+ mask = HASHmask(b->batCount);
if ((hp = GDKzalloc(sizeof(Heap))) == NULL ||
(hp->filename = GDKmalloc(nmelen + 30)) == NULL ||
(hp->farmid = BBPselectfarm(TRANSIENT, b->htype, hashheap))
< 0 ||
snprintf(hp->filename, nmelen + 30,
"%s.hash" SZFMT, nme, MT_getpid()) < 0 ||
(ext = GDKstrdup(hp->filename + nmelen + 1)) == NULL ||
- (hs = HASHnew(hp, b->htype, BUNlast(b),
- HASHmask(b->batCount))) == NULL) {
+ (hs = HASHnew(hp, b->htype, BUNlast(b), mask)) == NULL) {
if (hp) {
if (hp->filename)
GDKfree(hp->filename);
diff --git a/gdk/gdk_group.c b/gdk/gdk_group.c
--- a/gdk/gdk_group.c
+++ b/gdk/gdk_group.c
@@ -186,7 +186,6 @@
/* KEEP */ pv = v \
)
-
/* If a hash table exists on b we use it.
*
* The algorithm is simple. We go through b and for each value we
@@ -283,7 +282,7 @@
hb != HASHnil(hs) && \
grps[hb - r] == grps[p - r]; \
hb = HASHgetlink(hs,hb)) { \
- assert( HASHgetlink(hs,hb) ==
HASHnil(hs) \
+ assert(HASHgetlink(hs,hb) ==
HASHnil(hs) \
|| HASHgetlink(hs,hb) < hb); \
if (COMP) { \
oid grp = ngrps[hb - r]; \
@@ -302,7 +301,7 @@
hb = HASHnil(hs); \
} \
} else if (grps) { \
- prb = ((prb << bits) ^ (BUN) grps[p-r]) &
hs->mask; \
+ prb = (prb ^ (BUN) grps[p-r] << bits) &
hs->mask; \
for (hb = HASHget(hs,prb); \
hb != HASHnil(hs); \
hb = HASHgetlink(hs,hb)) { \
@@ -833,6 +832,16 @@ BATgroup_internal(BAT **groups, BAT **ex
subsorted, gc ? " (g clustered)" : "");
nme = BBP_physical(b->batCacheid);
nmelen = strlen(nme);
+ if (ATOMsize(t) == 1) {
+ mask = 1 << 16;
+ bits = 8;
+ } else if (ATOMsize(t) == 2) {
+ mask = 1 << 16;
+ bits = 8;
+ } else {
+ mask = HASHmask(b->batCount);
+ bits = 0;
+ }
if ((hp = GDKzalloc(sizeof(Heap))) == NULL ||
(hp->farmid = BBPselectfarm(TRANSIENT, b->ttype, hashheap))
< 0 ||
(hp->filename = GDKmalloc(nmelen + 30)) == NULL ||
@@ -840,7 +849,7 @@ BATgroup_internal(BAT **groups, BAT **ex
"%s.hash" SZFMT, nme, MT_getpid()) < 0 ||
(ext = GDKstrdup(hp->filename + nmelen + 1)) == NULL ||
(hs = HASHnew(hp, b->ttype, BUNlast(b),
- HASHmask(b->batCount))) == NULL) {
+ MAX(HASHmask(b->batCount), 1 << 16))) ==
NULL) {
if (hp) {
if (hp->filename)
GDKfree(hp->filename);
diff --git a/gdk/gdk_search.c b/gdk/gdk_search.c
--- a/gdk/gdk_search.c
+++ b/gdk/gdk_search.c
@@ -98,7 +98,7 @@ HASHwidth(BUN hashsize)
BUN
HASHmask(BUN cnt)
{
- BUN m = 8; /* minimum size */
+ BUN m = 1 << 8; /* minimum size */
while (m + m < cnt)
m += m;
@@ -263,7 +263,7 @@ BAThash(BAT *b, BUN masksize)
} else if (ATOMsize(tpe) == 1) {
mask = (1 << 8);
} else if (ATOMsize(tpe) == 2) {
- mask = (1 << 12);
+ mask = (1 << 16);
} else if (b->tkey) {
mask = HASHmask(cnt);
} else {
@@ -278,8 +278,6 @@ BAThash(BAT *b, BUN masksize)
p = q;
}
- if (mask < 1024)
- mask = 1024;
t0 = GDKusec();
do {
BUN nslots = mask >> 3; /* 1/8 full is too full */
diff --git a/gdk/gdk_search.h b/gdk/gdk_search.h
--- a/gdk/gdk_search.h
+++ b/gdk/gdk_search.h
@@ -128,14 +128,13 @@ gdk_export BUN HASHlist(Hash *h, BUN i);
} while (0)
#endif
-#define mix_sht(X) (((X)>>7)^(X))
#define mix_int(X) (((X)>>7)^((X)>>13)^((X)>>21)^(X))
#define hash_loc(H,V) hash_any(H,V)
#define hash_var(H,V) hash_any(H,V)
#define hash_any(H,V) (ATOMhash((H)->type, (V)) & (H)->mask)
#define heap_hash_any(hp,H,V) ((hp) && (hp)->hashash ? ((BUN *) (V))[-1] &
(H)->mask : hash_any(H,V))
-#define hash_bte(H,V) ((BUN) (*(const unsigned char*) (V)) & (H)->mask)
-#define hash_sht(H,V) ((BUN) mix_sht(*((const unsigned short*) (V))) &
(H)->mask)
+#define hash_bte(H,V) (assert(((H)->mask & 0xFF) == 0xFF), (BUN) *(const
unsigned char*) (V))
+#define hash_sht(H,V) (assert(((H)->mask & 0xFFFF) == 0xFFFF), (BUN) *(const
unsigned short*) (V))
#define hash_int(H,V) ((BUN) mix_int(*((const unsigned int*) (V))) &
(H)->mask)
/* XXX return size_t-sized value for 8-byte oid? */
#define hash_lng(H,V) ((BUN) mix_int((unsigned int) (*(const lng *)(V) ^
(*(const lng *)(V) >> 32))) & (H)->mask)
@@ -226,109 +225,26 @@ gdk_export BUN HASHlist(Hash *h, BUN i);
#define HASHfnd_any(x,y,z) HASHfnd(x,y,z)
/*
* A new entry is added with HASHins using the BAT, the BUN index, and
- * a pointer to the value to be stored. An entry is removed by HASdel.
- */
-#define HASHins_TYPE(h, i, v, TYPE) \
- do { \
- BUN _c = hash_##TYPE(h,v); \
- HASHputall(h,i,_c); \
- } while (0)
-
-#define HASHins_str(h,i,v) \
- do { \
- BUN _c; \
- GDK_STRHASH(v,_c); \
- _c &= (h)->mask; \
- HASHputall(h,i,_c); \
- } while (0)
-#define HASHins_str_hv(h,i,v) \
- do { \
- BUN _c = ((BUN *) v)[-1] & (h)->mask; \
- HASHputall(h,i,_c); \
- } while (0)
-
-#define HASHins_any(h,i,v) \
- do { \
- BUN _c = HASHprobe(h, v); \
- HASHputall(h,i,_c); \
- } while (0)
-
-/* HASHins receives a BAT* param and is adaptive, killing wrongly
+ * a pointer to the value to be stored.
+ *
+ * HASHins receives a BAT* param and is adaptive, killing wrongly
* configured hash tables.
* Use HASHins_any or HASHins_<tpe> instead if you know what you're
* doing or want to keep the hash. */
#define HASHins(b,i,v) \
do { \
- if (((i) & 1023) == 1023 && HASHgonebad((b),(v))) \
+ if (((i) & 1023) == 1023 && HASHgonebad((b), (v))) \
HASHremove(b); \
- else \
- HASHins_any((b)->T->hash,(i),(v)); \
+ else { \
+ BUN _c = HASHprobe((b)->T->hash, (v)); \
+ HASHputall((b)->T->hash, (i), _c); \
+ } \
} while (0)
-#if SIZEOF_VOID_P == SIZEOF_INT
-#define HASHins_ptr(h,i,v) HASHins_int(h,i,v)
-#else /* SIZEOF_VOID_P == SIZEOF_LNG */
-#define HASHins_ptr(h,i,v) HASHins_lng(h,i,v)
-#endif
-#define HASHins_bit(h,i,v) HASHins_bte(h,i,v)
-#if SIZEOF_OID == SIZEOF_INT /* OIDDEPEND */
-#define HASHins_oid(h,i,v) HASHins_int(h,i,v)
-#else
-#define HASHins_oid(h,i,v) HASHins_lng(h,i,v)
-#endif
-#define HASHins_flt(h,i,v) HASHins_int(h,i,v)
-#define HASHins_dbl(h,i,v) HASHins_lng(h,i,v)
-#define HASHinsvar(h,i,v) HASHins_any(h,i,v)
-#define HASHinsloc(h,i,v) HASHins_any(h,i,v)
-
-#define HASHins_bte(h,i,v) HASHins_TYPE(h,i,v,bte)
-#define HASHins_sht(h,i,v) HASHins_TYPE(h,i,v,sht)
-#define HASHins_int(h,i,v) HASHins_TYPE(h,i,v,int)
-#define HASHins_lng(h,i,v) HASHins_TYPE(h,i,v,lng)
-#ifdef HAVE_HGE
-#define HASHins_hge(h,i,v) HASHins_TYPE(h,i,v,hge)
-#endif
-
-#define HASHdel(h, i, v, next) \
- do { \
- if (next && HASHgetlink(h, i+1) == i) { \
- HASHputlink(h,i+1,HASHgetlink(h,i)); \
- } else { \
- BUN _c = HASHprobe(h, v); \
- if (HASHget(h,_c) == i) { \
- HASHput(h,_c, HASHgetlink(h,i)); \
- } else { \
- for(_c = HASHget(h,_c); _c != HASHnil(h); \
- _c = HASHgetlink(h,_c)) { \
- if (HASHgetlink(h,_c) == i) { \
- HASHputlink(h,_c,
HASHgetlink(h,i)); \
- break; \
- } \
- } \
- } \
- } \
- HASHputlink(h,i,HASHnil(h)); \
- } while (0)
-
-#define HASHmove(h, i, j, v, next) \
- do { \
- if (next && HASHgetlink(h,i+1) == i) { \
- HASHputlink(h,i+1,j); \
- } else { \
- BUN _c = HASHprobe(h, v); \
- if (HASHget(h,_c) == i) { \
- HASHput(h,_c,j); \
- } else { \
- for(_c = HASHget(h,_c) ; _c != HASHnil(h); \
- _c = HASHgetlink(h,_c)) { \
- if (HASHgetlink(h,_c) == i) { \
- HASHputlink(h,_c,j); \
- break; \
- } \
- } \
- } \
- } \
- HASHputlink(h,j, HASHgetlink(h,i)); \
+#define HASHins_oid(h,i,v) \
+ do { \
+ BUN _c = hash_oid(h,v); \
+ HASHputall(h,i,_c); \
} while (0)
/* Functions to perform a binary search on a sorted BAT.
diff --git a/gdk/gdk_select.c b/gdk/gdk_select.c
--- a/gdk/gdk_select.c
+++ b/gdk/gdk_select.c
@@ -152,12 +152,13 @@ doubleslice(BAT *b, BUN l1, BUN h1, BUN
return virtualize(bn);
}
_______________________________________________
checkin-list mailing list
[email protected]
https://www.monetdb.org/mailman/listinfo/checkin-list
