Index: benchmarks/unordered_set_comp.bench.cpp =================================================================== --- /dev/null +++ benchmarks/unordered_set_comp.bench.cpp @@ -0,0 +1,263 @@ +// This benchmarks the difference between the old comparison (old_comp) +// and new comparison (is_permutation) methods for unordered multisets. + +#include +#include +#include + +#include "benchmark/benchmark.h" + +using namespace std; + +// util + +template +struct simple_rand // thanks @mclow for this :) +{ + static const size_t seed_from_clock = (size_t) -1; + simple_rand(T min, T max, size_t seed = seed_from_clock) : + gen_(seed != seed_from_clock + ? seed + : std::chrono::system_clock::now().time_since_epoch().count()), + dist_(min, max) {} + + T operator ()() { return dist_(gen_); } + + std::default_random_engine gen_; + std::uniform_int_distribution dist_; +}; + +std::string random_string(size_t size) +{ + auto random_char = []() -> char + { + const char char_set[] = + "0123456789" + "ABCDEFGHIJKLMNOPQRSTUVWXYZ" + "abcdefghijklmnopqrstuvwxyz"; + int max_index = sizeof(char_set) - 1; + simple_rand r(0, max_index); + return char_set[r()]; + }; + + std::string str(size, 0); + std::generate_n(str.begin(), size, random_char); + return str; +} + +// setup + +unordered_multiset u1; +unordered_multiset u2; + +unordered_multiset u1_diff; +unordered_multiset u2_diff; + +unordered_multiset u1_small; +unordered_multiset u2_small; + +unordered_multiset u1_small_range; +unordered_multiset u2_small_range; + +unordered_multiset u1_back; +unordered_multiset u2_back; + +unordered_multiset u1_rand; +unordered_multiset u2_rand; + +unordered_multiset u1_rand_diff; +unordered_multiset u2_rand_diff; + +unordered_multiset u1_str_diff; +unordered_multiset u2_str_diff; + +unordered_multiset u1_str_long; +unordered_multiset u2_str_long; + +unordered_multiset u1_str_short; +unordered_multiset u2_str_short; + +template +bool +new_comp(const unordered_multiset& x, + const unordered_multiset& y) +{ + return x == y; +} + +template +bool +old_comp(const unordered_multiset& x, + const unordered_multiset& y) +{ + if (x.size() != y.size()) + return false; + + typedef typename unordered_multiset::const_iterator const_iterator; + typedef pair pair_t; + for (const_iterator i = x.begin(), __ex = x.end(); i != __ex;) + { + pair_t xeq = x.equal_range(*i); + pair_t yeq = y.equal_range(*i); + if (std::distance(xeq.first, xeq.second) != + std::distance(yeq.first, yeq.second) || + !std::is_permutation(xeq.first, xeq.second, yeq.first)) + return false; + i = xeq.second; + } + return true; +} + +void initialize_data(benchmark::State&) +{ + // large set + for (unsigned i = 0; i < 1000 * 1000; ++i) + { + u1.insert(i); + u2.insert(i); + } + for (unsigned i = 0; i < 1000; ++i) + { + u1.insert(i % 10); + u2.insert(i % 10); + } + + u1_diff = u1; + u2_diff = u2; + for (unsigned i = 0; i < 100; ++i) + { + u1_diff.insert(i); + u2_diff.insert(0); + } + + // small set + for (unsigned i = 0; i < 500; ++i) + { + u1_small.insert(i); + u2_small.insert(i); + } + for (unsigned i = 0; i < 500; ++i) + { + u1_small.insert(i % 10); + u2_small.insert(i % 10); + } + + // small range + for (unsigned i = 0; i < 1000; ++i) + { + u1_small_range.insert(i % 2); + u2_small_range.insert(i % 2); + } + + // back / front + for (unsigned i = 0; i < 1000 * 1000; ++i) + { + u1_back.insert(i); + u2_back.insert((1000 * 1000) - i); + } + for (unsigned i = 1000 * 1000; i > 0; --i) + { + u1_back.insert(i); + u2_back.insert((1000 * 1000) - i); + } + + // random fill + simple_rand r(1, 1000); + for (unsigned i = 0; i < 1000 * 100; ++i) + { + int value = r(); + u1_rand.insert(value); + u2_rand.insert(value); + } + + for (unsigned i = 0; i < 1000 * 50; ++i) + { + u1_rand_diff.insert(r()); + u2_rand_diff.insert(r()); + } + + // string set + for (unsigned i = 0; i < 1000 * 10; ++i) + { + std::string str = random_string(5); + u1_str_short.insert(str); + u2_str_short.insert(str); + } + + for (unsigned i = 0; i < 1000 * 10; ++i) + { + std::string str = random_string(100); + u1_str_long.insert(str); + u2_str_long.insert(str); + } + + for (unsigned i = 0; i < 1000 * 10; ++i) + { + u1_str_diff.insert(random_string(12)); + u2_str_diff.insert(random_string(12)); + } +} + +// benchmarks + +template +void test_old(benchmark::State& st, unordered_multiset u1, unordered_multiset u2) +{ + while (st.KeepRunning()) { + bool val = old_comp(u1, u2); + benchmark::DoNotOptimize(val); + } +} + +template +void test_new(benchmark::State& st, unordered_multiset u1, unordered_multiset u2) +{ + while (st.KeepRunning()) { + bool val = new_comp(u1, u2); + benchmark::DoNotOptimize(val); + } +} + +BENCHMARK(initialize_data); // TODO: how do I initialize this? + +// tests a small set (1000 items, 50 items overlap) +BENCHMARK_CAPTURE(test_old, OLD_compare_small_set, u1_small, u2_small); +BENCHMARK_CAPTURE(test_new, NEW_compare_small_set, u1_small, u2_small); + +// tests a small set (1000 items, 500 items overlap) +BENCHMARK_CAPTURE(test_old, OLD_compare_similar_set, u1_small_range, u2_small_range); +BENCHMARK_CAPTURE(test_new, NEW_compare_similar_set, u1_small_range, u2_small_range); + +// tests a big set (1,000,000 items, 100 items overlap) +BENCHMARK_CAPTURE(test_old, OLD_compare_big_set, u1, u2); +BENCHMARK_CAPTURE(test_new, NEW_compare_big_set, u1, u2); + +// tests a big set (1,000,000 items, 100 items overlap, 100 items different) +BENCHMARK_CAPTURE(test_old, OLD_compare_big_set_different, u1_diff, u2_diff); +BENCHMARK_CAPTURE(test_new, NEW_compare_big_set_different, u1_diff, u2_diff); + +// tests a big set (2,000,000 items, items are inserted in reverse order, 1,000,000 items overlap) +BENCHMARK_CAPTURE(test_old, OLD_compare_oposite_order_set, u1_back, u2_back); +BENCHMARK_CAPTURE(test_new, NEW_compare_oposite_order_set, u1_back, u2_back); + +// tests a random set (100,000 items, range from 0 to 1000) +BENCHMARK_CAPTURE(test_old, OLD_compare_random_set, u1_rand, u2_rand); +BENCHMARK_CAPTURE(test_new, NEW_compare_random_set, u1_rand, u2_rand); + +// tests a random set (50,000 items, range from 0 to 1000, each different) +BENCHMARK_CAPTURE(test_old, OLD_compare_random_set_different, u1_rand_diff, u2_rand_diff); +BENCHMARK_CAPTURE(test_new, NEW_compare_random_set_different, u1_rand_diff, u2_rand_diff); + +// tests a random set of strings (10,000 items, random strings, 5 chars) +BENCHMARK_CAPTURE(test_old, OLD_compare_short_string, u1_str_short, u2_str_short); +BENCHMARK_CAPTURE(test_new, NEW_compare_short_string, u1_str_short, u2_str_short); + +// tests a random set of strings (10,000 items, random strings, 100 chars) +BENCHMARK_CAPTURE(test_old, OLD_compare_long_string, u1_str_long, u2_str_long); +BENCHMARK_CAPTURE(test_new, NEW_compare_long_string, u1_str_long, u2_str_long); + +// tests a random set of strings (10,000 items, random strings, 12 chars, not necessarily the same in both sets) +BENCHMARK_CAPTURE(test_old, OLD_compare_different_strings, u1_str_diff, u2_str_diff); +BENCHMARK_CAPTURE(test_new, NEW_compare_different_strings, u1_str_diff, u2_str_diff); + +BENCHMARK_MAIN(); Index: include/unordered_map =================================================================== --- include/unordered_map +++ include/unordered_map @@ -79,12 +79,12 @@ unordered_map(InputIterator f, InputIterator l, size_type n, const allocator_type& a) : unordered_map(f, l, n, hasher(), key_equal(), a) {} // C++14 template - unordered_map(InputIterator f, InputIterator l, size_type n, const hasher& hf, + unordered_map(InputIterator f, InputIterator l, size_type n, const hasher& hf, const allocator_type& a) : unordered_map(f, l, n, hf, key_equal(), a) {} // C++14 unordered_map(initializer_list il, size_type n, const allocator_type& a) : unordered_map(il, n, hasher(), key_equal(), a) {} // C++14 - unordered_map(initializer_list il, size_type n, const hasher& hf, + unordered_map(initializer_list il, size_type n, const hasher& hf, const allocator_type& a) : unordered_map(il, n, hf, key_equal(), a) {} // C++14 ~unordered_map(); @@ -277,12 +277,12 @@ unordered_multimap(InputIterator f, InputIterator l, size_type n, const allocator_type& a) : unordered_multimap(f, l, n, hasher(), key_equal(), a) {} // C++14 template - unordered_multimap(InputIterator f, InputIterator l, size_type n, const hasher& hf, + unordered_multimap(InputIterator f, InputIterator l, size_type n, const hasher& hf, const allocator_type& a) : unordered_multimap(f, l, n, hf, key_equal(), a) {} // C++14 unordered_multimap(initializer_list il, size_type n, const allocator_type& a) : unordered_multimap(il, n, hasher(), key_equal(), a) {} // C++14 - unordered_multimap(initializer_list il, size_type n, const hasher& hf, + unordered_multimap(initializer_list il, size_type n, const hasher& hf, const allocator_type& a) : unordered_multimap(il, n, hf, key_equal(), a) {} // C++14 ~unordered_multimap(); @@ -951,14 +951,14 @@ : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) {} template _LIBCPP_INLINE_VISIBILITY - unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, + unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a) : unordered_map(__first, __last, __n, __hf, key_equal(), __a) {} _LIBCPP_INLINE_VISIBILITY unordered_map(initializer_list __il, size_type __n, const allocator_type& __a) : unordered_map(__il, __n, hasher(), key_equal(), __a) {} _LIBCPP_INLINE_VISIBILITY - unordered_map(initializer_list __il, size_type __n, const hasher& __hf, + unordered_map(initializer_list __il, size_type __n, const hasher& __hf, const allocator_type& __a) : unordered_map(__il, __n, __hf, key_equal(), __a) {} #endif @@ -1644,13 +1644,13 @@ { if (__x.size() != __y.size()) return false; - typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator - const_iterator; - for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); - __i != __ex; ++__i) + typedef + typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator + const_iterator; + for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex; ++__i) { - const_iterator __j = __y.find(__i->first); - if (__j == __ey || !(*__i == *__j)) + const_iterator __found = __y.find(__i->first); + if (__found == __y.end() || !(*__found == *__i)) return false; } return true; @@ -1778,14 +1778,14 @@ : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) {} template _LIBCPP_INLINE_VISIBILITY - unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, + unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a) : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) {} _LIBCPP_INLINE_VISIBILITY unordered_multimap(initializer_list __il, size_type __n, const allocator_type& __a) : unordered_multimap(__il, __n, hasher(), key_equal(), __a) {} _LIBCPP_INLINE_VISIBILITY - unordered_multimap(initializer_list __il, size_type __n, const hasher& __hf, + unordered_multimap(initializer_list __il, size_type __n, const hasher& __hf, const allocator_type& __a) : unordered_multimap(__il, __n, __hf, key_equal(), __a) {} #endif @@ -2271,16 +2271,26 @@ { if (__x.size() != __y.size()) return false; - typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator - const_iterator; - typedef pair _EqRng; - for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) + + auto __first1 = __x.begin(); + auto __last1 = __x.end(); + auto __first2 = __y.begin(); + for (; __first1 != __last1; ++__first1, (void) ++__first2) + if (!(*__first1 == *__first2)) + goto __not_done; + return true; + +__not_done: + typedef + typename _VSTD::unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator + const_iterator; + typedef _VSTD::pair _EqRng; + for (const_iterator __i = __first1; __i != __x.end();) { _EqRng __xeq = __x.equal_range(__i->first); _EqRng __yeq = __y.equal_range(__i->first); if (_VSTD::distance(__xeq.first, __xeq.second) != - _VSTD::distance(__yeq.first, __yeq.second) || - !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) + _VSTD::distance(__yeq.first, __yeq.second)) return false; __i = __xeq.second; } Index: include/unordered_set =================================================================== --- include/unordered_set +++ include/unordered_set @@ -75,7 +75,7 @@ template unordered_set(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14 template - unordered_set(InputIterator f, InputIterator l, size_type n, + unordered_set(InputIterator f, InputIterator l, size_type n, const hasher& hf, const allocator_type& a); // C++14 unordered_set(initializer_list il, size_type n, const allocator_type& a); // C++14 unordered_set(initializer_list il, size_type n, @@ -242,7 +242,7 @@ unordered_multiset(InputIterator f, InputIterator l, size_type n, const hasher& hf, const allocator_type& a); // C++14 unordered_multiset(initializer_list il, size_type n, const allocator_type& a); // C++14 - unordered_multiset(initializer_list il, size_type n, + unordered_multiset(initializer_list il, size_type n, const hasher& hf, const allocator_type& a); // C++14 ~unordered_multiset(); unordered_multiset& operator=(const unordered_multiset&); @@ -450,11 +450,11 @@ #if _LIBCPP_STD_VER > 11 template inline _LIBCPP_INLINE_VISIBILITY - unordered_set(_InputIterator __first, _InputIterator __last, + unordered_set(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a) : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) {} template - unordered_set(_InputIterator __first, _InputIterator __last, + unordered_set(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a) : unordered_set(__first, __last, __n, __hf, key_equal(), __a) {} #endif @@ -480,7 +480,7 @@ const allocator_type& __a) : unordered_set(__il, __n, hasher(), key_equal(), __a) {} inline _LIBCPP_INLINE_VISIBILITY - unordered_set(initializer_list __il, size_type __n, + unordered_set(initializer_list __il, size_type __n, const hasher& __hf, const allocator_type& __a) : unordered_set(__il, __n, __hf, key_equal(), __a) {} #endif @@ -957,13 +957,12 @@ { if (__x.size() != __y.size()) return false; - typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator - const_iterator; - for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); - __i != __ex; ++__i) + typedef + typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator + const_iterator; + for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex; ++__i) { - const_iterator __j = __y.find(*__i); - if (__j == __ey || !(*__i == *__j)) + if (__y.find(*__i) == __y.end()) return false; } return true; @@ -1052,7 +1051,7 @@ #if _LIBCPP_STD_VER > 11 template inline _LIBCPP_INLINE_VISIBILITY - unordered_multiset(_InputIterator __first, _InputIterator __last, + unordered_multiset(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a) : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {} template @@ -1530,16 +1529,24 @@ { if (__x.size() != __y.size()) return false; - typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator - const_iterator; - typedef pair _EqRng; - for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) + auto __first1 = __x.begin(); + auto __last1 = __x.end(); + auto __first2 = __y.begin(); + for (; __first1 != __last1; ++__first1, (void) ++__first2) + if (!(*__first1 == *__first2)) + goto __not_done; + return true; +__not_done: + typedef + typename _VSTD::unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator + const_iterator; + typedef _VSTD::pair _EqRng; + for (const_iterator __i = __first1; __i != __x.end();) { _EqRng __xeq = __x.equal_range(*__i); _EqRng __yeq = __y.equal_range(*__i); if (_VSTD::distance(__xeq.first, __xeq.second) != - _VSTD::distance(__yeq.first, __yeq.second) || - !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) + _VSTD::distance(__yeq.first, __yeq.second)) return false; __i = __xeq.second; }