Add `GtlReclaimExcessCapacity` customization point to `raw_hash_set` and compaction counters (`num_compactions` and `bytes_reclaimed`) to `HashtablezInfo`. PiperOrigin-RevId: 1014843548
diff --git a/absl/container/internal/hashtablez_sampler.cc b/absl/container/internal/hashtablez_sampler.cc index 82929bb..c23d6d5 100644 --- a/absl/container/internal/hashtablez_sampler.cc +++ b/absl/container/internal/hashtablez_sampler.cc
@@ -89,6 +89,8 @@ hashes_bitwise_or.store(0, std::memory_order_relaxed); hashes_bitwise_and.store(~size_t{}, std::memory_order_relaxed); max_reserve.store(0, std::memory_order_relaxed); + num_compactions.store(0, std::memory_order_relaxed); + bytes_reclaimed.store(0, std::memory_order_relaxed); create_time = absl::Now(); weight = stride; @@ -260,6 +262,17 @@ std::memory_order_relaxed); } +void RecordCompactionSlow(HashtablezInfo* info, size_t bytes) { + // There is only one concurrent writer, so `load` then `store` is sufficient + // instead of using `fetch_add`. + info->num_compactions.store( + 1 + info->num_compactions.load(std::memory_order_relaxed), + std::memory_order_relaxed); + info->bytes_reclaimed.store( + bytes + info->bytes_reclaimed.load(std::memory_order_relaxed), + std::memory_order_relaxed); +} + void SetHashtablezConfigListener(HashtablezConfigListener l) { g_hashtablez_config_listener.store(l, std::memory_order_release); }
diff --git a/absl/container/internal/hashtablez_sampler.h b/absl/container/internal/hashtablez_sampler.h index 540205e..d5d47e8 100644 --- a/absl/container/internal/hashtablez_sampler.h +++ b/absl/container/internal/hashtablez_sampler.h
@@ -89,6 +89,8 @@ std::atomic<size_t> hashes_bitwise_or; std::atomic<size_t> hashes_bitwise_and; std::atomic<size_t> max_reserve; + std::atomic<size_t> num_compactions; + std::atomic<size_t> bytes_reclaimed; // All of the fields below are set by `PrepareForSampling`, they must not be // mutated in `Record*` functions. They are logically `const` in that sense. @@ -123,6 +125,8 @@ void RecordEraseSlow(HashtablezInfo* info); +void RecordCompactionSlow(HashtablezInfo* info, size_t bytes); + struct SamplingState { int64_t next_sample; // When we make a sampling decision, we record that distance so we can weight @@ -184,6 +188,11 @@ RecordEraseSlow(info_); } + void RecordCompaction(size_t bytes) { + if (ABSL_PREDICT_TRUE(info_ == nullptr)) return; + RecordCompactionSlow(info_, bytes); + } + friend inline void swap(HashtablezInfoHandle& lhs, HashtablezInfoHandle& rhs) { std::swap(lhs.info_, rhs.info_); @@ -210,6 +219,7 @@ inline void RecordInsertMiss(size_t /*hash*/, size_t /*distance_from_desired*/) {} inline void RecordErase() {} + void RecordCompaction(size_t /*bytes*/) {} friend inline void swap(HashtablezInfoHandle& /*lhs*/, HashtablezInfoHandle& /*rhs*/) {}
diff --git a/absl/container/internal/hashtablez_sampler_test.cc b/absl/container/internal/hashtablez_sampler_test.cc index b61976d..5fab713 100644 --- a/absl/container/internal/hashtablez_sampler_test.cc +++ b/absl/container/internal/hashtablez_sampler_test.cc
@@ -107,6 +107,8 @@ EXPECT_EQ(info.hashes_bitwise_or.load(), 0); EXPECT_EQ(info.hashes_bitwise_and.load(), ~size_t{}); EXPECT_EQ(info.max_reserve.load(), 0); + EXPECT_EQ(info.num_compactions.load(std::memory_order_relaxed), 0); + EXPECT_EQ(info.bytes_reclaimed.load(std::memory_order_relaxed), 0); EXPECT_GE(info.create_time, test_start); EXPECT_EQ(info.weight, test_stride); EXPECT_EQ(info.inline_element_size, test_element_size); @@ -122,6 +124,8 @@ info.hashes_bitwise_or.store(1, std::memory_order_relaxed); info.hashes_bitwise_and.store(1, std::memory_order_relaxed); info.max_reserve.store(1, std::memory_order_relaxed); + info.num_compactions.store(3, std::memory_order_relaxed); + info.bytes_reclaimed.store(1024, std::memory_order_relaxed); info.create_time = test_start - absl::Hours(20); info.PrepareForSampling(test_stride * 2, test_element_size, @@ -137,6 +141,8 @@ EXPECT_EQ(info.hashes_bitwise_or.load(), 0); EXPECT_EQ(info.hashes_bitwise_and.load(), ~size_t{}); EXPECT_EQ(info.max_reserve.load(), 0); + EXPECT_EQ(info.num_compactions.load(std::memory_order_relaxed), 0); + EXPECT_EQ(info.bytes_reclaimed.load(std::memory_order_relaxed), 0); EXPECT_EQ(info.weight, 2 * test_stride); EXPECT_EQ(info.inline_element_size, test_element_size); EXPECT_EQ(info.key_size, test_key_size); @@ -253,6 +259,38 @@ EXPECT_EQ(info.soo_capacity, 0); } +TEST(HashtablezInfoTest, RecordCompaction) { + HashtablezInfo info; + absl::MutexLock l(info.init_mu); + const int64_t test_stride = 37; + const size_t test_element_size = 32; + const size_t test_key_size = 16; + const size_t test_value_size = 16; + + info.PrepareForSampling(test_stride, test_element_size, + /*key_size=*/test_key_size, + /*value_size=*/test_value_size, + /*soo_capacity_value=*/0); + EXPECT_EQ(info.num_compactions.load(std::memory_order_relaxed), 0); + EXPECT_EQ(info.bytes_reclaimed.load(std::memory_order_relaxed), 0); + + RecordCompactionSlow(&info, /*bytes=*/100); + EXPECT_EQ(info.num_compactions.load(std::memory_order_relaxed), 1); + EXPECT_EQ(info.bytes_reclaimed.load(std::memory_order_relaxed), 100); + + RecordCompactionSlow(&info, /*bytes=*/50); + EXPECT_EQ(info.num_compactions.load(std::memory_order_relaxed), 2); + EXPECT_EQ(info.bytes_reclaimed.load(std::memory_order_relaxed), 100 + 50); + +#if defined(ABSL_INTERNAL_HASHTABLEZ_SAMPLE) + HashtablezInfoHandle handle(&info); + handle.RecordCompaction(/*bytes=*/25); + EXPECT_EQ(info.num_compactions.load(std::memory_order_relaxed), 3); + EXPECT_EQ(info.bytes_reclaimed.load(std::memory_order_relaxed), + 100 + 50 + 25); +#endif +} + TEST(HashtablezInfoTest, RecordReservation) { HashtablezInfo info; absl::MutexLock l(info.init_mu);
diff --git a/absl/container/internal/raw_hash_set.cc b/absl/container/internal/raw_hash_set.cc index bd36659..0b5839d 100644 --- a/absl/container/internal/raw_hash_set.cc +++ b/absl/container/internal/raw_hash_set.cc
@@ -2482,6 +2482,39 @@ } } +void ReclaimExcessCapacityImpl(CommonFields& common, + const PolicyFunctions& __restrict policy) { + const size_t old_capacity = common.capacity(); + if (!common.empty() && is_single_group(old_capacity)) return; + + const size_t soo_capacity = policy.alloc_policy->soo_capacity(); + const size_t size = common.size(); + + // For tables that fit within SOO capacity (or are empty), `Rehash(..., 0)` + // shrinks to `soo_capacity` (or `NextCapacity(soo_capacity)` for a sampled + // 1-element SOO table to preserve Hashtablez sampling). + // For larger tables, keep one capacity doubling tier of growth headroom + // (`NextCapacity(SizeToCapacity(size))`) so subsequent insertions do not + // immediately trigger a rehash. + size_t target_capacity; + if (size > soo_capacity) { + target_capacity = NextCapacity(SizeToCapacity(size)); + } else if (size > 0 && common.has_infoz()) { + target_capacity = NextCapacity(soo_capacity); + } else { + target_capacity = soo_capacity; + } + if (old_capacity <= target_capacity) return; + + common.infoz().RecordCompaction( + (old_capacity - target_capacity) * policy.slot_size); + if (size <= soo_capacity) { + Rehash(common, policy, 0); + } else { + ResizeAllocatedTableWithSeedChange(common, policy, target_capacity); + } +} + void Copy(CommonFields& common, const PolicyFunctions& __restrict policy, const CommonFields& other, void (*copy_fn)(void* set, void* dst, const void* src)) {
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index f2761c5..bf23582 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h
@@ -2381,6 +2381,10 @@ // Requires: `n <= MaxValidCapacity()`. void Rehash(CommonFields& common, const PolicyFunctions& policy, size_t n); +// Type erased version of GtlReclaimExcessCapacity. +void ReclaimExcessCapacityImpl(CommonFields& common, + const PolicyFunctions& policy); + // Type erased version of copy constructor. void Copy(CommonFields& common, const PolicyFunctions& policy, const CommonFields& other, @@ -3800,6 +3804,13 @@ } } + // Customization point for `gtl::ReclaimExcessCapacity`. Do not call this + // function directly; call `gtl::ReclaimExcessCapacity(container)` instead. + friend void GtlReclaimExcessCapacity(raw_hash_set& container) { + ReclaimExcessCapacityImpl(container.common(), + container.GetPolicyFunctions()); + } + // Extension API: support for heterogeneous keys. // // std::unordered_set<std::string> s;
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc index 62f46c2..12ef00e 100644 --- a/absl/container/internal/raw_hash_set_test.cc +++ b/absl/container/internal/raw_hash_set_test.cc
@@ -4567,6 +4567,27 @@ EXPECT_EQ(latest_info->size.load(std::memory_order_relaxed), 2); } +TEST(RawHashSamplerTest, GtlReclaimExcessCapacityRecordsCompaction) { + std::vector<const HashtablezInfo*> infos = + SampleNonSooMutation([](NonSooIntTable& t) { + for (int i = 0; i < 64; ++i) { + t.insert(i); + } + const size_t old_cap = t.capacity(); + for (int i = 10; i < 64; ++i) { + t.erase(i); + } + GtlReclaimExcessCapacity(t); + EXPECT_LT(t.capacity(), old_cap); + }); + + for (const HashtablezInfo* info : infos) { + EXPECT_EQ(info->num_compactions.load(std::memory_order_relaxed), 1); + EXPECT_GT(info->bytes_reclaimed.load(std::memory_order_relaxed), 0); + EXPECT_EQ(info->max_reserve.load(std::memory_order_relaxed), 0); + } +} + #endif // ABSL_INTERNAL_HASHTABLEZ_SAMPLE TEST(RawHashSamplerTest, DoNotSampleCustomAllocators) { @@ -5661,6 +5682,171 @@ test(absl::flat_hash_set<int32_t, ZeroHash>()); } +TEST(Table, GtlReclaimExcessCapacityEmptySoo) { + // Small slot type (`sizeof(slot_type) <= 4`) guarantees SOO on both 32-bit + // and 64-bit platforms. + absl::flat_hash_map<uint8_t, uint8_t> soo_map; + for (int i = 0; i < 200; ++i) { + soo_map[static_cast<uint8_t>(i)] = static_cast<uint8_t>(i * 2); + } + EXPECT_GT(soo_map.capacity(), 100); + for (int i = 0; i < 200; ++i) { + soo_map.erase(static_cast<uint8_t>(i)); + } + EXPECT_TRUE(soo_map.empty()); + EXPECT_GT(soo_map.capacity(), 100); + + GtlReclaimExcessCapacity(soo_map); + EXPECT_TRUE(soo_map.empty()); + EXPECT_EQ(soo_map.capacity(), SooCapacity()); + + // Back-to-back call on an already empty SOO table is a no-op. + GtlReclaimExcessCapacity(soo_map); + EXPECT_EQ(soo_map.capacity(), SooCapacity()); +} + +TEST(Table, GtlReclaimExcessCapacityEmptyNonSoo) { + NonSooIntTable non_soo; + for (int i = 0; i < 200; ++i) { + non_soo.insert(i); + } + for (int i = 0; i < 200; ++i) { + non_soo.erase(i); + } + EXPECT_TRUE(non_soo.empty()); + EXPECT_GT(non_soo.capacity(), 100); + + GtlReclaimExcessCapacity(non_soo); + EXPECT_TRUE(non_soo.empty()); + EXPECT_EQ(non_soo.capacity(), 0); + + // Back-to-back call on an already empty non-SOO table is a no-op. + GtlReclaimExcessCapacity(non_soo); + EXPECT_EQ(non_soo.capacity(), 0); +} + +TEST(Table, GtlReclaimExcessCapacitySingleElementSoo) { + absl::flat_hash_set<uint8_t> soo_set; + for (int i = 0; i < 200; ++i) { + soo_set.insert(static_cast<uint8_t>(i)); + } + const size_t peak_capacity = soo_set.capacity(); + EXPECT_GT(peak_capacity, 100); + + for (int i = 1; i < 200; ++i) { + soo_set.erase(static_cast<uint8_t>(i)); + } + EXPECT_EQ(soo_set.size(), 1); + EXPECT_EQ(soo_set.capacity(), peak_capacity); + + GtlReclaimExcessCapacity(soo_set); + EXPECT_THAT(soo_set, UnorderedElementsAre(0)); + // Unsampled SOO tables shrink to inline SOO (`1`); sampled SOO tables retain + // `NextCapacity(SooCapacity())` (`3`). + EXPECT_LE(soo_set.capacity(), NextCapacity(SooCapacity())); + + const size_t compacted_soo_cap = soo_set.capacity(); + GtlReclaimExcessCapacity(soo_set); + EXPECT_EQ(soo_set.capacity(), compacted_soo_cap); +} + +TEST(Table, GtlReclaimExcessCapacitySingleElementNonSoo) { + StringTable non_soo_map; + for (int i = 0; i < 200; ++i) { + non_soo_map.emplace(std::to_string(i), "payload"); + } + EXPECT_GT(non_soo_map.capacity(), 100); + for (int i = 1; i < 200; ++i) { + non_soo_map.erase(std::to_string(i)); + } + EXPECT_EQ(non_soo_map.size(), 1); + + GtlReclaimExcessCapacity(non_soo_map); + const size_t compacted_non_soo_cap = non_soo_map.capacity(); + EXPECT_EQ(compacted_non_soo_cap, NextCapacity(SizeToCapacity(1))); + const std::string* val_ptr_before = &non_soo_map.find("0")->second; + // Back-to-back call on a compacted 1-element non-SOO table must not rehash or + // invalidate references. + GtlReclaimExcessCapacity(non_soo_map); + EXPECT_EQ(non_soo_map.capacity(), compacted_non_soo_cap); + EXPECT_EQ(&non_soo_map.find("0")->second, val_ptr_before); +} + +TEST(Table, GtlReclaimExcessCapacityThreshold) { + absl::flat_hash_map<int, int> map; + map.reserve(100); + const size_t peak_capacity = map.capacity(); + const size_t compacted_capacity = PreviousCapacity(peak_capacity); + const size_t shrink_size = + CapacityToGrowth(PreviousCapacity(compacted_capacity)); + const size_t no_shrink_size = shrink_size + 1; + + for (int i = 0; i < static_cast<int>(no_shrink_size); ++i) { + map[i] = i; + } + GtlReclaimExcessCapacity(map); + EXPECT_EQ(map.capacity(), peak_capacity); + + // Removing one more element crosses the shrink threshold and compacts to + // `NextCapacity(SizeToCapacity(shrink_size))`. + map.erase(static_cast<int>(no_shrink_size - 1)); + EXPECT_EQ(map.size(), shrink_size); + GtlReclaimExcessCapacity(map); + EXPECT_EQ(map.capacity(), compacted_capacity); +} + +TEST(Table, GtlReclaimExcessCapacityPreservesGrowthHeadroom) { + StringTable table; + table.reserve(100); + for (int i = 0; i < 20; ++i) { + table.emplace(std::to_string(i), "payload"); + } + const size_t peak_capacity = table.capacity(); + + GtlReclaimExcessCapacity(table); + const size_t compacted_capacity = table.capacity(); + EXPECT_LT(compacted_capacity, peak_capacity); + EXPECT_EQ(compacted_capacity, NextCapacity(SizeToCapacity(table.size()))); + const std::string* val_ptr = &table.find("0")->second; + + // Calling again without intervening mutations does not rehash again. + GtlReclaimExcessCapacity(table); + EXPECT_EQ(table.capacity(), compacted_capacity); + EXPECT_EQ(&table.find("0")->second, val_ptr); + + // Inserting and erasing elements around the compacted size does not rehash. + table.emplace("extra", "payload"); + EXPECT_EQ(table.capacity(), compacted_capacity); + EXPECT_EQ(&table.find("0")->second, val_ptr); + table.erase("extra"); + GtlReclaimExcessCapacity(table); + EXPECT_EQ(table.capacity(), compacted_capacity); + EXPECT_EQ(&table.find("0")->second, val_ptr); +} + +TEST(Table, GtlReclaimExcessCapacityBelowMinimumCapacityDoesNotShrink) { + StringTable small_map; + small_map.reserve(5); + small_map.emplace("a", "1"); + const size_t initial_capacity = small_map.capacity(); + ASSERT_TRUE(is_single_group(initial_capacity)); + ASSERT_GT(initial_capacity, NextCapacity(SizeToCapacity(small_map.size()))); + const std::string* val_ptr = &small_map.find("a")->second; + GtlReclaimExcessCapacity(small_map); + EXPECT_EQ(small_map.capacity(), initial_capacity); + EXPECT_EQ(&small_map.find("a")->second, val_ptr); + + absl::flat_hash_set<uint8_t> small_soo; + small_soo.insert(1); + small_soo.insert(2); + small_soo.erase(2); + const size_t initial_soo_capacity = small_soo.capacity(); + ASSERT_TRUE(is_single_group(initial_soo_capacity)); + ASSERT_GT(initial_soo_capacity, SooCapacity()); + GtlReclaimExcessCapacity(small_soo); + EXPECT_EQ(small_soo.capacity(), initial_soo_capacity); +} + } // namespace } // namespace container_internal ABSL_NAMESPACE_END