summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--Makefile8
-rw-r--r--a3/.gitignore1
-rw-r--r--a3/Makefile4
-rw-r--r--a3/concurrency.cc224
4 files changed, 236 insertions, 1 deletions
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 <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";
+ }
+ }
+ }
+ }
+}