11 files changed, 205 insertions, 17 deletions

diff --git a/CMakeLists.txt b/CMakeLists.txt
index 6fb4891..02efadf 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -87,12 +87,8 @@ set_target_properties(normal_distribution_expt3 PROPERTIES LINKER_LANGUAGE CXX)
 add_executable(normal_distribution_expt0702 expt_0702.cpp)
 set_target_properties(normal_distribution_expt0702 PROPERTIES LINKER_LANGUAGE CXX)
 
-add_executable(work work.cu)
-target_link_libraries(work m stdc++)
-
-set_target_properties(work PROPERTIES
-        CUDA_SEPARABLE_COMPILATION ON)
-set_target_properties(work PROPERTIES CUDA_ARCHITECTURES "75")
+add_executable(work_0719 work_0719.cu)
+set_cuda_target_base(work_0719)
 
 add_executable(expt_0722 expt_0722.cpp)
 set_target_properties(expt_0722 PROPERTIES LINKER_LANGUAGE CXX)
@@ -177,5 +173,6 @@ set_cuda_target_base(expt_0528)
 add_executable(expt_0529 expt_0529.cu read_helper.h)
 set_cuda_target_base(expt_0529)
 
-
+add_executable(expt_0604 expt_0604.cu read_helper.h)
+set_cuda_target_base(expt_0604)
 
diff --git a/analysis0510.py b/analysis0510.py
index 59cc65c..78290ab 100755
--- a/analysis0510.py
+++ b/analysis0510.py
@@ -6,7 +6,7 @@ def read_from_line(line: str) -> dict[str, int | float]:
     ret = {}
     if 'skip:' in line:
         ret.update({'skip': int(line.split('skip:', 1)[1].split(',')[0])})
-    ret.update({'sample': int(line.split('length:', 1)[1].split('|', 1)[0])})
+    ret.update({'sample': int(line.split('length:', 1)[1].split('custom time:', 1)[0])})
     ret.update({'custom': float(line.split('custom time: ', 1)[1].split('time')[0])})
     ret.update({'normal': float(line.rsplit('time:', 1)[1])})
     return ret
@@ -30,6 +30,11 @@ def get_array_summary(sz: list[float]) -> tuple[str, str]:
     return f'{middle:.6f}', f'{avg:.6f}'
 
 
+def calc_improve(element: list[int]) -> float:
+    a, b = list(map(float, element[:2]))
+    return a / b if a > b else b / a
+
+
 def read(file: str, need_calc: bool = False, output_latex: bool = False) -> None:
     items = {}
     with open(file) as fin:
@@ -50,8 +55,9 @@ def read(file: str, need_calc: bool = False, output_latex: bool = False) -> None
                     new_result[key][x].append(element[x])
         print(*keys)
         for key, value in new_result.items():
-            column = list(get_array_summary(value[x]) for x in keys)
+            column = list(get_array_summary(value[x])[1] for x in keys)
             if output_latex:
+                column.append(f'{calc_improve(column):.6f}')
                 column = list(map(str, column))
                 column.insert(0, str(key))
                 print('\\hline\n', ' & '.join(column), '\\\\')
diff --git a/expt_0501.cu b/expt_0501.cu
index 2d740e4..dcd25f5 100644
--- a/expt_0501.cu
+++ b/expt_0501.cu
@@ -1,5 +1,6 @@
 // Experimental content: Test the correctness of binary search and special
 // search
+#define ENABLE_SORT_TEST
 #include "sortlib.cuh"
 
 #include <algorithm>
diff --git a/expt_0503.cu b/expt_0503.cu
index 58f35aa..0ada96c 100644
--- a/expt_0503.cu
+++ b/expt_0503.cu
@@ -1,4 +1,5 @@
 // Experimental content: Test branch performance
+#define ENABLE_SORT_TEST
 #include "sortlib.cuh"
 
 #include <algorithm>
@@ -59,8 +60,7 @@ __global__ void kernel(unsigned long step, const double slice_size,
 
     // printf("%d\n", tid);
     auto index = (int)(custom_sort.sample_cdf_custom_version(
-                           cudaSampleItem, cudaSampleItem + cuda_sample_length,
-                           cudaPopulationItem[tid]) /
+                           cudaSampleItem, cudaPopulationItem[tid]) /
                        slice_size) -
                  1;
     cdf_result[index] = true;
