diff options
| -rw-r--r-- | libcxx/benchmarks/set_find.pass.cpp | 29 | ||||
| -rw-r--r-- | libcxx/include/__hash_table | 6 |
2 files changed, 33 insertions, 2 deletions
diff --git a/libcxx/benchmarks/set_find.pass.cpp b/libcxx/benchmarks/set_find.pass.cpp new file mode 100644 index 00000000000..32f90266dcc --- /dev/null +++ b/libcxx/benchmarks/set_find.pass.cpp @@ -0,0 +1,29 @@ +#include <unordered_set> +#include <vector> +#include <cstdint> + +#include "benchmark/benchmark_api.h" + +template <class IntT> +std::vector<IntT> getInputs(size_t N) { + std::vector<IntT> inputs; + for (size_t i=0; i < N; ++i) { + inputs.push_back(i); + } + return inputs; +} + +template <class Container, class Inputs> +void BM_SetLookup(benchmark::State& st, Container c, Inputs const& in) { + c.insert(in.begin(), in.end()); + const auto end = in.end(); + while (st.KeepRunning()) { + for (auto it = in.begin(); it != end; ++it) { + benchmark::DoNotOptimize(c.find(*it++)); + } + } +} +BENCHMARK_CAPTURE(BM_SetLookup, uint32_lookup, + std::unordered_set<uint32_t>{}, getInputs<uint32_t>(1024)); + +BENCHMARK_MAIN() diff --git a/libcxx/include/__hash_table b/libcxx/include/__hash_table index 6b93e848d5c..414019aa1fa 100644 --- a/libcxx/include/__hash_table +++ b/libcxx/include/__hash_table @@ -2201,7 +2201,8 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) if (__nd != nullptr) { for (__nd = __nd->__next_; __nd != nullptr && - __constrain_hash(__nd->__hash_, __bc) == __chash; + (__hash == __nd->__hash_ + || __constrain_hash(__nd->__hash_, __bc) == __chash); __nd = __nd->__next_) { if (key_eq()(__nd->__value_, __k)) @@ -2230,7 +2231,8 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const if (__nd != nullptr) { for (__nd = __nd->__next_; __nd != nullptr && - __constrain_hash(__nd->__hash_, __bc) == __chash; + (__hash == __nd->__hash_ + || __constrain_hash(__nd->__hash_, __bc) == __chash); __nd = __nd->__next_) { if (key_eq()(__nd->__value_, __k)) |
