vec_vs_map.cpp

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <chrono>
#include <cstdlib>
#include <algorithm>

	
#define USE_STD_STR

struct Macro
{
	std::string content;
	std::vector<std::string> args;
	std::string filepath;
	size_t line;
	size_t column;
	bool hasargs;

#ifdef USE_STD_STR
	std::string name;
	Macro(const std::string& name_ = {}) : name(name_) {}

	bool operator==(const Macro& other) const 
	{ 
		return name == other.name;
	}

	bool operator<(const Macro& other) const 
	{ 
		return name < other.name;
	}
#else
	char name[32];
	Macro(const std::string& name_ = {}) {
		strcpy_s(name, name_.c_str());
	}

	bool operator==(const Macro& other) const 
	{ 
		return strcmp(name, other.name) == 0;
	}

	bool operator<(const Macro& other) const 
	{ 
		return strcmp(name, other.name) < 0;
	}
#endif

};

std::string random_name()
{
    auto randchar = []() -> char
    {
        const char charset[] =
        "0123456789"
        "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
        "abcdefghijklmnopqrstuvwxyz";
        const size_t max_index = (sizeof(charset) - 1);
        return charset[ rand() % max_index ];
    };
	const size_t length = 20;
    std::string str(length,0);
    std::generate_n( str.begin(), length, randchar );
    return str;
}

void compare(int count)
{
	using namespace std::chrono; 

	const int samples = 100;
	const int inner_samples = 100;
	std::vector<std::string> names(count);
	std::generate(names.begin(), names.end(), random_name);

	std::vector<std::string> lookups(samples);
	std::generate(lookups.begin(), lookups.end(), [&names]() { return names[rand() % names.size()]; });

	std::cout << "Testing with " << count << " macros...\n";
	{

		std::vector<Macro> macros;
		std::transform(names.begin(), names.end(), std::back_inserter(macros), [](auto name) { return name; });

		microseconds duration{ 0 };
		for (size_t lookup_idx = 0; lookup_idx < lookups.size(); ++lookup_idx)
		{
			const auto& lookup = Macro(lookups[lookup_idx]);
			auto start = high_resolution_clock::now();
			for (int inner_sample_idx = 0; inner_sample_idx < inner_samples; ++inner_sample_idx)
			{
				size_t i;
				for (i = 0; i < macros.size() && !(macros[i] == lookup); ++i) {}
				//auto fitr = std::find(macros.begin(), macros.end(), lookup);
			}
			duration += duration_cast<microseconds>(high_resolution_clock::now() - start);
		}

		std::cout << "  Vector duration: " << (double)duration.count() / (samples * inner_samples) << "us\n";
	}
 
	{

		std::vector<Macro> macros;
		std::transform(names.begin(), names.end(), std::back_inserter(macros), [](auto name) { return name; });

		std::sort(macros.begin(), macros.end());

		microseconds duration{ 0 };
		for (size_t lookup_idx = 0; lookup_idx < lookups.size(); ++lookup_idx)
		{
			const auto& lookup = Macro(lookups[lookup_idx]);
			auto start = high_resolution_clock::now();
			for (int inner_sample_idx = 0; inner_sample_idx < inner_samples; ++inner_sample_idx)
			{
				//size_t i;
				//for (i = 0; i < macros.size() && !(macros[i] == lookup); ++i) {}
				auto fitr = std::binary_search(macros.begin(), macros.end(), lookup);
			}
			duration += duration_cast<microseconds>(high_resolution_clock::now() - start);
		}

		std::cout << "  Sorted vector duration: " << (double)duration.count() / (samples * inner_samples) << "us\n";
	}
	{

		std::unordered_map<std::string, Macro> macros;
		std::for_each(names.begin(), names.end(), [&macros](auto name) { macros[name] = Macro{ name }; });

		microseconds duration{ 0 };
		for (size_t lookup_idx = 0; lookup_idx < lookups.size(); ++lookup_idx)
		{
			const auto& lookup_str = lookups[lookup_idx];
			auto start = high_resolution_clock::now();
			for (int inner_sample_idx = 0; inner_sample_idx < inner_samples; ++inner_sample_idx)
			{
				auto fitr = macros.find(lookup_str);
			}
			duration += duration_cast<microseconds>(high_resolution_clock::now() - start);
		}

		std::cout << "  Unordered map duration: " << (double)duration.count() / (samples * inner_samples) << "us\n";
	}
}

int main()
{
	auto counts = { 1, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 200, 300, 400 };
	for (auto count : counts)
	{
		compare(count);
	}
}