feat(exp): Add expt_0516

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

1 files changed, 28 insertions, 62 deletions

diff --git a/sortlib.cuh b/sortlib.cuh
index ca5525b..58aa7c1 100644
--- a/sortlib.cuh
+++ b/sortlib.cuh
@@ -15,8 +15,9 @@ public:
 
   /// MOVE_OFFSET means bit to select branch
   const int MOVE_OFFSET;
-  const int STEP_LIMIT;
+  const unsigned int STEP_LIMIT;
 
+  // IEEE 754
   __device__ __host__ static size_t fast_log(size_t a) {
     float t = a;
     return (((*(int *)&t) >> 23) + 1) & 127;
@@ -35,20 +36,20 @@ public:
 
   __device__ __host__ __attribute__((unused)) void testCalculation() const {
     for (size_t i = 0; i < LENGTH; i++) {
-      auto l = calculate_index(i);
-      auto l2 = calculate_rank(l - 1);
+      auto left = calculate_index(i);
+      auto right = calculate_rank(left - 1);
       // printf("%lu %lu\n", l, l2);
-      assert(i + 1 == l2);
+      assert(i + 1 == right);
     }
   }
 
   __device__ __host__ const key_type *binary_search(key_type *const start,
-                                                    const key_type *end,
-                                                    const key_type val) {
+                                                    // const key_type *end,
+                                                    const key_type val) const {
 
     // int step_limit = (int)fast_log(LENGTH);
     key_type *last_known_point = start;
-    auto son = 0;
+    auto son = 0UL;
 
     for (int i = 0; i < STEP_LIMIT; i++) {
       const auto next_level_start = start + (1 << (i + 1)) - 1;
@@ -56,59 +57,16 @@ public:
       // printf("start: %ld, last: %ld\n", next_level_start - start,
       //        last_known_point - start);
 
-      if (last_known_point > end) {
+      /*if (last_known_point > end) {
         printf("%ld\n", last_known_point - start);
-      }
-      if (*last_known_point == val) {
-        return last_known_point;
-      }
-
-      if (next_level_start > end) {
-        printf("%ld\n", next_level_start - start);
-      }
-
-      // son = get_son_from_step(son, (*last_known_point > val));
-      auto branch_selector = ((*last_known_point - val) >> MOVE_OFFSET);
-      // printf("tmp: %llu\n", tmp);
-      //    printf("%llu %llu ", val, *last_known_point);
-      son = son * 2 + branch_selector;
-      // printf("%d\n", son);
-      // puts(tmp == 0 ? "1:left" : "1:right");
-      //   if (son < 0) son = 0;
-      /*printf("%d %d %d\n", (1 << (i + 1)), son,
-             -(int)((*last_known_point - val) >> brenchSelector));*/
-      last_known_point = next_level_start + son;
-      if (last_known_point > end) {
-        printf("%p %ld\n", end, next_level_start - start);
-      }
-    }
-    return last_known_point;
-  }
-
-  __device__ __host__ const key_type *binary_search2(key_type *const start,
-                                                     const key_type *end,
-                                                     const key_type val) {
-
-    // int step_limit = (int)fast_log(LENGTH);
-    key_type *last_known_point = start;
-    auto son = 0;
-
-    for (int i = 0; i < STEP_LIMIT; i++) {
-      const auto next_level_start = start + (1 << (i + 1)) - 1;
-
-      // printf("start: %ld, last: %ld\n", next_level_start - start,
-      //        last_known_point - start);
-
-      if (last_known_point > end) {
-        printf("%ld\n", last_known_point - start);
-      }
+      }*/
       if (*last_known_point == val) {
         return last_known_point;
       }
 
-      if (next_level_start > end) {
+      /*if (next_level_start > end) {
         printf("%ld\n", next_level_start - start);
-      }
+      }*/
 
       // son = get_son_from_step(son, (*last_known_point > val));
       auto branch_selector = ((*last_known_point - val) >> MOVE_OFFSET);
@@ -121,18 +79,19 @@ public:
       /*printf("%d %d %d\n", (1 << (i + 1)), son,
              -(int)((*last_known_point - val) >> brenchSelector));*/
       last_known_point = next_level_start + son;
-      if (last_known_point > end) {
+      /*if (last_known_point > end) {
         printf("%p %ld\n", end, next_level_start - start);
-      }
+      }*/
     }
     return last_known_point;
   }
 
   /// Should be correct version
-  __device__ __host__ double
-  sample_cdf_custom_version(key_type *start, const key_type *end, key_type x) {
+  __device__ __host__ double sample_cdf_custom_version(key_type *start,
+                                                       // const key_type *end,
+                                                       key_type x) const {
     // printf("custom version:\n");
-    auto it = this->binary_search(start, end, x);
+    auto it = this->binary_search(start, x);
     // printf("search result: %ld\n", it - start);
     // assert(it <= start + this->LENGTH);
     /*if (it < start) {
@@ -145,6 +104,7 @@ public:
     if (prev_real_location == this->LENGTH) {
       return 1;
     }
+
     if (prev_real_location == 0) {
       return 0;
     }
@@ -160,8 +120,9 @@ public:
   }
 
   /// First version
-  __device__ __host__ key_type *
-  original_binary_search(key_type *start, const key_type *end, key_type &val) {
+  __device__ __host__ key_type *original_binary_search(key_type *start,
+                                                       const key_type *end,
+                                                       key_type &val) const {
     auto begin = start;
     key_type *last_known_point = nullptr;
     while (begin < end) {
@@ -188,7 +149,7 @@ public:
 
   /// CDF original version (should only work on default data layout)
   __device__ __host__ double sample_cdf(key_type *start, key_type *end,
-                                        key_type x) {
+                                        key_type x) const {
     auto it = this->original_binary_search(start, end, x);
     if (it == end) {
       return 1;
@@ -202,6 +163,11 @@ public:
             (double)(x - *it_prev) / (double)(*it - *it_prev)) /
            (double)((end - start) - 1);
   }
+
+  static void testSelf(size_t length) {
+    CustomSort(length, sizeof(long) * 8).testCalculation();
+    puts("You can remove this function if passed already");
+  }
 };
 
 __global__ void testCustomCalculation(size_t length) {