Introduce and use `SetCtrlInLargeTable`, when we know that table is at least one group. Similarly to `SetCtrlInSingleGroupTable`, we can save some operations.
https://gcc.godbolt.org/z/PjrzxbMz7
We are saving ~3 microops that is not big, but still positive.
Currently the function is not used in the hot loop, but the plan is to use the function in the new implementation of `GrowToNextCapacityAndPrepareInsert`. So introducing and battle test the function in advance to simplify review iterations.
Additionally adding "PrepareInsert" to "DropDeletesWithoutResize". That is done for consistency with `GrowToNextCapacityAndPrepareInsert` and to move more code to the colder function.
Microbenchmarks:
```
name old INSTRUCTIONS/op new INSTRUCTIONS/op delta
BM_SWISSMAP_EraseInsert_Hot<::absl::flat_hash_set, 4>/set_size:16 179 ± 0% 179 ± 0% -0.29% (p=0.000 n=27+27)
BM_SWISSMAP_EraseInsert_Hot<::absl::flat_hash_set, 4>/set_size:32 197 ± 0% 196 ± 0% -0.66% (p=0.000 n=27+27)
BM_SWISSMAP_EraseInsert_Hot<::absl::flat_hash_set, 4>/set_size:64 206 ± 0% 204 ± 0% -0.68% (p=0.000 n=27+26)
BM_SWISSMAP_EraseInsert_Hot<::absl::flat_hash_set, 4>/set_size:128 210 ± 0% 208 ± 0% -0.66% (p=0.000 n=25+27)
BM_SWISSMAP_EraseInsert_Hot<::absl::flat_hash_set, 4>/set_size:256 212 ± 0% 210 ± 0% -0.67% (p=0.000 n=27+27)
BM_SWISSMAP_EraseInsert_Hot<::absl::flat_hash_set, 4>/set_size:512 213 ± 0% 211 ± 0% -0.74% (p=0.000 n=27+26)
BM_SWISSMAP_EraseInsert_Hot<::absl::flat_hash_set, 4>/set_size:1024 213 ± 0% 211 ± 0% -0.69% (p=0.000 n=27+27)
BM_SWISSMAP_EraseInsert_Hot<::absl::flat_hash_set, 4>/set_size:2048 213 ± 0% 212 ± 0% -0.72% (p=0.000 n=27+27)
BM_SWISSMAP_EraseInsert_Hot<::absl::flat_hash_set, 4>/set_size:4096 213 ± 0% 212 ± 0% -0.69% (p=0.000 n=27+27)
BM_SWISSMAP_EraseInsert_Hot<::absl::flat_hash_set, 4>/set_size:8192 213 ± 0% 212 ± 0% -0.68% (p=0.000 n=27+26)
BM_SWISSMAP_EraseInsert_Hot<::absl::flat_hash_set, 4>/set_size:16384 213 ± 0% 212 ± 0% -0.70% (p=0.000 n=27+27)
BM_SWISSMAP_EraseInsert_Hot<::absl::flat_hash_set, 4>/set_size:32768 213 ± 0% 212 ± 0% -0.70% (p=0.000 n=27+27)
BM_SWISSMAP_EraseInsert_Hot<::absl::flat_hash_set, 4>/set_size:65536 219 ± 1% 218 ± 0% -0.77% (p=0.000 n=27+26)
BM_SWISSMAP_EraseInsert_Hot<::absl::flat_hash_set, 4>/set_size:131072 210 ± 0% 209 ± 0% -0.56% (p=0.000 n=27+25)
BM_SWISSMAP_EraseInsert_Hot<::absl::flat_hash_set, 4>/set_size:262144 203 ± 0% 203 ± 0% -0.32% (p=0.000 n=27+27)
BM_SWISSMAP_EraseInsert_Hot<::absl::flat_hash_set, 4>/set_size:524288 203 ± 0% 202 ± 0% -0.29% (p=0.000 n=25+26)
BM_SWISSMAP_EraseInsert_Hot<::absl::flat_hash_set, 4>/set_size:1048576 202 ± 0% 201 ± 0% -0.20% (p=0.000 n=27+27)
```
PiperOrigin-RevId: 728988087
Change-Id: Ic63f45eed3b922c4255dc36077fcf9a3d9b8b5ec
diff --git a/absl/container/internal/raw_hash_set.cc b/absl/container/internal/raw_hash_set.cc
index 948ff86..b13cf5e 100644
--- a/absl/container/internal/raw_hash_set.cc
+++ b/absl/container/internal/raw_hash_set.cc
@@ -259,8 +259,9 @@
ABSL_UNREACHABLE();
}
-void DropDeletesWithoutResize(CommonFields& common,
- const PolicyFunctions& policy) {
+size_t DropDeletesWithoutResizeAndPrepareInsert(CommonFields& common,
+ size_t new_hash,
+ const PolicyFunctions& policy) {
void* set = &common;
void* slot_array = common.slot_array();
const size_t capacity = common.capacity();
@@ -320,7 +321,7 @@
// Element doesn't move.
if (ABSL_PREDICT_TRUE(probe_index(new_i) == probe_index(i))) {
- SetCtrl(common, i, H2(hash), slot_size);
+ SetCtrlInLargeTable(common, i, H2(hash), slot_size);
continue;
}
@@ -329,14 +330,14 @@
// Transfer element to the empty spot.
// SetCtrl poisons/unpoisons the slots so we have to call it at the
// right time.
- SetCtrl(common, new_i, H2(hash), slot_size);
+ SetCtrlInLargeTable(common, new_i, H2(hash), slot_size);
(*transfer)(set, new_slot_ptr, slot_ptr, 1);
- SetCtrl(common, i, ctrl_t::kEmpty, slot_size);
+ SetCtrlInLargeTable(common, i, ctrl_t::kEmpty, slot_size);
// Initialize or change empty space id.
tmp_space_id = i;
} else {
assert(IsDeleted(ctrl[new_i]));
- SetCtrl(common, new_i, H2(hash), slot_size);
+ SetCtrlInLargeTable(common, new_i, H2(hash), slot_size);
// Until we are done rehashing, DELETED marks previously FULL slots.
if (tmp_space_id == kUnknownId) {
@@ -357,8 +358,14 @@
slot_ptr = PrevSlot(slot_ptr, slot_size);
}
}
+ // Prepare insert for the new element.
+ PrepareInsertCommon(common);
ResetGrowthLeft(common);
+ FindInfo find_info = find_first_non_full(common, new_hash);
+ SetCtrlInLargeTable(common, find_info.offset, H2(new_hash), policy.slot_size);
+ common.infoz().RecordInsert(new_hash, find_info.probe_length);
common.infoz().RecordRehash(total_probe_length);
+ return find_info.offset;
}
static bool WasNeverFull(CommonFields& c, size_t index) {
@@ -416,7 +423,7 @@
}
c.growth_info().OverwriteFullAsDeleted();
- SetCtrl(c, index, ctrl_t::kDeleted, slot_size);
+ SetCtrlInLargeTable(c, index, ctrl_t::kDeleted, slot_size);
}
void ClearBackingArray(CommonFields& c, const PolicyFunctions& policy,
@@ -802,7 +809,7 @@
total_probe_length = policy.find_new_positions_and_transfer_slots(
common, old_ctrl, old_slots, old_capacity);
find_info = find_first_non_full(common, new_hash);
- SetCtrl(common, find_info.offset, new_h2, policy.slot_size);
+ SetCtrlInLargeTable(common, find_info.offset, new_h2, policy.slot_size);
}
assert(old_capacity > policy.soo_capacity);
(*policy.dealloc)(alloc, old_capacity, old_ctrl, slot_size, slot_align,
@@ -825,7 +832,7 @@
// tombstones via rehash or growth to next capacity.
ABSL_ATTRIBUTE_NOINLINE
size_t RehashOrGrowToNextCapacityAndPrepareInsert(
- CommonFields& common, size_t hash, const PolicyFunctions& policy) {
+ CommonFields& common, size_t new_hash, const PolicyFunctions& policy) {
const size_t cap = common.capacity();
ABSL_ASSUME(cap > 0);
if (cap > Group::kWidth &&
@@ -872,16 +879,10 @@
// 762 | 149836 0.37 13 | 148559 0.74 190
// 807 | 149736 0.39 14 | 151107 0.39 14
// 852 | 150204 0.42 15 | 151019 0.42 15
- DropDeletesWithoutResize(common, policy);
- FindInfo find_info = find_first_non_full(common, hash);
- PrepareInsertCommon(common);
- common.growth_info().OverwriteEmptyAsFull();
- SetCtrl(common, find_info.offset, H2(hash), policy.slot_size);
- common.infoz().RecordInsert(hash, find_info.probe_length);
- return find_info.offset;
+ return DropDeletesWithoutResizeAndPrepareInsert(common, new_hash, policy);
} else {
// Otherwise grow the container.
- return GrowToNextCapacityAndPrepareInsert(common, hash, policy);
+ return GrowToNextCapacityAndPrepareInsert(common, new_hash, policy);
}
}
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h
index 28f5cf0..0715bbf 100644
--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -1905,6 +1905,22 @@
SetCtrlInSingleGroupTable(c, i, static_cast<ctrl_t>(h), slot_size);
}
+// Like SetCtrl, but in a table with capacity >= Group::kWidth - 1,
+// we can save some operations when setting the cloned control byte.
+inline void SetCtrlInLargeTable(const CommonFields& c, size_t i, ctrl_t h,
+ size_t slot_size) {
+ ABSL_SWISSTABLE_ASSERT(c.capacity() >= Group::kWidth - 1);
+ DoSanitizeOnSetCtrl(c, i, h, slot_size);
+ ctrl_t* ctrl = c.control();
+ ctrl[i] = h;
+ ctrl[((i - NumClonedBytes()) & c.capacity()) + NumClonedBytes()] = h;
+}
+// Overload for setting to an occupied `h2_t` rather than a special `ctrl_t`.
+inline void SetCtrlInLargeTable(const CommonFields& c, size_t i, h2_t h,
+ size_t slot_size) {
+ SetCtrlInLargeTable(c, i, static_cast<ctrl_t>(h), slot_size);
+}
+
// growth_info (which is a size_t) is stored with the backing array.
constexpr size_t BackingArrayAlignment(size_t align_of_slot) {
return (std::max)(align_of_slot, alignof(GrowthInfo));
