A3: WIP

3 files changed, 229 insertions, 0 deletions

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";
+				}
+			}
+		}
+	}
+}