fix: Fix wrong level calc

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

4 files changed, 20 insertions, 17 deletions

diff --git a/CMakeLists.txt b/CMakeLists.txt
index b79091f..f816aed 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -53,9 +53,12 @@ function(build_different_target is_random build_size step_size)
 
 endfunction()
 
+build_different_target(true 1024 8)
 #build_different_target(false 1048576 2)
 build_different_target(false 1048576 4)
 build_different_target(false 1048576 8)
+build_different_target(true 1048576 4)
+build_different_target(true 1048576 2)
 build_different_target(true 1048576 8)
 
 
diff --git a/main.cu b/main.cu
index a463280..b1239d7 100644
--- a/main.cu
+++ b/main.cu
@@ -99,13 +99,15 @@ constexpr size_t FACTOR = 1;
 // should change this to dynamic next time
 constexpr size_t KEY_INDEX_SIZE = 32;
 
-constexpr int block_size = STEP_SIZE;
+volatile int block_size = STEP_SIZE;
 
 // Supported operations
 constexpr int ADD = 0;
 constexpr int DELETE = 1;
 constexpr int SEARCH = 2;
 
+typedef LL key_type;
+
 #ifdef RANDOM_TARGET
 constexpr const char *TARGET_STRING = "RANDOM";
 #else
@@ -540,21 +542,21 @@ __global__ void kernel(LL *items, LL *op, LL *result) {
 }*/
 
 // Generate the level of a newly created node
-LL Randomlevel(std::mt19937 &randomEngine) {
-  std::geometric_distribution<> distribution(0.5);
-  return std::min(MAX_LEVEL, (size_t)distribution(randomEngine) + 1);
+LL Randomlevel(std::mt19937 &randomEngine, double p) {
+  std::geometric_distribution<> distribution(p);
+  return std::min(MAX_LEVEL, (size_t)distribution(randomEngine));
 }
 
 std::vector<LL> storage;
 
-unsigned trailing_zeroes(LL n) {
+unsigned trailing_zeroes(size_t index) {
   unsigned bits = 0;
-  LL x = n;
+  LL x = index / block_size;
 
   if (x) {
-    while ((x & 1) == 0) {
+    while (x % block_size == 0) {
       ++bits;
-      x >>= 1;
+      x /= block_size;
     }
   }
   return bits;
@@ -572,7 +574,7 @@ LL CustomLevel(LL value) {
   auto index = left - storage.begin();
 
   if (index % block_size == 0) {
-    auto level = trailing_zeroes(index / block_size + 1) + 1;
+    auto level = trailing_zeroes(index) + 1;
     // printf("%ld,%u\n", index, level);
     return level;
   }
@@ -641,7 +643,7 @@ int main(int argc, char **argv) {
   // srand(0);
   for (i = 0; i < NUM_ITEMS; i++) {
 #ifdef RANDOM_HEIGHT
-    // levels[i] = Randomlevel(randomEngine) - 1; // 36/14
+    levels[i] = Randomlevel(1 / randomEngine) - 1; // 36/14
 #else
     levels[i] = CustomLevel(items[i]) - 1; // 31/18
 #endif
@@ -737,11 +739,7 @@ int main(int argc, char **argv) {
 
   // Print kernel execution time in milliseconds
 
-  printf("%s ", TARGET_STRING);
-
-#ifndef RANDOM_TARGET
-  printf("%d ", block_size);
-#endif
+  printf("%s %d ", TARGET_STRING, block_size);
 
   printf("%lu: %lf", NUM_ITEMS, time);
 
diff --git a/test.sh b/test.sh
index 8da5e7d..cc16cc8 100755
--- a/test.sh
+++ b/test.sh
@@ -2,7 +2,7 @@
 mkdir test || true
 pushd test > /dev/null
 cmake ..
-cmake --build .
-find -type f -executable -name lock\* -exec {} 100 0 \;
+cmake --build . --parallel $(nproc)
+find -type f -executable -name lock\* -exec '{}' 100 0 \;
 popd > /dev/null
 rm -rf test
\ No newline at end of file
diff --git a/test_without_compile.sh b/test_without_compile.sh
new file mode 100755
index 0000000..bc1c0e3
--- /dev/null
+++ b/test_without_compile.sh
@@ -0,0 +1,2 @@
+#!/usr/bin/env bash
+find -type f -executable -name lock\* -exec '{}' 100 0 \;
\ No newline at end of file