diff --git a/expt_0516.cu b/expt_0516.cu
index 351a8c4..48b3811 100644
--- a/expt_0516.cu
+++ b/expt_0516.cu
@@ -1,6 +1,6 @@
 // Experimental content: Test branch performance (optimized memory and output)
 // #define PRINT_READ_PROCESS
-#include "read_helper.h"
+#include "read_helper_p.h"
 #include "sortlib.cuh"
 
 #include <algorithm>
diff --git a/expt_0516_2.cu b/expt_0516_2.cu
index 860e146..9171d01 100644
--- a/expt_0516_2.cu
+++ b/expt_0516_2.cu
@@ -1,5 +1,6 @@
 // Experimental content: Test CustomSort Calculation
 #define DISABLE_TEST_WARNING
+#define ENABLE_SORT_TEST
 #include "sortlib.cuh"
 
 #include <algorithm>
diff --git a/expt_0520.cu b/expt_0520.cu
index bd1439f..42cdab3 100644
--- a/expt_0520.cu
+++ b/expt_0520.cu
@@ -202,14 +202,12 @@ int main(int argc, char **argv) {
   }
 
   auto error = cudaGetLastError();
-  auto total_row = 0UL;
   auto sample_length = strtol(argv[1], nullptr, 0);
   auto insertion_length = strtol(argv[2], nullptr, 0);
   printf("insert_length %ld, sample_length: %ld\n", insertion_length,
          sample_length);
 
-  ReadHelper reader("normal_distribution.txt", sample_length, insertion_length,
-                    total_row);
+  ReadHelper reader("normal_distribution.txt", sample_length, insertion_length);
   reader.readFile();
 
   key_type *cudaPopulation;
diff --git a/expt_0604.cu b/expt_0604.cu
new file mode 100644
index 0000000..bd64ad0
--- /dev/null
+++ b/expt_0604.cu
@@ -0,0 +1,73 @@
+// Experimental content: Print level by cdf
+
+#include "sortlib.cuh"
+#define READ_NO_OUTPUT
+#include "read_helper.h"
+
+long pow_for_sample(long n) {
+  auto x = 2;
+  for (int i = 1; i < n; i++) {
+    x *= 2;
+  }
+  return x - 1;
+}
+
+static unsigned trailing_zeroes(size_t index) {
+  constexpr auto block_size = 2;
+  unsigned bits = 0;
+  auto x = index / block_size;
+
+  if (x) {
+    while (x % block_size == 0) {
+      ++bits;
+      x /= block_size;
+    }
+  }
+  return bits;
+}
+
+inline double calcSliceSize(size_t insertion_size) {
+  return 1.0 / (double)insertion_size;
+}
+
+constexpr auto RESULT_LENGTH = 35;
+
+int main(int argc, char const *argv[]) {
+
+  if (argc != 3) {
+    printf("Usage %s [sample(pow)] [population]\n", argv[0]);
+    return 1;
+  }
+
+  auto sample_length = pow_for_sample(strtol(argv[1], nullptr, 10));
+  auto population_length = strtol(argv[2], nullptr, 10);
+
+  printf("sample length: %ld, population length: %ld\n", sample_length,
+         population_length);
+
+  ReadHelper readHelper("normal_distribution.txt", sample_length, 0);
+  readHelper.readFile();
+
+  std::vector<key_type> sample, population;
+  std::vector<unsigned int> result(RESULT_LENGTH);
+  readHelper.split_into(sample, population);
+  rebuildSort(sample);
+
+  auto scale_size = calcSliceSize(population_length);
+
+  auto sort = CustomSort(sample_length, sizeof(key_type) * 8);
+
+  for (auto element : readHelper.population_vector) {
+    auto ret = sort.sample_cdf_custom_version(sample.data(), element);
+    auto cdf_index = ret / scale_size;
+    auto index = trailing_zeroes((size_t)cdf_index);
+    result[index]++;
+  }
+
+  for (int i = 0; i < 32; i++) {
+    if (!result[i]) {
+      continue;
+    }
+    printf("%d: %d\n", i, result[i]);
+  }
+}
diff --git a/read_helper.h b/read_helper.h
index f8396f2..2256ef8 100644
--- a/read_helper.h
+++ b/read_helper.h
@@ -65,14 +65,14 @@ public:
     return dst(mt19937);
   }
 
