diff --git a/libcxx/benchmarks/ContainerBenchmarks.h b/libcxx/benchmarks/ContainerBenchmarks.h --- a/libcxx/benchmarks/ContainerBenchmarks.h +++ b/libcxx/benchmarks/ContainerBenchmarks.h @@ -179,6 +179,58 @@ } } +template +static void BM_Compare_same_container(benchmark::State& st, Container, GenInputs gen) { + auto in = gen(st.range(0)); + Container c1(in.begin(), in.end()); + Container c2 = c1; + + benchmark::DoNotOptimize(&(*c1.begin())); + benchmark::DoNotOptimize(&(*c2.begin())); + while (st.KeepRunning()) { + bool res = c1 == c2; + benchmark::DoNotOptimize(&res); + benchmark::ClobberMemory(); + } +} + +template +static void BM_Compare_different_containers(benchmark::State& st, Container, GenInputs gen) { + auto in1 = gen(st.range(0)); + auto in2 = gen(st.range(0)); + Container c1(in1.begin(), in1.end()); + Container c2(in2.begin(), in2.end()); + + benchmark::DoNotOptimize(&(*c1.begin())); + benchmark::DoNotOptimize(&(*c2.begin())); + while (st.KeepRunning()) { + bool res = c1 == c2; + benchmark::DoNotOptimize(&res); + benchmark::ClobberMemory(); + } +} + +template +static void BM_Compare_shared_prefix(benchmark::State& st, Container, GenInputs gen) { + auto in1 = gen(st.range(0)); + auto in2 = gen(st.range(0)); + // c1 and c2 both contain the first half of `in1`, but + // then c2 contains elements from `in2`. + Container c1(in1.begin(), in1.end()); + + std::size_t half = st.range(0) / 2; + Container c2(in1.begin(), in1.begin() + half); + c2.insert(in2.begin(), in2.begin() + half); + + benchmark::DoNotOptimize(&(*c1.begin())); + benchmark::DoNotOptimize(&(*c2.begin())); + while (st.KeepRunning()) { + bool res = c1 == c2; + benchmark::DoNotOptimize(&res); + benchmark::ClobberMemory(); + } +} + } // end namespace ContainerBenchmarks #endif // BENCHMARK_CONTAINER_BENCHMARKS_H diff --git a/libcxx/benchmarks/unordered_set_operations.bench.cpp b/libcxx/benchmarks/unordered_set_operations.bench.cpp --- a/libcxx/benchmarks/unordered_set_operations.bench.cpp +++ b/libcxx/benchmarks/unordered_set_operations.bench.cpp @@ -290,6 +290,32 @@ BENCHMARK_CAPTURE(BM_Rehash, unordered_set_int_arg, std::unordered_set{}, getRandomIntegerInputs) ->Arg(TestNumInputs); +//----------------------------------------------------------------------------// +// BM_Compare +// ---------------------------------------------------------------------------// + +BENCHMARK_CAPTURE( + BM_Compare_same_container, unordered_set_string, std::unordered_set{}, getRandomStringInputs) + ->Arg(TestNumInputs); + +BENCHMARK_CAPTURE(BM_Compare_same_container, unordered_set_int, std::unordered_set{}, getRandomIntegerInputs) + ->Arg(TestNumInputs); + +BENCHMARK_CAPTURE( + BM_Compare_different_containers, unordered_set_string, std::unordered_set{}, getRandomStringInputs) + ->Arg(TestNumInputs); + +BENCHMARK_CAPTURE( + BM_Compare_different_containers, unordered_set_int, std::unordered_set{}, getRandomIntegerInputs) + ->Arg(TestNumInputs); + +BENCHMARK_CAPTURE( + BM_Compare_shared_prefix, unordered_set_string, std::unordered_set{}, getRandomStringInputs) + ->Arg(TestNumInputs); + +BENCHMARK_CAPTURE(BM_Compare_shared_prefix, unordered_set_int, std::unordered_set{}, getRandomIntegerInputs) + ->Arg(TestNumInputs); + /////////////////////////////////////////////////////////////////////////////// BENCHMARK_CAPTURE(BM_InsertDuplicate, unordered_set_int, std::unordered_set{}, getRandomIntegerInputs) ->Arg(TestNumInputs); diff --git a/libcxx/include/unordered_map b/libcxx/include/unordered_map --- a/libcxx/include/unordered_map +++ b/libcxx/include/unordered_map @@ -584,6 +584,7 @@ */ #include <__algorithm/is_permutation.h> +#include <__algorithm/mismatch.h> #include <__assert> // all public C++ headers provide the assertion handler #include <__availability> #include <__config> @@ -1990,11 +1991,16 @@ { 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) - { + using const_iterator = typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator; + using _IteratorRange = pair; + + // First advance both sequences until we find a mismatch. If the two unordered maps + // happen to be in the same order, this can be a lot faster than doing repeated lookups. + const_iterator const __xend = __x.end(); + _IteratorRange __mismatch = std::mismatch(__x.begin(), __xend, __y.begin()); + + // Then compare the "tail" of the unordered maps using repeated lookups. + for (const_iterator __i = __mismatch.first, __ey = __y.end(); __i != __xend; ++__i) { const_iterator __j = __y.find(__i->first); if (__j == __ey || !(*__i == *__j)) return false; @@ -2748,16 +2754,22 @@ { 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;) - { - _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)) + using const_iterator = typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator; + using _IteratorRange = pair; + + // First advance both sequences until we find a mismatch. If the two unordered multimaps + // happen to be in the same order, this can be a lot faster than doing repeated lookups. + const_iterator const __xend = __x.end(); + _IteratorRange __mismatch = std::mismatch(__x.begin(), __xend, __y.begin()); + + // Then compare the "tail" of the unordered multimaps using repeated lookups. + // Note that we need to check with std::is_permutation because equal_range only + // considers the keys, not the values. + for (const_iterator __i = __mismatch.first; __i != __xend;) { + _IteratorRange __xeq = __x.equal_range(__i->first); + _IteratorRange __yeq = __y.equal_range(__i->first); + 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; } diff --git a/libcxx/include/unordered_set b/libcxx/include/unordered_set --- a/libcxx/include/unordered_set +++ b/libcxx/include/unordered_set @@ -527,7 +527,7 @@ */ -#include <__algorithm/is_permutation.h> +#include <__algorithm/mismatch.h> #include <__assert> // all public C++ headers provide the assertion handler #include <__availability> #include <__config> @@ -1242,11 +1242,16 @@ { 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) - { + using const_iterator = typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator; + using _IteratorRange = pair; + + // First advance both sequences until we find a mismatch. If the two unordered sets + // happen to be in the same order, this can be a lot faster than doing repeated lookups. + const_iterator const __xend = __x.end(); + _IteratorRange __mismatch = std::mismatch(__x.begin(), __xend, __y.begin()); + + // Then compare the "tail" of the unordered sets using repeated lookups. + for (const_iterator __i = __mismatch.first, __ey = __y.end(); __i != __xend; ++__i) { const_iterator __j = __y.find(*__i); if (__j == __ey || !(*__i == *__j)) return false; @@ -1928,16 +1933,19 @@ { 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;) - { - _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)) + using const_iterator = typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator; + using _IteratorRange = pair; + + // First advance both sequences until we find a mismatch. If the two unordered multisets + // happen to be in the same order, this can be a lot faster than doing repeated lookups. + const_iterator const __xend = __x.end(); + _IteratorRange __mismatch = std::mismatch(__x.begin(), __xend, __y.begin()); + + // Then compare the "tail" of the unordered multisets using repeated lookups. + for (const_iterator __i = __mismatch.first; __i != __xend;) { + _IteratorRange __xeq = __x.equal_range(*__i); + _IteratorRange __yeq = __y.equal_range(*__i); + if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second)) return false; __i = __xeq.second; } diff --git a/libcxx/test/std/containers/unord/unord.multimap/eq.pass.cpp b/libcxx/test/std/containers/unord/unord.multimap/eq.pass.cpp --- a/libcxx/test/std/containers/unord/unord.multimap/eq.pass.cpp +++ b/libcxx/test/std/containers/unord/unord.multimap/eq.pass.cpp @@ -221,5 +221,30 @@ } #endif - return 0; + // Make sure we take into account the number of times that a key repeats into equality. + { + typedef std::pair P; + P a[] = {{1, 'a'}, {1, 'b'}, {1, 'd'}, {2, 'b'}}; + P b[] = {{1, 'a'}, {1, 'b'}, {1, 'b'}, {1, 'd'}, {2, 'b'}}; + + std::unordered_multimap c1(std::begin(a), std::end(a)); + std::unordered_multimap c2(std::begin(b), std::end(b)); + assert(testEquality(c1, c2, false)); + } + + // Make sure we incorporate the values into the equality of the maps. + // If we were to compare only the keys (including how many time each key repeats), + // the following test would fail cause only the values differ. + { + typedef std::pair P; + P a[] = {{1, 'a'}, {1, 'b'}, {1, 'd'}, {2, 'b'}}; + P b[] = {{1, 'a'}, {1, 'b'}, {1, 'E'}, {2, 'b'}}; + // ^ different here + + std::unordered_multimap c1(std::begin(a), std::end(a)); + std::unordered_multimap c2(std::begin(b), std::end(b)); + assert(testEquality(c1, c2, false)); + } + + return 0; } diff --git a/libcxx/test/std/containers/unord/unord.multiset/eq.pass.cpp b/libcxx/test/std/containers/unord/unord.multiset/eq.pass.cpp --- a/libcxx/test/std/containers/unord/unord.multiset/eq.pass.cpp +++ b/libcxx/test/std/containers/unord/unord.multiset/eq.pass.cpp @@ -24,6 +24,8 @@ #include "test_macros.h" #include "min_allocator.h" +#include "test_comparisons.h" + int main(int, char**) { { @@ -178,5 +180,16 @@ } #endif - return 0; + // Make sure we take into account the number of times that a key repeats into equality. + { + typedef int P; + P a[] = {P(1), P(1), P(1), P(2)}; + P b[] = {P(1), P(1), P(1), P(1), P(2)}; + + std::unordered_multiset c1(std::begin(a), std::end(a)); + std::unordered_multiset c2(std::begin(b), std::end(b)); + assert(testEquality(c1, c2, false)); + } + + return 0; }