unordered_map 在实践中真的比地图快吗？
Is an unordered_map really faster than a map in practice?
当然，一个unordered_map的查找性能平均是恒定的，而一个映射的查找性能是O(logN)。
当然，为了在 unordered_map 中找到对象，我们必须：
- 散列我们要查找的密钥。
- equality_compare 每个键都在同一个桶中的键。
而在映射中，我们只需要 less_than 将查找到的键与 log2(N) 个键进行比较，其中 N 是映射中的项目数。
我想知道真正的性能差异是什么，因为哈希函数会增加开销并且 equality_compare 并不比 less_than 比较便宜。
我没有用自己可以回答的问题来打扰社区，而是编写了一个测试。
我已经在下面分享了结果，以防其他人觉得这有趣或有用。
如果有人能够并愿意添加更多信息，当然会邀请更多答案。
在下面的测试中，我使用 -O3 在 apple clang 上编译，我采取了一些措施来确保测试的公平性，例如：
通过 vtable 使用每次搜索的结果调用接收器函数，以防止优化器内联整个搜索！
运行 测试 3 种不同类型的地图，包含相同的数据，以相同的顺序并行。这意味着如果一个测试开始 'get ahead'，它开始进入搜索集的缓存未命中区域（参见代码）。这意味着没有任何测试会因遇到 'hot' 缓存而获得不公平的优势。
参数化密钥大小（以及复杂性）
参数化地图大小
测试了三种不同类型的地图（包含相同的数据）- unordered_map、地图和 key/value 对的排序向量。
检查了汇编器输出，以确保优化器无法优化掉由于死代码分析而导致的整个逻辑块。
代码如下：
#include <iostream>
#include <random>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <chrono>
#include <tuple>
#include <future>
#include <stdexcept>
#include <sstream>
using namespace std;
// this sets the length of the string we will be using as a key.
// modify this to test whether key complexity changes the performance ratios
// of the various maps
static const size_t key_length = 20;
// the number of keys we will generate (the size of the test)
const size_t nkeys = 1000000;
// the types of map we will test
unordered_map<string, string> unordered;
map<string, string> ordered;
vector<pair<string, string>> flat_map;
// a vector of all keys, which we can shuffle in order to randomise
// access order of all our maps consistently
vector<string> keys;
// use a virtual method to prevent the optimiser from detecting that
// our sink function actually does nothing. otherwise it might skew the test
struct string_user
{
virtual void sink(const std::string&) = 0;
virtual ~string_user() = default;
};
struct real_string_user : string_user
{
virtual void sink(const std::string&) override
{
}
};
struct real_string_user_print : string_user
{
virtual void sink(const std::string& s) override
{
cout << s << endl;
}
};
// generate a sink from a string - this is a runtime operation and therefore
// prevents the optimiser from realising that the sink does nothing
std::unique_ptr<string_user> make_sink(const std::string& name)
{
if (name == "print")
{
return make_unique<real_string_user_print>();
}
if (name == "noprint")
{
return make_unique<real_string_user>();
}
throw logic_error(name);
}
// generate a random key, given a random engine and a distribution
auto gen_string = [](auto& engine, auto& dist)
{
std::string result(key_length, ' ');
generate(begin(result), end(result), [&] {
return dist(engine);
});
return result;
};
// comparison predicate for our flat map.
struct pair_less
{
bool operator()(const pair<string, string>& l, const string& r) const {
return l.first < r;
}
bool operator()(const string& l, const pair<string, string>& r) const {
return l < r.first;
}
};
int main()
{
// generate the sink, preventing the optimiser from realising what it
// does.
stringstream ss;
ss << "noprint";
string arg;
ss >> arg;
auto puser = make_sink(arg);
// generate keys
auto eng = std::default_random_engine(std::random_device()());
auto alpha_dist = std::uniform_int_distribution<char>('A', 'Z');
for (size_t i = 0 ; i < nkeys ; ++i)
{
bool inserted = false;
auto value = to_string(i);
while(!inserted) {
// generate a key
auto key = gen_string(eng, alpha_dist);
// try to store it in the unordered map
// if it already exists, force a regeneration
// otherwise also store it in the ordered map and the flat map
tie(ignore, inserted) = unordered.emplace(key, value);
if (inserted) {
flat_map.emplace_back(key, value);
ordered.emplace(key, std::move(value));
// record the key for later use
keys.emplace_back(std::move(key));
}
}
}
// turn our vector 'flat map' into an actual flat map by sorting it by pair.first. This is the key.
sort(begin(flat_map), end(flat_map),
[](const auto& l, const auto& r) { return l.first < r.first; });
// shuffle the keys to randomise access order
shuffle(begin(keys), end(keys), eng);
// spawn a thread to time access to the unordered map
auto unordered_future = async(launch::async, [&]()
{
auto start_time = chrono::system_clock::now();
for (auto const& key : keys)
{
puser->sink(unordered.at(key));
}
auto stop_time = chrono::system_clock::now();
auto diff = stop_time - start_time;
return diff;
});
// spawn a thread to time access to the ordered map
auto ordered_future = async(launch::async, [&]
{
auto start_time = chrono::system_clock::now();
for (auto const& key : keys)
{
puser->sink(ordered.at(key));
}
auto stop_time = chrono::system_clock::now();
auto diff = stop_time - start_time;
return diff;
});
// spawn a thread to time access to the flat map
auto flat_future = async(launch::async, [&]
{
auto start_time = chrono::system_clock::now();
for (auto const& key : keys)
{
auto i = lower_bound(begin(flat_map),
end(flat_map),
key,
pair_less());
if (i != end(flat_map) && i->first == key)
puser->sink(i->second);
else
throw invalid_argument(key);
}
auto stop_time = chrono::system_clock::now();
auto diff = stop_time - start_time;
return diff;
});
// synchronise all the threads and get the timings
auto ordered_time = ordered_future.get();
auto unordered_time = unordered_future.get();
auto flat_time = flat_future.get();
// print
cout << " ordered time: " << ordered_time.count() << endl;
cout << "unordered time: " << unordered_time.count() << endl;
cout << " flat map time: " << flat_time.count() << endl;
return 0;
}
结果：
ordered time: 972711
unordered time: 335821
flat map time: 559768
如您所见，unordered_map 令人信服地击败了映射和排序的对向量。对向量的速度是地图解决方案的两倍。这很有趣，因为 lower_bound 和 map::at 具有几乎相同的复杂性。
TL;DR
在此测试中，无序映射的速度（对于查找）大约是有序映射的 3 倍，并且排序向量令人信服地击败了映射。
我真的对它的速度感到震惊。
为了回答有关错过搜索次数的性能问题，我重构了测试以对其进行参数化。
示例结果：
searches=1000000 set_size= 0 miss= 100% ordered= 4384 unordered= 12901 flat_map= 681
searches=1000000 set_size= 99 miss= 99.99% ordered= 89127 unordered= 42615 flat_map= 86091
searches=1000000 set_size= 172 miss= 99.98% ordered= 101283 unordered= 53468 flat_map= 96008
searches=1000000 set_size= 303 miss= 99.97% ordered= 112747 unordered= 53211 flat_map= 107343
searches=1000000 set_size= 396 miss= 99.96% ordered= 124179 unordered= 59655 flat_map= 112687
searches=1000000 set_size= 523 miss= 99.95% ordered= 132180 unordered= 51133 flat_map= 121669
searches=1000000 set_size= 599 miss= 99.94% ordered= 135850 unordered= 55078 flat_map= 121072
searches=1000000 set_size= 695 miss= 99.93% ordered= 140204 unordered= 60087 flat_map= 124961
searches=1000000 set_size= 795 miss= 99.92% ordered= 146071 unordered= 64790 flat_map= 127873
searches=1000000 set_size= 916 miss= 99.91% ordered= 154461 unordered= 50944 flat_map= 133194
searches=1000000 set_size= 988 miss= 99.9% ordered= 156327 unordered= 54094 flat_map= 134288
键：
searches = number of searches performed against each map
set_size = how big each map is (and therefore how many of the searches will result in a hit)
miss = the probability of generating a missed search. Used for generating searches and set_size.
ordered = the time spent searching the ordered map
unordered = the time spent searching the unordered_map
flat_map = the time spent searching the flat map
note: time is measured in std::system_clock::duration ticks.
TL;DR
结果：unordered_map地图一有数据就显示出它的优越性。它表现出比有序地图更差的唯一一次是当地图为空时。
这是新代码：
#include <iostream>
#include <iomanip>
#include <random>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <chrono>
#include <tuple>
#include <future>
#include <stdexcept>
#include <sstream>
using namespace std;
// this sets the length of the string we will be using as a key.
// modify this to test whether key complexity changes the performance ratios
// of the various maps
static const size_t key_length = 20;
// the number of keys we will generate (the size of the test)
const size_t nkeys = 1000000;
// use a virtual method to prevent the optimiser from detecting that
// our sink function actually does nothing. otherwise it might skew the test
struct string_user
{
virtual void sink(const std::string&) = 0;
virtual ~string_user() = default;
};
struct real_string_user : string_user
{
virtual void sink(const std::string&) override
{
}
};
struct real_string_user_print : string_user
{
virtual void sink(const std::string& s) override
{
cout << s << endl;
}
};
// generate a sink from a string - this is a runtime operation and therefore
// prevents the optimiser from realising that the sink does nothing
std::unique_ptr<string_user> make_sink(const std::string& name)
{
if (name == "print")
{
return make_unique<real_string_user_print>();
}
if (name == "noprint")
{
return make_unique<real_string_user>();
}
throw logic_error(name);
}
// generate a random key, given a random engine and a distribution
auto gen_string = [](auto& engine, auto& dist)
{
std::string result(key_length, ' ');
generate(begin(result), end(result), [&] {
return dist(engine);
});
return result;
};
// comparison predicate for our flat map.
struct pair_less
{
bool operator()(const pair<string, string>& l, const string& r) const {
return l.first < r;
}
bool operator()(const string& l, const pair<string, string>& r) const {
return l < r.first;
}
};
template<class F>
auto time_test(F&& f, const vector<string> keys)
{
auto start_time = chrono::system_clock::now();
for (auto const& key : keys)
{
f(key);
}
auto stop_time = chrono::system_clock::now();
auto diff = stop_time - start_time;
return diff;
}
struct report_key
{
size_t nkeys;
int miss_chance;
};
std::ostream& operator<<(std::ostream& os, const report_key& key)
{
return os << "miss=" << setw(2) << key.miss_chance << "%";
}
void run_test(string_user& sink, size_t nkeys, double miss_prob)
{
// the types of map we will test
unordered_map<string, string> unordered;
map<string, string> ordered;
vector<pair<string, string>> flat_map;
// a vector of all keys, which we can shuffle in order to randomise
// access order of all our maps consistently
vector<string> keys;
unordered_set<string> keys_record;
// generate keys
auto eng = std::default_random_engine(std::random_device()());
auto alpha_dist = std::uniform_int_distribution<char>('A', 'Z');
auto prob_dist = std::uniform_real_distribution<double>(0, 1.0 - std::numeric_limits<double>::epsilon());
auto generate_new_key = [&] {
while(true) {
// generate a key
auto key = gen_string(eng, alpha_dist);
// try to store it in the unordered map
// if it already exists, force a regeneration
// otherwise also store it in the ordered map and the flat map
if(keys_record.insert(key).second) {
return key;
}
}
};
for (size_t i = 0 ; i < nkeys ; ++i)
{
bool inserted = false;
auto value = to_string(i);
auto key = generate_new_key();
if (prob_dist(eng) >= miss_prob) {
unordered.emplace(key, value);
flat_map.emplace_back(key, value);
ordered.emplace(key, std::move(value));
}
// record the key for later use
keys.emplace_back(std::move(key));
}
// turn our vector 'flat map' into an actual flat map by sorting it by pair.first. This is the key.
sort(begin(flat_map), end(flat_map),
[](const auto& l, const auto& r) { return l.first < r.first; });
// shuffle the keys to randomise access order
shuffle(begin(keys), end(keys), eng);
auto unordered_lookup = [&](auto& key) {
auto i = unordered.find(key);
if (i != end(unordered)) {
sink.sink(i->second);
}
};
auto ordered_lookup = [&](auto& key) {
auto i = ordered.find(key);
if (i != end(ordered)) {
sink.sink(i->second);
}
};
auto flat_map_lookup = [&](auto& key) {
auto i = lower_bound(begin(flat_map),
end(flat_map),
key,
pair_less());
if (i != end(flat_map) && i->first == key) {
sink.sink(i->second);
}
};
// spawn a thread to time access to the unordered map
auto unordered_future = async(launch::async,
[&]()
{
return time_test(unordered_lookup, keys);
});
// spawn a thread to time access to the ordered map
auto ordered_future = async(launch::async, [&]
{
return time_test(ordered_lookup, keys);
});
// spawn a thread to time access to the flat map
auto flat_future = async(launch::async, [&]
{
return time_test(flat_map_lookup, keys);
});
// synchronise all the threads and get the timings
auto ordered_time = ordered_future.get();
auto unordered_time = unordered_future.get();
auto flat_time = flat_future.get();
cout << "searches=" << setw(7) << nkeys;
cout << " set_size=" << setw(7) << unordered.size();
cout << " miss=" << setw(7) << setprecision(6) << miss_prob * 100.0 << "%";
cout << " ordered=" << setw(7) << ordered_time.count();
cout << " unordered=" << setw(7) << unordered_time.count();
cout << " flat_map=" << setw(7) << flat_time.count() << endl;
}
int main()
{
// generate the sink, preventing the optimiser from realising what it
// does.
stringstream ss;
ss << "noprint";
string arg;
ss >> arg;
auto puser = make_sink(arg);
for (double chance = 1.0 ; chance >= 0.0 ; chance -= 0.0001)
{
run_test(*puser, 1000000, chance);
}
return 0;
}
当然，一个unordered_map的查找性能平均是恒定的，而一个映射的查找性能是O(logN)。
当然，为了在 unordered_map 中找到对象，我们必须：
- 散列我们要查找的密钥。
- equality_compare 每个键都在同一个桶中的键。
而在映射中，我们只需要 less_than 将查找到的键与 log2(N) 个键进行比较，其中 N 是映射中的项目数。
我想知道真正的性能差异是什么，因为哈希函数会增加开销并且 equality_compare 并不比 less_than 比较便宜。
我没有用自己可以回答的问题来打扰社区，而是编写了一个测试。
我已经在下面分享了结果，以防其他人觉得这有趣或有用。
如果有人能够并愿意添加更多信息，当然会邀请更多答案。
在下面的测试中，我使用 -O3 在 apple clang 上编译，我采取了一些措施来确保测试的公平性，例如：
通过 vtable 使用每次搜索的结果调用接收器函数，以防止优化器内联整个搜索！
运行 测试 3 种不同类型的地图，包含相同的数据，以相同的顺序并行。这意味着如果一个测试开始 'get ahead'，它开始进入搜索集的缓存未命中区域（参见代码）。这意味着没有任何测试会因遇到 'hot' 缓存而获得不公平的优势。
参数化密钥大小（以及复杂性）
参数化地图大小
测试了三种不同类型的地图（包含相同的数据）- unordered_map、地图和 key/value 对的排序向量。
检查了汇编器输出，以确保优化器无法优化掉由于死代码分析而导致的整个逻辑块。
代码如下：
#include <iostream>
#include <random>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <chrono>
#include <tuple>
#include <future>
#include <stdexcept>
#include <sstream>
using namespace std;
// this sets the length of the string we will be using as a key.
// modify this to test whether key complexity changes the performance ratios
// of the various maps
static const size_t key_length = 20;
// the number of keys we will generate (the size of the test)
const size_t nkeys = 1000000;
// the types of map we will test
unordered_map<string, string> unordered;
map<string, string> ordered;
vector<pair<string, string>> flat_map;
// a vector of all keys, which we can shuffle in order to randomise
// access order of all our maps consistently
vector<string> keys;
// use a virtual method to prevent the optimiser from detecting that
// our sink function actually does nothing. otherwise it might skew the test
struct string_user
{
virtual void sink(const std::string&) = 0;
virtual ~string_user() = default;
};
struct real_string_user : string_user
{
virtual void sink(const std::string&) override
{
}
};
struct real_string_user_print : string_user
{
virtual void sink(const std::string& s) override
{
cout << s << endl;
}
};
// generate a sink from a string - this is a runtime operation and therefore
// prevents the optimiser from realising that the sink does nothing
std::unique_ptr<string_user> make_sink(const std::string& name)
{
if (name == "print")
{
return make_unique<real_string_user_print>();
}
if (name == "noprint")
{
return make_unique<real_string_user>();
}
throw logic_error(name);
}
// generate a random key, given a random engine and a distribution
auto gen_string = [](auto& engine, auto& dist)
{
std::string result(key_length, ' ');
generate(begin(result), end(result), [&] {
return dist(engine);
});
return result;
};
// comparison predicate for our flat map.
struct pair_less
{
bool operator()(const pair<string, string>& l, const string& r) const {
return l.first < r;
}
bool operator()(const string& l, const pair<string, string>& r) const {
return l < r.first;
}
};
int main()
{
// generate the sink, preventing the optimiser from realising what it
// does.
stringstream ss;
ss << "noprint";
string arg;
ss >> arg;
auto puser = make_sink(arg);
// generate keys
auto eng = std::default_random_engine(std::random_device()());
auto alpha_dist = std::uniform_int_distribution<char>('A', 'Z');
for (size_t i = 0 ; i < nkeys ; ++i)
{
bool inserted = false;
auto value = to_string(i);
while(!inserted) {
// generate a key
auto key = gen_string(eng, alpha_dist);
// try to store it in the unordered map
// if it already exists, force a regeneration
// otherwise also store it in the ordered map and the flat map
tie(ignore, inserted) = unordered.emplace(key, value);
if (inserted) {
flat_map.emplace_back(key, value);
ordered.emplace(key, std::move(value));
// record the key for later use
keys.emplace_back(std::move(key));
}
}
}
// turn our vector 'flat map' into an actual flat map by sorting it by pair.first. This is the key.
sort(begin(flat_map), end(flat_map),
[](const auto& l, const auto& r) { return l.first < r.first; });
// shuffle the keys to randomise access order
shuffle(begin(keys), end(keys), eng);
// spawn a thread to time access to the unordered map
auto unordered_future = async(launch::async, [&]()
{
auto start_time = chrono::system_clock::now();
for (auto const& key : keys)
{
puser->sink(unordered.at(key));
}
auto stop_time = chrono::system_clock::now();
auto diff = stop_time - start_time;
return diff;
});
// spawn a thread to time access to the ordered map
auto ordered_future = async(launch::async, [&]
{
auto start_time = chrono::system_clock::now();
for (auto const& key : keys)
{
puser->sink(ordered.at(key));
}
auto stop_time = chrono::system_clock::now();
auto diff = stop_time - start_time;
return diff;
});
// spawn a thread to time access to the flat map
auto flat_future = async(launch::async, [&]
{
auto start_time = chrono::system_clock::now();
for (auto const& key : keys)
{
auto i = lower_bound(begin(flat_map),
end(flat_map),
key,
pair_less());
if (i != end(flat_map) && i->first == key)
puser->sink(i->second);
else
throw invalid_argument(key);
}
auto stop_time = chrono::system_clock::now();
auto diff = stop_time - start_time;
return diff;
});
// synchronise all the threads and get the timings
auto ordered_time = ordered_future.get();
auto unordered_time = unordered_future.get();
auto flat_time = flat_future.get();
// print
cout << " ordered time: " << ordered_time.count() << endl;
cout << "unordered time: " << unordered_time.count() << endl;
cout << " flat map time: " << flat_time.count() << endl;
return 0;
}
结果：
ordered time: 972711
unordered time: 335821
flat map time: 559768
如您所见，unordered_map 令人信服地击败了映射和排序的对向量。对向量的速度是地图解决方案的两倍。这很有趣，因为 lower_bound 和 map::at 具有几乎相同的复杂性。
TL;DR
在此测试中，无序映射的速度（对于查找）大约是有序映射的 3 倍，并且排序向量令人信服地击败了映射。
我真的对它的速度感到震惊。
为了回答有关错过搜索次数的性能问题，我重构了测试以对其进行参数化。
示例结果：
searches=1000000 set_size= 0 miss= 100% ordered= 4384 unordered= 12901 flat_map= 681
searches=1000000 set_size= 99 miss= 99.99% ordered= 89127 unordered= 42615 flat_map= 86091
searches=1000000 set_size= 172 miss= 99.98% ordered= 101283 unordered= 53468 flat_map= 96008
searches=1000000 set_size= 303 miss= 99.97% ordered= 112747 unordered= 53211 flat_map= 107343
searches=1000000 set_size= 396 miss= 99.96% ordered= 124179 unordered= 59655 flat_map= 112687
searches=1000000 set_size= 523 miss= 99.95% ordered= 132180 unordered= 51133 flat_map= 121669
searches=1000000 set_size= 599 miss= 99.94% ordered= 135850 unordered= 55078 flat_map= 121072
searches=1000000 set_size= 695 miss= 99.93% ordered= 140204 unordered= 60087 flat_map= 124961
searches=1000000 set_size= 795 miss= 99.92% ordered= 146071 unordered= 64790 flat_map= 127873
searches=1000000 set_size= 916 miss= 99.91% ordered= 154461 unordered= 50944 flat_map= 133194
searches=1000000 set_size= 988 miss= 99.9% ordered= 156327 unordered= 54094 flat_map= 134288
键：
searches = number of searches performed against each map
set_size = how big each map is (and therefore how many of the searches will result in a hit)
miss = the probability of generating a missed search. Used for generating searches and set_size.
ordered = the time spent searching the ordered map
unordered = the time spent searching the unordered_map
flat_map = the time spent searching the flat map
note: time is measured in std::system_clock::duration ticks.
TL;DR
结果：unordered_map地图一有数据就显示出它的优越性。它表现出比有序地图更差的唯一一次是当地图为空时。
这是新代码：
#include <iostream>
#include <iomanip>
#include <random>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <chrono>
#include <tuple>
#include <future>
#include <stdexcept>
#include <sstream>
using namespace std;
// this sets the length of the string we will be using as a key.
// modify this to test whether key complexity changes the performance ratios
// of the various maps
static const size_t key_length = 20;
// the number of keys we will generate (the size of the test)
const size_t nkeys = 1000000;
// use a virtual method to prevent the optimiser from detecting that
// our sink function actually does nothing. otherwise it might skew the test
struct string_user
{
virtual void sink(const std::string&) = 0;
virtual ~string_user() = default;
};
struct real_string_user : string_user
{
virtual void sink(const std::string&) override
{
}
};
struct real_string_user_print : string_user
{
virtual void sink(const std::string& s) override
{
cout << s << endl;
}
};
// generate a sink from a string - this is a runtime operation and therefore
// prevents the optimiser from realising that the sink does nothing
std::unique_ptr<string_user> make_sink(const std::string& name)
{
if (name == "print")
{
return make_unique<real_string_user_print>();
}
if (name == "noprint")
{
return make_unique<real_string_user>();
}
throw logic_error(name);
}
// generate a random key, given a random engine and a distribution
auto gen_string = [](auto& engine, auto& dist)
{
std::string result(key_length, ' ');
generate(begin(result), end(result), [&] {
return dist(engine);
});
return result;
};
// comparison predicate for our flat map.
struct pair_less
{
bool operator()(const pair<string, string>& l, const string& r) const {
return l.first < r;
}
bool operator()(const string& l, const pair<string, string>& r) const {
return l < r.first;
}
};
template<class F>
auto time_test(F&& f, const vector<string> keys)
{
auto start_time = chrono::system_clock::now();
for (auto const& key : keys)
{
f(key);
}
auto stop_time = chrono::system_clock::now();
auto diff = stop_time - start_time;
return diff;
}
struct report_key
{
size_t nkeys;
int miss_chance;
};
std::ostream& operator<<(std::ostream& os, const report_key& key)
{
return os << "miss=" << setw(2) << key.miss_chance << "%";
}
void run_test(string_user& sink, size_t nkeys, double miss_prob)
{
// the types of map we will test
unordered_map<string, string> unordered;
map<string, string> ordered;
vector<pair<string, string>> flat_map;
// a vector of all keys, which we can shuffle in order to randomise
// access order of all our maps consistently
vector<string> keys;
unordered_set<string> keys_record;
// generate keys
auto eng = std::default_random_engine(std::random_device()());
auto alpha_dist = std::uniform_int_distribution<char>('A', 'Z');
auto prob_dist = std::uniform_real_distribution<double>(0, 1.0 - std::numeric_limits<double>::epsilon());
auto generate_new_key = [&] {
while(true) {
// generate a key
auto key = gen_string(eng, alpha_dist);
// try to store it in the unordered map
// if it already exists, force a regeneration
// otherwise also store it in the ordered map and the flat map
if(keys_record.insert(key).second) {
return key;
}
}
};
for (size_t i = 0 ; i < nkeys ; ++i)
{
bool inserted = false;
auto value = to_string(i);
auto key = generate_new_key();
if (prob_dist(eng) >= miss_prob) {
unordered.emplace(key, value);
flat_map.emplace_back(key, value);
ordered.emplace(key, std::move(value));
}
// record the key for later use
keys.emplace_back(std::move(key));
}
// turn our vector 'flat map' into an actual flat map by sorting it by pair.first. This is the key.
sort(begin(flat_map), end(flat_map),
[](const auto& l, const auto& r) { return l.first < r.first; });
// shuffle the keys to randomise access order
shuffle(begin(keys), end(keys), eng);
auto unordered_lookup = [&](auto& key) {
auto i = unordered.find(key);
if (i != end(unordered)) {
sink.sink(i->second);
}
};
auto ordered_lookup = [&](auto& key) {
auto i = ordered.find(key);
if (i != end(ordered)) {
sink.sink(i->second);
}
};
auto flat_map_lookup = [&](auto& key) {
auto i = lower_bound(begin(flat_map),
end(flat_map),
key,
pair_less());
if (i != end(flat_map) && i->first == key) {
sink.sink(i->second);
}
};
// spawn a thread to time access to the unordered map
auto unordered_future = async(launch::async,
[&]()
{
return time_test(unordered_lookup, keys);
});
// spawn a thread to time access to the ordered map
auto ordered_future = async(launch::async, [&]
{
return time_test(ordered_lookup, keys);
});
// spawn a thread to time access to the flat map
auto flat_future = async(launch::async, [&]
{
return time_test(flat_map_lookup, keys);
});
// synchronise all the threads and get the timings
auto ordered_time = ordered_future.get();
auto unordered_time = unordered_future.get();
auto flat_time = flat_future.get();
cout << "searches=" << setw(7) << nkeys;
cout << " set_size=" << setw(7) << unordered.size();
cout << " miss=" << setw(7) << setprecision(6) << miss_prob * 100.0 << "%";
cout << " ordered=" << setw(7) << ordered_time.count();
cout << " unordered=" << setw(7) << unordered_time.count();
cout << " flat_map=" << setw(7) << flat_time.count() << endl;
}
int main()
{
// generate the sink, preventing the optimiser from realising what it
// does.
stringstream ss;
ss << "noprint";
string arg;
ss >> arg;
auto puser = make_sink(arg);
for (double chance = 1.0 ; chance >= 0.0 ; chance -= 0.0001)
{
run_test(*puser, 1000000, chance);
}
return 0;
}