Comparison of performance between std::map and std::unordered_map

map_benchmark.cpp

/* My result:
 * $ c++ --std=c++20 -O3 map_benchmark.cpp 2>&1 && ./a.out
 * tiny map, a lot of queries
 *         omap) hits: 27271969, setup: 0ms, query: 916ms
 *         umap) hits: 27271969, setup: 0ms, query: 637ms
 * small map, a lot of queries
 *         omap) hits: 4004139, setup: 0ms, query: 378ms
 *         umap) hits: 4004139, setup: 0ms, query: 167ms
 * big map, a few queries
 *         omap) hits: 63229, setup: 577ms, query: 60ms
 *         umap) hits: 63229, setup: 251ms, query: 9ms
 */
#include <chrono>
#include <iostream>
#include <map>
#include <random>
#include <string>
#include <unordered_map>

using namespace std;
using namespace std::chrono;

struct BenchmarkParameters {
	int seed; 
	int int_min; 
	int int_max; 
	int map_size; 
	int number_of_queries;
};

/* Build a map using {map_size} random numbers between {int_min} and {int_max}
 * as keys and its string representations as values. Call find()
 * {number_of_queries} times incrementing number_of_hits every time it finds
 * something. 
 *
 * Output parameters:
 * {number_of_hits} - number of times the value was found (has to be used to
 * 	avoid optimization)
 * {setup_time} - time of building a map
 * {query_time} - total time of queries
 */
template <typename MapIntToString>
void
run_benchmark(BenchmarkParameters parameters,
              int *number_of_hits,
              milliseconds *setup_time,
              milliseconds *query_time) {
	auto setup_start_time = steady_clock::now();
	MapIntToString map;
	mt19937 engine(parameters.seed);
	uniform_int_distribution<int> pick_random(parameters.int_min, parameters.int_max);
	for (int i = 0; i < parameters.map_size; ++i) {
		int key = pick_random(engine);
		string value = to_string(key);
		map[key] = value;
	}
	int hits = 0;
	auto query_start_time = steady_clock::now();
	for (int i = 0; i < parameters.number_of_queries; ++i) {
		int key = pick_random(engine);
		auto it = map.find(key); 
		if (it != map.end()) {
			++hits;
		}
	}
	auto query_finish_time = steady_clock::now();
	*number_of_hits = hits;
	*setup_time = duration_cast<milliseconds>(query_start_time - setup_start_time);
	*query_time = duration_cast<milliseconds>(query_finish_time - query_start_time);
}

void run_benchmarks(BenchmarkParameters parameters) {
	int hits;
	milliseconds setup_time, query_time;
	run_benchmark<map<int, string>>(parameters, &hits, &setup_time, &query_time);
	cout << "\tomap) hits: " << hits 
		<< ", setup: " << setup_time.count() << "ms" 
		<< ", query: " << query_time.count() << "ms"
		<< endl;
	run_benchmark<unordered_map<int, string>>(parameters, &hits, &setup_time, &query_time);
	cout << "\tumap) hits: " << hits 
		<< ", setup: " << setup_time.count() << "ms" 
		<< ", query: " << query_time.count() << "ms"
		<< endl;
}

int main() {
	cout << "tiny map, a lot of queries" << endl;
	BenchmarkParameters tiny_map_a_lot_of_queries;
	tiny_map_a_lot_of_queries.seed = 42;
	tiny_map_a_lot_of_queries.int_min = 0;
	tiny_map_a_lot_of_queries.int_max = 10;
	tiny_map_a_lot_of_queries.map_size = 10;
	tiny_map_a_lot_of_queries.number_of_queries = 50'000'000;
	run_benchmarks(tiny_map_a_lot_of_queries);

	cout << "small map, a lot of queries" << endl;
	BenchmarkParameters small_map_a_lot_of_queries;
	small_map_a_lot_of_queries.seed = 42;
	small_map_a_lot_of_queries.int_min = 0;
	small_map_a_lot_of_queries.int_max = 1000;
	small_map_a_lot_of_queries.map_size = 500;
	small_map_a_lot_of_queries.number_of_queries = 10'000'000;
	run_benchmarks(small_map_a_lot_of_queries);

	cout << "big map, a few queries" << endl;
	milliseconds setup_time, query_time;
	BenchmarkParameters big_map_a_few_queries;
	big_map_a_few_queries.seed = 43;
	big_map_a_few_queries.int_min = 0;
	big_map_a_few_queries.int_max = 1'000'000;
	big_map_a_few_queries.map_size = 1'000'000;
	big_map_a_few_queries.number_of_queries = 100'000;
	run_benchmarks(big_map_a_few_queries);

	return 0;
}