Changeset: d751bda6c6d2 for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=d751bda6c6d2
Modified Files:
gdk/gdk_group.c
Branch: partioned-hash
Log Message:
Calculate mixed hash for pre-grouped grouping differently.
This results in more than double the speed for TPC-H query 16 at scale
factor 10.
diffs (64 lines):
diff --git a/gdk/gdk_group.c b/gdk/gdk_group.c
--- a/gdk/gdk_group.c
+++ b/gdk/gdk_group.c
@@ -327,30 +327,6 @@
} while (0)
#endif
-/* Count number of 1 bits in the argument.
- * The algorithm comes from Henry S. Warren, Jr., Hacker's Delight,
- * 2nd Edition, page 82. */
-static inline int
-pop(BUN n)
-{
-#if SIZEOF_BUN == 4
- n -= (n >> 1) & 0x55555555;
- n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
- n = (n + (n >> 4)) & 0x0F0F0F0F;
- n += n >> 8;
- n += n >> 16;
- return (int) (n & 0x3F);
-#else
- n -= (n >> 1) & 0x5555555555555555;
- n = (n & 0x3333333333333333) + ((n >> 2) & 0x3333333333333333);
- n = (n + (n >> 4)) & 0x0F0F0F0F0F0F0F0F;
- n += n >> 8;
- n += n >> 16;
- n += n >> 32;
- return (int) (n & 0x7F);
-#endif
-}
-
#define GRP_create_partial_hash_table(INIT_0,INIT_1,HASH,COMP) \
do { \
INIT_0; \
@@ -383,7 +359,7 @@ pop(BUN n)
hb = HASHnil(hs); \
} \
} else if (grps) { \
- prb = (prb ^ (BUN) grps[p-r] << bits) &
hs->mask; \
+ prb = (prb ^ (BUN) grps[p-r]) & hs->mask; \
for (hb = HASHget(hs, 0, prb); \
hb != HASHnil(hs); \
hb = HASHgetlink(hs, hb)) { \
@@ -909,7 +885,6 @@ BATgroup_internal(BAT **groups, BAT **ex
size_t nmelen;
Heap *hp = NULL;
BUN prb;
- int bits = 0;
/* not sorted, and no pre-existing hash table: we'll
* build an incomplete hash table on the fly--also see
@@ -944,12 +919,6 @@ BATgroup_internal(BAT **groups, BAT **ex
goto error;
}
- /* when combining value and group-id hashes,
- * we left-shift one of them by half the hash-mask width
- * to better spread bits and use the entire hash-mask,
- * and thus reduce collisions */
- bits = pop(hs->mask) >> 1;
-
gn->tsorted = 1; /* be optimistic */
switch (t) {
_______________________________________________
checkin-list mailing list
checkin-list@monetdb.org
https://www.monetdb.org/mailman/listinfo/checkin-list