-  void readFile() {
+  bool readFile() {
     this->population_vector.clear();
     auto read_number = 0UL;
     FILE *file = fopen(filename, "r");
 
     if (file == nullptr) {
       fprintf(stderr, "Unable to open file %s\n", filename);
-      exit(1);
+      return false;
     }
 
     P_ERR("Reading sample");
@@ -98,6 +98,7 @@ public:
       read_number++;
     fclose(file);
     P_ERR("\r");
+    return true;
   }
 
   void split_into(std::vector<key_type> &sample, std::vector<key_type> &p) {
diff --git a/read_helper_p.h b/read_helper_p.h
new file mode 100644
index 0000000..1b1d0eb
--- /dev/null
+++ b/read_helper_p.h
@@ -0,0 +1,111 @@
+
+#ifndef LOCKFREE_READ_HELPER_H
+#define LOCKFREE_READ_HELPER_H
+
+#include <cassert>
+#include <fstream>
+#include <random>
+#include <vector>
+
+#ifndef P_ERR
+#ifdef PRINT_READ_PROCESS
+#define P_ERR(...) fprintf(stderr, __VA_ARGS__)
+#else
+#define P_ERR(...)
+#endif
+#endif
+
+template <typename key_type> class ReadHelper {
+  // typedef unsigned long long key_type;
+
+  key_type max_value = std::numeric_limits<key_type>::min(),
+           min_value = std::numeric_limits<key_type>::max();
+
+  inline void store_into_vector(key_type value) {
+    if (max_value < value) {
+      max_value = value;
+    }
+    if (min_value > value) {
+      min_value = value;
+    }
+    population_vector.push_back(value);
+  }
+
+  char const *filename;
+  static constexpr size_t REVERSED_BLOCK = 256;
+
+  auto genRandomRow(size_t total_row) const {
+    if (total_row != 0) {
+      assert(total_row > (population_length + sample_length + REVERSED_BLOCK));
+      return randomRow(total_row - population_length - sample_length -
+                       REVERSED_BLOCK);
+    }
+    return 0UL;
+  }
+
+public:
+  const size_t sample_length, population_length, random_number;
+  ReadHelper(char const *filename, size_t sample_length,
+             size_t population_length, size_t total_row = 0)
+      : filename(filename), sample_length(sample_length),
+        population_length(population_length),
+        random_number(genRandomRow(total_row)) {}
+  key_type maxValue() const { return max_value; }
+  key_type minValue() const { return min_value; }
+
+  std::vector<key_type> population_vector;
+
+  static unsigned long randomRow(unsigned long max_value_) {
+    std::random_device randomDevice;
+    std::mt19937 mt19937(randomDevice());
+    std::uniform_int_distribution<std::mt19937::result_type> dst(0, max_value_);
+    return dst(mt19937);
+  }
+
+  bool readFile() {
+    this->population_vector.clear();
+    auto read_number = 0UL;
+    std::ifstream fin(filename);
+
+    if (!fin.is_open()) {
+      return false;
+    }
+
+    for (key_type i; read_number < sample_length && !fin.eof();
+         store_into_vector(i)) {
+      fin >> i;
+      read_number++;
+    }
+
+    if (random_number > 0) {
+      read_number = random_number;
+      for (key_type i; read_number > 0 && !fin.eof(); fin >> i)
+        read_number--;
+    }
+
+    read_number = 0;
+
+    auto remain = population_length + REVERSED_BLOCK;
+    for (key_type i; read_number < remain && !fin.eof(); store_into_vector(i)) {
+      fin >> i;
+      read_number++;
+    }
+    fin.close();
+    return true;
+  }
+
+  void split_into(std::vector<key_type> &sample, std::vector<key_type> &p) {
+    sample.resize(sample_length - 2);
+    p.resize(population_length);
+    memcpy(sample.data(), population_vector.data(),
+           sizeof(key_type) * (sample_length - 2));
+    sample.push_back(this->max_value);
+    sample.push_back(this->min_value);
+    memcpy(p.data(), population_vector.data() + sample_length,
+           sizeof(key_type) * population_length);
+  }
+
+  size_t size() const { return this->population_vector.size(); }
+};
+
+#endif
\ No newline at end of file
diff --git a/work.cu b/work_0719.cu
index 46bdfb4..46bdfb4 100644
--- a/work.cu
+++ b/work_0719.cu