当然，unordered_map的查找性能平均是常量，并且映射的查找性能是O（logN）。
但是当然为了在unordered_map中找到一个对象，我们必须：
而在地图中，我们只需要将所搜索的密钥与log2（N）密钥进行比较，其中N是地图中的项目数。
我想知道真正的性能差异是什么，假设散列函数增加了开销，而且equality_compare并不比less_than比较便宜。
我写了一个测试，而不是用一个我可以自己回答的问题来打扰社区。
我已经分享了下面的结果，以防其他人发现这个有趣或有用。
如果有人能够并且愿意添加更多信息，当然会邀请更多答案。
在回答有关错过搜索次数的性能问题时，我已经重构了测试以对此进行参数化。
示例结果：
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;
}
在接下来的测试中，我使用-O3在apple clang上编译，我已采取措施确保测试公平，例如：
通过vtable调用每个搜索结果调用接收函数，以防止优化器内联整个搜索！
在3种不同类型的地图上运行测试，包含相同的数据，并行的顺序相同。这意味着如果一个测试开始“前进”，它将开始为搜索集输入缓存未命中区域（请参阅代码）。这意味着没有一个测试会遇到“热”缓存的不公平优势。
参数化密钥大小（因此复杂性）
参数化地图大小
测试了三种不同类型的地图（包含相同的数据） - 一个unordered_map，一个地图和一个键/值对的排序向量。
检查汇编器输出以确保优化器由于死代码分析而无法优化掉整个逻辑块。
这是代码：
#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具有几乎相同的复杂性。
在这个测试中，无序地图的速度大约是有序地图的3倍（对于查找），并且排序的向量令人信服地击败了地图。
我真的很震惊它的速度有多快。