diff options
| -rw-r--r-- | CMakeLists.txt | 22 | ||||
| -rw-r--r-- | headers/arena.cu | 4 | ||||
| -rw-r--r-- | headers/arena.cuh | 6 | ||||
| -rw-r--r-- | headers/arena_test.cu | 52 | ||||
| -rw-r--r-- | headers/random.h | 57 | ||||
| -rw-r--r-- | tests/arena.cu | 108 |
6 files changed, 132 insertions, 117 deletions
diff --git a/CMakeLists.txt b/CMakeLists.txt index d004e93..c5bbf68 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -3,9 +3,27 @@ project(cleveldb CUDA) set(CMAKE_CUDA_STANDARD 14) -add_executable(cleveldb main.cu headers/arena.cu headers/arena.cuh) +include(GNUInstallDirs) + +add_library(cleveldb "") + +target_sources( + cleveldb + PUBLIC + "headers/arena.cu" + "headers/arena.cuh" + "headers/random.h" +) + +add_executable(arena_test "") +target_sources(arena_test + PRIVATE + "headers/arena_test.cu") +target_link_libraries(arena_test cleveldb) +add_test(arena_test "arena_test" COMMAND "arena_test") + +add_executable(clevelmain main.cu cleveldb) -add_executable(arena_test tests/arena.cu headers/arena.cu headers/arena.cuh) set_target_properties(cleveldb PROPERTIES CUDA_SEPARABLE_COMPILATION ON) diff --git a/headers/arena.cu b/headers/arena.cu index 7f5de7a..fe316f2 100644 --- a/headers/arena.cu +++ b/headers/arena.cu @@ -1,7 +1,3 @@ -// -// Created by user on 20/10/2021. -// - #include "arena.cuh" namespace cleveldb { diff --git a/headers/arena.cuh b/headers/arena.cuh index 20da470..5f8d1c7 100644 --- a/headers/arena.cuh +++ b/headers/arena.cuh @@ -2,8 +2,8 @@ // Created by user on 20/10/2021. // -#ifndef CLEVELDB_ARENA_CUH -#define CLEVELDB_ARENA_CUH +#ifndef CLEVELDB_ARENA_TEST_CUH +#define CLEVELDB_ARENA_TEST_CUH #include <atomic> @@ -65,4 +65,4 @@ inline char* Arena::Allocate(size_t bytes) { } // namespace cleveldb -#endif //CLEVELDB_ARENA_CUH +#endif //CLEVELDB_ARENA_TEST_CUH diff --git a/headers/arena_test.cu b/headers/arena_test.cu new file mode 100644 index 0000000..68fc8ff --- /dev/null +++ b/headers/arena_test.cu @@ -0,0 +1,52 @@ +#include "arena.cuh" +#include "random.h" + +using namespace cleveldb; + +int main() { + std::vector<std::pair<size_t, char*>> allocated; + Arena arena; + const int N = 100000; + size_t bytes = 0; + Random rnd(301); + for (int i = 0; i < N; i++) { + size_t s; + if (i % (N / 10) == 0) { + s = i; + } else { + s = rnd.OneIn(4000) + ? rnd.Uniform(6000) + : (rnd.OneIn(10) ? rnd.Uniform(100) : rnd.Uniform(20)); + } + if (s == 0) { + // Our arena disallows size 0 allocations. + s = 1; + } + char* r; + if (rnd.OneIn(10)) { + r = arena.AllocateAligned(s); + } else { + r = arena.Allocate(s); + } + + for (size_t b = 0; b < s; b++) { + // Fill the "i"th allocation with a known bit pattern + r[b] = i % 256; + } + bytes += s; + allocated.push_back(std::make_pair(s, r)); + assert(arena.MemoryUsage() >= bytes); + if (i > N / 10) { + assert(arena.MemoryUsage() <= bytes * 1.10); + } + } + for (size_t i = 0; i < allocated.size(); i++) { + size_t num_bytes = allocated[i].first; + const char* p = allocated[i].second; + for (size_t b = 0; b < num_bytes; b++) { + // Check the "i"th allocation for the known bit pattern + assert((int(p[b]) & 0xff) == (i % 256)); + } + } + return 0; +} diff --git a/headers/random.h b/headers/random.h new file mode 100644 index 0000000..2b04757 --- /dev/null +++ b/headers/random.h @@ -0,0 +1,57 @@ +#ifndef CLEVELDB_RANDOM_H +#define CLEVELDB_RANDOM_H +#include <cstdint> + +namespace cleveldb { + +// A very simple random number generator. Not especially good at +// generating truly random bits, but good enough for our needs in this +// package. + class Random { + private: + uint32_t seed_; + + public: + explicit Random(uint32_t s) : seed_(s & 0x7fffffffu) { + // Avoid bad seeds. + if (seed_ == 0 || seed_ == 2147483647L) { + seed_ = 1; + } + } + uint32_t Next() { + static const uint32_t M = 2147483647L; // 2^31-1 + static const uint64_t A = 16807; // bits 14, 8, 7, 5, 2, 1, 0 + // We are computing + // seed_ = (seed_ * A) % M, where M = 2^31-1 + // + // seed_ must not be zero or M, or else all subsequent computed values + // will be zero or M respectively. For all other values, seed_ will end + // up cycling through every number in [1,M-1] + uint64_t product = seed_ * A; + + // Compute (product % M) using the fact that ((x << 31) % M) == x. + seed_ = static_cast<uint32_t>((product >> 31) + (product & M)); + // The first reduction may overflow by 1 bit, so we may need to + // repeat. mod == M is not possible; using > allows the faster + // sign-bit-based test. + if (seed_ > M) { + seed_ -= M; + } + return seed_; + } + // Returns a uniformly distributed value in the range [0..n-1] + // REQUIRES: n > 0 + uint32_t Uniform(int n) { return Next() % n; } + + // Randomly returns true ~"1/n" of the time, and false otherwise. + // REQUIRES: n > 0 + bool OneIn(int n) { return (Next() % n) == 0; } + + // Skewed: pick "base" uniformly from range [0,max_log] and then + // return "base" random bits. The effect is to pick a number in the + // range [0,2^max_log-1] with exponential bias towards smaller numbers. + uint32_t Skewed(int max_log) { return Uniform(1 << Uniform(max_log + 1)); } + }; + +} // namespace cleveldb +#endif //CLEVELDB_RANDOM_H diff --git a/tests/arena.cu b/tests/arena.cu deleted file mode 100644 index f7a4ddc..0000000 --- a/tests/arena.cu +++ /dev/null @@ -1,108 +0,0 @@ -#include <iostream> - -#include "../headers/arena.cuh" - - -using namespace cleveldb; - -#include <cstdint> - - -// A very simple random number generator. Not especially good at -// generating truly random bits, but good enough for our needs in this -// package. -class Random { -private: - uint32_t seed_; - -public: - explicit Random(uint32_t s) : seed_(s & 0x7fffffffu) { - // Avoid bad seeds. - if (seed_ == 0 || seed_ == 2147483647L) { - seed_ = 1; - } - } - uint32_t Next() { - static const uint32_t M = 2147483647L; // 2^31-1 - static const uint64_t A = 16807; // bits 14, 8, 7, 5, 2, 1, 0 - // We are computing - // seed_ = (seed_ * A) % M, where M = 2^31-1 - // - // seed_ must not be zero or M, or else all subsequent computed values - // will be zero or M respectively. For all other values, seed_ will end - // up cycling through every number in [1,M-1] - uint64_t product = seed_ * A; - - // Compute (product % M) using the fact that ((x << 31) % M) == x. - seed_ = static_cast<uint32_t>((product >> 31) + (product & M)); - // The first reduction may overflow by 1 bit, so we may need to - // repeat. mod == M is not possible; using > allows the faster - // sign-bit-based test. - if (seed_ > M) { - seed_ -= M; - } - return seed_; - } - // Returns a uniformly distributed value in the range [0..n-1] - // REQUIRES: n > 0 - uint32_t Uniform(int n) { return Next() % n; } - - // Randomly returns true ~"1/n" of the time, and false otherwise. - // REQUIRES: n > 0 - bool OneIn(int n) { return (Next() % n) == 0; } - - // Skewed: pick "base" uniformly from range [0,max_log] and then - // return "base" random bits. The effect is to pick a number in the - // range [0,2^max_log-1] with exponential bias towards smaller numbers. - uint32_t Skewed(int max_log) { return Uniform(1 << Uniform(max_log + 1)); } -}; - - - -int main() { - std::vector<std::pair<size_t, char*>> allocated; - Arena arena; - const int N = 100000; - size_t bytes = 0; - Random rnd(301); - for (int i = 0; i < N; i++) { - size_t s; - if (i % (N / 10) == 0) { - s = i; - } else { - s = rnd.OneIn(4000) - ? rnd.Uniform(6000) - : (rnd.OneIn(10) ? rnd.Uniform(100) : rnd.Uniform(20)); - } - if (s == 0) { - // Our arena disallows size 0 allocations. - s = 1; - } - char* r; - if (rnd.OneIn(10)) { - r = arena.AllocateAligned(s); - } else { - r = arena.Allocate(s); - } - - for (size_t b = 0; b < s; b++) { - // Fill the "i"th allocation with a known bit pattern - r[b] = i % 256; - } - bytes += s; - allocated.push_back(std::make_pair(s, r)); - assert(arena.MemoryUsage() >= bytes); - if (i > N / 10) { - assert(arena.MemoryUsage() <= bytes * 1.10); - } - } - for (size_t i = 0; i < allocated.size(); i++) { - size_t num_bytes = allocated[i].first; - const char* p = allocated[i].second; - for (size_t b = 0; b < num_bytes; b++) { - // Check the "i"th allocation for the known bit pattern - assert((int(p[b]) & 0xff) == (i % 256)); - } - } - return 0; -} |