Pass swisstable seed as seed to absl::Hash so we can save an XOR in H1.
This reverts the optimization in Copy() of not hashing keys for single-group tables because we can no longer depend on H2 being constant for different tables of the same type.
Note that I also tried a version in which we don't change PerTableSeed to use sign-extended loads, but that version had worse performance on loadtests - presumably because the high bits of the seed are all 0. The intuition here is that if the high bits of the seed are all 0, then the high bits of the 128-bit product of the first Mix can also be all 0, which degrades the quality of the state after the first Mix.
PiperOrigin-RevId: 772077751
Change-Id: I5193d90209f4a0c7b41e36a484adb989311aed65
diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel
index 9a79523..6658772 100644
--- a/absl/container/BUILD.bazel
+++ b/absl/container/BUILD.bazel
@@ -410,6 +410,7 @@
linkopts = ABSL_DEFAULT_LINKOPTS,
deps = [
"//absl/base:config",
+ "//absl/hash",
"//absl/memory",
"//absl/meta:type_traits",
"//absl/utility",
@@ -749,6 +750,7 @@
":hashtable_debug_hooks",
":hashtablez_sampler",
":raw_hash_set_resize_impl",
+ "//absl/base",
"//absl/base:config",
"//absl/base:core_headers",
"//absl/base:dynamic_annotations",
diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt
index b1c3ffa..6adba18 100644
--- a/absl/container/CMakeLists.txt
+++ b/absl/container/CMakeLists.txt
@@ -469,6 +469,7 @@
${ABSL_DEFAULT_COPTS}
DEPS
absl::config
+ absl::hash
absl::memory
absl::type_traits
absl::utility
@@ -786,6 +787,7 @@
COPTS
${ABSL_DEFAULT_COPTS}
DEPS
+ absl::base
absl::bits
absl::common_policy_traits
absl::compressed_tuple
diff --git a/absl/container/flat_hash_map.h b/absl/container/flat_hash_map.h
index 5fa5023..a1f4f24 100644
--- a/absl/container/flat_hash_map.h
+++ b/absl/container/flat_hash_map.h
@@ -660,10 +660,10 @@
std::forward<Args>(args)...);
}
- template <class Hash>
+ template <class Hash, bool kIsDefault>
static constexpr HashSlotFn get_hash_slot_fn() {
return memory_internal::IsLayoutCompatible<K, V>::value
- ? &TypeErasedApplyToSlotFn<Hash, K>
+ ? &TypeErasedApplyToSlotFn<Hash, K, kIsDefault>
: nullptr;
}
diff --git a/absl/container/flat_hash_set.h b/absl/container/flat_hash_set.h
index bc1ceb1..2d25552 100644
--- a/absl/container/flat_hash_set.h
+++ b/absl/container/flat_hash_set.h
@@ -558,9 +558,9 @@
static size_t space_used(const T*) { return 0; }
- template <class Hash>
+ template <class Hash, bool kIsDefault>
static constexpr HashSlotFn get_hash_slot_fn() {
- return &TypeErasedApplyToSlotFn<Hash, T>;
+ return &TypeErasedApplyToSlotFn<Hash, T, kIsDefault>;
}
};
} // namespace container_internal
diff --git a/absl/container/flat_hash_set_test.cc b/absl/container/flat_hash_set_test.cc
index bb90efa..ca069b4 100644
--- a/absl/container/flat_hash_set_test.cc
+++ b/absl/container/flat_hash_set_test.cc
@@ -383,6 +383,20 @@
EXPECT_THAT(s, UnorderedElementsAre(1, 2, 3));
}
+TEST(FlatHashSet, IsDefaultHash) {
+ using absl::container_internal::hashtable_debug_internal::
+ HashtableDebugAccess;
+ EXPECT_EQ(HashtableDebugAccess<flat_hash_set<int>>::kIsDefaultHash, true);
+ EXPECT_EQ(HashtableDebugAccess<flat_hash_set<std::string>>::kIsDefaultHash,
+ true);
+
+ struct Hash {
+ size_t operator()(size_t i) const { return i; }
+ };
+ EXPECT_EQ((HashtableDebugAccess<flat_hash_set<size_t, Hash>>::kIsDefaultHash),
+ false);
+}
+
} // namespace
} // namespace container_internal
ABSL_NAMESPACE_END
diff --git a/absl/container/internal/container_memory.h b/absl/container/internal/container_memory.h
index ed7b90b..8c97469 100644
--- a/absl/container/internal/container_memory.h
+++ b/absl/container/internal/container_memory.h
@@ -26,6 +26,7 @@
#include <utility>
#include "absl/base/config.h"
+#include "absl/hash/hash.h"
#include "absl/memory/memory.h"
#include "absl/meta/type_traits.h"
#include "absl/utility/utility.h"
@@ -483,19 +484,33 @@
// Variadic arguments hash function that ignore the rest of the arguments.
// Useful for usage with policy traits.
-template <class Hash>
+template <class Hash, bool kIsDefault>
struct HashElement {
+ HashElement(const Hash& h, size_t s) : hash(h), seed(s) {}
+
template <class K, class... Args>
size_t operator()(const K& key, Args&&...) const {
- return h(key);
+ if constexpr (kIsDefault) {
+ // TODO(b/384509507): resolve `no header providing
+ // "absl::hash_internal::SupportsHashWithSeed" is directly included`.
+ // Maybe we should make "internal/hash.h" be a separate library.
+ return absl::hash_internal::HashWithSeed().hash(hash, key, seed);
+ }
+ // NOLINTNEXTLINE(clang-diagnostic-sign-conversion)
+ return hash(key) ^ seed;
}
- const Hash& h;
+ const Hash& hash;
+ size_t seed;
};
// No arguments function hash function for a specific key.
-template <class Hash, class Key>
+template <class Hash, class Key, bool kIsDefault>
struct HashKey {
- size_t operator()() const { return HashElement<Hash>{hash}(key); }
+ HashKey(const Hash& h, const Key& k) : hash(h), key(k) {}
+
+ size_t operator()(size_t seed) const {
+ return HashElement<Hash, kIsDefault>{hash, seed}(key);
+ }
const Hash& hash;
const Key& key;
};
@@ -513,23 +528,24 @@
};
// Type erased function for computing hash of the slot.
-using HashSlotFn = size_t (*)(const void* hash_fn, void* slot);
+using HashSlotFn = size_t (*)(const void* hash_fn, void* slot, size_t seed);
// Type erased function to apply `Fn` to data inside of the `slot`.
// The data is expected to have type `T`.
-template <class Fn, class T>
-size_t TypeErasedApplyToSlotFn(const void* fn, void* slot) {
+template <class Fn, class T, bool kIsDefault>
+size_t TypeErasedApplyToSlotFn(const void* fn, void* slot, size_t seed) {
const auto* f = static_cast<const Fn*>(fn);
- return HashElement<Fn>{*f}(*static_cast<const T*>(slot));
+ return HashElement<Fn, kIsDefault>{*f, seed}(*static_cast<const T*>(slot));
}
// Type erased function to apply `Fn` to data inside of the `*slot_ptr`.
// The data is expected to have type `T`.
-template <class Fn, class T>
-size_t TypeErasedDerefAndApplyToSlotFn(const void* fn, void* slot_ptr) {
+template <class Fn, class T, bool kIsDefault>
+size_t TypeErasedDerefAndApplyToSlotFn(const void* fn, void* slot_ptr,
+ size_t seed) {
const auto* f = static_cast<const Fn*>(fn);
const T* slot = *static_cast<const T**>(slot_ptr);
- return HashElement<Fn>{*f}(*slot);
+ return HashElement<Fn, kIsDefault>{*f, seed}(*slot);
}
} // namespace container_internal
diff --git a/absl/container/internal/container_memory_test.cc b/absl/container/internal/container_memory_test.cc
index 7e4357d..97b09f7 100644
--- a/absl/container/internal/container_memory_test.cc
+++ b/absl/container/internal/container_memory_test.cc
@@ -300,16 +300,46 @@
TEST(ApplyTest, TypeErasedApplyToSlotFn) {
size_t x = 7;
+ size_t seed = 100;
auto fn = [](size_t v) { return v * 2; };
- EXPECT_EQ((TypeErasedApplyToSlotFn<decltype(fn), size_t>(&fn, &x)), 14);
+ EXPECT_EQ(
+ (TypeErasedApplyToSlotFn<decltype(fn), size_t, /*kIsDefault=*/false>(
+ &fn, &x, seed)),
+ (HashElement<decltype(fn), /*kIsDefault=*/false>(fn, seed)(x)));
}
TEST(ApplyTest, TypeErasedDerefAndApplyToSlotFn) {
size_t x = 7;
+ size_t seed = 100;
auto fn = [](size_t v) { return v * 2; };
size_t* x_ptr = &x;
+ EXPECT_EQ((TypeErasedDerefAndApplyToSlotFn<decltype(fn), size_t,
+ /*kIsDefault=*/false>(&fn, &x_ptr,
+ seed)),
+ (HashElement<decltype(fn), /*kIsDefault=*/false>(fn, seed)(x)));
+}
+
+TEST(HashElement, DefaultHash) {
+ size_t x = 7;
+ size_t seed = 100;
+ struct HashWithSeed {
+ size_t operator()(size_t v) const { return v * 2; }
+ size_t hash_with_seed(size_t v, size_t seed) const {
+ return v * 2 + seed * 3;
+ }
+ } hash;
+ EXPECT_EQ((HashElement<HashWithSeed, /*kIsDefault=*/true>(hash, seed)(x)),
+ hash.hash_with_seed(x, seed));
+}
+
+TEST(HashElement, NonDefaultHash) {
+ size_t x = 7;
+ size_t seed = 100;
+ auto fn = [](size_t v) { return v * 2; };
EXPECT_EQ(
- (TypeErasedDerefAndApplyToSlotFn<decltype(fn), size_t>(&fn, &x_ptr)), 14);
+ (HashElement<decltype(fn), /*kIsDefault=*/false>(
+ fn, seed)(x)),
+ fn(x) ^ seed);
}
} // namespace
diff --git a/absl/container/internal/hash_function_defaults.h b/absl/container/internal/hash_function_defaults.h
index c2a757b..eefecab 100644
--- a/absl/container/internal/hash_function_defaults.h
+++ b/absl/container/internal/hash_function_defaults.h
@@ -79,6 +79,18 @@
size_t operator()(const absl::Cord& v) const {
return absl::Hash<absl::Cord>{}(v);
}
+
+ private:
+ friend struct absl::hash_internal::HashWithSeed;
+
+ size_t hash_with_seed(absl::string_view v, size_t seed) const {
+ return absl::hash_internal::HashWithSeed().hash(
+ absl::Hash<absl::string_view>{}, v, seed);
+ }
+ size_t hash_with_seed(const absl::Cord& v, size_t seed) const {
+ return absl::hash_internal::HashWithSeed().hash(absl::Hash<absl::Cord>{}, v,
+ seed);
+ }
};
struct StringEq {
diff --git a/absl/container/internal/hash_policy_traits.h b/absl/container/internal/hash_policy_traits.h
index 1d7c910..82eed2a 100644
--- a/absl/container/internal/hash_policy_traits.h
+++ b/absl/container/internal/hash_policy_traits.h
@@ -146,7 +146,7 @@
return P::value(elem);
}
- template <class Hash>
+ template <class Hash, bool kIsDefault>
static constexpr HashSlotFn get_hash_slot_fn() {
// get_hash_slot_fn may return nullptr to signal that non type erased function
// should be used. GCC warns against comparing function address with nullptr.
@@ -155,9 +155,9 @@
// silent error: the address of * will never be NULL [-Werror=address]
#pragma GCC diagnostic ignored "-Waddress"
#endif
- return Policy::template get_hash_slot_fn<Hash>() == nullptr
- ? &hash_slot_fn_non_type_erased<Hash>
- : Policy::template get_hash_slot_fn<Hash>();
+ return Policy::template get_hash_slot_fn<Hash, kIsDefault>() == nullptr
+ ? &hash_slot_fn_non_type_erased<Hash, kIsDefault>
+ : Policy::template get_hash_slot_fn<Hash, kIsDefault>();
#if defined(__GNUC__) && !defined(__clang__)
#pragma GCC diagnostic pop
#endif
@@ -167,10 +167,12 @@
static constexpr bool soo_enabled() { return soo_enabled_impl(Rank1{}); }
private:
- template <class Hash>
- static size_t hash_slot_fn_non_type_erased(const void* hash_fn, void* slot) {
- return Policy::apply(HashElement<Hash>{*static_cast<const Hash*>(hash_fn)},
- Policy::element(static_cast<slot_type*>(slot)));
+ template <class Hash, bool kIsDefault>
+ static size_t hash_slot_fn_non_type_erased(const void* hash_fn, void* slot,
+ size_t seed) {
+ return Policy::apply(
+ HashElement<Hash, kIsDefault>{*static_cast<const Hash*>(hash_fn), seed},
+ Policy::element(static_cast<slot_type*>(slot)));
}
// Use go/ranked-overloads for dispatching. Rank1 is preferred.
diff --git a/absl/container/internal/hash_policy_traits_test.cc b/absl/container/internal/hash_policy_traits_test.cc
index 2d2c7c2..03de132 100644
--- a/absl/container/internal/hash_policy_traits_test.cc
+++ b/absl/container/internal/hash_policy_traits_test.cc
@@ -45,7 +45,7 @@
static std::function<int(int)> apply_impl;
static std::function<Slot&(Slot*)> value;
- template <class Hash>
+ template <class Hash, bool kIsDefault>
static constexpr HashSlotFn get_hash_slot_fn() {
return nullptr;
}
@@ -99,7 +99,7 @@
return fn(v);
}
- template <class Hash>
+ template <class Hash, bool kIsDefault>
static constexpr HashSlotFn get_hash_slot_fn() {
return nullptr;
}
@@ -108,9 +108,9 @@
size_t* PolicyNoHashFn::apply_called_count;
struct PolicyCustomHashFn : PolicyNoHashFn {
- template <class Hash>
+ template <class Hash, bool kIsDefault>
static constexpr HashSlotFn get_hash_slot_fn() {
- return &TypeErasedApplyToSlotFn<Hash, int>;
+ return &TypeErasedApplyToSlotFn<Hash, int, kIsDefault>;
}
};
@@ -120,9 +120,11 @@
Hash hasher;
Slot value = 7;
- auto* fn = hash_policy_traits<PolicyNoHashFn>::get_hash_slot_fn<Hash>();
+ auto* fn = hash_policy_traits<PolicyNoHashFn>::get_hash_slot_fn<
+ Hash, /*kIsDefault=*/false>();
EXPECT_NE(fn, nullptr);
- EXPECT_EQ(fn(&hasher, &value), hasher(value));
+ EXPECT_EQ(fn(&hasher, &value, 100),
+ (HashElement<Hash, /*kIsDefault=*/false>(hasher, 100)(value)));
EXPECT_EQ(apply_called_count, 1);
}
@@ -132,9 +134,12 @@
Hash hasher;
Slot value = 7;
- auto* fn = hash_policy_traits<PolicyCustomHashFn>::get_hash_slot_fn<Hash>();
- EXPECT_EQ(fn, PolicyCustomHashFn::get_hash_slot_fn<Hash>());
- EXPECT_EQ(fn(&hasher, &value), hasher(value));
+ auto* fn = hash_policy_traits<PolicyCustomHashFn>::get_hash_slot_fn<
+ Hash, /*kIsDefault=*/false>();
+ EXPECT_EQ(
+ fn, (PolicyCustomHashFn::get_hash_slot_fn<Hash, /*kIsDefault=*/false>()));
+ EXPECT_EQ(fn(&hasher, &value, 100),
+ (HashElement<Hash, /*kIsDefault=*/false>(hasher, 100)(value)));
EXPECT_EQ(apply_called_count, 0);
}
diff --git a/absl/container/internal/raw_hash_set.cc b/absl/container/internal/raw_hash_set.cc
index daa9ff6..640c5a5 100644
--- a/absl/container/internal/raw_hash_set.cc
+++ b/absl/container/internal/raw_hash_set.cc
@@ -88,13 +88,13 @@
return value ^ static_cast<size_t>(reinterpret_cast<uintptr_t>(&counter));
}
-bool ShouldRehashForBugDetection(PerTableSeed seed, size_t capacity) {
+bool ShouldRehashForBugDetection(size_t capacity) {
// Note: we can't use the abseil-random library because abseil-random
// depends on swisstable. We want to return true with probability
// `min(1, RehashProbabilityConstant() / capacity())`. In order to do this,
// we probe based on a random hash and see if the offset is less than
// RehashProbabilityConstant().
- return probe(seed, capacity, absl::HashOf(RandomSeed())).offset() <
+ return probe(capacity, absl::HashOf(RandomSeed())).offset() <
RehashProbabilityConstant();
}
@@ -140,23 +140,22 @@
}
bool CommonFieldsGenerationInfoEnabled::
- should_rehash_for_bug_detection_on_insert(PerTableSeed seed,
- size_t capacity) const {
+ should_rehash_for_bug_detection_on_insert(size_t capacity) const {
if (reserved_growth_ == kReservedGrowthJustRanOut) return true;
if (reserved_growth_ > 0) return false;
- return ShouldRehashForBugDetection(seed, capacity);
+ return ShouldRehashForBugDetection(capacity);
}
bool CommonFieldsGenerationInfoEnabled::should_rehash_for_bug_detection_on_move(
- PerTableSeed seed, size_t capacity) const {
- return ShouldRehashForBugDetection(seed, capacity);
+ size_t capacity) const {
+ return ShouldRehashForBugDetection(capacity);
}
namespace {
FindInfo find_first_non_full_from_h1(const ctrl_t* ctrl, size_t h1,
size_t capacity) {
- auto seq = probe(h1, capacity);
+ auto seq = probe_h1(capacity, h1);
if (IsEmptyOrDeleted(ctrl[seq.offset()])) {
return {seq.offset(), /*probe_length=*/0};
}
@@ -248,7 +247,7 @@
}
FindInfo find_first_non_full(const CommonFields& common, size_t hash) {
- return find_first_non_full_from_h1(common.control(), H1(hash, common.seed()),
+ return find_first_non_full_from_h1(common.control(), H1(hash),
common.capacity());
}
@@ -344,7 +343,7 @@
continue;
}
if (!IsDeleted(ctrl[i])) continue;
- const size_t hash = (*hasher)(hash_fn, slot_ptr);
+ const size_t hash = (*hasher)(hash_fn, slot_ptr, common.seed().seed());
const FindInfo target = find_first_non_full(common, hash);
const size_t new_i = target.offset;
total_probe_length += target.probe_length;
@@ -576,9 +575,10 @@
void* new_slots = common.slot_array();
const void* hash_fn = policy.hash_fn(common);
const size_t slot_size = policy.slot_size;
+ const size_t seed = common.seed().seed();
const auto insert_slot = [&](void* slot) {
- size_t hash = policy.hash_slot(hash_fn, slot);
+ size_t hash = policy.hash_slot(hash_fn, slot, seed);
FindInfo target;
if (common.is_small()) {
target = FindInfo{0, 0};
@@ -687,8 +687,9 @@
common.set_capacity(new_capacity);
const auto [new_ctrl, new_slots] =
AllocBackingArray(common, policy, new_capacity, has_infoz, alloc);
- common.set_control</*kGenerateSeed=*/true>(new_ctrl);
+ common.set_control(new_ctrl);
common.set_slots(new_slots);
+ common.generate_new_seed(has_infoz);
size_t total_probe_length = 0;
ResetCtrl(common, slot_size);
@@ -738,23 +739,26 @@
// It is rare to resize an SOO table with one element to a large size.
// Requires: `c` contains SOO data.
void InsertOldSooSlotAndInitializeControlBytes(
- CommonFields& c, const PolicyFunctions& __restrict policy, size_t hash,
- ctrl_t* new_ctrl, void* new_slots) {
+ CommonFields& c, const PolicyFunctions& __restrict policy, ctrl_t* new_ctrl,
+ void* new_slots, bool has_infoz) {
ABSL_SWISSTABLE_ASSERT(c.size() == policy.soo_capacity());
ABSL_SWISSTABLE_ASSERT(policy.soo_enabled);
size_t new_capacity = c.capacity();
- c.generate_new_seed();
- size_t offset = probe(c.seed(), new_capacity, hash).offset();
+ c.generate_new_seed(has_infoz);
+
+ const size_t soo_slot_hash =
+ policy.hash_slot(policy.hash_fn(c), c.soo_data(), c.seed().seed());
+ size_t offset = probe(new_capacity, soo_slot_hash).offset();
offset = offset == new_capacity ? 0 : offset;
SanitizerPoisonMemoryRegion(new_slots, policy.slot_size * new_capacity);
void* target_slot = SlotAddress(new_slots, offset, policy.slot_size);
SanitizerUnpoisonMemoryRegion(target_slot, policy.slot_size);
policy.transfer_n(&c, target_slot, c.soo_data(), 1);
- c.set_control</*kGenerateSeed=*/false>(new_ctrl);
+ c.set_control(new_ctrl);
c.set_slots(new_slots);
ResetCtrl(c, policy.slot_size);
- SetCtrl(c, offset, H2(hash), policy.slot_size);
+ SetCtrl(c, offset, H2(soo_slot_hash), policy.slot_size);
}
enum class ResizeFullSooTableSamplingMode {
@@ -783,6 +787,7 @@
void* alloc = policy.get_char_alloc(common);
HashtablezInfoHandle infoz;
+ bool has_infoz = false;
if (sampling_mode ==
ResizeFullSooTableSamplingMode::kForceSampleNoResizeIfUnsampled) {
if (ABSL_PREDICT_FALSE(policy.is_hashtablez_eligible)) {
@@ -790,13 +795,10 @@
policy.soo_capacity());
}
- if (!infoz.IsSampled()) {
- return;
- }
+ if (!infoz.IsSampled()) return;
+ has_infoz = true;
}
- const bool has_infoz = infoz.IsSampled();
-
common.set_capacity(new_capacity);
// We do not set control and slots in CommonFields yet to avoid overriding
@@ -804,11 +806,8 @@
const auto [new_ctrl, new_slots] =
AllocBackingArray(common, policy, new_capacity, has_infoz, alloc);
- const size_t soo_slot_hash =
- policy.hash_slot(policy.hash_fn(common), common.soo_data());
-
- InsertOldSooSlotAndInitializeControlBytes(common, policy, soo_slot_hash,
- new_ctrl, new_slots);
+ InsertOldSooSlotAndInitializeControlBytes(common, policy, new_ctrl, new_slots,
+ has_infoz);
ResetGrowthLeft(common);
if (has_infoz) {
common.set_has_infoz();
@@ -998,12 +997,13 @@
const void* hash_fn = policy.hash_fn(c);
auto hash_slot = policy.hash_slot;
auto transfer_n = policy.transfer_n;
+ const size_t seed = c.seed().seed();
for (size_t old_index = start; old_index < old_capacity; ++old_index) {
if (old_ctrl[old_index] != ctrl_t::kSentinel) {
continue;
}
void* src_slot = SlotAddress(old_slots, old_index, slot_size);
- const size_t hash = hash_slot(hash_fn, src_slot);
+ const size_t hash = hash_slot(hash_fn, src_slot, seed);
const FindInfo target = find_first_non_full(c, hash);
total_probe_length += target.probe_length;
const size_t new_i = target.offset;
@@ -1276,7 +1276,7 @@
std::pair<ctrl_t*, void*> Grow1To3AndPrepareInsert(
CommonFields& common, const PolicyFunctions& __restrict policy,
- absl::FunctionRef<size_t()> get_hash) {
+ absl::FunctionRef<size_t(size_t)> get_hash) {
// TODO(b/413062340): Refactor to reuse more code with
// GrowSooTableToNextCapacityAndPrepareInsert.
ABSL_SWISSTABLE_ASSERT(common.capacity() == 1);
@@ -1296,13 +1296,18 @@
const auto [new_ctrl, new_slots] =
AllocBackingArray(common, policy, kNewCapacity, has_infoz, alloc);
- common.set_control</*kGenerateSeed=*/true>(new_ctrl);
+ common.set_control(new_ctrl);
common.set_slots(new_slots);
SanitizerPoisonMemoryRegion(new_slots, kNewCapacity * slot_size);
- const size_t new_hash = get_hash();
+ if (ABSL_PREDICT_TRUE(!has_infoz)) {
+ // When we're sampled, we already have a seed.
+ common.generate_new_seed(/*has_infoz=*/false);
+ }
+ const size_t new_hash = get_hash(common.seed().seed());
h2_t new_h2 = H2(new_hash);
- size_t orig_hash = policy.hash_slot(policy.hash_fn(common), old_slots);
+ size_t orig_hash =
+ policy.hash_slot(policy.hash_fn(common), old_slots, common.seed().seed());
size_t offset = Resize1To3NewOffset(new_hash, common.seed());
InitializeThreeElementsControlBytes(H2(orig_hash), new_h2, offset, new_ctrl);
@@ -1348,7 +1353,7 @@
const auto [new_ctrl, new_slots] =
AllocBackingArray(common, policy, new_capacity, has_infoz, alloc);
- common.set_control</*kGenerateSeed=*/false>(new_ctrl);
+ common.set_control(new_ctrl);
common.set_slots(new_slots);
SanitizerPoisonMemoryRegion(new_slots, new_capacity * slot_size);
@@ -1397,7 +1402,7 @@
std::pair<ctrl_t*, void*> PrepareInsertSmallNonSoo(
CommonFields& common, const PolicyFunctions& __restrict policy,
- absl::FunctionRef<size_t()> get_hash) {
+ absl::FunctionRef<size_t(size_t)> get_hash) {
ABSL_SWISSTABLE_ASSERT(common.is_small());
ABSL_SWISSTABLE_ASSERT(!policy.soo_enabled);
if (common.capacity() == 1) {
@@ -1426,15 +1431,16 @@
const auto [new_ctrl, new_slots] =
AllocBackingArray(common, policy, kNewCapacity, has_infoz, alloc);
- // In small tables seed is not needed.
- common.set_control</*kGenerateSeed=*/false>(new_ctrl);
+ common.set_control(new_ctrl);
common.set_slots(new_slots);
static_assert(NextCapacity(0) == 1);
PrepareInsertCommon(common);
if (ABSL_PREDICT_FALSE(has_infoz)) {
- ReportSingleGroupTableGrowthToInfoz(common, infoz, get_hash());
+ common.generate_new_seed(/*has_infoz=*/true);
+ ReportSingleGroupTableGrowthToInfoz(common, infoz,
+ get_hash(common.seed().seed()));
}
return {SooControl(), new_slots};
}
@@ -1535,11 +1541,12 @@
ABSL_ATTRIBUTE_NOINLINE size_t
GrowEmptySooTableToNextCapacityForceSamplingAndPrepareInsert(
CommonFields& common, const PolicyFunctions& __restrict policy,
- size_t new_hash) {
+ absl::FunctionRef<size_t(size_t)> get_hash) {
ResizeEmptyNonAllocatedTableImpl(common, policy, NextCapacity(SooCapacity()),
/*force_infoz=*/true);
PrepareInsertCommon(common);
common.growth_info().OverwriteEmptyAsFull();
+ const size_t new_hash = get_hash(common.seed().seed());
SetCtrlInSingleGroupTable(common, SooSlotIndex(), H2(new_hash),
policy.slot_size);
common.infoz().RecordInsert(new_hash, /*distance_from_desired=*/0);
@@ -1630,12 +1637,12 @@
template <size_t SooSlotMemcpySize, bool TransferUsesMemcpy>
size_t GrowSooTableToNextCapacityAndPrepareInsert(
CommonFields& common, const PolicyFunctions& __restrict policy,
- size_t new_hash, ctrl_t soo_slot_ctrl) {
+ absl::FunctionRef<size_t(size_t)> get_hash, bool force_sampling) {
AssertSoo(common, policy);
- if (ABSL_PREDICT_FALSE(soo_slot_ctrl == ctrl_t::kEmpty)) {
+ if (ABSL_PREDICT_FALSE(force_sampling)) {
// The table is empty, it is only used for forced sampling of SOO tables.
return GrowEmptySooTableToNextCapacityForceSamplingAndPrepareInsert(
- common, policy, new_hash);
+ common, policy, get_hash);
}
ABSL_SWISSTABLE_ASSERT(common.size() == policy.soo_capacity());
static constexpr size_t kNewCapacity = NextCapacity(SooCapacity());
@@ -1654,11 +1661,14 @@
PrepareInsertCommon(common);
ABSL_SWISSTABLE_ASSERT(common.size() == 2);
GetGrowthInfoFromControl(new_ctrl).InitGrowthLeftNoDeleted(kNewCapacity - 2);
- common.generate_new_seed();
+ common.generate_new_seed(/*has_infoz=*/false);
+ const h2_t soo_slot_h2 = H2(policy.hash_slot(
+ policy.hash_fn(common), common.soo_data(), common.seed().seed()));
+ const size_t new_hash = get_hash(common.seed().seed());
const size_t offset = Resize1To3NewOffset(new_hash, common.seed());
- InitializeThreeElementsControlBytes(static_cast<h2_t>(soo_slot_ctrl),
- H2(new_hash), offset, new_ctrl);
+ InitializeThreeElementsControlBytes(soo_slot_h2, H2(new_hash), offset,
+ new_ctrl);
SanitizerPoisonMemoryRegion(new_slots, slot_size * kNewCapacity);
void* target_slot = SlotAddress(new_slots, SooSlotIndex(), slot_size);
@@ -1680,8 +1690,7 @@
static_assert(SooSlotMemcpySize == 0);
policy.transfer_n(&common, target_slot, common.soo_data(), 1);
}
- // Seed was already generated above.
- common.set_control</*kGenerateSeed=*/false>(new_ctrl);
+ common.set_control(new_ctrl);
common.set_slots(new_slots);
// Full SOO table couldn't be sampled. If SOO table is sampled, it would
@@ -1793,47 +1802,22 @@
ABSL_SWISSTABLE_ASSERT(other.capacity() > soo_capacity);
const size_t cap = common.capacity();
ABSL_SWISSTABLE_ASSERT(cap > soo_capacity);
- // Note about single group tables:
- // 1. It is correct to have any order of elements.
- // 2. Order has to be non deterministic.
- // 3. We are assigning elements with arbitrary `shift` starting from
- // `capacity + shift` position.
- // 4. `shift` must be coprime with `capacity + 1` in order to be able to use
- // modular arithmetic to traverse all positions, instead of cycling
- // through a subset of positions. Odd numbers are coprime with any
- // `capacity + 1` (2^N).
size_t offset = cap;
- const size_t shift = is_single_group(cap) ? (common.seed().seed() | 1) : 0;
const void* hash_fn = policy.hash_fn(common);
auto hasher = policy.hash_slot;
+ const size_t seed = common.seed().seed();
IterateOverFullSlotsImpl(
- other, slot_size, [&](const ctrl_t* that_ctrl, void* that_slot) {
- if (shift == 0) {
- // Big tables case. Position must be searched via probing.
- // The table is guaranteed to be empty, so we can do faster than
- // a full `insert`.
- const size_t hash = (*hasher)(hash_fn, that_slot);
- FindInfo target = find_first_non_full(common, hash);
- infoz.RecordInsert(hash, target.probe_length);
- offset = target.offset;
- } else {
- // Small tables case. Next position is computed via shift.
- offset = (offset + shift) & cap;
- }
- const h2_t h2 = static_cast<h2_t>(*that_ctrl);
- // We rely on the hash not changing for small tables.
- ABSL_SWISSTABLE_ASSERT(
- H2((*hasher)(hash_fn, that_slot)) == h2 &&
- "hash function value changed unexpectedly during the copy");
- SetCtrl(common, offset, h2, slot_size);
+ other, slot_size, [&](const ctrl_t*, void* that_slot) {
+ // The table is guaranteed to be empty, so we can do faster than
+ // a full `insert`.
+ const size_t hash = (*hasher)(hash_fn, that_slot, seed);
+ FindInfo target = find_first_non_full(common, hash);
+ infoz.RecordInsert(hash, target.probe_length);
+ offset = target.offset;
+ SetCtrl(common, offset, H2(hash), slot_size);
copy_fn(SlotAddress(common.slot_array(), offset, slot_size), that_slot);
common.maybe_increment_generation_on_insert();
});
- if (shift != 0) {
- // On small table copy we do not record individual inserts.
- // RecordInsert requires hash, but it is unknown for small tables.
- infoz.RecordStorageChanged(size, cap);
- }
common.increment_size(size);
common.growth_info().OverwriteManyEmptyAsFull(size);
}
@@ -1859,18 +1843,11 @@
ReserveAllocatedTable(common, policy, new_size);
}
-size_t PrepareInsertLarge(CommonFields& common,
- const PolicyFunctions& __restrict policy, size_t hash,
- FindInfo target) {
+namespace {
+size_t PrepareInsertLargeImpl(CommonFields& common,
+ const PolicyFunctions& __restrict policy,
+ size_t hash, FindInfo target) {
ABSL_SWISSTABLE_ASSERT(!common.is_small());
- if (common.should_rehash_for_bug_detection_on_insert()) {
- // Move to a different heap allocation in order to detect bugs.
- const size_t cap = common.capacity();
- ResizeAllocatedTableWithSeedChange(
- common, policy, common.growth_left() > 0 ? cap : NextCapacity(cap));
- target = find_first_non_full(common, hash);
- }
-
const GrowthInfo growth_info = common.growth_info();
// When there are no deleted slots in the table
// and growth_left is positive, we can insert at the first
@@ -1884,6 +1861,31 @@
common.infoz().RecordInsert(hash, target.probe_length);
return target.offset;
}
+} // namespace
+
+size_t PrepareInsertLarge(CommonFields& common,
+ const PolicyFunctions& __restrict policy, size_t hash,
+ FindInfo target) {
+ // NOLINTNEXTLINE(misc-static-assert)
+ ABSL_SWISSTABLE_ASSERT(!SwisstableGenerationsEnabled());
+ return PrepareInsertLargeImpl(common, policy, hash, target);
+}
+
+size_t PrepareInsertLargeGenerationsEnabled(
+ CommonFields& common, const PolicyFunctions& policy, size_t hash,
+ FindInfo target, absl::FunctionRef<size_t(size_t)> recompute_hash) {
+ // NOLINTNEXTLINE(misc-static-assert)
+ ABSL_SWISSTABLE_ASSERT(SwisstableGenerationsEnabled());
+ if (common.should_rehash_for_bug_detection_on_insert()) {
+ // Move to a different heap allocation in order to detect bugs.
+ const size_t cap = common.capacity();
+ ResizeAllocatedTableWithSeedChange(
+ common, policy, common.growth_left() > 0 ? cap : NextCapacity(cap));
+ hash = recompute_hash(common.seed().seed());
+ target = find_first_non_full(common, hash);
+ }
+ return PrepareInsertLargeImpl(common, policy, hash, target);
+}
namespace {
// Returns true if the following is true
@@ -1919,32 +1921,33 @@
// We need to instantiate ALL possible template combinations because we define
// the function in the cc file.
template size_t GrowSooTableToNextCapacityAndPrepareInsert<0, false>(
- CommonFields&, const PolicyFunctions&, size_t, ctrl_t);
+ CommonFields&, const PolicyFunctions&, absl::FunctionRef<size_t(size_t)>,
+ bool);
template size_t GrowSooTableToNextCapacityAndPrepareInsert<
- OptimalMemcpySizeForSooSlotTransfer(1), true>(CommonFields&,
- const PolicyFunctions&,
- size_t, ctrl_t);
+ OptimalMemcpySizeForSooSlotTransfer(1), true>(
+ CommonFields&, const PolicyFunctions&, absl::FunctionRef<size_t(size_t)>,
+ bool);
static_assert(VerifyOptimalMemcpySizeForSooSlotTransferRange(2, 3));
template size_t GrowSooTableToNextCapacityAndPrepareInsert<
- OptimalMemcpySizeForSooSlotTransfer(3), true>(CommonFields&,
- const PolicyFunctions&,
- size_t, ctrl_t);
+ OptimalMemcpySizeForSooSlotTransfer(3), true>(
+ CommonFields&, const PolicyFunctions&, absl::FunctionRef<size_t(size_t)>,
+ bool);
static_assert(VerifyOptimalMemcpySizeForSooSlotTransferRange(4, 8));
template size_t GrowSooTableToNextCapacityAndPrepareInsert<
- OptimalMemcpySizeForSooSlotTransfer(8), true>(CommonFields&,
- const PolicyFunctions&,
- size_t, ctrl_t);
+ OptimalMemcpySizeForSooSlotTransfer(8), true>(
+ CommonFields&, const PolicyFunctions&, absl::FunctionRef<size_t(size_t)>,
+ bool);
#if UINTPTR_MAX == UINT32_MAX
static_assert(MaxSooSlotSize() == 8);
#else
static_assert(VerifyOptimalMemcpySizeForSooSlotTransferRange(9, 16));
template size_t GrowSooTableToNextCapacityAndPrepareInsert<
- OptimalMemcpySizeForSooSlotTransfer(16), true>(CommonFields&,
- const PolicyFunctions&,
- size_t, ctrl_t);
+ OptimalMemcpySizeForSooSlotTransfer(16), true>(
+ CommonFields&, const PolicyFunctions&, absl::FunctionRef<size_t(size_t)>,
+ bool);
static_assert(MaxSooSlotSize() == 16);
#endif
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h
index 7106bc8..08c5d57 100644
--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -194,6 +194,7 @@
#include <utility>
#include "absl/base/attributes.h"
+#include "absl/base/casts.h"
#include "absl/base/config.h"
#include "absl/base/internal/endian.h"
#include "absl/base/internal/iterator_traits.h"
@@ -446,18 +447,29 @@
// The number of bits in the seed.
// It is big enough to ensure non-determinism of iteration order.
// We store the seed inside a uint64_t together with size and other metadata.
- // Using 16 bits allows us to save one `and` instruction in H1 (we use movzwl
- // instead of movq+and).
+ // Using 16 bits allows us to save one `and` instruction in H1 (we use
+ // sign-extended move instead of mov+and).
static constexpr size_t kBitCount = 16;
+ static constexpr size_t kSignBit = uint64_t{1} << (kBitCount - 1);
- // Returns the seed for the table. Only the lowest kBitCount are non zero.
- size_t seed() const { return seed_; }
+ // Returns the seed for the table.
+ size_t seed() const {
+ // We use a sign-extended load to ensure high bits are non-zero.
+ int16_t seed_signed = absl::bit_cast<int16_t>(seed_);
+ auto seed_sign_extended =
+ static_cast<std::make_signed_t<size_t>>(seed_signed);
+ return absl::bit_cast<size_t>(seed_sign_extended);
+ }
private:
friend class HashtableSize;
- explicit PerTableSeed(size_t seed) : seed_(seed) {}
+ explicit PerTableSeed(uint16_t seed) : seed_(seed) {
+ ABSL_SWISSTABLE_ASSERT((seed & kSignBit) != 0 || seed == 0);
+ }
- const size_t seed_;
+ // The most significant bit of the seed is always 1 when there is a non-zero
+ // seed. This way, when sign-extended the seed has non-zero high bits.
+ const uint16_t seed_;
};
// Returns next per-table seed.
@@ -496,8 +508,14 @@
return PerTableSeed(static_cast<size_t>(data_) & kSeedMask);
}
- void generate_new_seed() {
- data_ = (data_ & ~kSeedMask) ^ uint64_t{NextSeed()};
+ void generate_new_seed() { set_seed(NextSeed()); }
+
+ // We need to use a constant seed when the table is sampled so that sampled
+ // hashes use the same seed and can e.g. identify stuck bits accurately.
+ void set_sampled_seed() { set_seed(PerTableSeed::kSignBit); }
+
+ bool is_sampled_seed() const {
+ return (data_ & kSeedMask) == PerTableSeed::kSignBit;
}
// Returns true if the table has infoz.
@@ -511,6 +529,9 @@
void set_no_seed_for_testing() { data_ &= ~kSeedMask; }
private:
+ void set_seed(uint16_t seed) {
+ data_ = (data_ & ~kSeedMask) | (seed | PerTableSeed::kSignBit);
+ }
static constexpr size_t kSizeShift = 64 - kSizeBitCount;
static constexpr uint64_t kSizeOneNoMetadata = uint64_t{1} << kSizeShift;
static constexpr uint64_t kMetadataMask = kSizeOneNoMetadata - 1;
@@ -521,11 +542,8 @@
uint64_t data_;
};
-// Mixes the hash with a per-table seed. Note that we only use the low bits of
-// H1 because we bitwise-and with capacity later.
-inline size_t H1(size_t hash, PerTableSeed seed) {
- return hash ^ seed.seed();
-}
+// H1 is just the low bits of the hash.
+inline size_t H1(size_t hash) { return hash; }
// Extracts the H2 portion of a hash: the 7 most significant bits.
//
@@ -566,11 +584,9 @@
// references. We rehash on the first insertion after reserved_growth_ reaches
// 0 after a call to reserve. We also do a rehash with low probability
// whenever reserved_growth_ is zero.
- bool should_rehash_for_bug_detection_on_insert(PerTableSeed seed,
- size_t capacity) const;
+ bool should_rehash_for_bug_detection_on_insert(size_t capacity) const;
// Similar to above, except that we don't depend on reserved_growth_.
- bool should_rehash_for_bug_detection_on_move(PerTableSeed seed,
- size_t capacity) const;
+ bool should_rehash_for_bug_detection_on_move(size_t capacity) const;
void maybe_increment_generation_on_insert() {
if (reserved_growth_ == kReservedGrowthJustRanOut) reserved_growth_ = 0;
@@ -623,12 +639,8 @@
CommonFieldsGenerationInfoDisabled& operator=(
CommonFieldsGenerationInfoDisabled&&) = default;
- bool should_rehash_for_bug_detection_on_insert(PerTableSeed, size_t) const {
- return false;
- }
- bool should_rehash_for_bug_detection_on_move(PerTableSeed, size_t) const {
- return false;
- }
+ bool should_rehash_for_bug_detection_on_insert(size_t) const { return false; }
+ bool should_rehash_for_bug_detection_on_move(size_t) const { return false; }
void maybe_increment_generation_on_insert() {}
void increment_generation() {}
void reset_reserved_growth(size_t, size_t) {}
@@ -955,19 +967,7 @@
ABSL_SWISSTABLE_IGNORE_UNINITIALIZED_RETURN(heap_or_soo_.control().get());
}
- // When we set the control bytes, we also often want to generate a new seed.
- // So we bundle these two operations together to make sure we don't forget to
- // generate a new seed.
- // The table will be invalidated if
- // `kGenerateSeed && !empty() && !is_single_group(capacity())` because H1 is
- // being changed. In such cases, we will need to rehash the table.
- template <bool kGenerateSeed>
- void set_control(ctrl_t* c) {
- heap_or_soo_.control().set(c);
- if constexpr (kGenerateSeed) {
- generate_new_seed();
- }
- }
+ void set_control(ctrl_t* c) { heap_or_soo_.control().set(c); }
// Note: we can't use slots() because Qt defines "slots" as a macro.
void* slot_array() const { return heap_or_soo_.slot_array().get(); }
@@ -1002,13 +1002,20 @@
}
bool empty() const { return size_.empty(); }
- // The seed used for the H1 part of the hash function.
+ // The seed used for the hash function.
PerTableSeed seed() const { return size_.seed(); }
- // Generates a new seed for the H1 part of the hash function.
- // The table will be invalidated if
- // `kGenerateSeed && !empty() && !is_single_group(capacity())` because H1 is
- // being changed. In such cases, we will need to rehash the table.
- void generate_new_seed() { size_.generate_new_seed(); }
+ // Generates a new seed the hash function.
+ // The table will be invalidated if `!empty()` because hash is being changed.
+ // In such cases, we will need to rehash the table.
+ void generate_new_seed(bool has_infoz) {
+ // Note: we can't use has_infoz() here because we set has_infoz later than
+ // we generate the seed.
+ if (ABSL_PREDICT_FALSE(has_infoz)) {
+ size_.set_sampled_seed();
+ return;
+ }
+ size_.generate_new_seed();
+ }
void set_no_seed_for_testing() { size_.set_no_seed_for_testing(); }
// The total number of available slots.
@@ -1036,7 +1043,10 @@
}
bool has_infoz() const { return size_.has_infoz(); }
- void set_has_infoz() { size_.set_has_infoz(); }
+ void set_has_infoz() {
+ ABSL_SWISSTABLE_ASSERT(size_.is_sampled_seed());
+ size_.set_has_infoz();
+ }
HashtablezInfoHandle* infoz_ptr() const {
// growth_info is stored before control bytes.
@@ -1063,11 +1073,11 @@
// will end up rehashing anyways.
if (growth_left() == 0) return false;
return CommonFieldsGenerationInfo::
- should_rehash_for_bug_detection_on_insert(seed(), capacity());
+ should_rehash_for_bug_detection_on_insert(capacity());
}
bool should_rehash_for_bug_detection_on_move() const {
return CommonFieldsGenerationInfo::should_rehash_for_bug_detection_on_move(
- seed(), capacity());
+ capacity());
}
void reset_reserved_growth(size_t reservation) {
CommonFieldsGenerationInfo::reset_reserved_growth(reservation, size());
@@ -1402,15 +1412,14 @@
}
// Begins a probing operation on `common.control`, using `hash`.
-inline probe_seq<Group::kWidth> probe(size_t h1, size_t capacity) {
+inline probe_seq<Group::kWidth> probe_h1(size_t capacity, size_t h1) {
return probe_seq<Group::kWidth>(h1, capacity);
}
-inline probe_seq<Group::kWidth> probe(PerTableSeed seed, size_t capacity,
- size_t hash) {
- return probe(H1(hash, seed), capacity);
+inline probe_seq<Group::kWidth> probe(size_t capacity, size_t hash) {
+ return probe_h1(capacity, H1(hash));
}
inline probe_seq<Group::kWidth> probe(const CommonFields& common, size_t hash) {
- return probe(common.seed(), common.capacity(), hash);
+ return probe(common.capacity(), hash);
}
// Probes an array of control bits using a probe sequence derived from `hash`,
@@ -1611,7 +1620,7 @@
void* (*hash_fn)(CommonFields& common);
// Returns the hash of the pointed-to slot.
- size_t (*hash_slot)(const void* hash_fn, void* slot);
+ HashSlotFn hash_slot;
// Transfers the contents of `count` slots from src_slot to dst_slot.
// We use ability to transfer several slots in single group table growth.
@@ -1766,17 +1775,12 @@
// Resizes SOO table to the NextCapacity(SooCapacity()) and prepares insert for
// the given new_hash. Returns the offset of the new element.
-// `soo_slot_ctrl` is the control byte of the SOO slot.
-// If soo_slot_ctrl is kEmpty
-// 1. The table must be empty.
-// 2. Table will be forced to be sampled.
// All possible template combinations are defined in cc file to improve
// compilation time.
template <size_t SooSlotMemcpySize, bool TransferUsesMemcpy>
-size_t GrowSooTableToNextCapacityAndPrepareInsert(CommonFields& common,
- const PolicyFunctions& policy,
- size_t new_hash,
- ctrl_t soo_slot_ctrl);
+size_t GrowSooTableToNextCapacityAndPrepareInsert(
+ CommonFields& common, const PolicyFunctions& policy,
+ absl::FunctionRef<size_t(size_t)> get_hash, bool force_sampling);
// PrepareInsert for small tables (is_small()==true).
// Returns the new control and the new slot.
@@ -1784,7 +1788,7 @@
// (is_small()==false).
std::pair<ctrl_t*, void*> PrepareInsertSmallNonSoo(
CommonFields& common, const PolicyFunctions& policy,
- absl::FunctionRef<size_t()> get_hash);
+ absl::FunctionRef<size_t(size_t)> get_hash);
// Resizes table with allocated slots and change the table seed.
// Tables with SOO enabled must have capacity > policy.soo_capacity.
@@ -1837,6 +1841,12 @@
size_t PrepareInsertLarge(CommonFields& common, const PolicyFunctions& policy,
size_t hash, FindInfo target);
+// 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.
+size_t PrepareInsertLargeGenerationsEnabled(
+ CommonFields& common, const PolicyFunctions& policy, size_t hash,
+ FindInfo target, absl::FunctionRef<size_t(size_t)> recompute_hash);
+
// A SwissTable.
//
// Policy: a policy defines how to perform different operations on
@@ -1890,6 +1900,10 @@
using slot_type = typename PolicyTraits::slot_type;
+ constexpr static bool kIsDefaultHash =
+ std::is_same_v<hasher, absl::Hash<key_type>> ||
+ std::is_same_v<hasher, absl::container_internal::StringHash>;
+
// TODO(b/289225379): we could add extra SOO space inside raw_hash_set
// after CommonFields to allow inlining larger slot_types (e.g. std::string),
// but it's a bit complicated if we want to support incomplete mapped_type in
@@ -3091,11 +3105,13 @@
}
template <class K>
ABSL_ATTRIBUTE_ALWAYS_INLINE size_t hash_of(const K& key) const {
- return HashElement<hasher>{hash_ref()}(key);
+ return HashElement<hasher, kIsDefaultHash>{hash_ref(),
+ common().seed().seed()}(key);
}
ABSL_ATTRIBUTE_ALWAYS_INLINE size_t hash_of(slot_type* slot) const {
- return PolicyTraits::apply(HashElement<hasher>{hash_ref()},
- PolicyTraits::element(slot));
+ return PolicyTraits::apply(
+ HashElement<hasher, kIsDefaultHash>{hash_ref(), common().seed().seed()},
+ PolicyTraits::element(slot));
}
// Casting directly from e.g. char* to slot_type* can cause compilation errors
@@ -3211,25 +3227,26 @@
template <class K>
std::pair<iterator, bool> find_or_prepare_insert_soo(const K& key) {
ABSL_SWISSTABLE_ASSERT(is_soo());
- ctrl_t soo_slot_ctrl;
+ bool force_sampling;
if (empty()) {
if (!should_sample_soo()) {
common().set_full_soo();
return {single_iterator(), true};
}
- soo_slot_ctrl = ctrl_t::kEmpty;
+ force_sampling = true;
} else if (equal_to(key, single_slot())) {
return {single_iterator(), false};
} else {
- soo_slot_ctrl = static_cast<ctrl_t>(H2(hash_of(single_slot())));
+ force_sampling = false;
}
ABSL_SWISSTABLE_ASSERT(capacity() == 1);
- const size_t hash = hash_of(key);
constexpr bool kUseMemcpy =
PolicyTraits::transfer_uses_memcpy() && SooEnabled();
size_t index = GrowSooTableToNextCapacityAndPrepareInsert<
kUseMemcpy ? OptimalMemcpySizeForSooSlotTransfer(sizeof(slot_type)) : 0,
- kUseMemcpy>(common(), GetPolicyFunctions(), hash, soo_slot_ctrl);
+ kUseMemcpy>(common(), GetPolicyFunctions(),
+ HashKey<hasher, K, kIsDefaultHash>{hash_ref(), key},
+ force_sampling);
return {iterator_at(index), true};
}
@@ -3244,9 +3261,9 @@
return {single_iterator(), false};
}
}
- return {iterator_at_ptr(
- PrepareInsertSmallNonSoo(common(), GetPolicyFunctions(),
- HashKey<hasher, K>{hash_ref(), key})),
+ return {iterator_at_ptr(PrepareInsertSmallNonSoo(
+ common(), GetPolicyFunctions(),
+ HashKey<hasher, K, kIsDefaultHash>{hash_ref(), key})),
true};
}
@@ -3270,10 +3287,15 @@
auto mask_empty = g.MaskEmpty();
if (ABSL_PREDICT_TRUE(mask_empty)) {
size_t target = seq.offset(mask_empty.LowestBitSet());
- return {
- iterator_at(PrepareInsertLarge(common(), GetPolicyFunctions(), hash,
- FindInfo{target, seq.index()})),
- true};
+ size_t index =
+ SwisstableGenerationsEnabled()
+ ? PrepareInsertLargeGenerationsEnabled(
+ common(), GetPolicyFunctions(), hash,
+ FindInfo{target, seq.index()},
+ HashKey<hasher, K, kIsDefaultHash>{hash_ref(), key})
+ : PrepareInsertLarge(common(), GetPolicyFunctions(), hash,
+ FindInfo{target, seq.index()});
+ return {iterator_at(index), true};
}
seq.next();
ABSL_SWISSTABLE_ASSERT(seq.index() <= capacity() && "full table!");
@@ -3526,8 +3548,6 @@
ctrl_t* new_ctrl = common.control();
slot_type* new_slots = set->slot_array();
- const PerTableSeed seed = common.seed();
-
for (size_t group_index = 0; group_index < old_capacity;
group_index += Group::kWidth) {
GroupFullEmptyOrDeleted old_g(old_ctrl + group_index);
@@ -3543,7 +3563,7 @@
// TODO(b/382423690): try to avoid entire hash calculation since we need
// only one new bit of h1.
size_t hash = set->hash_of(old_slot);
- size_t h1 = H1(hash, seed);
+ size_t h1 = H1(hash);
h2_t h2 = H2(hash);
size_t new_index = TryFindNewIndexWithoutProbing(
h1, old_index, old_capacity, new_ctrl, new_capacity);
@@ -3586,7 +3606,7 @@
// for standard layout and alignof(Hash) <= alignof(CommonFields).
std::is_empty_v<hasher> ? &GetRefForEmptyClass
: &raw_hash_set::get_hash_ref_fn,
- PolicyTraits::template get_hash_slot_fn<hasher>(),
+ PolicyTraits::template get_hash_slot_fn<hasher, kIsDefaultHash>(),
PolicyTraits::transfer_uses_memcpy()
? TransferNRelocatable<sizeof(slot_type)>
: &raw_hash_set::transfer_n_slots_fn,
@@ -3689,6 +3709,8 @@
using Traits = typename Set::PolicyTraits;
using Slot = typename Traits::slot_type;
+ constexpr static bool kIsDefaultHash = Set::kIsDefaultHash;
+
static size_t GetNumProbes(const Set& set,
const typename Set::key_type& key) {
if (set.is_soo()) return 0;
@@ -3733,16 +3755,21 @@
// Extern template instantiations reduce binary size and linker input size.
// Function definition is in raw_hash_set.cc.
extern template size_t GrowSooTableToNextCapacityAndPrepareInsert<0, false>(
- CommonFields&, const PolicyFunctions&, size_t, ctrl_t);
+ CommonFields&, const PolicyFunctions&, absl::FunctionRef<size_t(size_t)>,
+ bool);
extern template size_t GrowSooTableToNextCapacityAndPrepareInsert<1, true>(
- CommonFields&, const PolicyFunctions&, size_t, ctrl_t);
+ CommonFields&, const PolicyFunctions&, absl::FunctionRef<size_t(size_t)>,
+ bool);
extern template size_t GrowSooTableToNextCapacityAndPrepareInsert<4, true>(
- CommonFields&, const PolicyFunctions&, size_t, ctrl_t);
+ CommonFields&, const PolicyFunctions&, absl::FunctionRef<size_t(size_t)>,
+ bool);
extern template size_t GrowSooTableToNextCapacityAndPrepareInsert<8, true>(
- CommonFields&, const PolicyFunctions&, size_t, ctrl_t);
+ CommonFields&, const PolicyFunctions&, absl::FunctionRef<size_t(size_t)>,
+ bool);
#if UINTPTR_MAX == UINT64_MAX
extern template size_t GrowSooTableToNextCapacityAndPrepareInsert<16, true>(
- CommonFields&, const PolicyFunctions&, size_t, ctrl_t);
+ CommonFields&, const PolicyFunctions&, absl::FunctionRef<size_t(size_t)>,
+ bool);
#endif
} // namespace container_internal
diff --git a/absl/container/internal/raw_hash_set_allocator_test.cc b/absl/container/internal/raw_hash_set_allocator_test.cc
index 7e7a506..2e6f8f5 100644
--- a/absl/container/internal/raw_hash_set_allocator_test.cc
+++ b/absl/container/internal/raw_hash_set_allocator_test.cc
@@ -180,7 +180,7 @@
static slot_type& element(slot_type* slot) { return *slot; }
- template <class Hash>
+ template <class Hash, bool kIsDefault>
static constexpr HashSlotFn get_hash_slot_fn() {
return nullptr;
}
diff --git a/absl/container/internal/raw_hash_set_benchmark.cc b/absl/container/internal/raw_hash_set_benchmark.cc
index ac94877..07a5b90 100644
--- a/absl/container/internal/raw_hash_set_benchmark.cc
+++ b/absl/container/internal/raw_hash_set_benchmark.cc
@@ -64,7 +64,7 @@
return std::forward<F>(f)(x, x);
}
- template <class Hash>
+ template <class Hash, bool kIsDefault>
static constexpr HashSlotFn get_hash_slot_fn() {
return nullptr;
}
@@ -127,7 +127,7 @@
PairArgs(std::forward<Args>(args)...));
}
- template <class Hash>
+ template <class Hash, bool kIsDefault>
static constexpr HashSlotFn get_hash_slot_fn() {
return nullptr;
}
diff --git a/absl/container/internal/raw_hash_set_probe_benchmark.cc b/absl/container/internal/raw_hash_set_probe_benchmark.cc
index e56648f..458038e 100644
--- a/absl/container/internal/raw_hash_set_probe_benchmark.cc
+++ b/absl/container/internal/raw_hash_set_probe_benchmark.cc
@@ -71,7 +71,7 @@
return std::forward<F>(f)(arg, arg);
}
- template <class Hash>
+ template <class Hash, bool kIsDefault>
static constexpr auto get_hash_slot_fn() {
return nullptr;
}
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc
index f835b94..e1dafff 100644
--- a/absl/container/internal/raw_hash_set_test.cc
+++ b/absl/container/internal/raw_hash_set_test.cc
@@ -386,7 +386,7 @@
std::forward<F>(f), std::forward<Args>(args)...);
}
- template <class Hash>
+ template <class Hash, bool kIsDefault>
static constexpr HashSlotFn get_hash_slot_fn() {
return nullptr;
}
@@ -534,7 +534,7 @@
PairArgs(std::forward<Args>(args)...));
}
- template <class Hash>
+ template <class Hash, bool kIsDefault>
static constexpr HashSlotFn get_hash_slot_fn() {
return nullptr;
}
@@ -1131,7 +1131,7 @@
return std::forward<F>(f)(x, x);
}
- template <class Hash>
+ template <class Hash, bool kIsDefault>
static constexpr HashSlotFn get_hash_slot_fn() {
return nullptr;
}
@@ -2814,12 +2814,12 @@
// Expect that we sampled at the requested sampling rate of ~1%.
EXPECT_NEAR((end_size - start_size) / static_cast<double>(tables.size()),
0.01, 0.005);
- EXPECT_EQ(observed_checksums.size(), 5);
+ ASSERT_EQ(observed_checksums.size(), 5);
for (const auto& [_, count] : observed_checksums) {
EXPECT_NEAR((100 * count) / static_cast<double>(tables.size()), 0.2, 0.05);
}
- EXPECT_EQ(reservations.size(), 10);
+ ASSERT_EQ(reservations.size(), 10);
for (const auto& [reservation, count] : reservations) {
EXPECT_GE(reservation, 0);
EXPECT_LT(reservation, 100);
@@ -4057,7 +4057,7 @@
CommonFields& common = RawHashSetTestOnlyAccess::GetCommon(t);
// Set 0 seed so that H1 is always 0.
common.set_no_seed_for_testing();
- ASSERT_EQ(H1(t.hash_function()(75), common.seed()), 0);
+ ASSERT_EQ(H1(t.hash_function()(75)), 0);
uint8_t inserted_till = 210;
for (uint8_t i = 0; i < inserted_till; ++i) {
t.insert(i);
@@ -4081,6 +4081,16 @@
EXPECT_EQ(t.capacity(), kTargetCapacity);
}
+// Test that after calling generate_new_seed(), the high bits of the returned
+// seed are non-zero.
+TEST(PerTableSeed, HighBitsAreNonZero) {
+ HashtableSize hs(no_seed_empty_tag_t{});
+ for (int i = 0; i < 100; ++i) {
+ hs.generate_new_seed();
+ ASSERT_GT(hs.seed().seed() >> 16, 0);
+ }
+}
+
} // namespace
} // namespace container_internal
ABSL_NAMESPACE_END
diff --git a/absl/container/node_hash_map.h b/absl/container/node_hash_map.h
index 5f6be95..46faa89 100644
--- a/absl/container/node_hash_map.h
+++ b/absl/container/node_hash_map.h
@@ -663,10 +663,10 @@
static Value& value(value_type* elem) { return elem->second; }
static const Value& value(const value_type* elem) { return elem->second; }
- template <class Hash>
+ template <class Hash, bool kIsDefault>
static constexpr HashSlotFn get_hash_slot_fn() {
return memory_internal::IsLayoutCompatible<Key, Value>::value
- ? &TypeErasedDerefAndApplyToSlotFn<Hash, Key>
+ ? &TypeErasedDerefAndApplyToSlotFn<Hash, Key, kIsDefault>
: nullptr;
}
};
diff --git a/absl/container/node_hash_set.h b/absl/container/node_hash_set.h
index 127c640..9eef870 100644
--- a/absl/container/node_hash_set.h
+++ b/absl/container/node_hash_set.h
@@ -557,9 +557,9 @@
static size_t element_space_used(const T*) { return sizeof(T); }
- template <class Hash>
+ template <class Hash, bool kIsDefault>
static constexpr HashSlotFn get_hash_slot_fn() {
- return &TypeErasedDerefAndApplyToSlotFn<Hash, T>;
+ return &TypeErasedDerefAndApplyToSlotFn<Hash, T, kIsDefault>;
}
};
} // namespace container_internal
diff --git a/absl/hash/internal/hash.h b/absl/hash/internal/hash.h
index 9eacccd..3e27d3f 100644
--- a/absl/hash/internal/hash.h
+++ b/absl/hash/internal/hash.h
@@ -353,6 +353,15 @@
}
};
+// For use in `raw_hash_set` to pass a seed to the hash function.
+struct HashWithSeed {
+ template <typename Hasher, typename T>
+ size_t hash(const Hasher& hasher, const T& value, size_t seed) const {
+ // NOLINTNEXTLINE(clang-diagnostic-sign-conversion)
+ return hasher.hash_with_seed(value, seed);
+ }
+};
+
// Convenience function that combines `hash_state` with the byte representation
// of `value`.
template <typename H, typename T,
@@ -1244,20 +1253,25 @@
}
using MixingHashState::HashStateBase::combine_contiguous;
+ template <typename T>
+ static size_t hash(const T& value) {
+ return hash_with_seed(value, Seed());
+ }
+
// For performance reasons in non-opt mode, we specialize this for
// integral types.
// Otherwise we would be instantiating and calling dozens of functions for
// something that is just one multiplication and a couple xor's.
// The result should be the same as running the whole algorithm, but faster.
template <typename T, absl::enable_if_t<IntegralFastPath<T>::value, int> = 0>
- static size_t hash(T value) {
+ static size_t hash_with_seed(T value, size_t seed) {
return static_cast<size_t>(
- Mix(Seed() ^ static_cast<std::make_unsigned_t<T>>(value), kMul));
+ Mix(seed ^ static_cast<std::make_unsigned_t<T>>(value), kMul));
}
template <typename T, absl::enable_if_t<!IntegralFastPath<T>::value, int> = 0>
- static size_t hash(const T& value) {
- return static_cast<size_t>(combine(MixingHashState{}, value).state_);
+ static size_t hash_with_seed(const T& value, size_t seed) {
+ return static_cast<size_t>(combine(MixingHashState{seed}, value).state_);
}
private:
@@ -1366,6 +1380,13 @@
size_t operator()(const T& value) const {
return MixingHashState::hash(value);
}
+
+ private:
+ friend struct HashWithSeed;
+
+ size_t hash_with_seed(const T& value, size_t seed) const {
+ return MixingHashState::hash_with_seed(value, seed);
+ }
};
template <typename T>
