From a2419e63b8ae3b924152822f3c9f9da67ff6e215 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Wed, 23 Jun 2021 09:44:41 -0700 Subject: Export of internal Abseil changes -- 2684e80d877b688b8d9e0af1b7acddbadc973152 by Evan Brown : Add an insert codegen function for raw_hash_set_benchmark. PiperOrigin-RevId: 381052237 -- 8394ef3071714a41484cb5b271cba0611d954a7a by Abseil Team : Optimize raw_hash_set ctor for random-access iterators PiperOrigin-RevId: 380832215 GitOrigin-RevId: 2684e80d877b688b8d9e0af1b7acddbadc973152 Change-Id: Icf7929fdfab50a1b26f3dc5505575363b4f5838d --- absl/container/internal/raw_hash_set.h | 19 +++- absl/container/internal/raw_hash_set_benchmark.cc | 24 +++++ absl/container/internal/raw_hash_set_test.cc | 104 +++++++++++++++++++--- 3 files changed, 135 insertions(+), 12 deletions(-) diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index 508f2124..03f199a5 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h @@ -502,6 +502,22 @@ inline size_t GrowthToLowerboundCapacity(size_t growth) { return growth + static_cast((static_cast(growth) - 1) / 7); } +template +size_t SelectBucketCountForIterRange(InputIter first, InputIter last, + size_t bucket_count) { + if (bucket_count != 0) { + return bucket_count; + } + using InputIterCategory = + typename std::iterator_traits::iterator_category; + if (std::is_base_of::value) { + return GrowthToLowerboundCapacity( + static_cast(std::distance(first, last))); + } + return 0; +} + inline void AssertIsFull(ctrl_t* ctrl) { ABSL_HARDENING_ASSERT((ctrl != nullptr && IsFull(*ctrl)) && "Invalid operation on iterator. The element might have " @@ -820,7 +836,8 @@ class raw_hash_set { raw_hash_set(InputIter first, InputIter last, size_t bucket_count = 0, const hasher& hash = hasher(), const key_equal& eq = key_equal(), const allocator_type& alloc = allocator_type()) - : raw_hash_set(bucket_count, hash, eq, alloc) { + : raw_hash_set(SelectBucketCountForIterRange(first, last, bucket_count), + hash, eq, alloc) { insert(first, last); } diff --git a/absl/container/internal/raw_hash_set_benchmark.cc b/absl/container/internal/raw_hash_set_benchmark.cc index f9be2c5a..977ff4c0 100644 --- a/absl/container/internal/raw_hash_set_benchmark.cc +++ b/absl/container/internal/raw_hash_set_benchmark.cc @@ -254,6 +254,23 @@ void BM_CopyAssign(benchmark::State& state) { } BENCHMARK(BM_CopyAssign)->Range(128, 4096); +void BM_RangeCtor(benchmark::State& state) { + std::random_device rd; + std::mt19937 rng(rd()); + std::uniform_int_distribution dist(0, ~uint64_t{}); + std::vector values; + const size_t desired_size = state.range(0); + while (values.size() < desired_size) { + values.emplace_back(dist(rng)); + } + + for (auto unused : state) { + IntTable t{values.begin(), values.end()}; + benchmark::DoNotOptimize(t); + } +} +BENCHMARK(BM_RangeCtor)->Range(128, 65536); + void BM_NoOpReserveIntTable(benchmark::State& state) { IntTable t; t.reserve(100000); @@ -378,6 +395,12 @@ bool CodegenAbslRawHashSetInt64FindNeEnd( return table->find(key) != table->end(); } +auto CodegenAbslRawHashSetInt64Insert(absl::container_internal::IntTable* table, + int64_t key) + -> decltype(table->insert(key)) { + return table->insert(key); +} + bool CodegenAbslRawHashSetInt64Contains( absl::container_internal::IntTable* table, int64_t key) { return table->contains(key); @@ -391,6 +414,7 @@ void CodegenAbslRawHashSetInt64Iterate( int odr = (::benchmark::DoNotOptimize(std::make_tuple( &CodegenAbslRawHashSetInt64Find, &CodegenAbslRawHashSetInt64FindNeEnd, + &CodegenAbslRawHashSetInt64Insert, &CodegenAbslRawHashSetInt64Contains, &CodegenAbslRawHashSetInt64Iterate)), 1); diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc index 87cbdfcc..a191bff9 100644 --- a/absl/container/internal/raw_hash_set_test.cc +++ b/absl/container/internal/raw_hash_set_test.cc @@ -627,28 +627,53 @@ TEST(Table, Contains2) { } int decompose_constructed; +int decompose_copy_constructed; +int decompose_copy_assigned; +int decompose_move_constructed; +int decompose_move_assigned; struct DecomposeType { - DecomposeType(int i) : i(i) { // NOLINT + DecomposeType(int i = 0) : i(i) { // NOLINT ++decompose_constructed; } explicit DecomposeType(const char* d) : DecomposeType(*d) {} + DecomposeType(const DecomposeType& other) : i(other.i) { + ++decompose_copy_constructed; + } + DecomposeType& operator=(const DecomposeType& other) { + ++decompose_copy_assigned; + i = other.i; + return *this; + } + DecomposeType(DecomposeType&& other) : i(other.i) { + ++decompose_move_constructed; + } + DecomposeType& operator=(DecomposeType&& other) { + ++decompose_move_assigned; + i = other.i; + return *this; + } + int i; }; struct DecomposeHash { using is_transparent = void; - size_t operator()(DecomposeType a) const { return a.i; } + size_t operator()(const DecomposeType& a) const { return a.i; } size_t operator()(int a) const { return a; } size_t operator()(const char* a) const { return *a; } }; struct DecomposeEq { using is_transparent = void; - bool operator()(DecomposeType a, DecomposeType b) const { return a.i == b.i; } - bool operator()(DecomposeType a, int b) const { return a.i == b; } - bool operator()(DecomposeType a, const char* b) const { return a.i == *b; } + bool operator()(const DecomposeType& a, const DecomposeType& b) const { + return a.i == b.i; + } + bool operator()(const DecomposeType& a, int b) const { return a.i == b; } + bool operator()(const DecomposeType& a, const char* b) const { + return a.i == *b; + } }; struct DecomposePolicy { @@ -658,9 +683,9 @@ struct DecomposePolicy { template static void construct(void*, DecomposeType* slot, T&& v) { - *slot = DecomposeType(std::forward(v)); + ::new (slot) DecomposeType(std::forward(v)); } - static void destroy(void*, DecomposeType*) {} + static void destroy(void*, DecomposeType* slot) { slot->~DecomposeType(); } static DecomposeType& element(slot_type* slot) { return *slot; } template @@ -675,8 +700,13 @@ void TestDecompose(bool construct_three) { const int one = 1; const char* three_p = "3"; const auto& three = three_p; + const int elem_vector_count = 256; + std::vector elem_vector(elem_vector_count, DecomposeType{0}); + std::iota(elem_vector.begin(), elem_vector.end(), 0); - raw_hash_set> set1; + using DecomposeSet = + raw_hash_set>; + DecomposeSet set1; decompose_constructed = 0; int expected_constructed = 0; @@ -734,20 +764,72 @@ void TestDecompose(bool construct_three) { expected_constructed += construct_three; EXPECT_EQ(expected_constructed, decompose_constructed); } + + decompose_copy_constructed = 0; + decompose_copy_assigned = 0; + decompose_move_constructed = 0; + decompose_move_assigned = 0; + int expected_copy_constructed = 0; + int expected_move_constructed = 0; + { // raw_hash_set(first, last) with random-access iterators + DecomposeSet set2(elem_vector.begin(), elem_vector.end()); + // Expect exactly one copy-constructor call for each element if no + // rehashing is done. + expected_copy_constructed += elem_vector_count; + EXPECT_EQ(expected_copy_constructed, decompose_copy_constructed); + EXPECT_EQ(expected_move_constructed, decompose_move_constructed); + EXPECT_EQ(0, decompose_move_assigned); + EXPECT_EQ(0, decompose_copy_assigned); + } + + { // raw_hash_set(first, last) with forward iterators + std::list elem_list(elem_vector.begin(), elem_vector.end()); + expected_copy_constructed = decompose_copy_constructed; + DecomposeSet set2(elem_list.begin(), elem_list.end()); + // Expect exactly N elements copied into set, expect at most 2*N elements + // moving internally for all resizing needed (for a growth factor of 2). + expected_copy_constructed += elem_vector_count; + EXPECT_EQ(expected_copy_constructed, decompose_copy_constructed); + expected_move_constructed += elem_vector_count; + EXPECT_LT(expected_move_constructed, decompose_move_constructed); + expected_move_constructed += elem_vector_count; + EXPECT_GE(expected_move_constructed, decompose_move_constructed); + EXPECT_EQ(0, decompose_move_assigned); + EXPECT_EQ(0, decompose_copy_assigned); + expected_copy_constructed = decompose_copy_constructed; + expected_move_constructed = decompose_move_constructed; + } + + { // insert(first, last) + DecomposeSet set2; + set2.insert(elem_vector.begin(), elem_vector.end()); + // Expect exactly N elements copied into set, expect at most 2*N elements + // moving internally for all resizing needed (for a growth factor of 2). + const int expected_new_elements = elem_vector_count; + const int expected_max_element_moves = 2 * elem_vector_count; + expected_copy_constructed += expected_new_elements; + EXPECT_EQ(expected_copy_constructed, decompose_copy_constructed); + expected_move_constructed += expected_max_element_moves; + EXPECT_GE(expected_move_constructed, decompose_move_constructed); + EXPECT_EQ(0, decompose_move_assigned); + EXPECT_EQ(0, decompose_copy_assigned); + expected_copy_constructed = decompose_copy_constructed; + expected_move_constructed = decompose_move_constructed; + } } TEST(Table, Decompose) { TestDecompose(false); struct TransparentHashIntOverload { - size_t operator()(DecomposeType a) const { return a.i; } + size_t operator()(const DecomposeType& a) const { return a.i; } size_t operator()(int a) const { return a; } }; struct TransparentEqIntOverload { - bool operator()(DecomposeType a, DecomposeType b) const { + bool operator()(const DecomposeType& a, const DecomposeType& b) const { return a.i == b.i; } - bool operator()(DecomposeType a, int b) const { return a.i == b; } + bool operator()(const DecomposeType& a, int b) const { return a.i == b; } }; TestDecompose(true); TestDecompose(true); -- cgit v1.2.3