Line data Source code
1 : #include "benchmark_suite.h"
2 :
3 : #include "core/memory_manager.h"
4 : #include "core/timer.h"
5 : #include "stats_analyzer.h"
6 : #include "structures/dynamic_array.h"
7 : #include "structures/hash_map.h"
8 : #include "structures/linked_list.h"
9 :
10 : #include <algorithm>
11 : #include <cstdio>
12 : #include <fstream>
13 : #include <iostream>
14 : #include <map>
15 : #include <optional>
16 : #include <random>
17 : #include <sstream>
18 :
19 : #ifdef __linux__
20 : #include <sched.h>
21 : #elif defined(_WIN32)
22 : #include <windows.h>
23 : #endif
24 :
25 : namespace hashbrowns {
26 :
27 : // Forward declarations for serialization helpers defined in benchmark_io.cpp.
28 : void write_results_csv_impl(const std::string& path, const std::vector<BenchmarkResult>& results,
29 : const BenchmarkConfig& cfg, unsigned long long actual_seed);
30 : void write_results_json_impl(const std::string& path, const std::vector<BenchmarkResult>& results,
31 : const BenchmarkConfig& config, unsigned long long actual_seed);
32 :
33 : // ---------------------------------------------------------------------------
34 : // CPU affinity / turbo helpers (used only by run())
35 : // ---------------------------------------------------------------------------
36 :
37 0 : [[maybe_unused]] static bool set_cpu_affinity(int cpu_index) {
38 : #ifdef __linux__
39 0 : cpu_set_t set;
40 0 : CPU_ZERO(&set);
41 0 : CPU_SET(cpu_index, &set);
42 0 : return sched_setaffinity(0, sizeof(set), &set) == 0;
43 : #elif defined(_WIN32)
44 : DWORD_PTR mask = (cpu_index >= 0 && cpu_index < (int)(8 * sizeof(DWORD_PTR))) ? (DWORD_PTR(1) << cpu_index) : 1;
45 : HANDLE h = GetCurrentThread();
46 : return SetThreadAffinityMask(h, mask) != 0;
47 : #else
48 : (void)cpu_index;
49 : return false;
50 : #endif
51 : }
52 :
53 : #ifdef __linux__
54 0 : [[maybe_unused]] static bool disable_turbo_linux() {
55 0 : std::ofstream turbo("/sys/devices/system/cpu/intel_pstate/no_turbo");
56 0 : if (turbo) {
57 0 : turbo << "1";
58 0 : return true;
59 : }
60 0 : std::ofstream turbo2("/sys/devices/system/cpu/cpufreq/boost");
61 0 : if (turbo2) {
62 0 : turbo2 << "0";
63 0 : return true;
64 : }
65 0 : return false;
66 0 : }
67 : #else
68 : [[maybe_unused]] static bool disable_turbo_linux() {
69 : return false;
70 : }
71 : #endif
72 :
73 : // ---------------------------------------------------------------------------
74 : // Structure factory
75 : // ---------------------------------------------------------------------------
76 :
77 67 : static DataStructurePtr make_structure(const std::string& name, const BenchmarkConfig& cfg) {
78 67 : if (name == "array" || name == "dynamic-array") {
79 30 : return std::make_unique<DynamicArray<std::pair<int, std::string>>>();
80 37 : } else if (name == "slist" || name == "list" || name == "singly-list") {
81 13 : return std::make_unique<SinglyLinkedList<std::pair<int, std::string>>>();
82 24 : } else if (name == "dlist" || name == "doubly-list") {
83 3 : return std::make_unique<DoublyLinkedList<std::pair<int, std::string>>>();
84 21 : } else if (name == "hashmap" || name == "hash-map") {
85 20 : std::size_t cap = cfg.hash_initial_capacity.value_or(16);
86 20 : auto hm = std::make_unique<HashMap>(cfg.hash_strategy, cap);
87 20 : if (cfg.hash_max_load_factor)
88 4 : hm->set_max_load_factor(*cfg.hash_max_load_factor);
89 20 : return hm;
90 20 : }
91 1 : return nullptr;
92 : }
93 :
94 : // ---------------------------------------------------------------------------
95 : // BenchmarkSuite::run
96 : // ---------------------------------------------------------------------------
97 :
98 12 : std::vector<BenchmarkResult> BenchmarkSuite::run(const BenchmarkConfig& config) {
99 12 : std::vector<BenchmarkResult> out_results;
100 12 : if (config.structures.empty())
101 0 : return out_results;
102 :
103 : // RNG setup for RANDOM/MIXED patterns
104 12 : std::mt19937_64 rng;
105 12 : unsigned long long actual_seed = 0ULL;
106 12 : if (config.pattern != BenchmarkConfig::Pattern::SEQUENTIAL) {
107 2 : if (config.seed.has_value()) {
108 2 : actual_seed = *config.seed;
109 2 : rng.seed(actual_seed);
110 : } else {
111 0 : std::random_device rd;
112 0 : actual_seed = ((uint64_t)rd() << 32) ^ rd();
113 0 : rng.seed(actual_seed);
114 0 : }
115 : }
116 :
117 29 : for (const auto& name : config.structures) {
118 17 : auto ds = make_structure(name, config);
119 17 : if (!ds) {
120 1 : std::cerr << "Unknown structure: " << name << "\n";
121 1 : continue;
122 : }
123 :
124 16 : std::vector<double> insert_ms, search_ms, remove_ms;
125 16 : std::vector<double> mem_ins, mem_sea, mem_rem;
126 16 : std::vector<double> probes_ins, probes_sea, probes_rem;
127 16 : insert_ms.reserve(config.runs);
128 16 : search_ms.reserve(config.runs);
129 16 : remove_ms.reserve(config.runs);
130 16 : mem_ins.reserve(config.runs);
131 16 : mem_sea.reserve(config.runs);
132 16 : mem_rem.reserve(config.runs);
133 :
134 : // Warm-up runs (discarded from aggregation)
135 20 : for (int w = 0; w < config.warmup_runs; ++w) {
136 4 : auto warm = make_structure(name, config);
137 12 : std::vector<int> keys(config.size);
138 198 : for (std::size_t i = 0; i < config.size; ++i)
139 194 : keys[i] = static_cast<int>(i);
140 4 : std::vector<int> ins_keys = keys, sea_keys = keys, rem_keys = keys;
141 4 : if (config.pattern == BenchmarkConfig::Pattern::RANDOM) {
142 2 : std::shuffle(ins_keys.begin(), ins_keys.end(), rng);
143 2 : sea_keys = ins_keys;
144 2 : std::shuffle(rem_keys.begin(), rem_keys.end(), rng);
145 2 : } else if (config.pattern == BenchmarkConfig::Pattern::MIXED) {
146 1 : std::shuffle(ins_keys.begin(), ins_keys.end(), rng);
147 1 : std::shuffle(rem_keys.begin(), rem_keys.end(), rng);
148 : }
149 4 : std::string v;
150 198 : for (auto k : ins_keys)
151 194 : warm->insert(k, std::to_string(k));
152 198 : for (auto k : sea_keys)
153 194 : warm->search(k, v);
154 198 : for (auto k : rem_keys)
155 194 : warm->remove(k);
156 4 : }
157 :
158 46 : for (int r = 0; r < config.runs; ++r) {
159 30 : ds = make_structure(name, config);
160 :
161 90 : std::vector<int> keys(config.size);
162 1082 : for (std::size_t i = 0; i < config.size; ++i)
163 1052 : keys[i] = static_cast<int>(i);
164 30 : std::vector<int> ins_keys = keys;
165 30 : std::vector<int> sea_keys = keys;
166 30 : std::vector<int> rem_keys = keys;
167 30 : if (config.pattern == BenchmarkConfig::Pattern::RANDOM) {
168 4 : std::shuffle(ins_keys.begin(), ins_keys.end(), rng);
169 4 : sea_keys = ins_keys;
170 4 : std::shuffle(rem_keys.begin(), rem_keys.end(), rng);
171 26 : } else if (config.pattern == BenchmarkConfig::Pattern::MIXED) {
172 2 : std::shuffle(ins_keys.begin(), ins_keys.end(), rng);
173 2 : std::shuffle(rem_keys.begin(), rem_keys.end(), rng);
174 : }
175 :
176 : // Insert
177 30 : MemoryTracker::instance().reset();
178 30 : auto mem_before = MemoryTracker::instance().get_stats().current_usage;
179 30 : Timer t;
180 30 : t.start();
181 30 : if (name == "hashmap" || name == "hash-map") {
182 9 : if (auto hm = dynamic_cast<HashMap*>(ds.get()))
183 9 : hm->metrics_reset();
184 : }
185 1082 : for (auto k : ins_keys)
186 1052 : ds->insert(k, std::to_string(k));
187 30 : auto ins_us = t.stop().count();
188 30 : insert_ms.push_back(ins_us / 1000.0);
189 30 : auto mem_after_insert = MemoryTracker::instance().get_stats().current_usage;
190 30 : mem_ins.push_back(static_cast<double>(mem_after_insert - mem_before));
191 30 : if (name == "hashmap" || name == "hash-map") {
192 9 : if (auto hm = dynamic_cast<HashMap*>(ds.get()))
193 9 : probes_ins.push_back(hm->avg_insert_probes());
194 : }
195 :
196 : // Search
197 30 : t.start();
198 30 : std::string v;
199 30 : if (name == "hashmap" || name == "hash-map") {
200 9 : if (auto hm = dynamic_cast<HashMap*>(ds.get()))
201 9 : hm->metrics_reset();
202 : }
203 1082 : for (auto k : sea_keys) {
204 1052 : bool found = ds->search(k, v);
205 1052 : if (!found) { /* ensure no UB in opt build */
206 : }
207 : }
208 30 : auto sea_us = t.stop().count();
209 30 : search_ms.push_back(sea_us / 1000.0);
210 30 : auto mem_after_search = MemoryTracker::instance().get_stats().current_usage;
211 30 : mem_sea.push_back(static_cast<double>(mem_after_search - mem_after_insert));
212 30 : if (name == "hashmap" || name == "hash-map") {
213 9 : if (auto hm = dynamic_cast<HashMap*>(ds.get()))
214 9 : probes_sea.push_back(hm->avg_search_probes());
215 : }
216 :
217 : // Remove
218 30 : t.start();
219 30 : if (name == "hashmap" || name == "hash-map") {
220 9 : if (auto hm = dynamic_cast<HashMap*>(ds.get()))
221 9 : hm->metrics_reset();
222 : }
223 1082 : for (auto k : rem_keys)
224 1052 : ds->remove(k);
225 30 : auto rem_us = t.stop().count();
226 30 : remove_ms.push_back(rem_us / 1000.0);
227 30 : auto mem_after_remove = MemoryTracker::instance().get_stats().current_usage;
228 30 : mem_rem.push_back(static_cast<double>(mem_after_remove - mem_after_search));
229 30 : if (name == "hashmap" || name == "hash-map") {
230 9 : if (auto hm = dynamic_cast<HashMap*>(ds.get()))
231 9 : probes_rem.push_back(hm->avg_remove_probes());
232 : }
233 30 : }
234 :
235 16 : auto ins = summarize(insert_ms, config.bootstrap_iters);
236 16 : auto sea = summarize(search_ms, config.bootstrap_iters);
237 16 : auto rem = summarize(remove_ms, config.bootstrap_iters);
238 16 : auto mins = summarize(mem_ins);
239 16 : auto msea = summarize(mem_sea);
240 16 : auto mrem = summarize(mem_rem);
241 :
242 : // Fresh instance to estimate memory footprint after inserts
243 16 : auto mem_ds = make_structure(name, config);
244 584 : for (std::size_t i = 0; i < config.size; ++i)
245 568 : mem_ds->insert(static_cast<int>(i), std::to_string(i));
246 :
247 16 : BenchmarkResult br;
248 16 : br.structure = name;
249 16 : br.insert_ms_mean = ins.mean;
250 16 : br.insert_ms_stddev = ins.stddev;
251 16 : br.insert_ms_median = ins.median;
252 16 : br.insert_ms_p95 = ins.p95;
253 16 : br.insert_ci_low = ins.ci_low;
254 16 : br.insert_ci_high = ins.ci_high;
255 16 : br.search_ms_mean = sea.mean;
256 16 : br.search_ms_stddev = sea.stddev;
257 16 : br.search_ms_median = sea.median;
258 16 : br.search_ms_p95 = sea.p95;
259 16 : br.search_ci_low = sea.ci_low;
260 16 : br.search_ci_high = sea.ci_high;
261 16 : br.remove_ms_mean = rem.mean;
262 16 : br.remove_ms_stddev = rem.stddev;
263 16 : br.remove_ms_median = rem.median;
264 16 : br.remove_ms_p95 = rem.p95;
265 16 : br.remove_ci_low = rem.ci_low;
266 16 : br.remove_ci_high = rem.ci_high;
267 16 : br.memory_bytes = mem_ds->memory_usage();
268 16 : br.memory_insert_bytes_mean = mins.mean;
269 16 : br.memory_insert_bytes_stddev = mins.stddev;
270 16 : br.memory_search_bytes_mean = msea.mean;
271 16 : br.memory_search_bytes_stddev = msea.stddev;
272 16 : br.memory_remove_bytes_mean = mrem.mean;
273 16 : br.memory_remove_bytes_stddev = mrem.stddev;
274 :
275 16 : if (!probes_ins.empty()) {
276 5 : auto s = summarize(probes_ins);
277 5 : br.insert_probes_mean = s.mean;
278 5 : br.insert_probes_stddev = s.stddev;
279 : }
280 16 : if (!probes_sea.empty()) {
281 5 : auto s = summarize(probes_sea);
282 5 : br.search_probes_mean = s.mean;
283 5 : br.search_probes_stddev = s.stddev;
284 : }
285 16 : if (!probes_rem.empty()) {
286 5 : auto s = summarize(probes_rem);
287 5 : br.remove_probes_mean = s.mean;
288 5 : br.remove_probes_stddev = s.stddev;
289 : }
290 16 : out_results.push_back(br);
291 17 : }
292 :
293 12 : if (config.csv_output) {
294 2 : if (config.output_format == BenchmarkConfig::OutputFormat::CSV)
295 1 : write_results_csv_impl(*config.csv_output, out_results, config, actual_seed);
296 : else
297 1 : write_results_json_impl(*config.csv_output, out_results, config, actual_seed);
298 : }
299 12 : return out_results;
300 0 : }
301 :
302 : // ---------------------------------------------------------------------------
303 : // BenchmarkSuite::run_series
304 : // ---------------------------------------------------------------------------
305 :
306 1 : BenchmarkSuite::Series BenchmarkSuite::run_series(const BenchmarkConfig& baseConfig,
307 : const std::vector<std::size_t>& sizes) {
308 1 : Series all;
309 3 : for (auto s : sizes) {
310 2 : BenchmarkConfig cfg = baseConfig;
311 2 : cfg.size = s;
312 2 : auto results = run(cfg);
313 6 : for (const auto& r : results) {
314 4 : all.push_back(SeriesPoint{s, r.structure, r.insert_ms_mean, r.search_ms_mean, r.remove_ms_mean});
315 : }
316 2 : }
317 1 : return all;
318 0 : }
319 :
320 : // ---------------------------------------------------------------------------
321 : // Crossover computation
322 : // ---------------------------------------------------------------------------
323 :
324 3 : static std::optional<std::size_t> find_crossover_1d(const std::vector<std::pair<std::size_t, double>>& a,
325 : const std::vector<std::pair<std::size_t, double>>& b) {
326 3 : for (std::size_t i = 1; i < a.size(); ++i) {
327 3 : double d0 = a[i - 1].second - b[i - 1].second;
328 3 : double d1 = a[i].second - b[i].second;
329 3 : if ((d0 <= 0 && d1 >= 0) || (d0 >= 0 && d1 <= 0)) {
330 3 : double x0 = static_cast<double>(a[i - 1].first);
331 3 : double x1 = static_cast<double>(a[i].first);
332 3 : if (std::fabs(d1 - d0) < 1e-9)
333 2 : return static_cast<std::size_t>((x0 + x1) / 2);
334 1 : double t = (-d0) / (d1 - d0);
335 1 : double xc = x0 + t * (x1 - x0);
336 1 : if (xc < x0)
337 0 : xc = x0;
338 1 : if (xc > x1)
339 0 : xc = x1;
340 1 : return static_cast<std::size_t>(xc);
341 : }
342 : }
343 0 : return std::nullopt;
344 : }
345 :
346 1 : std::vector<BenchmarkSuite::CrossoverInfo> BenchmarkSuite::compute_crossovers(const Series& series) {
347 1 : std::vector<CrossoverInfo> out;
348 1 : std::map<std::string, std::vector<std::pair<std::size_t, double>>> ins, sea, rem;
349 5 : for (const auto& p : series) {
350 4 : ins[p.structure].push_back({p.size, p.insert_ms});
351 4 : sea[p.structure].push_back({p.size, p.search_ms});
352 4 : rem[p.structure].push_back({p.size, p.remove_ms});
353 : }
354 1 : auto sort_by_size = [](auto& m) {
355 9 : for (auto& kv : m)
356 6 : std::sort(kv.second.begin(), kv.second.end(),
357 12 : [](const auto& a, const auto& b) { return a.first < b.first; });
358 3 : };
359 1 : sort_by_size(ins);
360 1 : sort_by_size(sea);
361 1 : sort_by_size(rem);
362 :
363 1 : std::vector<std::string> names;
364 1 : names.reserve(ins.size());
365 3 : for (auto& kv : ins)
366 2 : names.push_back(kv.first);
367 :
368 3 : for (std::size_t i = 0; i < names.size(); ++i) {
369 3 : for (std::size_t j = i + 1; j < names.size(); ++j) {
370 1 : const auto& A = names[i];
371 1 : const auto& B = names[j];
372 1 : if (ins[A].size() == ins[B].size() && !ins[A].empty()) {
373 1 : if (auto cx = find_crossover_1d(ins[A], ins[B]))
374 3 : out.push_back(CrossoverInfo{"insert", A, B, *cx});
375 : }
376 1 : if (sea[A].size() == sea[B].size() && !sea[A].empty()) {
377 1 : if (auto cx = find_crossover_1d(sea[A], sea[B]))
378 3 : out.push_back(CrossoverInfo{"search", A, B, *cx});
379 : }
380 1 : if (rem[A].size() == rem[B].size() && !rem[A].empty()) {
381 1 : if (auto cx = find_crossover_1d(rem[A], rem[B]))
382 3 : out.push_back(CrossoverInfo{"remove", A, B, *cx});
383 : }
384 : }
385 : }
386 2 : return out;
387 1 : }
388 :
389 : } // namespace hashbrowns
|
