Pass target group offset instead of FindInfo to PrepareInsertLarge functions. The PrepareInsertLarge implementations computes probe length for sampled tables. Passing only target_group_offset directly reduces register pressure. It also helps experimentation with different probing algorithms that doesn't require probe index, e.g., linear probing. PiperOrigin-RevId: 988358373 Change-Id: Icbef12fcfff4542ba21e8c9791534787b28e7f44
diff --git a/absl/container/internal/raw_hash_set.cc b/absl/container/internal/raw_hash_set.cc index 97fd8ad..51b7544 100644 --- a/absl/container/internal/raw_hash_set.cc +++ b/absl/container/internal/raw_hash_set.cc
@@ -1008,9 +1008,9 @@ return total_probe_length; } -void ReportGrowthToInfozImpl(CommonFields& common, HashtablezInfoHandle infoz, - size_t hash, size_t total_probe_length, - size_t distance_from_desired) { +ABSL_ATTRIBUTE_NOINLINE ABSL_ATTRIBUTE_COLD void ReportGrowthToInfozImpl( + CommonFields& common, HashtablezInfoHandle infoz, size_t hash, + size_t total_probe_length, size_t distance_from_desired) { ABSL_SWISSTABLE_ASSERT(infoz.IsSampled()); infoz.RecordStorageChanged(common.size() - 1, common.capacity()); infoz.RecordRehash(total_probe_length); @@ -1020,8 +1020,9 @@ } // Specialization to avoid passing two 0s from hot function. -ABSL_ATTRIBUTE_NOINLINE void ReportSingleGroupTableGrowthToInfoz( - CommonFields& common, HashtablezInfoHandle infoz, size_t hash) { +ABSL_ATTRIBUTE_NOINLINE ABSL_ATTRIBUTE_COLD void +ReportSingleGroupTableGrowthToInfoz(CommonFields& common, + HashtablezInfoHandle infoz, size_t hash) { ReportGrowthToInfozImpl(common, infoz, hash, /*total_probe_length=*/0, /*distance_from_desired=*/0); } @@ -1029,23 +1030,46 @@ // Outlines cold infoz recording so callers do not inline infoz extraction // or spill registers across SetCtrl. `common` is first and `hash` is third to // match argument order in callers. -ABSL_ATTRIBUTE_NOINLINE ABSL_ATTRIBUTE_COLD void RecordInsertMissCold( +ABSL_ATTRIBUTE_NOINLINE ABSL_ATTRIBUTE_COLD void ReportInsertMissToInfoz( CommonFields& common, size_t probe_length, size_t hash) { common.infoz().RecordInsertMiss(hash, probe_length); } -ABSL_ATTRIBUTE_NOINLINE void ReportGrowthToInfoz(CommonFields& common, - HashtablezInfoHandle infoz, - size_t hash, - size_t total_probe_length, - size_t distance_from_desired) { +// Outlines cold infoz recording with computation of hash so callers can +// avoid calling the hash function and seed extraction in the hot path. +// `common` is first and `get_hash` is third to match argument order in callers. +ABSL_ATTRIBUTE_NOINLINE ABSL_ATTRIBUTE_COLD void +ReportInsertMissToInfozAndComputeHash( + CommonFields& common, size_t probe_length, + absl::FunctionRef<size_t(size_t)> get_hash) { + common.infoz().RecordInsertMiss(get_hash(common.seed().seed()), probe_length); +} + +// Outlines cold infoz recording with computation of probe_length so callers can +// skip tracking of probe_length. `common` is first and `hash` is third to match +// argument order in callers. +ABSL_ATTRIBUTE_NOINLINE ABSL_ATTRIBUTE_COLD void +ReportInsertMissToInfozAndComputeProbeLength(CommonFields& common, + size_t target, size_t hash) { + const size_t cap = common.capacity(); + auto seq = probe(ProbeCapacity{cap}, hash); + while (((target - seq.offset()) & cap) >= Group::kWidth) { + seq.next(); + ABSL_SWISSTABLE_ASSERT(seq.index() < common.capacity()); + } + common.infoz().RecordInsertMiss(hash, seq.index()); +} + +ABSL_ATTRIBUTE_NOINLINE ABSL_ATTRIBUTE_COLD void ReportGrowthToInfoz( + CommonFields& common, HashtablezInfoHandle infoz, size_t hash, + size_t total_probe_length, size_t distance_from_desired) { ReportGrowthToInfozImpl(common, infoz, hash, total_probe_length, distance_from_desired); } -ABSL_ATTRIBUTE_NOINLINE void ReportResizeToInfoz(CommonFields& common, - HashtablezInfoHandle infoz, - size_t total_probe_length) { +ABSL_ATTRIBUTE_NOINLINE ABSL_ATTRIBUTE_COLD void ReportResizeToInfoz( + CommonFields& common, HashtablezInfoHandle infoz, + size_t total_probe_length) { ABSL_SWISSTABLE_ASSERT(infoz.IsSampled()); infoz.RecordStorageChanged(common.size(), common.capacity()); infoz.RecordRehash(total_probe_length); @@ -1831,8 +1855,8 @@ void* res = common.slot_array(/*capacity=*/1); // Call NOINLINE function to move infoz instructions out of line. if (common.has_infoz()) { - RecordInsertMissCold(common, /*probe_length=*/0, - get_hash(common.seed().seed())); + ReportInsertMissToInfozAndComputeHash(common, /*probe_length=*/0, + get_hash); } return res; } else { @@ -1965,7 +1989,7 @@ SlotAddress(common.slot_array(cap), target.offset, policy.slot_size); SetCtrlInLargeTable(common, target.offset, H2(hash), policy.slot_size); if (common.has_infoz()) { - RecordInsertMissCold(common, target.probe_length, hash); + ReportInsertMissToInfoz(common, target.probe_length, hash); } return res; } @@ -1993,7 +2017,7 @@ SetCtrlInSingleGroupTable(common, SooSlotIndex(), H2(new_hash), policy.slot_size); if (common.has_infoz()) { - RecordInsertMissCold(common, /*probe_length=*/0, new_hash); + ReportInsertMissToInfoz(common, /*probe_length=*/0, new_hash); } return res; } @@ -2345,7 +2369,7 @@ const PolicyFunctions& __restrict policy, size_t hash, Group::NonIterableBitMaskType mask_empty, - FindInfo target_group) { + size_t target_group_offset) { ABSL_SWISSTABLE_ASSERT(!common.is_small()); // When there are no deleted slots in the table // and growth_left is positive, we can insert at the first @@ -2358,15 +2382,17 @@ common.OverwriteEmptyAsFull(); const size_t cap = common.capacity(); ABSL_ASSUME(cap > kMaxSmallCapacity); - target_group.offset += mask_empty.LowestBitSet(); - target_group.offset &= cap; + target_group_offset += mask_empty.LowestBitSet(); + target_group_offset &= cap; // Compute before `SetCtrl` to avoid reloading `control_`. - void* res = SlotAddress(common.slot_array(cap), target_group.offset, + void* res = SlotAddress(common.slot_array(cap), target_group_offset, policy.slot_size); - SetCtrl(common, target_group.offset, H2(hash), policy.slot_size); + const bool hash_infoz = common.has_infoz(); + SetCtrl(common, target_group_offset, H2(hash), policy.slot_size); // Call NOINLINE function to move infoz instructions out of line. - if (common.has_infoz()) { - RecordInsertMissCold(common, target_group.probe_length, hash); + if (hash_infoz) { + ReportInsertMissToInfozAndComputeProbeLength(common, target_group_offset, + hash); } return res; } @@ -2375,15 +2401,16 @@ void* PrepareInsertLarge(CommonFields& common, const PolicyFunctions& __restrict policy, size_t hash, Group::NonIterableBitMaskType mask_empty, - FindInfo target_group) { + size_t target_group_offset) { // NOLINTNEXTLINE(misc-static-assert) ABSL_SWISSTABLE_ASSERT(!SwisstableGenerationsEnabled()); - return PrepareInsertLargeImpl(common, policy, hash, mask_empty, target_group); + return PrepareInsertLargeImpl(common, policy, hash, mask_empty, + target_group_offset); } void* PrepareInsertLargeGenerationsEnabled( CommonFields& common, const PolicyFunctions& __restrict policy, size_t hash, - Group::NonIterableBitMaskType mask_empty, FindInfo target_group, + Group::NonIterableBitMaskType mask_empty, size_t target_group_offset, absl::FunctionRef<size_t(size_t)> recompute_hash) { // NOLINTNEXTLINE(misc-static-assert) ABSL_SWISSTABLE_ASSERT(SwisstableGenerationsEnabled()); @@ -2395,10 +2422,13 @@ // Move to a different heap allocation in order to detect bugs. ResizeAllocatedTableWithSeedChange(common, policy, cap); hash = recompute_hash(common.seed().seed()); + FindInfo target_group; std::tie(target_group, mask_empty) = find_first_non_full_group(common, hash); + target_group_offset = target_group.offset; } - return PrepareInsertLargeImpl(common, policy, hash, mask_empty, target_group); + return PrepareInsertLargeImpl(common, policy, hash, mask_empty, + target_group_offset); } namespace {
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index a73a36a..32e6797 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h
@@ -2255,13 +2255,13 @@ // at least one empty slot. void* PrepareInsertLarge(CommonFields& common, const PolicyFunctions& policy, size_t hash, Group::NonIterableBitMaskType mask_empty, - FindInfo target_group); + size_t target_group_offset); // Same as above, but with generations enabled, we may end up changing the seed, // which means we need to be able to recompute the hash. void* PrepareInsertLargeGenerationsEnabled( CommonFields& common, const PolicyFunctions& policy, size_t hash, - Group::NonIterableBitMaskType mask_empty, FindInfo target_group, + Group::NonIterableBitMaskType mask_empty, size_t target_group_offset, absl::FunctionRef<size_t(size_t)> recompute_hash); template <typename Policy, typename Hash, typename Eq, typename Alloc> @@ -3798,12 +3798,12 @@ void* slot = SwisstableGenerationsEnabled() ? PrepareInsertLargeGenerationsEnabled( common(), GetPolicyFunctions(), hash, mask_empty, - FindInfo{target_group_offset, seq.index()}, + target_group_offset, HashKey<hasher, K, kIsAbslHash, kSeedShift>{ hash_ref(), key}) : PrepareInsertLarge( common(), GetPolicyFunctions(), hash, mask_empty, - FindInfo{target_group_offset, seq.index()}); + target_group_offset); return {to_slot(slot), true}; } seq.next();