feat(exp): Add expt_0516_2

Signed-off-by: KunoiSayami <[email protected]>

1 files changed, 61 insertions, 0 deletions

diff --git a/expt_0516_2.cu b/expt_0516_2.cu
new file mode 100644
index 0000000..f0eb69a
--- /dev/null
+++ b/expt_0516_2.cu
@@ -0,0 +1,61 @@
+// Experimental content: Test CustomSort Calculation
+#include <algorithm>
+#include <cstdio>
+
+#ifndef LOCKFREE_SORTLIB_CUH
+#include <cassert>
+class CustomSort {
+public:
+  explicit CustomSort(size_t length) : LENGTH(length) {}
+  const size_t LENGTH;
+  static size_t fast_log(size_t a) {
+    float t = a;
+    return (((*(int *)&t) >> 23) + 1) & 127;
+  }
+
+  size_t calculate_index(size_t rank) const {
+    size_t bit_low = (LENGTH + 1) >> fast_log(++rank) >> 1;
+    return (((rank << 1) | 1) * bit_low - LENGTH - 1);
+  }
+
+  size_t calculate_rank(size_t index) const {
+    index++;
+    size_t low_bit = index & (-index);
+    return ((LENGTH + index) / low_bit) >> 1;
+  }
+
+  __attribute__((unused)) void testCalculation() const {
+    for (size_t i = 0; i < LENGTH; i++) {
+      auto left = calculate_index(i);
+      auto right = calculate_rank(left - 1);
+      if (i + 1 == LENGTH || i + 1 != right) {
+        printf("%lu %lu %lu\n", i, left, right);
+        printf("%lu %lu %lu\n", LENGTH, fast_log(i + 1),
+               (LENGTH + 1) >> fast_log(i + 1) >> 1);
+      }
+      assert(i + 1 == right);
+    }
+  }
+
+  static void testSelf(size_t length) { CustomSort(length).testCalculation(); }
+};
+#endif
+
+long pow_for_sample(long n) {
+  auto x = 2;
+  for (int i = 1; i < n; i++) {
+    x *= 2;
+  }
+  return x - 1;
+}
+
+int main(int argc, char const *argv[]) {
+  auto max = 30L;
+  if (argc > 1) {
+    max = strtol(argv[1], nullptr, 10);
+  }
+  for (int i = 4; i < max; i++) {
+    CustomSort::testSelf(pow_for_sample(i));
+    printf("%d pass\n", i);
+  }
+}