basedOpinionated utility library |
| git clone git://git.dimitrijedobrota.com/based.git |
| Log | Files | Refs | README | HACKING | CONTRIBUTING | CODE_OF_CONDUCT | BUILDING | |
instrumentation.hpp (6065B)
1 #pragma once 2 3 #include <algorithm> 4 #include <array> 5 #include <chrono> 6 #include <cmath> 7 #include <concepts> 8 #include <cstddef> 9 #include <cstdint> 10 #include <format> 11 #include <iostream> 12 #include <numbers> 13 #include <numeric> 14 #include <random> 15 #include <vector> 16 17 #include "based/enum.hpp" 18 19 namespace based 20 { 21 22 class table 23 { 24 public: 25 explicit table(std::size_t min_wth) 26 : m_min_wth(min_wth) 27 { 28 } 29 30 template<typename I> 31 void print_header(I first, I last) 32 { 33 while (first != last) { 34 std::cout << std::format("{:^{}} | ", *first, m_min_wth); 35 first++; 36 } 37 std::cout << '\n'; 38 } 39 40 template<typename I> 41 void print_row(I first, I last, std::size_t precision) 42 { 43 std::cout << std::format("{:{}} | ", *first++, m_min_wth); 44 while (first != last) { 45 std::cout << std::format("{:{}.{}f} | ", *first, m_min_wth, precision); 46 first++; 47 } 48 std::cout << '\n'; 49 } 50 51 private: 52 std::size_t m_min_wth; 53 }; 54 55 inline auto dont_normalize(double x, double /* n */) 56 { 57 return x; 58 } 59 60 inline auto normalize_n(double x, double n) 61 { 62 return x / n; 63 } 64 65 inline auto normalize_nlogn(double x, double n) 66 { 67 return x / (n * (std::log(n) / std::numbers::ln2)); 68 } 69 70 inline auto normalize_nlogn1(double x, double n) 71 { 72 return x / (n * std::log(n) - n); 73 } 74 75 struct instrumented_base 76 { 77 BASED_ENUM(op, 78 std::uint8_t, 79 n, 80 ctor_default, 81 ctor_value, 82 ctor_copy, 83 ctor_move, 84 asgn_copy, 85 asgn_move, 86 destructor, 87 equality, 88 comparison) 89 90 static constexpr std::array<const char*, op::size> names = { 91 "n", 92 "ctor_default", 93 "ctor_value", 94 "ctor_copy", 95 "ctor_move", 96 "asgn_copy", 97 "asgn_move", 98 "destructor", 99 "equality", 100 "comparison", 101 }; 102 103 static std::array<double, op::size> counts; 104 105 static constexpr auto op_num = op::size; 106 107 static void initialize(std::size_t size); 108 }; 109 110 template<typename T> 111 requires std::semiregular<T> 112 struct instrumented : instrumented_base 113 { 114 using value_type = T; 115 116 value_type value; 117 118 instrumented(const value_type& val) // NOLINT *-explicit-constructor 119 : value(std::move(val)) 120 { 121 ++counts[op::ctor_value]; 122 } 123 124 instrumented(value_type&& val) // NOLINT *-explicit-constructor 125 : value(std::move(val)) 126 { 127 ++counts[op::ctor_value]; 128 } 129 130 // Semiregular: 131 instrumented() { ++counts[op::ctor_default]; } 132 133 instrumented(const instrumented& val) 134 : value(val.value) 135 { 136 ++counts[op::ctor_copy]; 137 } 138 139 instrumented(instrumented&& val) noexcept 140 : value(std::move(val.value)) 141 { 142 ++counts[op::ctor_move]; 143 } 144 145 // self assign should be handled by the value_type 146 instrumented& operator=(const instrumented& val) // NOLINT cert-oop54-cpp 147 { 148 ++counts[op::asgn_copy]; 149 value = val.value; 150 return *this; 151 } 152 153 // self assign should be handled by the value_type 154 instrumented& operator=(instrumented&& val) noexcept // NOLINT cert-oop54-cpp 155 { 156 ++counts[op::asgn_move]; 157 value = std::move(val.value); 158 return *this; 159 } 160 161 ~instrumented() { ++counts[op::destructor]; } 162 163 // Regular 164 165 friend bool operator==(const instrumented& lhs, const instrumented& rhs) 166 { 167 ++counts[op::equality]; 168 return lhs.value == rhs.value; 169 } 170 171 friend bool operator!=(const instrumented& lhs, const instrumented& rhs) 172 { 173 return !(lhs == rhs); 174 } 175 176 // TotallyOrdered 177 178 friend bool operator<(const instrumented& lhs, const instrumented& rhs) 179 { 180 ++counts[op::comparison]; 181 return lhs.value < rhs.value; 182 } 183 184 friend bool operator>(const instrumented& lhs, const instrumented& rhs) 185 { 186 return rhs < lhs; 187 } 188 189 friend bool operator<=(const instrumented& lhs, const instrumented& rhs) 190 { 191 return !(rhs < lhs); 192 } 193 194 friend bool operator>=(const instrumented& lhs, const instrumented& rhs) 195 { 196 return !(lhs < rhs); 197 } 198 199 friend std::ostream& operator<<(std::ostream& ost, const instrumented& rhs) 200 { 201 return ost << rhs.value; 202 } 203 }; 204 205 template<typename Function> 206 void count_operations(size_t i, 207 size_t j, 208 Function fun, 209 double (*norm)(double, double) = dont_normalize) 210 { 211 using instrumented = based::instrumented<double>; 212 213 constexpr size_t cols = instrumented::op_num; 214 const size_t decimals((norm == dont_normalize) ? 0 : 2); 215 216 std::array<double, cols> values = {0}; 217 218 table tbl(12); 219 tbl.print_header(std::begin(instrumented::names), 220 std::end(instrumented::names)); 221 222 std::mt19937 rng(0); // NOLINT cert-msc32-c cert-msc51-cpp 223 while (i <= j) { 224 std::vector<instrumented> vec(i); 225 std::iota(std::begin(vec), std::end(vec), 0.0); 226 std::shuffle(std::begin(vec), std::end(vec), rng); 227 228 instrumented::initialize(i); 229 fun(std::begin(vec), std::end(vec)); 230 231 const auto dbl = static_cast<double>(i); 232 233 values[0] = dbl; 234 for (size_t k = 1; k < cols; ++k) { 235 values[k] = norm(instrumented::counts[k], dbl); 236 } 237 238 tbl.print_row(std::begin(values), std::end(values), decimals); 239 240 i <<= 1U; 241 } 242 } 243 244 class timer 245 { 246 public: 247 using clock_t = std::chrono::high_resolution_clock; 248 using duration_t = std::chrono::microseconds; 249 250 timer() 251 : m_startp(clock_t::now()) 252 { 253 } 254 255 timer(const timer&) = delete; 256 timer(timer&&) = delete; 257 timer& operator=(const timer&) = delete; 258 timer& operator=(timer&&) = delete; 259 260 ~timer() 261 { 262 stop(); 263 std::cout << std::flush; 264 } 265 266 void stop() 267 { 268 static const auto count = [](const auto& time) 269 { 270 return std::chrono::time_point_cast<duration_t>(time) 271 .time_since_epoch() 272 .count(); 273 }; 274 275 const auto endp = clock_t::now(); 276 277 const auto start = count(m_startp); 278 const auto end = count(endp); 279 280 const auto duration = end - start; 281 const auto ms = static_cast<double>(duration) * 0.001; 282 283 std::cout << std::format("{}us ({}ms)\n", duration, ms); 284 } 285 286 private: 287 std::chrono::time_point<clock_t> m_startp; 288 }; 289 290 } // namespace based