std::set and std::priority_queue

benchmark.cpp

// Mivik 2021.6.18
#include <chrono>
#include <iostream>
#include <queue>
#include <random>
#include <set>
#include <vector>

const int QUERY_NUM = 2000000;
const int INSERT_NUM = 2000000;
const int OPERATIONS_NUM = QUERY_NUM + INSERT_NUM;

std::pair<uint64_t, uint64_t> perform_one_test() {
	static std::mt19937 rng;
	static std::uniform_int_distribution<int> percentage_dist(1, 100);
	static std::uniform_int_distribution<uint32_t> dist(1U, -1U);

	using namespace std::chrono;

	volatile int out_value; // prevent the output to be optimized out

	std::vector<uint32_t> data(OPERATIONS_NUM);
	for (int i = 0; i < QUERY_NUM; ++i) data[i] = 0;
	for (int i = 0; i < INSERT_NUM; ++i) data[QUERY_NUM + i] = dist(rng);
	std::shuffle(data.begin(), data.end(), rng);

	std::pair<uint64_t, uint64_t> result;

	{
		std::set<uint32_t> set;
		auto st_time = steady_clock::now();
		for (uint32_t val : data) {
			if (val) set.insert(val);
			else out_value = set.empty()? -1: *set.begin();
		}
		auto en_time = steady_clock::now();
		result.first = duration_cast<milliseconds>(en_time - st_time).count();
	}

	{
		std::priority_queue<
			uint32_t,
			std::vector<uint32_t>,
			std::greater<uint32_t>
		> queue;
		auto st_time = steady_clock::now();
		for (uint32_t val : data) {
			if (val) queue.push(val);
			else out_value = queue.empty()? -1: queue.top();
		}
		auto en_time = steady_clock::now();
		result.second = duration_cast<milliseconds>(en_time - st_time).count();
	}

	return result;
}
int main() {
	const int TEST_ROUNDS = 10;

	uint64_t set_time = 0, queue_time = 0;

	for (int i = 0; i < TEST_ROUNDS; ++i) {
		std::cout << "Running test " << (i + 1) << "..." << std::endl;
		auto res = perform_one_test();
		set_time += res.first;
		queue_time += res.second;
	}

	std::cout << std::endl;

	std::cout << "Test Results" << std::endl;

	std::cout << "std::set" << std::endl;
	std::cout << "Total: " << set_time << "ms" << std::endl;
	std::cout << "Average: " << ((double)set_time / TEST_ROUNDS / OPERATIONS_NUM) << "ms per operation" << std::endl;

	std::cout << std::endl;

	std::cout << "std::priority_queue" << std::endl;
	std::cout << "Total: " << queue_time << "ms" << std::endl;
	std::cout << "Average: " << ((double)queue_time / TEST_ROUNDS / OPERATIONS_NUM) << "ms per operation" << std::endl;
}

results.md

QUERY_NUM = INSERT_NUM = 2000000

std::set
Total: 11583ms
Average: 0.000289575ms per operation

std::priority_queue
Total: 2751ms
Average: 6.8775e-05ms per operation

QUERY_NUM = 500000, INSERT_NUM = 1000000

std::set
Total: 3987ms
Average: 6.645e-05ms per operation

std::priority_queue
Total: 1189ms
Average: 1.98167e-05ms per operation

QUERY_NUM = 100000, INSERT_NUM = 5000000

std::set
Total: 39902ms
Average: 0.000665033ms per operation

std::priority_queue
Total: 7275ms
Average: 0.00012125ms per operation