From 6a8ae2de4261fecd0281685b9eea66bbd82bd7fb Mon Sep 17 00:00:00 2001 From: Bent Bisballe Nyeng Date: Tue, 1 Aug 2023 08:27:01 +0200 Subject: A4: WIP --- Makefile | 21 +++-- a4/Makefile | 4 + a4/exercise.tex | 25 +++++ a4/generator.h | 86 +++++++++++++++++ a4/list_vs_vector.cc | 262 +++++++++++++++++++++++++++++++++++++++++++++++++++ a4/octave.cc | 90 ++++++++++++++++++ a4/octave.h | 45 +++++++++ preamble.tex | 2 +- 8 files changed, 528 insertions(+), 7 deletions(-) create mode 100644 a4/Makefile create mode 100644 a4/exercise.tex create mode 100644 a4/generator.h create mode 100644 a4/list_vs_vector.cc create mode 100644 a4/octave.cc create mode 100644 a4/octave.h diff --git a/Makefile b/Makefile index a975039..3293304 100644 --- a/Makefile +++ b/Makefile @@ -1,29 +1,38 @@ PRE=au_BentBisballeNyeng_ -all: A3 Tour3_Log +all: A4 Tour3_Log A1: zip ${PRE}$@.zip a1/hello.cc zip ${PRE}$@.zip a1/hello-cpp20.cc zip ${PRE}$@.zip a1/Makefile - xelatex -halt-on-error -jobname=${PRE}$@ -auxdir=build a1/exercise.tex + xelatex -halt-on-error -jobname=${PRE}$@ a1/exercise.tex rm -f ${PRE}$@.aux ${PRE}$@.log A2: zip ${PRE}$@.zip a2/Makefile zip ${PRE}$@.zip a2/measurement.cc - xelatex -halt-on-error -jobname=${PRE}$@ -auxdir=build a2/exercise.tex + xelatex -halt-on-error -jobname=${PRE}$@ a2/exercise.tex rm -f ${PRE}$@.aux ${PRE}$@.log A3: zip ${PRE}$@.zip a3/Makefile zip ${PRE}$@.zip a3/concurrency.cc zip ${PRE}$@.zip a3/console.log - xelatex -halt-on-error -jobname=${PRE}$@ -auxdir=build a3/exercise.tex - xelatex -halt-on-error -jobname=${PRE}$@ -auxdir=build a3/exercise.tex + xelatex -halt-on-error -jobname=${PRE}$@ a3/exercise.tex + xelatex -halt-on-error -jobname=${PRE}$@ a3/exercise.tex + rm -f ${PRE}$@.aux ${PRE}$@.log + +A4: + zip ${PRE}$@.zip a4/Makefile + zip ${PRE}$@.zip a4/*.cc + zip ${PRE}$@.zip a4/*.h +# zip ${PRE}$@.zip a4/console.log + xelatex -halt-on-error -jobname=${PRE}$@ a4/exercise.tex + xelatex -halt-on-error -jobname=${PRE}$@ a4/exercise.tex rm -f ${PRE}$@.aux ${PRE}$@.log Tour3_Log: - xelatex -halt-on-error -jobname=${PRE}$@ -auxdir=build tour3_log/tour3_log.tex + xelatex -halt-on-error -jobname=${PRE}$@ tour3_log/tour3_log.tex rm -f ${PRE}$@.aux ${PRE}$@.log clean: diff --git a/a4/Makefile b/a4/Makefile new file mode 100644 index 0000000..dc61cde --- /dev/null +++ b/a4/Makefile @@ -0,0 +1,4 @@ +all: list_vs_vector + +list_vs_vector: list_vs_vector.cc Makefile octave.cc + g++ -fcoroutines -O2 -Wall -Werror -Wextra -Wconversion -std=c++20 octave.cc $< -o $@ diff --git a/a4/exercise.tex b/a4/exercise.tex new file mode 100644 index 0000000..11def5d --- /dev/null +++ b/a4/exercise.tex @@ -0,0 +1,25 @@ +\title{A4: List vs Vector} +\input{preamble.tex} + +I wanted to experiment with co-routine generator for the random +numbers but discovered the \texttt{std::generator} is not supported +for my compiler. +Instead I found what seemed like a similar implementation here: +\texttt{https://en.cppreference.com/w/cpp/language/coroutines}, which +I have copied to the \texttt{generator.h} file for use in my program. + +I am aware that the random number generator already kind-of works like +a co-routine generator seen from the outside, so the whole experiment +is a bit pointless from a software design perspective. + +\bigskip + +\begin{figure} + \includegraphics[scale=0.95]{a4/insert.pdf} +\end{figure} + +\begin{figure} + \includegraphics[scale=.95]{a4/remove.pdf} +\end{figure} + +\end{document} diff --git a/a4/generator.h b/a4/generator.h new file mode 100644 index 0000000..c857a40 --- /dev/null +++ b/a4/generator.h @@ -0,0 +1,86 @@ +// -*- c++ -*- +#pragma once + +// The code in this file has been taken directly from: +// https://en.cppreference.com/w/cpp/language/coroutines + +#include +#include +#include +#include + +template +struct Generator +{ + // The class name 'Generator' is our choice and it is not required for coroutine + // magic. Compiler recognizes coroutine by the presence of 'co_yield' keyword. + // You can use name 'MyGenerator' (or any other name) instead as long as you include + // nested struct promise_type with 'MyGenerator get_return_object()' method. + + struct promise_type; + using handle_type = std::coroutine_handle; + + struct promise_type // required + { + T value_; + std::exception_ptr exception_; + + Generator get_return_object() + { + return Generator(handle_type::from_promise(*this)); + } + std::suspend_always initial_suspend() { return {}; } + std::suspend_always final_suspend() noexcept { return {}; } + void unhandled_exception() { exception_ = std::current_exception(); } // saving + // exception + + template From> // C++20 concept + std::suspend_always yield_value(From&& from) + { + value_ = std::forward(from); // caching the result in promise + return {}; + } + void return_void() { } + }; + + handle_type h_; + + Generator(handle_type h) + : h_(h) + { + } + ~Generator() { h_.destroy(); } + explicit operator bool() + { + fill(); // The only way to reliably find out whether or not we finished coroutine, + // whether or not there is going to be a next value generated (co_yield) + // in coroutine via C++ getter (operator () below) is to execute/resume + // coroutine until the next co_yield point (or let it fall off end). + // Then we store/cache result in promise to allow getter (operator() below + // to grab it without executing coroutine). + return !h_.done(); + } + T operator()() + { + fill(); + full_ = false; // we are going to move out previously cached + // result to make promise empty again + return std::move(h_.promise().value_); + } + +private: + bool full_ = false; + + void fill() + { + if (!full_) + { + h_(); + if (h_.promise().exception_) + std::rethrow_exception(h_.promise().exception_); + // propagate coroutine exception in called context + + full_ = true; + } + } +}; diff --git a/a4/list_vs_vector.cc b/a4/list_vs_vector.cc new file mode 100644 index 0000000..1665e3e --- /dev/null +++ b/a4/list_vs_vector.cc @@ -0,0 +1,262 @@ +#include +#include +#include +#include +#include +#include +#include +#include + +#include "generator.h" +#include "octave.h" + +template +Generator get_random(int seed, + T min = std::numeric_limits::min(), + T max = std::numeric_limits::max()) +{ + std::default_random_engine generator(seed); + // Randomly generate T-values from the range [min; max] + std::uniform_int_distribution distrib(min, max); + + while(true) + { + co_yield distrib(generator); + } +} + +class Timer +{ +public: + void start() + { + _start = std::chrono::high_resolution_clock::now(); + } + + void stop() + { + _elapsed = std::chrono::high_resolution_clock::now() - _start; + std::cout << " took " << _elapsed.count() * 1000 << "ms\n"; + } + + double elapsed() const + { + return _elapsed.count() * 1000; // return number of milliseconds passed + } + +private: + std::chrono::time_point _start{}; + std::chrono::duration _elapsed{}; +}; + +class Measure +{ +public: + Measure(Timer& timer) + : timer(timer) + { + timer.start(); + } + + ~Measure() + { + timer.stop(); + } + +private: + Timer& timer; +}; + +template +void sorted_insert(C& container, T element) +{ + auto it = std::begin(container); + while(it != std::end(container) && *it < element) + { + ++it; + } + + container.insert(it, element); +} + +template +void remove_index(C& container, int index) +{ + auto it = std::begin(container); + for(int i = 0; i < index; ++i) + { + ++it; + } + + container.erase(it); +} + +int main() +{ + Timer timer; + Octave ins_oct("insert"); + ins_oct.setAxis("N", "time (ms)"); + + auto& ins_plot_v = ins_oct.add("std::vector"); + auto& ins_plot_l = ins_oct.add("std::list"); + auto& ins_plot_s = ins_oct.add("std::set"); + + Octave rem_oct("remove"); + rem_oct.setAxis("N", "time (ms)"); + + auto& rem_plot_v = rem_oct.add("std::vector"); + auto& rem_plot_l = rem_oct.add("std::list"); + auto& rem_plot_s = rem_oct.add("std::set"); + + constexpr std::size_t Ns[]{10, 50, 100, 200, 500, 1000, 5000, 10'000, 15'000, 20'000, 25'000}; + + for(auto N : Ns) + { + ins_plot_v.setX(double(N)); + ins_plot_l.setX(double(N)); + ins_plot_s.setX(double(N)); + + rem_plot_v.setX(double(N)); + rem_plot_l.setX(double(N)); + rem_plot_s.setX(double(N)); + + for(int i = 0; i < 3; ++i) + { + // Create N unique values in rnd vector: + std::vector rnd; + auto gen = get_random(i, 0, int(N) * 10); + while(rnd.size() < N) + { + auto r = gen(); + if(std::find(rnd.begin(), rnd.end(), r) == std::end(rnd)) + { + rnd.push_back(r); + } + } + + // Create vector of removal indices + std::vector rem; + { + std::default_random_engine generator(i); + for(int end = int(N) - 1; end >= 0; --end) + { + // Gradually decrease the range of valid removal indices + std::uniform_int_distribution distrib(0, end); + rem.push_back(distrib(generator)); + } + + if(N < 64) + { + std::cout << "rem:"; + for(auto i : rem) + { + std::cout << " " << i; + } + std::cout << '\n'; + } + } + + // std::vector experiment + { + std::vector vec; + std::cout << "std::vector insert (N=" + std::to_string(N) + "):\n"; + { + Measure _(timer); + for(auto r : rnd) + { + sorted_insert(vec, r); + } + } + ins_plot_v.add(timer.elapsed()); + + if(N < 64) + { + std::cout << "vec:"; + for(auto i : vec) + { + std::cout << " " << i; + } + std::cout << '\n'; + } + + std::cout << "std::vector remove (N=" + std::to_string(N) + "):\n"; + { + Measure _(timer); + for(auto r : rem) + { + remove_index(vec, r); + } + } + rem_plot_v.add(timer.elapsed()); + } + + // std::list experiment + { + std::list lst; + std::cout << "std::list insert (N=" + std::to_string(N) + "):\n"; + { + Measure _(timer); + for(auto r : rnd) + { + sorted_insert(lst, r); + } + } + ins_plot_l.add(timer.elapsed()); + + if(N < 64) + { + std::cout << "lst:"; + for(auto i : lst) + { + std::cout << " " << i; + } + std::cout << '\n'; + } + + std::cout << "std::list remove (N=" + std::to_string(N) + "):\n"; + { + Measure _(timer); + for(auto r : rem) + { + remove_index(lst, r); + } + } + rem_plot_l.add(timer.elapsed()); + } + + // std::set experiment + { + std::set set; + std::cout << "std::set insert (N=" + std::to_string(N) + "):\n"; + { + Measure _(timer); + for(auto r : rnd) + { + set.insert(r); + } + } + ins_plot_s.add(timer.elapsed()); + + if(N < 64) + { + std::cout << "set:"; + for(auto i : set) + { + std::cout << " " << i; + } + std::cout << '\n'; + } + + std::cout << "std::set remove (N=" + std::to_string(N) + "):\n"; + { + Measure _(timer); + for(auto r : rem) + { + remove_index(set, r); + } + } + rem_plot_s.add(timer.elapsed()); + } + } + } +} diff --git a/a4/octave.cc b/a4/octave.cc new file mode 100644 index 0000000..e48fe6c --- /dev/null +++ b/a4/octave.cc @@ -0,0 +1,90 @@ +#include "octave.h" + +const Plot& operator<<(std::ostream& out, const Plot& plot) +{ + out << "x = [ "; + for(const auto& [x,y] : plot.data) + { + out << x << " "; + } + out << "]\n"; + + out << "y = [ "; + for(const auto& [x,y] : plot.data) + { + out << y << " "; + } + out << "]\n"; + out << "scatter(x, y)\n"; + return plot; +} + +const std::string& Plot::getTitle() const +{ + return title; +} + +void Plot::add(const std::pair& point) +{ + data.push_back(point); +} + +void Plot::add(double y) +{ + if(y < 1000.0) + { + add({x, y}); + } +} + +void Plot::setX(double x) +{ + this->x = x; +} + +Octave::Octave(const std::string& file) + : out(file + ".m") + , file(file) +{ +} + +Octave::~Octave() +{ + if(!out.good()) + { + return; + } + + out << "fig = figure()\n"; + out << "hold on;\n"; + + for(const auto& plot : plots) + { + out << plot; + } + + out << "legend ({"; + for(const auto& plot : plots) + { + out << "'" << plot.getTitle() << "' " ; + } + out << "}, 'location', 'east');\n"; + out << "xlabel ('" << x_axis << "');\n"; + out << "ylabel ('" << y_axis << "');\n"; +// out << "set(gca, 'yscale', 'log')\n"; + out << "set(gcf, 'PaperPosition', [0 0 5 5])\n"; + out << "set(gcf, 'PaperSize', [5 5])\n"; + out << "print(fig, '" << file << ".pdf');\n"; +} + +Plot& Octave::add(const std::string& title) +{ + plots.push_back(title); + return plots.back(); +} + +void Octave::setAxis(const std::string& x_axis, const std::string& y_axis) +{ + this->x_axis = x_axis; + this->y_axis = y_axis; +} diff --git a/a4/octave.h b/a4/octave.h new file mode 100644 index 0000000..3c814c5 --- /dev/null +++ b/a4/octave.h @@ -0,0 +1,45 @@ +// -*- c++ -*- +#pragma once + +#include +#include +#include +#include +#include + +class Plot +{ +public: + Plot(const std::string& title) : title(title) {} + + const std::string& getTitle() const; + void add(const std::pair& point); + void add(double y); + void setX(double x); + + friend const Plot& operator<<(std::ostream& out, const Plot& plot); + +private: + std::vector> data; + std::string title; + double x{}; +}; + +class Octave +{ +public: + Octave(const std::string& file); + ~Octave(); + + Plot& add(const std::string& title); + void setAxis(const std::string& x_axis, const std::string& y_axis); + +private: + std::deque plots; + std::ofstream out; + + std::string x_axis; + std::string y_axis; + + std::string file; +}; diff --git a/preamble.tex b/preamble.tex index 8ab3a88..94ef2ba 100644 --- a/preamble.tex +++ b/preamble.tex @@ -8,6 +8,6 @@ \noindent\textit{This exercise is done one a stationary PC (ie. not laptop), 64-bit Intel i7 with 4 cores, each with hyper-threading enabled (8 hyper-threads in total) and 16GB RAM, running Gentoo - linux using gcc-11.2.} + linux using gcc-11.2. Optimization flags set to -O2} \bigskip -- cgit v1.2.3