diff options
| -rw-r--r-- | Makefile | 8 | ||||
| -rw-r--r-- | a3/.gitignore | 1 | ||||
| -rw-r--r-- | a3/Makefile | 4 | ||||
| -rw-r--r-- | a3/concurrency.cc | 224 |
4 files changed, 236 insertions, 1 deletions
@@ -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 <chrono> +#include <vector> +#include <iostream> +#include <algorithm> +#include <string> +#include <thread> +#include <random> +#include <cstddef> +#include <algorithm> +#include <concepts> +#include <future> +#include <ranges> + +class Measure +{ +public: + Measure() + : start(std::chrono::high_resolution_clock::now()) + { + } + + ~Measure() + { + auto end = std::chrono::high_resolution_clock::now(); + std::chrono::duration<double> delta = end - start; + std::cout << " " << delta.count() * 1000 << " ms passed" << std::endl; + } + + std::chrono::time_point<std::chrono::high_resolution_clock> start{}; +}; + +template<typename Callable> +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<typename C, typename T> +// requires std::forward_iterator<Iter> + requires std:: ranges::input_range<C> +//std::vector<const T*> find_all(Iter begin, Iter end, const T& key) +std::vector<const T*> find_all(const C& c, const T& key) +{ + std::vector<const T*> res{}; + std::for_each(c.begin(), c.end(), + [&key, &res](const T& value) + { + if(value == key) + { + res.push_back(&value); + } + }); + return res; +} + +template<typename C, typename T> +//requires /*std::is_container<C> &&*/ std::is_same<C::value_type, T>::value + requires std:: ranges::input_range<C> +std::vector<const T*> find_all(const C& v, const T& key, std::size_t n) +{ + std::condition_variable cv; + bool run{false}; + + std::vector<const T*> 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::ptrdiff_t>(std::ceil(static_cast<float>(v.size()) / static_cast<float>(n))); + + std::vector<std::future<std::vector<const T*>>> 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<typename T> +std::vector<T> get_random_vector(std::size_t size, + T min = std::numeric_limits<T>::min(), + T max = std::numeric_limits<T>::max()) +{ + std::default_random_engine generator; + // Randomly generate T-values from the range [min; max] + std::uniform_int_distribution<T> distrib(min, max); + + std::vector<T> v; + v.resize(size); + for(auto& item : v) + { + item = distrib(generator); + } + + return v; +} + +std::vector<std::string> 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<char> distrib(min, max); + + std::vector<std::string> 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<int>(10'000'000, 0, 100); +// std::array<int, 10> 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"; + } + } + } + } +} |