From 1a06fe5f7ea47112a5e8ac6e0cc471ef96759591 Mon Sep 17 00:00:00 2001
From: Eric Fiselier <eric@efcs.ca>
Date: Sun, 24 Jul 2016 06:22:25 +0000
Subject: [PATCH] Skip chash computation in insert/emplace if the unconstrained
 hash matches.

llvm-svn: 276549
---
 libcxx/benchmarks/ContainerBenchmarks.hpp          | 32 ++++++++++++++++++
 libcxx/benchmarks/GenerateInput.hpp                |  7 ++++
 .../benchmarks/unordered_set_operations.bench.cpp  | 38 ++++++++++++++++++++++
 libcxx/include/__hash_table                        |  2 +-
 4 files changed, 78 insertions(+), 1 deletion(-)

diff --git a/libcxx/benchmarks/ContainerBenchmarks.hpp b/libcxx/benchmarks/ContainerBenchmarks.hpp
index d6107f6..8321caf 100644
--- a/libcxx/benchmarks/ContainerBenchmarks.hpp
+++ b/libcxx/benchmarks/ContainerBenchmarks.hpp
@@ -34,6 +34,38 @@ void BM_InsertValueRehash(benchmark::State& st, Container c, GenInputs gen) {
     }
 }
 
+
+template <class Container, class GenInputs>
+void BM_InsertDuplicate(benchmark::State& st, Container c, GenInputs gen) {
+    auto in = gen(st.range_x());
+    const auto end = in.end();
+    c.insert(in.begin(), in.end());
+    benchmark::DoNotOptimize(&c);
+    benchmark::DoNotOptimize(&in);
+    while (st.KeepRunning()) {
+        for (auto it = in.begin(); it != end; ++it) {
+            benchmark::DoNotOptimize(&(*c.insert(*it).first));
+        }
+        benchmark::ClobberMemory();
+    }
+}
+
+
+template <class Container, class GenInputs>
+void BM_EmplaceDuplicate(benchmark::State& st, Container c, GenInputs gen) {
+    auto in = gen(st.range_x());
+    const auto end = in.end();
+    c.insert(in.begin(), in.end());
+    benchmark::DoNotOptimize(&c);
+    benchmark::DoNotOptimize(&in);
+    while (st.KeepRunning()) {
+        for (auto it = in.begin(); it != end; ++it) {
+            benchmark::DoNotOptimize(&(*c.emplace(*it).first));
+        }
+        benchmark::ClobberMemory();
+    }
+}
+
 template <class Container, class GenInputs>
 static void BM_Find(benchmark::State& st, Container c, GenInputs gen) {
     auto in = gen(st.range_x());
diff --git a/libcxx/benchmarks/GenerateInput.hpp b/libcxx/benchmarks/GenerateInput.hpp
index 5ddda76..49fb48d 100644
--- a/libcxx/benchmarks/GenerateInput.hpp
+++ b/libcxx/benchmarks/GenerateInput.hpp
@@ -130,4 +130,11 @@ inline std::vector<std::string> getReverseSortedStringInputs(size_t N) {
     return inputs;
 }
 
+inline std::vector<const char*> getRandomCStringInputs(size_t N) {
+    static std::vector<std::string> inputs = getRandomStringInputs(N);
+    std::vector<const char*> cinputs;
+    for (auto const& str : inputs)
+        cinputs.push_back(str.c_str());
+    return cinputs;
+}
 #endif // BENCHMARK_GENERATE_INPUT_HPP
diff --git a/libcxx/benchmarks/unordered_set_operations.bench.cpp b/libcxx/benchmarks/unordered_set_operations.bench.cpp
index ab737c1..8c44638 100644
--- a/libcxx/benchmarks/unordered_set_operations.bench.cpp
+++ b/libcxx/benchmarks/unordered_set_operations.bench.cpp
@@ -265,4 +265,42 @@ BENCHMARK_CAPTURE(BM_FindRehash,
     std::unordered_set<std::string>{},
     getRandomStringInputs)->Arg(TestNumInputs);
 
+///////////////////////////////////////////////////////////////////////////////
+BENCHMARK_CAPTURE(BM_InsertDuplicate,
+    unordered_set_int,
+    std::unordered_set<int>{},
+    getRandomIntegerInputs<int>)->Arg(TestNumInputs);
+BENCHMARK_CAPTURE(BM_InsertDuplicate,
+    unordered_set_string,
+    std::unordered_set<std::string>{},
+    getRandomStringInputs)->Arg(TestNumInputs);
+
+BENCHMARK_CAPTURE(BM_EmplaceDuplicate,
+    unordered_set_int,
+    std::unordered_set<int>{},
+    getRandomIntegerInputs<int>)->Arg(TestNumInputs);
+BENCHMARK_CAPTURE(BM_EmplaceDuplicate,
+    unordered_set_string,
+    std::unordered_set<std::string>{},
+    getRandomStringInputs)->Arg(TestNumInputs);
+
+BENCHMARK_CAPTURE(BM_InsertDuplicate,
+    unordered_set_int_insert_arg,
+    std::unordered_set<int>{},
+    getRandomIntegerInputs<int>)->Arg(TestNumInputs);
+BENCHMARK_CAPTURE(BM_InsertDuplicate,
+    unordered_set_string_insert_arg,
+    std::unordered_set<std::string>{},
+    getRandomStringInputs)->Arg(TestNumInputs);
+
+BENCHMARK_CAPTURE(BM_EmplaceDuplicate,
+    unordered_set_int_insert_arg,
+    std::unordered_set<int>{},
+    getRandomIntegerInputs<unsigned>)->Arg(TestNumInputs);
+
+BENCHMARK_CAPTURE(BM_EmplaceDuplicate,
+    unordered_set_string_arg,
+    std::unordered_set<std::string>{},
+    getRandomCStringInputs)->Arg(TestNumInputs);
+
 BENCHMARK_MAIN()
diff --git a/libcxx/include/__hash_table b/libcxx/include/__hash_table
index 0210c6f..6a0e6fe 100644
--- a/libcxx/include/__hash_table
+++ b/libcxx/include/__hash_table
@@ -1961,7 +1961,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_key_args(_Key const&
         if (__nd != nullptr)
         {
             for (__nd = __nd->__next_; __nd != nullptr &&
-                                       __constrain_hash(__nd->__hash(), __bc) == __chash;
+                (__nd->__hash() == __hash || __constrain_hash(__nd->__hash(), __bc) == __chash);
                                                            __nd = __nd->__next_)
             {
                 if (key_eq()(__nd->__upcast()->__value_, __k))
-- 
2.7.4