Changeset: c9b93c649d19 for MonetDB
URL: https://dev.monetdb.org/hg/MonetDB/rev/c9b93c649d19
Modified Files:
gdk/gdk_group.c
gdk/gdk_join.c
Branch: Jul2021
Log Message:
A little cleanup.
diffs (161 lines):
diff --git a/gdk/gdk_group.c b/gdk/gdk_group.c
--- a/gdk/gdk_group.c
+++ b/gdk/gdk_group.c
@@ -437,41 +437,43 @@ rev(oid x)
return x;
}
-/* population count: count number of 1 bits in a value */
-static inline int
-pop(oid x)
+/* count trailing zeros, also see candmask_lobit in gdk_cand.h */
+static inline int __attribute__((__const__))
+ctz(oid x)
{
-#ifdef __GNUC__
+#if defined(__GNUC__)
#if SIZEOF_OID == SIZEOF_INT
- return __builtin_popcount(x);
+ return __builtin_ctz(x);
#else
- return __builtin_popcountl(x);
+ return __builtin_ctzl(x);
#endif
-#else
-#ifdef _MSC_VER
+#elif defined(_MSC_VER)
#if SIZEOF_OID == SIZEOF_INT
- return (int) __popcnt((unsigned int) (x));
-#else
- return (int) __popcnt64((unsigned __int64) (x));
-#endif
+ unsigned long idx;
+ if (_BitScanForward(&idx, (unsigned long) x))
+ return (int) idx;
#else
- /* divide and conquer implementation */
-#if SIZEOF_OID == 8
- x = (x & 0x5555555555555555) + ((x >> 1) & 0x5555555555555555);
- x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
- x = (x & 0x0F0F0F0F0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F0F0F0F0F);
- x = (x & 0x00FF00FF00FF00FF) + ((x >> 8) & 0x00FF00FF00FF00FF);
- x = (x & 0x0000FFFF0000FFFF) + ((x >> 16) & 0x0000FFFF0000FFFF);
- x = (x & 0x00000000FFFFFFFF) + ((x >> 32) & 0x00000000FFFFFFFF);
+ unsigned long idx;
+ if (_BitScanForward64(&idx, (unsigned __int64) x))
+ return (int) idx;
+#endif
+ return -1;
#else
- x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
- x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
- x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
- x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
- x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF);
+ /* use binary search for the lowest set bit */
+ int n = 1;
+#if SIZEOF_OID == SIZEOF_INT
+ if ((x & 0x0000FFFF) == 0) { n += 16; x >>= 16; }
+ if ((x & 0x000000FF) == 0) { n += 8; x >>= 8; }
+ if ((x & 0x0000000F) == 0) { n += 4; x >>= 4; }
+ if ((x & 0x00000003) == 0) { n += 2; x >>= 2; }
+#else
+ if ((x & UINT64_C(0x00000000FFFFFFFF)) == 0) { n += 32; x >>= 32; }
+ if ((x & UINT64_C(0x000000000000FFFF)) == 0) { n += 16; x >>= 16; }
+ if ((x & UINT64_C(0x00000000000000FF)) == 0) { n += 8; x >>= 8; }
+ if ((x & UINT64_C(0x000000000000000F)) == 0) { n += 4; x >>= 4; }
+ if ((x & UINT64_C(0x0000000000000003)) == 0) { n += 2; x >>= 2; }
#endif
- return (int) x;
-#endif
+ return n - (x & 1);
#endif
}
@@ -1091,9 +1093,9 @@ BATgroup_internal(BAT **groups, BAT **ex
nbucket |= nbucket >> 32;
#endif
nbucket++;
- /* nbucket is a power of two, so pop(nbucket - 1)
+ /* nbucket is a power of two, so ctz(nbucket)
* tells us which power of two */
- bits = 8 * SIZEOF_OID - pop(nbucket - 1);
+ bits = 8 * SIZEOF_OID - ctz(nbucket);
} else {
nbucket = MAX(HASHmask(cnt), 1 << 16);
}
diff --git a/gdk/gdk_join.c b/gdk/gdk_join.c
--- a/gdk/gdk_join.c
+++ b/gdk/gdk_join.c
@@ -2897,35 +2897,6 @@ hashjoin(BAT **r1p, BAT **r2p, BAT *l, B
return GDK_FAIL;
}
-/* population count: count number of 1 bits in a value */
-static inline uint32_t __attribute__((__const__))
-pop(uint32_t x)
-{
-#if defined(__GNUC__)
- return (uint32_t) __builtin_popcount(x);
-#elif defined(_MSC_VER)
- return (uint32_t) __popcnt((unsigned int) (x));
-#else
- /* divide and conquer implementation (the two versions are
- * essentially equivalent, but the first version is written a
- * bit smarter) */
-#if 1
- x -= (x >> 1) & ~0U/3 /* 0x55555555 */; /* 3-1=2; 2-1=1; 1-0=1; 0-0=0 */
- x = (x & ~0U/5) + ((x >> 2) & ~0U/5) /* 0x33333333 */;
- x = (x + (x >> 4)) & ~0UL/0x11 /* 0x0F0F0F0F */;
- x = (x + (x >> 8)) & ~0UL/0x101 /* 0x00FF00FF */;
- x = (x + (x >> 16)) & 0xFFFF /* ~0UL/0x10001 */;
-#else
- x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
- x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
- x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
- x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
- x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF);
-#endif
- return x;
-#endif
-}
-
/* Count the number of unique values for the first half and the complete
* set (the sample s of b) and return the two values in *cnt1 and
* *cnt2. In case of error, both values are 0. */
@@ -3004,7 +2975,7 @@ count_unique(BAT *b, BAT *s, BUN *cnt1,
if (i == ci.ncand/ 2) {
cnt = 0;
for (int j = 0; j < 256 / 32; j++)
- cnt += pop(seen[j]);
+ cnt += candmask_pop(seen[j]);
*cnt1 = cnt;
}
o = canditer_next(&ci);
@@ -3015,7 +2986,7 @@ count_unique(BAT *b, BAT *s, BUN *cnt1,
}
cnt = 0;
for (int j = 0; j < 256 / 32; j++)
- cnt += pop(seen[j]);
+ cnt += candmask_pop(seen[j]);
*cnt2 = cnt;
} else if (ATOMbasetype(b->ttype) == TYPE_sht) {
unsigned short val;
@@ -3030,7 +3001,7 @@ count_unique(BAT *b, BAT *s, BUN *cnt1,
if (i == half) {
cnt = 0;
for (int j = 0; j < 65536 / 32; j++)
- cnt += pop(seen[j]);
+ cnt += candmask_pop(seen[j]);
*cnt1 = cnt;
}
o = canditer_next(&ci);
@@ -3041,7 +3012,7 @@ count_unique(BAT *b, BAT *s, BUN *cnt1,
}
cnt = 0;
for (int j = 0; j < 65536 / 32; j++)
- cnt += pop(seen[j]);
+ cnt += candmask_pop(seen[j]);
*cnt2 = cnt;
GDKfree(seen);
seen = NULL;
_______________________________________________
checkin-list mailing list
[email protected]
https://www.monetdb.org/mailman/listinfo/checkin-list
