Changeset b7d6a36 for doc/theses/thierry_delisle_PhD/code/utils.hpp

Timestamp:

Feb 20, 2020, 4:15:51 PM (6 years ago)

Author:

Thierry Delisle <tdelisle@…>

Branches:

ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum

Children:

6a490b2

Parents:

dca5802 (diff), 2cbfe92 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

Merge branch 'master' into relaxed_ready

File:

• doc/theses/thierry_delisle_PhD/code/utils.hpp (modified) (4 diffs)

doc/theses/thierry_delisle_PhD/code/utils.hpp

@@ -10 +10 @@
 #include <unistd.h>
 #include <sys/sysinfo.h>
+
+#include <x86intrin.h>
 
 // Barrier from
@@ -56 +58 @@
 }
 
-void affinity(int tid) {
+static inline void affinity(int tid) {
         static int cpus = get_nprocs();
 
@@ -70 +72 @@
 
 static const constexpr std::size_t cache_line_size = 64;
-void check_cache_line_size() {
+static inline void check_cache_line_size() {
         std::cout << "Checking cache line size" << std::endl;
         const std::string cache_file = "/sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size";
@@ -103 +105 @@
         return std::chrono::duration_cast<std::chrono::duration<T, Ratio>>(std::chrono::duration<T>(seconds)).count();
 }
+
+static inline unsigned rand_bit(unsigned rnum, size_t mask) {
+        unsigned bit = mask ? rnum % __builtin_popcountl(mask) : 0;
+#if !defined(__BMI2__)
+        uint64_t v = mask;   // Input value to find position with rank r.
+        unsigned int r = bit + 1;// Input: bit's desired rank [1-64].
+        unsigned int s;      // Output: Resulting position of bit with rank r [1-64]
+        uint64_t a, b, c, d; // Intermediate temporaries for bit count.
+        unsigned int t;      // Bit count temporary.
+
+        // Do a normal parallel bit count for a 64-bit integer,
+        // but store all intermediate steps.
+        a =  v - ((v >> 1) & ~0UL/3);
+        b = (a & ~0UL/5) + ((a >> 2) & ~0UL/5);
+        c = (b + (b >> 4)) & ~0UL/0x11;
+        d = (c + (c >> 8)) & ~0UL/0x101;
+
+
+        t = (d >> 32) + (d >> 48);
+        // Now do branchless select!
+        s  = 64;
+        s -= ((t - r) & 256) >> 3; r -= (t & ((t - r) >> 8));
+        t  = (d >> (s - 16)) & 0xff;
+        s -= ((t - r) & 256) >> 4; r -= (t & ((t - r) >> 8));
+        t  = (c >> (s - 8)) & 0xf;
+        s -= ((t - r) & 256) >> 5; r -= (t & ((t - r) >> 8));
+        t  = (b >> (s - 4)) & 0x7;
+        s -= ((t - r) & 256) >> 6; r -= (t & ((t - r) >> 8));
+        t  = (a >> (s - 2)) & 0x3;
+        s -= ((t - r) & 256) >> 7; r -= (t & ((t - r) >> 8));
+        t  = (v >> (s - 1)) & 0x1;
+        s -= ((t - r) & 256) >> 8;
+        return s - 1;
+#else
+        uint64_t picked = _pdep_u64(1ul << bit, mask);
+        return picked ? __builtin_ctzl(picked) : 0;
+#endif
+}