Extract slow path for PrepareInsertNonSoo to a separate function `PrepareInsertNonSooSlow`. https://gcc.godbolt.org/z/c9onP4qs3 shows a drastic reduction of operations. We can see that the new version fits everything into registers and doesn't have push and pop on stack. Microbenchmarks are quite positive. Although small tables `InsertManyToEmpty` are slightly slower (<0.5%). ``` BM_SWISSMAP_InsertManyOrdered_Hot<::absl::flat_hash_set, 4>/set_size:1/density:1 42.4 ± 0% 41.2 ± 0% -2.93% (p=0.000 n=27+25) BM_SWISSMAP_InsertManyOrdered_Hot<::absl::flat_hash_set, 4>/set_size:2/density:1 38.1 ± 0% 37.0 ± 0% -2.91% (p=0.000 n=26+27) BM_SWISSMAP_InsertManyOrdered_Hot<::absl::flat_hash_set, 4>/set_size:4/density:1 38.2 ± 0% 37.1 ± 0% -2.91% (p=0.000 n=27+25) BM_SWISSMAP_InsertManyOrdered_Hot<::absl::flat_hash_set, 4>/set_size:8/density:1 35.8 ± 0% 34.7 ± 0% -3.09% (p=0.000 n=25+27) BM_SWISSMAP_InsertManyOrdered_Hot<::absl::flat_hash_set, 4>/set_size:16/density:1 31.6 ± 1% 30.9 ± 1% -2.40% (p=0.000 n=26+24) BM_SWISSMAP_InsertManyUnordered_Hot<::absl::flat_hash_set, 4>/set_size:65536/density:0 29.3 ± 1% 25.6 ± 1% -12.47% (p=0.000 n=21+22) BM_SWISSMAP_InsertManyUnordered_Hot<::absl::flat_hash_set, 4>/set_size:131072/density:0 36.1 ± 1% 31.5 ± 2% -12.79% (p=0.000 n=21+22) BM_SWISSMAP_InsertManyUnordered_Hot<::absl::flat_hash_set, 4>/set_size:262144/density:0 40.8 ± 3% 35.5 ± 3% -12.89% (p=0.000 n=24+23) BM_SWISSMAP_InsertManyUnordered_Hot<::absl::flat_hash_set, 4>/set_size:524288/density:0 43.3 ± 2% 38.2 ± 3% -11.86% (p=0.000 n=21+22) BM_SWISSMAP_InsertManyUnordered_Hot<::absl::flat_hash_set, 4>/set_size:1048576/density:0 44.6 ± 2% 40.6 ±10% -9.09% (p=0.000 n=21+21) BM_SWISSMAP_EraseInsert_Hot<::absl::flat_hash_set, 64>/set_size:1024 118 ± 1% 115 ± 1% -2.95% (p=0.000 n=27+25) BM_SWISSMAP_EraseInsert_Hot<::absl::flat_hash_set, 64>/set_size:2048 120 ± 0% 115 ± 1% -3.46% (p=0.000 n=24+23) BM_SWISSMAP_EraseInsert_Hot<::absl::flat_hash_set, 64>/set_size:4096 122 ± 0% 118 ± 1% -3.47% (p=0.000 n=27+27) BM_SWISSMAP_EraseInsert_Hot<::absl::flat_hash_set, 64>/set_size:8192 133 ± 1% 129 ± 1% -3.59% (p=0.000 n=27+27) BM_SWISSMAP_EraseInsert_Hot<::absl::flat_hash_set, 64>/set_size:16384 136 ± 1% 132 ± 1% -3.22% (p=0.000 n=27+24) BM_SWISSMAP_EraseInsert_Hot<::absl::flat_hash_set, 64>/set_size:32768 138 ± 1% 134 ± 1% -3.21% (p=0.000 n=27+25) BM_SWISSMAP_EraseInsert_Hot<::absl::flat_hash_set, 64>/set_size:65536 149 ± 2% 144 ± 2% -3.48% (p=0.000 n=26+21) BM_SWISSMAP_InsertManyToEmpty_Hot<::absl::flat_hash_set, 4>/set_size:1 15.0 ± 0% 15.0 ± 1% +0.25% (p=0.014 n=22+22) BM_SWISSMAP_InsertManyToEmpty_Hot<::absl::flat_hash_set, 4>/set_size:2 28.0 ± 1% 28.1 ± 1% +0.15% (p=0.030 n=23+25) BM_SWISSMAP_InsertManyToEmpty_Hot<::absl::flat_hash_set, 4>/set_size:4 44.7 ± 1% 44.3 ± 0% -0.73% (p=0.000 n=26+25) BM_SWISSMAP_InsertManyToEmpty_Hot<::absl::flat_hash_set, 4>/set_size:8 44.9 ± 1% 44.5 ± 1% -0.86% (p=0.000 n=24+26) BM_SWISSMAP_InsertManyToEmpty_Hot<::absl::flat_hash_set, 4>/set_size:16 53.1 ± 1% 54.0 ± 1% +1.61% (p=0.000 n=24+26) BM_SWISSMAP_InsertManyToEmpty_Hot<::absl::flat_hash_set, 4>/set_size:32 53.5 ± 2% 54.6 ± 2% +2.07% (p=0.000 n=26+26) BM_SWISSMAP_InsertManyToEmpty_Hot<::absl::flat_hash_set, 4>/set_size:64 51.5 ± 1% 52.4 ± 2% +1.77% (p=0.000 n=24+27) BM_SWISSMAP_InsertManyToEmpty_Hot<::absl::flat_hash_set, 4>/set_size:128 49.6 ± 2% 50.0 ± 1% +0.66% (p=0.007 n=26+27) BM_SWISSMAP_InsertManyToEmpty_Hot<::absl::flat_hash_set, 4>/set_size:256 47.9 ± 2% 47.7 ± 2% ~ (p=0.084 n=24+27) BM_SWISSMAP_InsertManyToEmpty_Hot<::absl::flat_hash_set, 4>/set_size:512 46.8 ± 2% 46.1 ± 2% -1.49% (p=0.000 n=26+27) BM_SWISSMAP_InsertManyToEmpty_Hot<::absl::flat_hash_set, 4>/set_size:1024 46.5 ± 2% 45.5 ± 1% -2.12% (p=0.000 n=26+27) BM_SWISSMAP_InsertManyToEmpty_Hot<::absl::flat_hash_set, 4>/set_size:2048 47.8 ± 2% 46.5 ± 2% -2.75% (p=0.000 n=25+26) BM_SWISSMAP_InsertManyToEmpty_Hot<::absl::flat_hash_set, 4>/set_size:4096 53.9 ± 2% 52.0 ± 1% -3.60% (p=0.000 n=26+26) BM_SWISSMAP_InsertManyToEmpty_Hot<::absl::flat_hash_set, 4>/set_size:8192 62.1 ± 1% 59.8 ± 1% -3.62% (p=0.000 n=27+27) BM_SWISSMAP_InsertManyToEmpty_Hot<::absl::flat_hash_set, 4>/set_size:16384 64.8 ± 1% 62.5 ± 1% -3.51% (p=0.000 n=27+25) BM_SWISSMAP_InsertManyToEmpty_Hot<::absl::flat_hash_set, 4>/set_size:32768 66.1 ± 1% 63.6 ± 1% -3.71% (p=0.000 n=27+27) BM_SWISSMAP_InsertManyToEmpty_Hot<::absl::flat_hash_set, 4>/set_size:65536 67.6 ± 1% 65.0 ± 1% -3.82% (p=0.000 n=27+26) BM_SWISSMAP_InsertManyToEmpty_Hot<::absl::flat_hash_set, 4>/set_size:131072 69.4 ± 1% 66.4 ± 1% -4.28% (p=0.000 n=27+25) BM_SWISSMAP_InsertManyToEmpty_Hot<::absl::flat_hash_set, 4>/set_size:262144 72.2 ± 2% 68.4 ± 2% -5.26% (p=0.000 n=27+26) BM_SWISSMAP_InsertManyToEmpty_Hot<::absl::flat_hash_set, 4>/set_size:524288 76.1 ± 2% 71.6 ± 2% -5.96% (p=0.000 n=27+27) BM_SWISSMAP_InsertManyToEmpty_Hot<::absl::flat_hash_set, 4>/set_size:1048576 80.9 ± 2% 76.2 ± 6% -5.89% (p=0.000 n=26+23) ``` PiperOrigin-RevId: 729614125 Change-Id: I2d36fddaa02d21572f6928dc148b8e2f1c2b159f
diff --git a/absl/container/internal/raw_hash_set.cc b/absl/container/internal/raw_hash_set.cc index b58484e..31a6f4e 100644 --- a/absl/container/internal/raw_hash_set.cc +++ b/absl/container/internal/raw_hash_set.cc
@@ -882,6 +882,30 @@ } } +// Slow path for PrepareInsertNonSoo that is called when the table has deleted +// slots or need to be resized or rehashed. +size_t PrepareInsertNonSooSlow(CommonFields& common, size_t hash, + const PolicyFunctions& policy) { + const GrowthInfo growth_info = common.growth_info(); + assert(!growth_info.HasNoDeletedAndGrowthLeft()); + if (ABSL_PREDICT_TRUE(growth_info.HasNoGrowthLeftAndNoDeleted())) { + // Table without deleted slots (>95% cases) that needs to be resized. + assert(growth_info.HasNoDeleted() && growth_info.GetGrowthLeft() == 0); + return GrowToNextCapacityAndPrepareInsert(common, hash, policy); + } + if (ABSL_PREDICT_FALSE(growth_info.HasNoGrowthLeftAssumingMayHaveDeleted())) { + // Table with deleted slots that needs to be rehashed or resized. + return RehashOrGrowToNextCapacityAndPrepareInsert(common, hash, policy); + } + // Table with deleted slots that has space for the inserting element. + FindInfo target = find_first_non_full(common, hash); + PrepareInsertCommon(common); + common.growth_info().OverwriteControlAsFull(common.control()[target.offset]); + SetCtrlInLargeTable(common, target.offset, H2(hash), policy.slot_size); + common.infoz().RecordInsert(hash, target.probe_length); + return target.offset; +} + } // namespace void* GetRefForEmptyClass(CommonFields& common) { @@ -1013,8 +1037,8 @@ common.infoz().RecordReservation(n); } -size_t PrepareInsertNonSoo(CommonFields& common, size_t hash, FindInfo target, - const PolicyFunctions& policy) { +size_t PrepareInsertNonSoo(CommonFields& common, size_t hash, + const PolicyFunctions& policy, FindInfo target) { const bool rehash_for_bug_detection = common.should_rehash_for_bug_detection_on_insert() && // Required to allow use of ResizeAllocatedTable. @@ -1032,25 +1056,7 @@ // and growth_left is positive, we can insert at the first // empty slot in the probe sequence (target). if (ABSL_PREDICT_FALSE(!growth_info.HasNoDeletedAndGrowthLeft())) { - if (ABSL_PREDICT_TRUE(growth_info.HasNoGrowthLeftAndNoDeleted())) { - // Table without deleted slots (>95% cases) that needs to be resized. - assert(growth_info.HasNoDeleted() && growth_info.GetGrowthLeft() == 0); - return GrowToNextCapacityAndPrepareInsert(common, hash, policy); - } else { - if (ABSL_PREDICT_FALSE( - growth_info.HasNoGrowthLeftAssumingMayHaveDeleted())) { - // Table with deleted slots that needs to be rehashed or resized. - return RehashOrGrowToNextCapacityAndPrepareInsert(common, hash, policy); - } - // Table with deleted slots that has space for the inserting element. - target = find_first_non_full(common, hash); - // We need to overwrite the control byte to full, but we do that in two - // steps: overwrite to empty and then to full. - // This is done in order to avoid reading the control byte in the most - // common case below. - common.growth_info().OverwriteControlAsEmpty( - common.control()[target.offset]); - } + return PrepareInsertNonSooSlow(common, hash, policy); } PrepareInsertCommon(common); common.growth_info().OverwriteEmptyAsFull();
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index b62599a..506579b 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h
@@ -1145,9 +1145,11 @@ growth_left_info_ -= count; } - // Overwrites specified control element with empty slot. - void OverwriteControlAsEmpty(ctrl_t ctrl) { - growth_left_info_ += static_cast<size_t>(!IsEmpty(ctrl)); + // Overwrites specified control element with full slot. + void OverwriteControlAsFull(ctrl_t ctrl) { + ABSL_SWISSTABLE_ASSERT(GetGrowthLeft() >= + static_cast<size_t>(IsEmpty(ctrl))); + growth_left_info_ -= static_cast<size_t>(IsEmpty(ctrl)); } // Overwrites single full slot with a deleted slot. @@ -2285,8 +2287,8 @@ // REQUIRES: Table is not SOO. // REQUIRES: At least one non-full slot available. // REQUIRES: `target` is a valid empty position to insert. -size_t PrepareInsertNonSoo(CommonFields& common, size_t hash, FindInfo target, - const PolicyFunctions& policy); +size_t PrepareInsertNonSoo(CommonFields& common, size_t hash, + const PolicyFunctions& policy, FindInfo target); // A SwissTable. // @@ -3781,8 +3783,8 @@ size_t target = seq.offset( GetInsertionOffset(mask_empty, capacity(), hash, control())); return {iterator_at(PrepareInsertNonSoo(common(), hash, - FindInfo{target, seq.index()}, - GetPolicyFunctions())), + GetPolicyFunctions(), + FindInfo{target, seq.index()})), true}; } seq.next();
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc index 4e48f48..9a231a9 100644 --- a/absl/container/internal/raw_hash_set_test.cc +++ b/absl/container/internal/raw_hash_set_test.cc
@@ -193,15 +193,15 @@ EXPECT_FALSE(gi.HasNoDeleted()); } -TEST(GrowthInfoTest, OverwriteControlAsEmpty) { +TEST(GrowthInfoTest, OverwriteControlAsFull) { GrowthInfo gi; gi.InitGrowthLeftNoDeleted(5); - gi.OverwriteControlAsEmpty(ctrl_t::kEmpty); - EXPECT_EQ(gi.GetGrowthLeft(), 5); - gi.OverwriteControlAsEmpty(ctrl_t::kDeleted); - EXPECT_EQ(gi.GetGrowthLeft(), 6); + gi.OverwriteControlAsFull(ctrl_t::kEmpty); + EXPECT_EQ(gi.GetGrowthLeft(), 4); + gi.OverwriteControlAsFull(ctrl_t::kDeleted); + EXPECT_EQ(gi.GetGrowthLeft(), 4); gi.OverwriteFullAsDeleted(); - gi.OverwriteControlAsEmpty(ctrl_t::kDeleted); + gi.OverwriteControlAsFull(ctrl_t::kDeleted); // We do not count number of deleted, so the bit sticks till the next rehash. EXPECT_FALSE(gi.HasNoDeletedAndGrowthLeft()); EXPECT_FALSE(gi.HasNoDeleted()); @@ -213,7 +213,10 @@ gi.OverwriteFullAsDeleted(); EXPECT_EQ(gi.GetGrowthLeft(), 1); EXPECT_FALSE(gi.HasNoGrowthLeftAssumingMayHaveDeleted()); - gi.OverwriteControlAsEmpty(ctrl_t::kDeleted); + gi.OverwriteControlAsFull(ctrl_t::kDeleted); + EXPECT_EQ(gi.GetGrowthLeft(), 1); + EXPECT_FALSE(gi.HasNoGrowthLeftAssumingMayHaveDeleted()); + gi.OverwriteFullAsEmpty(); EXPECT_EQ(gi.GetGrowthLeft(), 2); EXPECT_FALSE(gi.HasNoGrowthLeftAssumingMayHaveDeleted()); gi.OverwriteEmptyAsFull();