Make PolicyFunctions always be the second argument (after CommonFields) for type-erased functions. The motivation is to save `mov` instructions by keeping the same argument in the same register for calling convention. PiperOrigin-RevId: 736617245 Change-Id: I72944c9082ccc8aa7dcdb74e52fc9ee78f43117d
diff --git a/absl/container/internal/raw_hash_set.cc b/absl/container/internal/raw_hash_set.cc index f1a317a..426664a 100644 --- a/absl/container/internal/raw_hash_set.cc +++ b/absl/container/internal/raw_hash_set.cc
@@ -265,8 +265,8 @@ } size_t DropDeletesWithoutResizeAndPrepareInsert(CommonFields& common, - size_t new_hash, - const PolicyFunctions& policy) { + const PolicyFunctions& policy, + size_t new_hash) { void* set = &common; void* slot_array = common.slot_array(); const size_t capacity = common.capacity(); @@ -515,9 +515,8 @@ }; template <ResizeNonSooMode kMode> -void ResizeNonSooImpl(CommonFields& common, size_t new_capacity, - HashtablezInfoHandle infoz, - const PolicyFunctions& policy) { +void ResizeNonSooImpl(CommonFields& common, const PolicyFunctions& policy, + size_t new_capacity, HashtablezInfoHandle infoz) { assert(IsValidCapacity(new_capacity)); assert(new_capacity > policy.soo_capacity); @@ -563,9 +562,9 @@ } } -void ResizeEmptyNonAllocatedTableImpl(CommonFields& common, size_t new_capacity, - bool force_infoz, - const PolicyFunctions& policy) { +void ResizeEmptyNonAllocatedTableImpl(CommonFields& common, + const PolicyFunctions& policy, + size_t new_capacity, bool force_infoz) { assert(IsValidCapacity(new_capacity)); assert(new_capacity > policy.soo_capacity); assert(!force_infoz || policy.soo_capacity > 0); @@ -579,18 +578,18 @@ infoz = ForcedTrySample(slot_size, policy.key_size, policy.value_size, policy.soo_capacity); } - ResizeNonSooImpl<ResizeNonSooMode::kGuaranteedEmpty>(common, new_capacity, - infoz, policy); + ResizeNonSooImpl<ResizeNonSooMode::kGuaranteedEmpty>(common, policy, + new_capacity, infoz); } // If the table was SOO, initializes new control bytes and transfers slot. // After transferring the slot, sets control and slots in CommonFields. // It is rare to resize an SOO table with one element to a large size. // Requires: `c` contains SOO data. -void InsertOldSooSlotAndInitializeControlBytes(CommonFields& c, size_t hash, - ctrl_t* new_ctrl, - void* new_slots, - const PolicyFunctions& policy) { +void InsertOldSooSlotAndInitializeControlBytes(CommonFields& c, + const PolicyFunctions& policy, + size_t hash, ctrl_t* new_ctrl, + void* new_slots) { assert(c.size() == policy.soo_capacity); assert(policy.soo_capacity == SooCapacity()); size_t new_capacity = c.capacity(); @@ -614,9 +613,9 @@ kForceSampleNoResizeIfUnsampled, }; -void ResizeFullSooTable(CommonFields& common, size_t new_capacity, - ResizeFullSooTableSamplingMode sampling_mode, - const PolicyFunctions& policy) { +void ResizeFullSooTable(CommonFields& common, const PolicyFunctions& policy, + size_t new_capacity, + ResizeFullSooTableSamplingMode sampling_mode) { assert(common.capacity() == policy.soo_capacity); assert(common.size() == policy.soo_capacity); assert(policy.soo_capacity == SooCapacity()); @@ -656,8 +655,8 @@ const size_t soo_slot_hash = policy.hash_slot(policy.hash_fn(common), common.soo_data()); - InsertOldSooSlotAndInitializeControlBytes(common, soo_slot_hash, new_ctrl, - new_slots, policy); + InsertOldSooSlotAndInitializeControlBytes(common, policy, soo_slot_hash, + new_ctrl, new_slots); ResetGrowthLeft(common); if (has_infoz) { common.set_has_infoz(); @@ -789,8 +788,9 @@ // new_ctrl after 2nd store = E0123456EEEEEEESE0123456EEEEEEE } -size_t GrowToNextCapacityAndPrepareInsert(CommonFields& common, size_t new_hash, - const PolicyFunctions& policy) { +size_t GrowToNextCapacityAndPrepareInsert(CommonFields& common, + const PolicyFunctions& policy, + size_t new_hash) { assert(common.growth_left() == 0); const size_t old_capacity = common.capacity(); assert(old_capacity == 0 || old_capacity > policy.soo_capacity); @@ -885,8 +885,9 @@ // Called whenever the table needs to vacate empty slots either by removing // tombstones via rehash or growth to next capacity. ABSL_ATTRIBUTE_NOINLINE -size_t RehashOrGrowToNextCapacityAndPrepareInsert( - CommonFields& common, size_t new_hash, const PolicyFunctions& policy) { +size_t RehashOrGrowToNextCapacityAndPrepareInsert(CommonFields& common, + const PolicyFunctions& policy, + size_t new_hash) { const size_t cap = common.capacity(); ABSL_ASSUME(cap > 0); if (cap > Group::kWidth && @@ -933,27 +934,27 @@ // 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 - return DropDeletesWithoutResizeAndPrepareInsert(common, new_hash, policy); + return DropDeletesWithoutResizeAndPrepareInsert(common, policy, new_hash); } else { // Otherwise grow the container. - return GrowToNextCapacityAndPrepareInsert(common, new_hash, policy); + return GrowToNextCapacityAndPrepareInsert(common, policy, new_hash); } } // 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) { +size_t PrepareInsertNonSooSlow(CommonFields& common, + const PolicyFunctions& policy, size_t hash) { 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); + return GrowToNextCapacityAndPrepareInsert(common, policy, hash); } if (ABSL_PREDICT_FALSE(growth_info.HasNoGrowthLeftAssumingMayHaveDeleted())) { // Table with deleted slots that needs to be rehashed or resized. - return RehashOrGrowToNextCapacityAndPrepareInsert(common, hash, policy); + return RehashOrGrowToNextCapacityAndPrepareInsert(common, policy, hash); } // Table with deleted slots that has space for the inserting element. FindInfo target = find_first_non_full(common, hash); @@ -975,20 +976,19 @@ } void ResizeAllocatedTableWithSeedChange(CommonFields& common, - size_t new_capacity, - const PolicyFunctions& policy) { + const PolicyFunctions& policy, + size_t new_capacity) { ResizeNonSooImpl<ResizeNonSooMode::kGuaranteedAllocated>( - common, new_capacity, common.infoz(), policy); + common, policy, new_capacity, common.infoz()); } - void ReserveEmptyNonAllocatedTableToFitNewSize(CommonFields& common, - size_t new_size, - const PolicyFunctions& policy) { + const PolicyFunctions& policy, + size_t new_size) { ValidateMaxSize(new_size, policy.slot_size); ResizeEmptyNonAllocatedTableImpl( - common, NormalizeCapacity(GrowthToLowerboundCapacity(new_size)), - /*force_infoz=*/false, policy); + common, policy, NormalizeCapacity(GrowthToLowerboundCapacity(new_size)), + /*force_infoz=*/false); // This is after resize, to ensure that we have completed the allocation // and have potentially sampled the hashtable. common.infoz().RecordReservation(new_size); @@ -997,23 +997,24 @@ } void ReserveEmptyNonAllocatedTableToFitBucketCount( - CommonFields& common, size_t bucket_count, const PolicyFunctions& policy) { + CommonFields& common, const PolicyFunctions& policy, size_t bucket_count) { size_t new_capacity = NormalizeCapacity(bucket_count); ValidateMaxSize(CapacityToGrowth(new_capacity), policy.slot_size); - ResizeEmptyNonAllocatedTableImpl(common, new_capacity, - /*force_infoz=*/false, policy); + ResizeEmptyNonAllocatedTableImpl(common, policy, new_capacity, + /*force_infoz=*/false); } void GrowEmptySooTableToNextCapacityForceSampling( CommonFields& common, const PolicyFunctions& policy) { - ResizeEmptyNonAllocatedTableImpl(common, NextCapacity(SooCapacity()), - /*force_infoz=*/true, policy); + ResizeEmptyNonAllocatedTableImpl(common, policy, NextCapacity(SooCapacity()), + /*force_infoz=*/true); } // Resizes a full SOO table to the NextCapacity(SooCapacity()). template <size_t SooSlotMemcpySize, bool TransferUsesMemcpy> -void GrowFullSooTableToNextCapacity(CommonFields& common, size_t soo_slot_hash, - const PolicyFunctions& policy) { +void GrowFullSooTableToNextCapacity(CommonFields& common, + const PolicyFunctions& policy, + size_t soo_slot_hash) { assert(common.capacity() == policy.soo_capacity); assert(common.size() == policy.soo_capacity); static constexpr size_t kNewCapacity = NextCapacity(SooCapacity()); @@ -1073,11 +1074,11 @@ assert(common.size() == policy.soo_capacity); assert(policy.soo_capacity == SooCapacity()); ResizeFullSooTable( - common, NextCapacity(SooCapacity()), - ResizeFullSooTableSamplingMode::kForceSampleNoResizeIfUnsampled, policy); + common, policy, NextCapacity(SooCapacity()), + ResizeFullSooTableSamplingMode::kForceSampleNoResizeIfUnsampled); } -void Rehash(CommonFields& common, size_t n, const PolicyFunctions& policy) { +void Rehash(CommonFields& common, const PolicyFunctions& policy, size_t n) { const size_t cap = common.capacity(); auto clear_backing_array = [&]() { @@ -1099,8 +1100,8 @@ static constexpr size_t kInitialSampledCapacity = NextCapacity(SooCapacity()); if (cap > kInitialSampledCapacity) { - ResizeAllocatedTableWithSeedChange(common, kInitialSampledCapacity, - policy); + ResizeAllocatedTableWithSeedChange(common, policy, + kInitialSampledCapacity); } // This asserts that we didn't lose sampling coverage in `resize`. assert(common.infoz().IsSampled()); @@ -1129,14 +1130,14 @@ if (n == 0 || new_capacity > cap) { if (cap == policy.soo_capacity) { if (common.empty()) { - ResizeEmptyNonAllocatedTableImpl(common, new_capacity, - /*force_infoz=*/false, policy); + ResizeEmptyNonAllocatedTableImpl(common, policy, new_capacity, + /*force_infoz=*/false); } else { - ResizeFullSooTable(common, new_capacity, - ResizeFullSooTableSamplingMode::kNoSampling, policy); + ResizeFullSooTable(common, policy, new_capacity, + ResizeFullSooTableSamplingMode::kNoSampling); } } else { - ResizeAllocatedTableWithSeedChange(common, new_capacity, policy); + ResizeAllocatedTableWithSeedChange(common, policy, new_capacity); } // This is after resize, to ensure that we have completed the allocation // and have potentially sampled the hashtable. @@ -1144,8 +1145,8 @@ } } -void ReserveAllocatedTable(CommonFields& common, size_t n, - const PolicyFunctions& policy) { +void ReserveAllocatedTable(CommonFields& common, const PolicyFunctions& policy, + size_t n) { common.reset_reserved_growth(n); common.set_reservation_size(n); @@ -1162,17 +1163,17 @@ const size_t new_capacity = NormalizeCapacity(GrowthToLowerboundCapacity(n)); if (cap == policy.soo_capacity) { assert(!common.empty()); - ResizeFullSooTable(common, new_capacity, - ResizeFullSooTableSamplingMode::kNoSampling, policy); + ResizeFullSooTable(common, policy, new_capacity, + ResizeFullSooTableSamplingMode::kNoSampling); } else { assert(cap > policy.soo_capacity); - ResizeAllocatedTableWithSeedChange(common, new_capacity, policy); + ResizeAllocatedTableWithSeedChange(common, policy, new_capacity); } common.infoz().RecordReservation(n); } -size_t PrepareInsertNonSoo(CommonFields& common, size_t hash, - const PolicyFunctions& policy, FindInfo target) { +size_t PrepareInsertNonSoo(CommonFields& common, const PolicyFunctions& policy, + size_t hash, FindInfo target) { const bool rehash_for_bug_detection = common.should_rehash_for_bug_detection_on_insert() && // Required to allow use of ResizeAllocatedTable. @@ -1181,7 +1182,7 @@ // Move to a different heap allocation in order to detect bugs. const size_t cap = common.capacity(); ResizeAllocatedTableWithSeedChange( - common, common.growth_left() > 0 ? cap : NextCapacity(cap), policy); + common, policy, common.growth_left() > 0 ? cap : NextCapacity(cap)); target = find_first_non_full(common, hash); } @@ -1190,7 +1191,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())) { - return PrepareInsertNonSooSlow(common, hash, policy); + return PrepareInsertNonSooSlow(common, policy, hash); } PrepareInsertCommon(common); common.growth_info().OverwriteEmptyAsFull(); @@ -1226,21 +1227,22 @@ // We need to instantiate ALL possible template combinations because we define // the function in the cc file. -template void GrowFullSooTableToNextCapacity<0, false>(CommonFields&, size_t, - const PolicyFunctions&); +template void GrowFullSooTableToNextCapacity<0, false>(CommonFields&, + const PolicyFunctions&, + size_t); template void GrowFullSooTableToNextCapacity<OptimalMemcpySizeForSooSlotTransfer(1), true>( - CommonFields&, size_t, const PolicyFunctions&); + CommonFields&, const PolicyFunctions&, size_t); static_assert(VerifyOptimalMemcpySizeForSooSlotTransferRange(2, 3)); template void GrowFullSooTableToNextCapacity<OptimalMemcpySizeForSooSlotTransfer(3), true>( - CommonFields&, size_t, const PolicyFunctions&); + CommonFields&, const PolicyFunctions&, size_t); static_assert(VerifyOptimalMemcpySizeForSooSlotTransferRange(4, 8)); template void GrowFullSooTableToNextCapacity<OptimalMemcpySizeForSooSlotTransfer(8), true>( - CommonFields&, size_t, const PolicyFunctions&); + CommonFields&, const PolicyFunctions&, size_t); #if UINTPTR_MAX == UINT32_MAX static_assert(MaxSooSlotSize() == 8); @@ -1248,7 +1250,7 @@ static_assert(VerifyOptimalMemcpySizeForSooSlotTransferRange(9, 16)); template void GrowFullSooTableToNextCapacity<OptimalMemcpySizeForSooSlotTransfer(16), true>( - CommonFields&, size_t, const PolicyFunctions&); + CommonFields&, const PolicyFunctions&, size_t); static_assert(MaxSooSlotSize() == 16); #endif
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index 87906a4..41a480a 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h
@@ -1736,13 +1736,13 @@ // 3. `new_size > policy.soo_capacity`. // The table will be attempted to be sampled. void ReserveEmptyNonAllocatedTableToFitNewSize(CommonFields& common, - size_t new_size, - const PolicyFunctions& policy); + const PolicyFunctions& policy, + size_t new_size); // The same as ReserveEmptyNonAllocatedTableToFitNewSize, but resizes to the // next valid capacity after `bucket_count`. void ReserveEmptyNonAllocatedTableToFitBucketCount( - CommonFields& common, size_t bucket_count, const PolicyFunctions& policy); + CommonFields& common, const PolicyFunctions& policy, size_t bucket_count); // Resizes empty non-allocated SOO table to NextCapacity(SooCapacity()) and // forces the table to be sampled. @@ -1754,7 +1754,7 @@ CommonFields& common, const PolicyFunctions& policy); // Type erased version of raw_hash_set::rehash. -void Rehash(CommonFields& common, size_t n, const PolicyFunctions& policy); +void Rehash(CommonFields& common, const PolicyFunctions& policy, size_t n); // Type erased version of raw_hash_set::reserve for tables that have an // allocated backing array. @@ -1762,8 +1762,8 @@ // Requires: // 1. `c.capacity() > policy.soo_capacity` OR `!c.empty()`. // Reserving already allocated tables is considered to be a rare case. -void ReserveAllocatedTable(CommonFields& common, size_t n, - const PolicyFunctions& policy); +void ReserveAllocatedTable(CommonFields& common, const PolicyFunctions& policy, + size_t n); // Returns the optimal size for memcpy when transferring SOO slot. // Otherwise, returns the optimal size for memcpy SOO slot transfer @@ -1804,8 +1804,9 @@ // All possible template combinations are defined in cc file to improve // compilation time. template <size_t SooSlotMemcpySize, bool TransferUsesMemcpy> -void GrowFullSooTableToNextCapacity(CommonFields& common, size_t soo_slot_hash, - const PolicyFunctions& policy); +void GrowFullSooTableToNextCapacity(CommonFields& common, + const PolicyFunctions& policy, + size_t soo_slot_hash); // As `ResizeFullSooTableToNextCapacity`, except that we also force the SOO // table to be sampled. SOO tables need to switch from SOO to heap in order to @@ -1817,8 +1818,8 @@ // Tables with SOO enabled must have capacity > policy.soo_capacity. // No sampling will be performed since table is already allocated. void ResizeAllocatedTableWithSeedChange(CommonFields& common, - size_t new_capacity, - const PolicyFunctions& policy); + const PolicyFunctions& policy, + size_t new_capacity); inline void PrepareInsertCommon(CommonFields& common) { common.increment_size(); @@ -1870,8 +1871,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, - const PolicyFunctions& policy, FindInfo target); +size_t PrepareInsertNonSoo(CommonFields& common, const PolicyFunctions& policy, + size_t hash, FindInfo target); // A SwissTable. // @@ -2182,8 +2183,8 @@ : settings_(CommonFields::CreateDefault<SooEnabled()>(), hash, eq, alloc) { if (bucket_count > DefaultCapacity()) { - ReserveEmptyNonAllocatedTableToFitBucketCount(common(), bucket_count, - GetPolicyFunctions()); + ReserveEmptyNonAllocatedTableToFitBucketCount( + common(), GetPolicyFunctions(), bucket_count); } } @@ -2857,7 +2858,7 @@ typename AllocTraits::propagate_on_container_swap{}); } - void rehash(size_t n) { Rehash(common(), n, GetPolicyFunctions()); } + void rehash(size_t n) { Rehash(common(), GetPolicyFunctions(), n); } void reserve(size_t n) { const size_t cap = capacity(); @@ -2865,11 +2866,11 @@ // !SooEnabled() implies empty(), so we can skip the // check for optimization. (SooEnabled() && !empty()))) { - ReserveAllocatedTable(common(), n, GetPolicyFunctions()); + ReserveAllocatedTable(common(), GetPolicyFunctions(), n); } else { if (ABSL_PREDICT_TRUE(n > DefaultCapacity())) { - ReserveEmptyNonAllocatedTableToFitNewSize(common(), n, - GetPolicyFunctions()); + ReserveEmptyNonAllocatedTableToFitNewSize(common(), + GetPolicyFunctions(), n); } } } @@ -3206,7 +3207,7 @@ sizeof(slot_type)) : 0, PolicyTraits::transfer_uses_memcpy()>( - common(), hash_of(soo_slot()), GetPolicyFunctions()); + common(), GetPolicyFunctions(), hash_of(soo_slot())); } } @@ -3263,8 +3264,8 @@ } common().increment_generation(); if (!empty() && common().should_rehash_for_bug_detection_on_move()) { - ResizeAllocatedTableWithSeedChange(common(), capacity(), - GetPolicyFunctions()); + ResizeAllocatedTableWithSeedChange(common(), GetPolicyFunctions(), + capacity()); } } @@ -3358,8 +3359,8 @@ if (ABSL_PREDICT_TRUE(mask_empty)) { size_t target = seq.offset( GetInsertionOffset(mask_empty, capacity(), hash, common().seed())); - return {iterator_at(PrepareInsertNonSoo(common(), hash, - GetPolicyFunctions(), + return {iterator_at(PrepareInsertNonSoo(common(), GetPolicyFunctions(), + hash, FindInfo{target, seq.index()})), true}; } @@ -3780,16 +3781,16 @@ // Extern template instantiations reduce binary size and linker input size. // Function definition is in raw_hash_set.cc. extern template void GrowFullSooTableToNextCapacity<0, false>( - CommonFields&, size_t, const PolicyFunctions&); + CommonFields&, const PolicyFunctions&, size_t); extern template void GrowFullSooTableToNextCapacity<1, true>( - CommonFields&, size_t, const PolicyFunctions&); + CommonFields&, const PolicyFunctions&, size_t); extern template void GrowFullSooTableToNextCapacity<4, true>( - CommonFields&, size_t, const PolicyFunctions&); + CommonFields&, const PolicyFunctions&, size_t); extern template void GrowFullSooTableToNextCapacity<8, true>( - CommonFields&, size_t, const PolicyFunctions&); + CommonFields&, const PolicyFunctions&, size_t); #if UINTPTR_MAX == UINT64_MAX extern template void GrowFullSooTableToNextCapacity<16, true>( - CommonFields&, size_t, const PolicyFunctions&); + CommonFields&, const PolicyFunctions&, size_t); #endif } // namespace container_internal