diff options
| -rw-r--r-- | CMakeLists.txt | 12 | ||||
| -rw-r--r-- | valid_sort.cpp | 183 |
2 files changed, 194 insertions, 1 deletions
diff --git a/CMakeLists.txt b/CMakeLists.txt index 9d72a91..71f9202 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -4,6 +4,13 @@ set(CMAKE_CUDA_STANDARD 14) #set(GXX_INCLUDE /usr/lib/gcc/x86_64-pc-linux-gnu/11.3.0/include) +# from: Coelacanthus +add_compile_options( + $<$<COMPILE_LANGUAGE:CXX>:-Wall> + $<$<COMPILE_LANGUAGE:CXX>:-pedantic> + $<$<COMPILE_LANGUAGE:CXX>:-Wextra> +) + add_executable(lockfree main.cu) #add_definitions(-DNUM_ITEMS=1048576 -DKEYS=1048576 -DFACTOR=1) @@ -117,5 +124,8 @@ set_target_properties(expt_0809 PROPERTIES CUDA_ARCHITECTURES "75") set_target_properties(expt_0809 PROPERTIES LINKER_LANGUAGE CUDA) -add_executable(valid_sort valid_sort_new.cpp) +add_executable(valid_sort_new valid_sort_new.cpp) +target_link_libraries(valid_sort_new m stdc++) + +add_executable(valid_sort valid_sort.cpp) target_link_libraries(valid_sort m stdc++)
\ No newline at end of file diff --git a/valid_sort.cpp b/valid_sort.cpp new file mode 100644 index 0000000..f4d5ef4 --- /dev/null +++ b/valid_sort.cpp @@ -0,0 +1,183 @@ +#include <algorithm> +#include <cassert> +#include <cmath> +#include <iostream> +#include <vector> + +typedef unsigned long long key_type; +std::vector<unsigned long long> population_vector, sample_vector; +std::vector<bool> result_storage; +constexpr size_t SAMPLE_LENGTH = 1024, TEST_LENGTH = 1024; + +constexpr int MOVE_OFFSET = sizeof(key_type) * 8 - 1; + +size_t fast_log(size_t a) { + float t = a; + return (((*(int *)&t) >> 23) + 1) & 127; +} + +size_t calculate_location(size_t index) { + size_t bit_low = SAMPLE_LENGTH >> fast_log(++index) >> 1; + return (!bit_low) ? SAMPLE_LENGTH + : ((index << 1) | 1) * bit_low - SAMPLE_LENGTH; +} + +size_t calculate_location_inverse(size_t index) { + ++index; + size_t low_bit = index & (-index); + return (low_bit == SAMPLE_LENGTH) ? SAMPLE_LENGTH + : ((SAMPLE_LENGTH + index) / low_bit) >> 1; +} + +/*size_t calculate_location(size_t index) { + int step = (int)std::log2(++index) + 1; + auto location = + SAMPLE_LENGTH / (1 << step) * ((index & ((1 << (step - 1)) - 1)) * 2 + 1); + return location ? location : SAMPLE_LENGTH; +}*/ + +const key_type *cudaBinarySearch(key_type *const start, const key_type val) { + int step_limit = (int)fast_log(SAMPLE_LENGTH) - 1; + 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; + if (*last_known_point == val) { + return last_known_point; + } + + // son = get_son_from_step(son, (*last_known_point > val)); + son = son * 2 + (int)((*last_known_point - val) >> MOVE_OFFSET); + // if (son < 0) son = 0; + /*printf("%d %d %d\n", (1 << (i + 1)), son, + -(int)((*last_known_point - val) >> MOVE_OFFSET));*/ + last_known_point = next_level_start + son; + assert(last_known_point < &*sample_vector.end()); + // printf("%d\n", *last_known_point); + } + return last_known_point; +} + +long double sample_cdf(long double x) { + auto it = std::lower_bound(sample_vector.begin(), sample_vector.end(), x); + if (it == sample_vector.end()) { + return 1; + } + if (it == sample_vector.begin()) { + return 0; + } + auto it_prev = it - 1; + + return ((long double)(it_prev - sample_vector.begin()) + + (long double)(x - *it_prev) / (*it - *it_prev)) / + (long double)(sample_vector.size() - 1); +} + +long double sample_cdf_custom_version(long double x) { + auto it = cudaBinarySearch(sample_vector.data(), x); + assert(it < &*sample_vector.end()); + if (it == (&*sample_vector.end() - 1)) { + return 1; + } + if (it == sample_vector.data()) { + return 0; + } + auto it_prev = sample_vector.data() + + calculate_location_inverse( + calculate_location(it - sample_vector.data()) - 2) - + 1; + + // printf("------------ %ld %ld\n", it - &*sample_vector.begin(), it_prev - + // it); + + auto test = ((long double)(it_prev - (&*sample_vector.begin())) + + (long double)(x - *it_prev) / (*it - *it_prev)) / + (long double)(sample_vector.size() - 1); + return test; +} + +unsigned long long max_value = 0, min_value = 0xfffffffff; +inline void store_into_vector(unsigned long long value) { + if (max_value < value) { + max_value = value; + } + if (min_value > value) { + min_value = value; + } + population_vector.push_back(value); +} + +inline long double safe_ceil(long double value) { + auto c = std::ceil(value); + return c == 0 ? 1 : c; +} + +typedef long double (*cdf_function_type)(long double); +typedef void (*init_function_type)(const std::vector<key_type> &); + +void process_function(const std::vector<key_type> &tmp, + cdf_function_type cdf_function, init_function_type init) { + sample_vector.clear(); + sample_vector.resize(SAMPLE_LENGTH); + + init(tmp); + + for (int scale = 2; scale < 9; scale++) { + const long split_size = TEST_LENGTH * scale; + result_storage.clear(); + result_storage.resize(scale * SAMPLE_LENGTH, false); + auto slice_size = 1.0 / (double)(split_size); + + // printf("\nscale: %d\n", scale); + for (size_t i = 0; i < TEST_LENGTH; i++) { + + auto index = + (int)safe_ceil(cdf_function(population_vector[i + SAMPLE_LENGTH]) / + slice_size) - + 1; + // printf("index: %d\n", index); + while (result_storage[index]) { + index++; + } + result_storage[index] = true; + } + for (auto &&element : result_storage) { + printf("%d", element ? 1 : 0); + } + puts(""); + } +} + +void process_function(const std::vector<key_type> &tmp, + cdf_function_type cdf_function) { + process_function(tmp, cdf_function, [](const std::vector<key_type> &tmp) { + sample_vector.assign(tmp.begin(), tmp.end()); + }); +} + +int main() { + FILE *file = fopen("normal_distribution.txt", "r"); + assert(file); + for (long long i; fscanf(file, "%lld ", &i) != EOF; store_into_vector(i)) + ; + fclose(file); + + std::vector<key_type> tmp(population_vector.begin(), + population_vector.begin() + SAMPLE_LENGTH - 2); + tmp.push_back(max_value); + tmp.push_back(min_value); + std::sort(tmp.begin(), tmp.end()); + + process_function(tmp, sample_cdf); + process_function( + tmp, sample_cdf_custom_version, [](const std::vector<key_type> &tmp_) { + for (size_t i = 0; i < SAMPLE_LENGTH; i++) { + sample_vector[calculate_location(i) - 1] = tmp_[i]; + auto location = calculate_location(i); + auto location2 = calculate_location_inverse(location - 1); + assert(location2 - 1 == i); + // printf("%zu %zu\n", location, location2); + } + }); +}
\ No newline at end of file |