@@ -17,12 +17,14 @@
// { dg-do run { target c++11 } }
-#include <testsuite_performance.h>
+#include <string>
#include <random>
#include <sstream>
#include <tr1/unordered_set>
#include <unordered_set>
+#include <testsuite_performance.h>
+
#define USE_MY_FOO 1
struct Foo
@@ -71,10 +73,13 @@ struct HashFunction
};
const int sz = 300000;
+const int usz = sz / 2;
template<typename _ContType>
void
- bench(const char* container_desc, const typename _ContType::value_type* foos)
+ bench(const char* container_desc,
+ const typename _ContType::value_type* foos,
+ const typename _ContType::value_type* ufoos)
{
using namespace __gnu_test;
@@ -106,6 +111,51 @@ template<typename _ContType>
ostr << container_desc << nb_loop << " times insertion of "
<< sz << " elements";
report_performance(__FILE__, ostr.str().c_str(), time, resource);
+
+ // Try to lookup for mostly unknown entries.
+ start_counters(time, resource);
+
+ int fcount = 0;
+ for (int j = 0; j != nb_loop; ++j)
+ for (int i = 0; i != usz; ++i)
+ fcount += s.find(ufoos[i]) != s.end() ? 1 : 0;
+
+ stop_counters(time, resource);
+ ostr.str("");
+ ostr << container_desc << nb_loop << " times lookup of "
+ << usz << " elements " << fcount / nb_loop << " found";
+ report_performance(__FILE__, ostr.str().c_str(), time, resource);
+
+ // Try again the previous operations but on a copy with potentially
+ // less memory fragmentation.
+ _ContType scopy(s);
+
+ // Try to insert again to check performance of collision detection
+ start_counters(time, resource);
+
+ for (int j = 0; j != nb_loop; ++j)
+ for (int i = 0; i != sz; ++i)
+ scopy.insert(foos[i]);
+
+ stop_counters(time, resource);
+ ostr.str("");
+ ostr << container_desc << nb_loop << " times insertion of "
+ << sz << " elements in copy";
+ report_performance(__FILE__, ostr.str().c_str(), time, resource);
+
+ // Try to lookup for mostly unknown entries.
+ start_counters(time, resource);
+
+ fcount = 0;
+ for (int j = 0; j != nb_loop; ++j)
+ for (int i = 0; i != usz; ++i)
+ fcount += scopy.find(ufoos[i]) != scopy.end() ? 1 : 0;
+
+ stop_counters(time, resource);
+ ostr.str("");
+ ostr << container_desc << nb_loop << " times lookup of "
+ << usz << " elements " << fcount / nb_loop << " found";
+ report_performance(__FILE__, ostr.str().c_str(), time, resource);
}
template<bool cache>
@@ -155,67 +205,78 @@ int main()
{
int bars[sz];
+ int ubars[usz];
for (int i = 0; i != sz; ++i)
bars[i] = i;
+ for (int i = 0; i != usz; ++i)
+ ubars[i] = sz + i;
bench<std::tr1::unordered_set<int>>(
- "std::tr1::unordered_set<int> ", bars);
+ "std::tr1::unordered_set<int> ", bars, ubars);
bench<std::unordered_set<int>>(
- "std::unordered_set<int> ", bars);
+ "std::unordered_set<int> ", bars, ubars);
}
- Foo foos[sz];
-#if USE_MY_FOO
{
- std::random_device randev;
- for (int i = 0; i != sz; ++i)
- foos[i].init(randev);
- }
+ Foo foos[sz];
+ Foo ufoos[usz];
+#if USE_MY_FOO
+ {
+ std::random_device randev;
+ for (int i = 0; i != sz; ++i)
+ foos[i].init(randev);
+ for (int i = 0; i != usz; ++i)
+ ufoos[i].init(randev);
+ }
#endif
- time_counter time;
- resource_counter resource;
- start_counters(time, resource);
-
- bench<__tr1_uset<false>>(
- "std::tr1::unordered_set without hash code cached ", foos);
- bench<__tr1_uset<true>>(
- "std::tr1::unordered_set with hash code cached ", foos);
- bench<__tr1_umset<false>>(
- "std::tr1::unordered_multiset without hash code cached ", foos);
- bench<__tr1_umset<true>>(
- "std::tr1::unordered_multiset with hash code cached ", foos);
-
- stop_counters(time, resource);
- report_performance(__FILE__, "tr1 benches", time, resource);
-
- start_counters(time, resource);
- bench<__uset<false>>(
- "std::unordered_set without hash code cached ", foos);
- bench<__uset<true>>(
- "std::unordered_set with hash code cached ", foos);
- bench<__umset<false>>(
- "std::unordered_multiset without hash code cached ", foos);
- bench<__umset<true>>(
- "std::unordered_multiset with hash code cached ", foos);
-
- stop_counters(time, resource);
- report_performance(__FILE__, "std benches", time, resource);
-
- start_counters(time, resource);
- bench<__uset2<false>>(
- "std::unordered_set2 without hash code cached ", foos);
- bench<__uset2<true>>(
- "std::unordered_set2 with hash code cached ", foos);
- bench<__umset2<false>>(
- "std::unordered_multiset2 without hash code cached ", foos);
- bench<__umset2<true>>(
- "std::unordered_multiset2 with hash code cached ", foos);
-
- stop_counters(time, resource);
- report_performance(__FILE__, "std2 benches", time, resource);
-
- bench<std::unordered_set<Foo, HashFunction>>(
- "std::unordered_set default cache ", foos);
- bench<std::unordered_multiset<Foo, HashFunction>>(
- "std::unordered_multiset default cache ", foos);
+ time_counter time;
+ resource_counter resource;
+ start_counters(time, resource);
+
+ bench<__tr1_uset<false>>(
+ "std::tr1::unordered_set without hash code cached ", foos, ufoos);
+ bench<__tr1_uset<true>>(
+ "std::tr1::unordered_set with hash code cached ", foos, ufoos);
+ bench<__tr1_umset<false>>(
+ "std::tr1::unordered_multiset without hash code cached ", foos, ufoos);
+ bench<__tr1_umset<true>>(
+ "std::tr1::unordered_multiset with hash code cached ", foos, ufoos);
+
+ stop_counters(time, resource);
+ report_performance(__FILE__, "tr1 benches", time, resource);
+
+ start_counters(time, resource);
+ bench<__uset<false>>(
+ "std::unordered_set without hash code cached ", foos, ufoos);
+ bench<__uset<true>>(
+ "std::unordered_set with hash code cached ", foos, ufoos);
+ bench<__umset<false>>(
+ "std::unordered_multiset without hash code cached ", foos, ufoos);
+ bench<__umset<true>>(
+ "std::unordered_multiset with hash code cached ", foos, ufoos);
+
+ stop_counters(time, resource);
+ report_performance(__FILE__, "std benches", time, resource);
+
+ start_counters(time, resource);
+ bench<__uset2<false>>(
+ "std::unordered_set2 without hash code cached ", foos, ufoos);
+ bench<__uset2<true>>(
+ "std::unordered_set2 with hash code cached ", foos, ufoos);
+ bench<__umset2<false>>(
+ "std::unordered_multiset2 without hash code cached ", foos, ufoos);
+ bench<__umset2<true>>(
+ "std::unordered_multiset2 with hash code cached ", foos, ufoos);
+
+ stop_counters(time, resource);
+ report_performance(__FILE__, "std2 benches", time, resource);
+
+ bench<std::unordered_set<Foo, HashFunction>>(
+ "std::unordered_set default cache ", foos, ufoos);
+ bench<std::unordered_multiset<Foo, HashFunction>>(
+ "std::unordered_multiset default cache ", foos, ufoos);
+ }
+
+ {
+ }
}
@@ -27,310 +27,170 @@
namespace
{
const int sz = 2000000;
- const std::string pattern = "test string #";
- const int nb_copies = 100;
+ const std::string pattern = "long enough test string #";
- // Special std::string hasher based on std::hash<std::string> but not tag as
- // slow so that hash code is not cached. It is easier to show impact of
- // hinting in this context.
+ // Perfect std::string hasher knowing how string instances have been
+ // generated. It is not tag as slow so that hash code is not cached.
+ // It is easier to show impact of hint in this context.
struct hasher
{
std::size_t
operator()(const std::string& str) const noexcept
{
- //std::istringstream istr(str.substr(pattern.size()));
- //std::size_t str_index;
- //istr >> str_index;
- //return str_index;
std::hash<std::string> std_hasher;
- return std_hasher(str);
+ auto hash = std_hasher(pattern);
+ std::istringstream isstr(str.substr(pattern.length()));
+ int idx;
+ isstr >> idx;
+ return (std::size_t)(hash / sz) * sz + idx;
}
};
- using ums_t = std::unordered_multiset<std::string, hasher>;
-
- void
- insert_with_perfect_hint1(const std::vector<std::string>& strs,
- ums_t& ms)
- {
- std::vector<typename ums_t::iterator> hints;
- hints.reserve(strs.size());
- for (auto str : strs)
- hints.push_back(ms.insert(str));
-
- for (int j = 1; j != nb_copies; ++j)
- for (std::size_t i = 0; i != strs.size(); ++i)
- ms.insert(hints[i], strs[i]);
- }
-
- void
- insert_with_perfect_hint2(const std::vector<std::string>& strs,
- ums_t& ms)
- {
- std::vector<typename ums_t::iterator> hints;
- hints.reserve(strs.size());
- for (auto str : strs)
- hints.push_back(ms.insert(str));
-
- for (std::size_t i = 0; i != strs.size(); ++i)
- for (int j = 1; j != nb_copies; ++j)
- ms.insert(hints[i], strs[i]);
- }
-
- // Always insert with the result of the previous insertion. The result of
- // the previous insertion will never be followed by an equivalent node
- // resulting in a re-computation of its hash code which is expensive.
- void
- insert_with_good_hint(const std::vector<std::string>& strs,
- ums_t& ms)
- {
- std::vector<typename ums_t::iterator> hints;
- hints.reserve(strs.size());
- for (auto str : strs)
- hints.push_back(ms.insert(str));
-
- for (int j = 1; j != nb_copies; ++j)
- for (std::size_t i = 0; i != strs.size(); ++i)
- hints[i] = ms.insert(hints[i], strs[i]);
- }
-
- // Note that the following use case is particularly bad especially compared to
- // the solution without hint because without hint the first insertion will put
- // it first in the bucket and following insertions will detect it and insert
- // just before. By giving a hint insertion will be done just after forcing to
- // check if it has no impact on the following bucket.
- void
- insert_with_bad_hint(const std::vector<std::string>& strs,
- ums_t& ms)
- {
- std::vector<typename ums_t::iterator> hints;
- hints.reserve(strs.size());
- for (auto str : strs)
- hints.push_back(ms.insert(str));
-
- for (std::size_t i = 0; i != strs.size(); ++i)
- for (int j = 1; j != nb_copies; ++j)
- hints[i] = ms.insert(hints[i], strs[i]);
- }
-
- void
- insert_without_hint1(const std::vector<std::string>& strs,
- ums_t& ms)
- {
- std::vector<typename ums_t::iterator> hints;
- hints.reserve(strs.size());
- for (auto str : strs)
- hints.push_back(ms.insert(str));
-
- for (int j = 1; j != nb_copies; ++j)
- for (std::size_t i = 0; i != strs.size(); ++i)
- hints[i] = ms.insert(strs[i]);
- }
-
- // This version is the best one if you insert all equivalent elements at the
- // same time. It demonstrates that most of the time it is better not to give
- // any hint unless you have written a benchmark for your application showing
- // that it does have a positive effect.
- void
- insert_without_hint2(const std::vector<std::string>& strs,
- ums_t& ms)
+ // Like previous hasher but tagged as slow.
+ struct slow_hasher
{
- std::vector<typename ums_t::iterator> hints;
- hints.reserve(strs.size());
- for (auto str : strs)
- hints.push_back(ms.insert(str));
-
- for (std::size_t i = 0; i != strs.size(); ++i)
- for (int j = 1; j != nb_copies; ++j)
- hints[i] = ms.insert(strs[i]);
- }
+ std::size_t
+ operator()(const std::string& str) const noexcept
+ { return hasher{}(str); }
+ };
- void
- insert_with_any_hint1(const std::vector<std::string>& strs,
- ums_t& ms)
- {
- std::vector<typename ums_t::iterator> hints;
- hints.reserve(strs.size());
- for (auto str : strs)
- hints.push_back(ms.insert(ms.begin(), str));
+ template<typename _Hash>
+ using ums_t = std::unordered_multiset<std::string, _Hash>;
- std::size_t offset = strs.size() / 2;
- for (int j = 1; j != nb_copies; ++j)
- for (std::size_t i = 0; i != strs.size(); ++i)
+ template<typename _Hash>
+ void
+ insert_with_perfect_hint(const std::vector<std::string>& strs,
+ ums_t<_Hash>& ms)
+ {
+ auto hint = ms.end();
+ for (auto str : strs)
{
- ms.insert(hints[(i + offset) % hints.size()], strs[i]);
- ++offset;
+ auto insert_pos = ms.insert(hint, str);
+ if (std::next(insert_pos) == ms.end())
+ hint = insert_pos;
}
- }
-
- void
- insert_with_any_hint2(const std::vector<std::string>& strs,
- ums_t& ms)
- {
- std::vector<typename ums_t::iterator> hints;
- hints.reserve(strs.size());
- for (auto str : strs)
- hints.push_back(ms.insert(ms.begin(), str));
+ }
- std::size_t offset = strs.size() / 2;
- for (std::size_t i = 0; i != strs.size(); ++i)
- for (int j = 1; j != nb_copies; ++j)
+ template<typename _Hash>
+ void
+ insert_with_bad_hint(const std::vector<std::string>& strs,
+ ums_t<_Hash>& ms)
+ {
+ auto hint = ms.begin();
+ for (auto str : strs)
{
- ms.insert(hints[(i + offset) % hints.size()], strs[i]);
- ++offset;
+ auto insert_pos = ms.insert(hint, str);
+ if (std::next(insert_pos) == hint)
+ hint = ms.begin();
}
- }
-}
-
-int main()
-{
- using namespace __gnu_test;
-
- const int nb_iter = 10;
-
- std::vector<std::string> strs;
- strs.reserve(sz / nb_copies);
+ }
- for (int i = 0; i != sz / nb_copies; ++i)
+ template<typename _Hash>
+ void
+ insert_without_hint(const std::vector<std::string>& strs,
+ ums_t<_Hash>& ms)
{
- std::ostringstream osstr;
- osstr << pattern << i;
- strs.push_back(osstr.str());
+ for (auto str : strs)
+ ms.insert(str);
}
- ums_t ms;
- // Use a large load factor to make the context ideal for using hint because we
- // will have many elements per bucket.
- ms.max_load_factor(10.0f);
- ms.reserve(sz);
+ template<typename _Hash>
+ void
+ insert_range(const std::vector<std::string>& strs,
+ ums_t<_Hash>& ms)
+ { ms.insert(strs.begin(), strs.end()); }
+}
- // Warm up.
+template<typename _Hash>
+ void bench(const char* ctx)
{
- for (auto str : strs)
- for (int j = 0; j != nb_copies; ++j)
- ms.insert(str);
- }
-
- time_counter time_no_hint1, time_any_hint1, time_bad_hint, time_perfect_hint1;
- time_counter time_no_hint2, time_any_hint2, time_good_hint, time_perfect_hint2;
- resource_counter resource_no_hint1, resource_any_hint1, resource_bad_hint,
- resource_perfect_hint1;
- resource_counter resource_no_hint2, resource_any_hint2, resource_good_hint,
- resource_perfect_hint2;
-
- for (int i = 0; i != nb_iter; ++i)
- {
- // Bad hint
- {
- ms.clear();
- start_counters(time_bad_hint, resource_bad_hint);
- insert_with_bad_hint(strs, ms);
- stop_counters(time_bad_hint, resource_bad_hint);
- }
+ using namespace __gnu_test;
- // No hint
- {
- ms.clear();
- start_counters(time_no_hint1, resource_no_hint1);
- insert_without_hint1(strs, ms);
- stop_counters(time_no_hint1, resource_no_hint1);
- }
-
- // Any hint
- {
- ms.clear();
- start_counters(time_any_hint1, resource_any_hint1);
- insert_with_any_hint1(strs, ms);
- stop_counters(time_any_hint1, resource_any_hint1);
- }
+ const int nb_iter = 10;
- // Good hint
- {
- ms.clear();
- start_counters(time_good_hint, resource_good_hint);
- insert_with_good_hint(strs, ms);
- stop_counters(time_good_hint, resource_good_hint);
- }
-
- // No hint
- {
- ms.clear();
- start_counters(time_no_hint2, resource_no_hint2);
- insert_without_hint2(strs, ms);
- stop_counters(time_no_hint2, resource_no_hint2);
- }
+ std::vector<std::string> strs;
+ strs.reserve(sz);
- // Perfect hint
+ for (int i = 0; i != sz; ++i)
{
- ms.clear();
- start_counters(time_perfect_hint2, resource_perfect_hint2);
- insert_with_perfect_hint2(strs, ms);
- stop_counters(time_perfect_hint2, resource_perfect_hint2);
+ std::ostringstream osstr;
+ osstr << pattern << i;
+ strs.push_back(osstr.str());
}
- // Any hint
- {
- ms.clear();
- start_counters(time_any_hint2, resource_any_hint2);
- insert_with_any_hint2(strs, ms);
- stop_counters(time_any_hint2, resource_any_hint2);
- }
+ ums_t<_Hash> ms;
+ ms.reserve(sz);
- // Perfect hint
- {
- ms.clear();
- start_counters(time_perfect_hint1, resource_perfect_hint1);
- insert_with_perfect_hint1(strs, ms);
- stop_counters(time_perfect_hint1, resource_perfect_hint1);
- }
+ // Warm up.
+ {
+ for (auto str : strs)
+ ms.insert(str);
}
- std::ostringstream ostr;
- ostr << "unordered_set " << nb_copies << " X " << sz / nb_copies
- << " insertions w/o hint";
- report_performance(__FILE__, ostr.str().c_str(),
- time_no_hint1, resource_no_hint1);
-
- ostr.str("");
- ostr << "unordered_set " << nb_copies << " X " << sz / nb_copies
- << " insertions with any hint";
- report_performance(__FILE__, ostr.str().c_str(),
- time_any_hint1, resource_any_hint1);
+ time_counter time_no_hint, time_bad_hint, time_perfect_hint,
+ time_range;
+ resource_counter resource_no_hint, resource_bad_hint, resource_perfect_hint,
+ resource_range;
- ostr.str("");
- ostr << "unordered_set " << nb_copies << " X " << sz / nb_copies
- << " insertions with good hint";
- report_performance(__FILE__, ostr.str().c_str(),
- time_good_hint, resource_good_hint);
+ for (int i = 0; i != nb_iter; ++i)
+ {
+ // Bad hint
+ {
+ ms.clear();
+ start_counters(time_bad_hint, resource_bad_hint);
+ insert_with_bad_hint(strs, ms);
+ stop_counters(time_bad_hint, resource_bad_hint);
+ }
- ostr.str("");
- ostr << "unordered_set " << nb_copies << " X " << sz / nb_copies
- << " insertions with perfect hint";
- report_performance(__FILE__, ostr.str().c_str(),
- time_perfect_hint1, resource_perfect_hint1);
+ // No hint
+ {
+ ms.clear();
+ start_counters(time_no_hint, resource_no_hint);
+ insert_without_hint(strs, ms);
+ stop_counters(time_no_hint, resource_no_hint);
+ }
- ostr.str("");
- ostr << "unordered_set " << sz / nb_copies << " X " << nb_copies
- << " insertions w/o hint";
- report_performance(__FILE__, ostr.str().c_str(),
- time_no_hint2, resource_no_hint2);
+ // Perfect hint
+ {
+ ms.clear();
+ start_counters(time_perfect_hint, resource_perfect_hint);
+ insert_with_perfect_hint(strs, ms);
+ stop_counters(time_perfect_hint, resource_perfect_hint);
+ }
- ostr.str("");
- ostr << "unordered_set " << sz / nb_copies << " X " << nb_copies
- << " insertions with any hint";
- report_performance(__FILE__, ostr.str().c_str(),
- time_any_hint2, resource_any_hint2);
+ // Range insert
+ {
+ ms.clear();
+ start_counters(time_range, resource_range);
+ insert_range(strs, ms);
+ stop_counters(time_range, resource_range);
+ }
+ }
- ostr.str("");
- ostr << "unordered_set " << sz / nb_copies << " X " << nb_copies
- << " insertions with bad hint";
- report_performance(__FILE__, ostr.str().c_str(),
- time_bad_hint, resource_bad_hint);
+ std::ostringstream ostr;
+ ostr << ctx << ' ' << sz << " insertions w/o hint";
+ report_performance(__FILE__, ostr.str().c_str(),
+ time_no_hint, resource_no_hint);
+
+ ostr.str("");
+ ostr << ctx << ' ' << sz << " insertions with perfect hint";
+ report_performance(__FILE__, ostr.str().c_str(),
+ time_perfect_hint, resource_perfect_hint);
+
+ ostr.str("");
+ ostr << ctx << ' ' << sz << " insertions with bad hint";
+ report_performance(__FILE__, ostr.str().c_str(),
+ time_bad_hint, resource_bad_hint);
+
+ ostr.str("");
+ ostr << ctx << ' ' << sz << " range insertions";
+ report_performance(__FILE__, ostr.str().c_str(),
+ time_range, resource_range);
+ }
- ostr.str("");
- ostr << "unordered_set " << sz / nb_copies << " X " << nb_copies
- << " insertions with perfect hint";
- report_performance(__FILE__, ostr.str().c_str(),
- time_perfect_hint2, resource_perfect_hint2);
+int main()
+{
+ bench<hasher>("hash code NOT cached");
+ bench<slow_hasher>("hash code cached");
return 0;
}
new file mode 100644
@@ -0,0 +1,186 @@
+// { dg-do run { target c++11 } }
+
+#include <testsuite_performance.h>
+
+#include <sstream>
+#include <string>
+#include <vector>
+#include <unordered_set>
+
+namespace
+{
+ const int sz = 2000000;
+ const std::string pattern = "long enough test string #";
+
+ // Perfect std::string hasher knowing how string instances have been
+ // generated. It is not tag as slow so that hash code is not cached.
+ // It is easier to show impact of hint in this context.
+ struct hasher
+ {
+ std::size_t
+ operator()(const std::string& str) const noexcept
+ {
+ std::hash<std::string> std_hasher;
+ auto hash = std_hasher(pattern);
+ std::istringstream isstr(str.substr(pattern.length()));
+ int idx;
+ isstr >> idx;
+ return (std::size_t)(hash / sz) * sz + idx;
+ }
+ };
+
+ // Like previous hasher but tagged as slow.
+ struct slow_hasher
+ {
+ std::size_t
+ operator()(const std::string& str) const noexcept
+ { return hasher{}(str); }
+ };
+
+ template<typename _Hash>
+ using us_t = std::unordered_set<std::string, _Hash>;
+
+ template<typename _Hash>
+ void
+ insert_with_perfect_hint(const std::vector<std::string>& strs,
+ us_t<_Hash>& s)
+ {
+ auto hint = s.end();
+ for (auto str : strs)
+ {
+ auto insert_pos = s.insert(hint, str);
+ if (std::next(insert_pos) == s.end())
+ hint = insert_pos;
+ }
+ }
+
+ template<typename _Hash>
+ void
+ insert_with_bad_hint(const std::vector<std::string>& strs,
+ us_t<_Hash>& s)
+ {
+ auto hint = s.begin();
+ for (auto str : strs)
+ {
+ auto insert_pos = s.insert(hint, str);
+ if (std::next(insert_pos) == hint)
+ hint = s.begin();
+ }
+ }
+
+ template<typename _Hash>
+ void
+ insert_without_hint(const std::vector<std::string>& strs,
+ us_t<_Hash>& s)
+ {
+ for (auto str : strs)
+ s.insert(str);
+ }
+
+ template<typename _Hash>
+ void
+ insert_range(const std::vector<std::string>& strs,
+ us_t<_Hash>& s)
+ { s.insert(strs.begin(), strs.end()); }
+}
+
+template<typename _Hash>
+ void bench(const char* ctx)
+ {
+ using namespace __gnu_test;
+
+ const int nb_iter = 10;
+
+ std::vector<std::string> strs;
+ strs.reserve(sz);
+
+ for (int i = 0; i != sz; ++i)
+ {
+ std::ostringstream osstr;
+ osstr << pattern << i;
+ strs.push_back(osstr.str());
+ }
+
+ us_t<_Hash> s;
+ s.reserve(sz);
+
+ // Warm up.
+ {
+ for (auto str : strs)
+ s.insert(str);
+ }
+
+ time_counter time_no_hint, time_bad_hint, time_perfect_hint,
+ time_range;
+ resource_counter resource_no_hint, resource_bad_hint, resource_perfect_hint,
+ resource_range;
+
+ for (int i = 0; i != nb_iter; ++i)
+ {
+ // Bad hint
+ {
+ s.clear();
+ start_counters(time_bad_hint, resource_bad_hint);
+ insert_with_bad_hint(strs, s);
+ stop_counters(time_bad_hint, resource_bad_hint);
+ }
+
+ // No hint
+ {
+ s.clear();
+ start_counters(time_no_hint, resource_no_hint);
+ insert_without_hint(strs, s);
+ stop_counters(time_no_hint, resource_no_hint);
+ }
+
+ // Perfect hint
+ {
+ s.clear();
+ start_counters(time_perfect_hint, resource_perfect_hint);
+ insert_with_perfect_hint(strs, s);
+ stop_counters(time_perfect_hint, resource_perfect_hint);
+ }
+
+ // Range insert
+ {
+ s.clear();
+ start_counters(time_range, resource_range);
+ insert_range(strs, s);
+ stop_counters(time_range, resource_range);
+ }
+ }
+
+ std::ostringstream ostr;
+ ostr << ctx << ' ' << sz << " insertions w/o hint";
+ report_performance(__FILE__, ostr.str().c_str(),
+ time_no_hint, resource_no_hint);
+
+ ostr.str("");
+ ostr << ctx << ' ' << sz << " insertions with perfect hint";
+ report_performance(__FILE__, ostr.str().c_str(),
+ time_perfect_hint, resource_perfect_hint);
+
+ ostr.str("");
+ ostr << ctx << ' ' << sz << " insertions with bad hint";
+ report_performance(__FILE__, ostr.str().c_str(),
+ time_bad_hint, resource_bad_hint);
+
+ ostr.str("");
+ ostr << ctx << ' ' << sz << " range insertions";
+ report_performance(__FILE__, ostr.str().c_str(),
+ time_range, resource_range);
+ }
+
+namespace std
+{
+ template<>
+ struct __is_fast_hash<slow_hasher> : std::false_type
+ { };
+}
+
+int main()
+{
+ bench<hasher>("hash code NOT cached");
+ bench<slow_hasher>("hash code cached");
+ return 0;
+}
new file mode 100644
@@ -0,0 +1,211 @@
+// { dg-do run { target c++11 } }
+
+#include <testsuite_performance.h>
+
+#include <sstream>
+#include <string>
+#include <vector>
+#include <unordered_set>
+
+namespace
+{
+ const int sz = 2000000;
+ const std::string pattern = "long enough test string #";
+ const int nb_copies = 2;
+
+ // Perfect std::string hasher knowing how string instances have been
+ // generated. It is not tag as slow so that hash code is not cached.
+ // It is easier to show impact of hint in this context.
+ struct hasher
+ {
+ static int nb_calls;
+
+ std::size_t
+ operator()(const std::string& str) const noexcept
+ {
+ ++nb_calls;
+ std::hash<std::string> std_hasher;
+ auto hash = std_hasher(pattern);
+ std::istringstream isstr(str.substr(pattern.length()));
+ int idx = -1;
+ isstr >> idx;
+ if (idx != -1)
+ return (std::size_t)(hash / sz) * sz + idx;
+
+ return hash;
+ }
+ };
+
+ // Like previous hasher but tagged as slow.
+ struct slow_hasher
+ {
+ std::size_t
+ operator()(const std::string& str) const noexcept
+ { return hasher{}(str); }
+ };
+
+ int hasher::nb_calls = 0;
+
+ template<typename _Hash>
+ using us_t = std::unordered_set<std::string, _Hash>;
+
+ template<typename _Hash>
+ void
+ insert_once_individually(const std::vector<std::string>& strs,
+ us_t<_Hash>& s)
+ {
+ for (std::size_t i = 0; i != strs.size(); ++i)
+ s.insert(strs[i]);
+ }
+
+ template<typename _Hash>
+ void
+ insert_once_range(const std::vector<std::string>& strs,
+ us_t<_Hash>& s)
+ {
+ s.insert("initial string to not leave s empty");
+ s.insert(strs.begin(), strs.end());
+ }
+
+ template<typename _Hash>
+ void
+ insert_individually(const std::vector<std::string>& strs,
+ us_t<_Hash>& s)
+ {
+ for (int j = 1; j != nb_copies; ++j)
+ for (std::size_t i = 0; i != strs.size(); ++i)
+ s.insert(strs[i]);
+ }
+
+ template<typename _Hash>
+ void
+ insert_range(const std::vector<std::string>& strs,
+ us_t<_Hash>& s)
+ {
+ s.insert("initial string to not leave s empty");
+ for (int j = 1; j != nb_copies; ++j)
+ s.insert(strs.begin(), strs.end());
+ }
+}
+
+template<typename _Hash>
+ void bench(const char* ctx)
+ {
+ using namespace __gnu_test;
+
+ const int nb_iter = 10;
+
+ std::vector<std::string> strs;
+ strs.reserve(sz / nb_copies);
+
+ for (int i = 0; i != sz / nb_copies; ++i)
+ {
+ std::ostringstream osstr;
+ osstr << pattern << i;
+ strs.push_back(osstr.str());
+ }
+
+ us_t<_Hash> s;
+ s.reserve(sz / nb_copies);
+
+ // Warm up.
+ {
+ for (auto str : strs)
+ for (int j = 0; j != nb_copies; ++j)
+ s.insert(str);
+ }
+
+ int nb_calls_once_individually = 0;
+ int nb_calls_once_range = 0;
+ int nb_calls_individually = 0;
+ int nb_calls_range = 0;
+ time_counter time_once_individually, time_once_range;
+ time_counter time_individually, time_range;
+ resource_counter resource_once_individually, resource_once_range;
+ resource_counter resource_individually, resource_range;
+
+ for (int i = 0; i != nb_iter; ++i)
+ {
+ {
+ hasher::nb_calls = 0;
+ s.clear();
+ start_counters(time_once_individually, resource_once_individually);
+ insert_once_individually(strs, s);
+ stop_counters(time_once_individually, resource_once_individually);
+ nb_calls_once_individually += hasher::nb_calls;
+ }
+
+ {
+ hasher::nb_calls = 0;
+ s.clear();
+ start_counters(time_once_range, resource_once_range);
+ insert_once_range(strs, s);
+ stop_counters(time_once_range, resource_once_range);
+ nb_calls_once_range += hasher::nb_calls;
+ }
+
+ {
+ hasher::nb_calls = 0;
+ s.clear();
+ start_counters(time_individually, resource_individually);
+ insert_individually(strs, s);
+ stop_counters(time_individually, resource_individually);
+ nb_calls_individually += hasher::nb_calls;
+ }
+
+ {
+ hasher::nb_calls = 0;
+ s.clear();
+ start_counters(time_range, resource_range);
+ insert_range(strs, s);
+ stop_counters(time_range, resource_range);
+ nb_calls_range += hasher::nb_calls;
+ }
+ }
+
+ std::ostringstream ostr;
+ ostr << ctx << ' '
+ << nb_copies << " X " << sz / nb_copies << " inserts individually";
+ if (nb_calls_individually != 0)
+ ostr << ' ' << nb_calls_individually << " calls";
+ report_performance(__FILE__, ostr.str().c_str(),
+ time_individually, resource_individually);
+
+ ostr.str("");
+ ostr << ctx << ' '
+ << nb_copies << " X " << sz / nb_copies << " inserts in range";
+ if (nb_calls_range)
+ ostr << ' ' << nb_calls_range << " calls";
+ report_performance(__FILE__, ostr.str().c_str(),
+ time_range, resource_range);
+
+ ostr.str("");
+ ostr << ctx << ' '
+ << sz / nb_copies << " X inserts individually";
+ if (nb_calls_once_individually != 0)
+ ostr << ' ' << nb_calls_once_individually << " calls";
+ report_performance(__FILE__, ostr.str().c_str(),
+ time_once_individually, resource_once_individually);
+
+ ostr.str("");
+ ostr << ctx << ' '
+ << sz / nb_copies << " X inserts in range";
+ if (nb_calls_once_range != 0)
+ ostr << ' ' << nb_calls_once_range << " calls";
+ report_performance(__FILE__, ostr.str().c_str(),
+ time_once_range, resource_once_range);
+ }
+
+namespace std
+{
+ template<>
+ struct __is_fast_hash<slow_hasher> : std::false_type
+ { };
+}
+
+int main()
+{
+ bench<hasher>("hash code NOT cached");
+ bench<slow_hasher>("hash code cached");
+ return 0;
+}
@@ -26,10 +26,10 @@
namespace
{
const int nb_elements = 20;
- const int nb_insts = 150000;
+ const int nb_insts = 15000;
template<typename _ElemType>
- void bench(const char* desc, const std::vector<_ElemType>& elems)
+ void bench(const char* desc, const std::vector<_ElemType>& elems, bool with_copy)
{
using namespace __gnu_test;
@@ -52,6 +52,19 @@ namespace
ostr << desc << " 1st insert";
report_performance(__FILE__, ostr.str().c_str(), time, resource);
+ if (with_copy)
+ {
+ start_counters(time, resource);
+
+ std::vector<std::unordered_set<_ElemType>>(insts).swap(insts);
+
+ stop_counters(time, resource);
+
+ ostr.str("");
+ ostr << desc << " copy";
+ report_performance(__FILE__, ostr.str().c_str(), time, resource);
+ }
+
start_counters(time, resource);
for (auto& us : insts)
@@ -103,7 +116,8 @@ int main()
for (int i = 0; i != nb_elements; ++i)
elems.push_back(i);
- bench("std::unordered_set<int>: ", elems);
+ bench("std::unordered_set<int>: ", elems, false);
+ bench("std::unordered_set<int>: ", elems, true);
}
{
@@ -118,7 +132,8 @@ int main()
}
}
- bench("std::unordered_set<string>: ", elems);
+ bench("std::unordered_set<string>: ", elems, false);
+ bench("std::unordered_set<string>: ", elems, true);
}
return 0;