From b91be737efcfed6ed5bebbe07d03527aa878f963 Mon Sep 17 00:00:00 2001 From: Bent Bisballe Nyeng Date: Thu, 27 Jul 2023 16:47:22 +0200 Subject: A3: WIP --- Makefile | 8 +- a3/.gitignore | 1 + a3/Makefile | 4 + a3/concurrency.cc | 224 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 236 insertions(+), 1 deletion(-) create mode 100644 a3/.gitignore create mode 100644 a3/Makefile create mode 100644 a3/concurrency.cc diff --git a/Makefile b/Makefile index b53744e..17776c9 100644 --- a/Makefile +++ b/Makefile @@ -1,5 +1,5 @@ PRE=au_BentBisballeNyeng_ -all: A2 Tour3_Log +all: A3 Tour3_Log A1: zip ${PRE}$@.zip a1/hello.cc @@ -14,6 +14,12 @@ A2: xelatex -halt-on-error -jobname=${PRE}$@ -auxdir=build a2/exercise.tex rm -f ${PRE}$@.aux ${PRE}$@.log +A3: + zip ${PRE}$@.zip a3/Makefile + zip ${PRE}$@.zip a3/concurrency.cc + xelatex -halt-on-error -jobname=${PRE}$@ -auxdir=build a3/exercise.tex + rm -f ${PRE}$@.aux ${PRE}$@.log + Tour3_Log: xelatex -halt-on-error -jobname=${PRE}$@ -auxdir=build tour3_log/tour3_log.tex rm -f ${PRE}$@.aux ${PRE}$@.log diff --git a/a3/.gitignore b/a3/.gitignore new file mode 100644 index 0000000..cc89412 --- /dev/null +++ b/a3/.gitignore @@ -0,0 +1 @@ +concurrency \ No newline at end of file diff --git a/a3/Makefile b/a3/Makefile new file mode 100644 index 0000000..1de80ba --- /dev/null +++ b/a3/Makefile @@ -0,0 +1,4 @@ +all: concurrency + +concurrency: concurrency.cc Makefile + g++ -Wall -Werror -Wextra -Wconversion -std=c++20 -pthread $< -o $@ diff --git a/a3/concurrency.cc b/a3/concurrency.cc new file mode 100644 index 0000000..da7b51e --- /dev/null +++ b/a3/concurrency.cc @@ -0,0 +1,224 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +class Measure +{ +public: + Measure() + : start(std::chrono::high_resolution_clock::now()) + { + } + + ~Measure() + { + auto end = std::chrono::high_resolution_clock::now(); + std::chrono::duration delta = end - start; + std::cout << " " << delta.count() * 1000 << " ms passed" << std::endl; + } + + std::chrono::time_point start{}; +}; + +template +void measure(const std::string& text, Callable c) +{ + std::cout << text << ":\n"; + + for(int i = 0; i < 3; ++i) + { // RAII timed scoped + Measure m; + c(); + } +} + +template +// requires std::forward_iterator + requires std:: ranges::input_range +//std::vector find_all(Iter begin, Iter end, const T& key) +std::vector find_all(const C& c, const T& key) +{ + std::vector res{}; + std::for_each(c.begin(), c.end(), + [&key, &res](const T& value) + { + if(value == key) + { + res.push_back(&value); + } + }); + return res; +} + +template +//requires /*std::is_container &&*/ std::is_same::value + requires std:: ranges::input_range +std::vector find_all(const C& v, const T& key, std::size_t n) +{ + std::condition_variable cv; + bool run{false}; + + std::vector res{}; + + // Calculate the chunk size needed for splitting the values into + // (at most) n portions and at least 1 big portion. + std::ptrdiff_t chunk_size = + static_cast(std::ceil(static_cast(v.size()) / static_cast(n))); + + std::vector>> futures; + + auto begin = v.begin(); + auto end = v.end(); + while(begin < v.end()) + { + end = begin + chunk_size; + if(end > v.end()) + { + end = v.end(); + } + // create suspended thread for searching on [begin, end[ range + futures.emplace_back(std::async(std::launch::async, + [&key, &cv, &run, begin, end]() + { + std::mutex m; + std::unique_lock lk(m); + cv.wait(lk, [&run](){ return run; }); + return find_all(std::ranges::subrange(begin, end), key); + })); + begin = end; + } + + { + Measure meas; + + // Signal all threads to run + run = true; + cv.notify_all(); + + // Get and append the result from each thread into accumulated results + // vector + for(auto& future : futures) + { + auto v = future.get(); + res.insert(res.end(), v.begin(), v.end()); + } + } + + return res; +} + +template +std::vector get_random_vector(std::size_t size, + T min = std::numeric_limits::min(), + T max = std::numeric_limits::max()) +{ + std::default_random_engine generator; + // Randomly generate T-values from the range [min; max] + std::uniform_int_distribution distrib(min, max); + + std::vector v; + v.resize(size); + for(auto& item : v) + { + item = distrib(generator); + } + + return v; +} + +std::vector get_random_strings(std::size_t size, + std::size_t length, + char min, char max) +{ + std::default_random_engine generator; + // Randomly generate T-values from the range [min; max] + std::uniform_int_distribution distrib(min, max); + + std::vector v; + v.resize(size); + for(auto& str : v) + { + str.reserve(length); + for(auto i = 0u; i < str.capacity(); ++i) + { + str += distrib(generator); + } + } + + return v; +} + +int main() +{ + { + auto v = get_random_vector(10'000'000, 0, 100); +// std::array v{1,2,42,4,5,6,7,8,42,10}; // - this also works +// int v[] = {1,2,42,4,5,6,7,8,42,10}; // - doesn't seem to work :-( + + // 42 is expected to be in the vector in ~1/100th of the indices + int needle{42}; + std::size_t found_items{}; + { // non-threaded + measure("Single threaded search for int", + [&]() + { + auto res = find_all(v, needle); + found_items = res.size(); // consider this the 'truth" + }); + } + + for(auto num_threads = 1u; num_threads < 17u; ++num_threads) + { + std::cout << "Multi threaded (" << num_threads << ") search for int:\n"; + for(int i = 0; i < 3; ++i) + { + auto res = find_all(v, needle, num_threads); + if(res.size() != found_items) + { + std::cout << "That was unexpected!\n"; + } + } + } + } + + { + auto v = get_random_strings(10'000'000, 20, 'a', 'z'); + + // Pick middle string as needle so we get one match: + std::string needle{v[v.size() / 2]}; + + { // non-threaded + measure("Single threaded search for string", + [&]() + { + auto res = find_all(v, needle); + if(res.size() != 1) + { + std::cout << "That was unexpected!\n"; + } + }); + } + + for(auto num_threads = 1u; num_threads < 17u; ++num_threads) + { + std::cout << "Multi threaded (" << num_threads << ") search for string:\n"; + for(int i = 0; i < 3; ++i) + { + auto res = find_all(v, needle, num_threads); + if(res.size() != 1) + { + std::cout << "That was unexpected!\n"; + } + } + } + } +} -- cgit v1.2.3