Add more bits to size by reducing size of capacity and seed. This change fixes the hash seed size to 5 bits in HashtableInlineDataImpl, whereas previously it could be 8 or 16 bits depending on the storage mode. Additionally capacity is stored as 6 bits in ByLog mode. That gives size extra 5 bits that are necessary for other experiments. In particular there is idea to store 1 byte of GrowthInfo in HashtableInlineDataImpl. That would allow to get 8-16 byte RAM savings if we remove cloned bytes. PiperOrigin-RevId: 964541923 Change-Id: Ia6a881bbf7c633fd42692bd1e75fd6d8b6ea0cff
diff --git a/absl/container/internal/raw_hash_set.cc b/absl/container/internal/raw_hash_set.cc index 4de53f8..3f9263c 100644 --- a/absl/container/internal/raw_hash_set.cc +++ b/absl/container/internal/raw_hash_set.cc
@@ -141,9 +141,8 @@ // Must be defined out-of-line to avoid MSVC error C2482 on some platforms, // which is caused by non-constexpr initialization. -uint16_t NextHashTableSeed() { - static_assert(PerTableSeed::kBitCount <= 16); - return static_cast<uint16_t>(RandomSeed()); +uint8_t NextHashTableSeed() { + return static_cast<uint8_t>(RandomSeed()); } GenerationType* EmptyGeneration() {
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index 5a4fce8..0531300 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h
@@ -568,7 +568,9 @@ // We use these sentinel capacity values in debug mode to indicate different // classes of bugs. enum InvalidCapacity : IntType { - kAboveMaxValidCapacity = (std::numeric_limits<IntType>::max)() - 100, + kAboveMaxValidCapacity = StorageMode == kCapacityByValue + ? (std::numeric_limits<IntType>::max)() - 100 + : 64 - 10, kReentrance, kDestroyed, @@ -590,39 +592,24 @@ class HashtableInlineDataImpl; // Returns next per-table seed. -uint16_t NextHashTableSeed(); +uint8_t NextHashTableSeed(); // Per table hash salt. This gets mixed into H1 to randomize iteration order // per-table. // The seed is needed to ensure non-determinism of iteration order. -template <typename StorageType> -class PerTableSeedImpl { +class PerTableSeed { public: - using IntType = StorageType; - - // 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 8 or 16 bits allows us to save one `and` instruction in H1 (we use - // zero-extended move instead of mov+and). When absl::Hash is inlined, it can - // also have lower latency knowing that the high bits of the seed are zero. - static constexpr size_t kBitCount = sizeof(IntType) * 8; - - // 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. - static constexpr IntType kSampledSeed = static_cast<IntType>(~IntType{0}); - // Returns the seed for the table. size_t seed() const { return seed_; } private: - template <HashtableCapacityStorageMode StorageMode> + template <HashtableCapacityStorageMode StorageModeOfData> friend class HashtableInlineDataImpl; - explicit PerTableSeedImpl(uint64_t seed) - : seed_(static_cast<IntType>(seed)) {} + explicit PerTableSeed(uint64_t seed) + : seed_(static_cast<uint16_t>(seed)) {} - const IntType seed_; + const uint16_t seed_; }; // Represents blocked elements info: log2_period and tail_blocked. @@ -672,18 +659,25 @@ // bit of the seed is repurposed to track if sampling has been tried). template <HashtableCapacityStorageMode StorageMode> class HashtableInlineDataImpl { + // 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. When absl::Hash is inlined, it can + // have lower latency knowing that the high bits of the seed are zero. + static constexpr size_t kSeedBitCount = 5; + public: static constexpr HashtableCapacityStorageMode kStorageMode = StorageMode; - using PerTableSeed = PerTableSeedImpl< - std::conditional_t<StorageMode == kCapacityByValue, uint16_t, uint8_t>>; using HashtableCapacity = HashtableCapacityImpl<StorageMode>; static constexpr size_t kBlockedElementBitCount = 3; static constexpr size_t kMaxBlockedElementCount = (uint64_t{1} << kBlockedElementBitCount) - 1; + static constexpr size_t kCapacityBitCount = + StorageMode == kCapacityByValue ? sizeof(HashtableCapacity) * 8 : 6; + static constexpr size_t kCapacityBitStoredInDataCount = + StorageMode == kCapacityByValue ? 0 : kCapacityBitCount; static constexpr size_t kSizeBitCount = - 64 - - (kBlockedElementBitCount + PerTableSeed::kBitCount + /*has_infoz*/ 1 + - (StorageMode == kCapacityByValue ? 0 : sizeof(HashtableCapacity) * 8)); + 64 - (kBlockedElementBitCount + kSeedBitCount + + /*has_infoz*/ 1 + kCapacityBitStoredInDataCount); explicit HashtableInlineDataImpl(uninitialized_tag_t) {} explicit HashtableInlineDataImpl(HashtableCapacity capacity, @@ -727,18 +721,18 @@ (data_ & kMetadataMask) | (static_cast<uint64_t>(size) << kSizeShift); } - PerTableSeed seed() const { return PerTableSeed(data_ & kSeedMask); } - - void generate_new_seed() { - set_seed(static_cast<typename PerTableSeed::IntType>(NextHashTableSeed())); + PerTableSeed seed() const { + return PerTableSeed(ToPublicSeed(data_ & kSeedMask)); } + void generate_new_seed() { set_seed(NextHashTableSeed()); } + // 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::kSampledSeed); } + void set_sampled_seed() { set_seed(kSampledSeed); } bool is_sampled_seed() const { - return seed().seed() == PerTableSeed::kSampledSeed; + return seed().seed() == ToPublicSeed(kSampledSeed); } // Returns true if the table has infoz. @@ -767,34 +761,46 @@ void set_no_seed_for_testing() { data_ &= ~kSeedMask; } private: - // Bit layout of `data_` from MSB to LSB: - // (44 bits) : size + // Bit layout of `data_` and `capacity_internal_` from MSB to LSB: + // (55/49 bits) : size // (3 bits) : blocked_element_count // (1 bit) : has_infoz - // (16 or 8 bits) : seed + // (5 bits) : seed + // (6 bits) : capacity (only for kCapacityByLog) // We don't split these components of `data_` into separate bit field elements // because we get worse generated code that way. + static constexpr size_t kDataBitCount = - PerTableSeed::kBitCount + 1 + kSizeBitCount + kBlockedElementBitCount; + kSeedBitCount + 1 + kSizeBitCount + kBlockedElementBitCount; static constexpr size_t kSizeShift = kDataBitCount - kSizeBitCount; static constexpr uint64_t kSizeOneNoMetadata = uint64_t{1} << kSizeShift; static constexpr uint64_t kMetadataMask = kSizeOneNoMetadata - 1; - static constexpr uint64_t kSeedMask = - (uint64_t{1} << PerTableSeed::kBitCount) - 1; + static constexpr uint64_t kSeedMask = (uint64_t{1} << kSeedBitCount) - 1; // The next bit after the seed. static constexpr uint64_t kHasInfozMask = kSeedMask + 1; - static constexpr uint64_t kBlockedElementsShift = PerTableSeed::kBitCount + 1; + static constexpr uint64_t kBlockedElementsShift = kSeedBitCount + 1; static constexpr uint64_t kBlockedElementMask = kMaxBlockedElementCount << kBlockedElementsShift; // For SOO tables, the seed is unused, and bit 0 is repurposed to track // whether the table has already queried should_sample_soo(). static constexpr uint64_t kSooHasTriedSamplingMask = 1; - void set_seed(typename PerTableSeed::IntType seed) { - data_ = (data_ & ~kSeedMask) | seed; + // 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. + static constexpr uint8_t kSampledSeed = (1 << kSeedBitCount) - 1; + + static constexpr uint64_t ToPublicSeed(uint64_t seed) { + // In kCapacityByLog mode, we shift public seed to the left to keep bits of + // the seed in the original place. It allows us to use single instruction to + // access the seed (e.g., `andl $0x7c0, %r8d`). + return seed << kCapacityBitStoredInDataCount; } - uint64_t capacity_internal_ : sizeof(HashtableCapacity) * 8; + void set_seed(uint8_t seed) { + data_ = (data_ & ~kSeedMask) | (seed & kSeedMask); + } + + uint64_t capacity_internal_ : kCapacityBitCount; uint64_t data_ : kDataBitCount; }; @@ -814,7 +820,6 @@ #else using HashtableInlineData = HashtableInlineDataImpl<kCapacityByValue>; #endif // ABSL_SWISSTABLE_INTERNAL_ENABLE_CAPACITY_BY_VALUE -using PerTableSeed = HashtableInlineData::PerTableSeed; using HashtableCapacity = HashtableInlineData::HashtableCapacity; // For large tables, we limit the number of blocked elements to maintain O(1)
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc index 4db52f2..f60398d 100644 --- a/absl/container/internal/raw_hash_set_test.cc +++ b/absl/container/internal/raw_hash_set_test.cc
@@ -1545,13 +1545,12 @@ for (size_t capacity = 31; capacity < 256; capacity = NextCapacity(capacity)) { SCOPED_TRACE(absl::StrCat("capacity: ", capacity)); - // Number of elements we keep empty in order to force a rehash without + // Number of elements we reserve in order to force a rehash without // growth. RehashOrGrowToNextCapacityAndPrepareInsert grow if number of full - // slots is greater than 25/32 of capacity, so we leave 7/32 + 5 empty to - // have extra margin. - size_t empty_till_full = (capacity + 1) / 32 * 7 + 5; + // slots is greater than 25/32 of capacity. We reserve slightly less than + // 25/32 of capacity to have extra space for tombstones. int64_t reserve_size = - static_cast<int64_t>(CapacityToGrowth(capacity) - empty_till_full); + static_cast<int64_t>((capacity - 5) * 25 / 32 - 2); BadTwoValuesHashTable t( 0, @@ -1560,9 +1559,8 @@ // will be placed at the beginning of the table. BadTwoValuesHash(static_cast<size_t>(reserve_size))); // Remove seed to make table layout deterministic. - RawHashSetTestOnlyAccess::GetCommon(t).set_no_seed_for_testing(); - t.reserve(static_cast<size_t>(reserve_size)); + RawHashSetTestOnlyAccess::GetCommon(t).set_no_seed_for_testing(); for (int64_t i = 1; i <= reserve_size; ++i) { ASSERT_TRUE(t.insert(i * kCoef).second); } @@ -1632,10 +1630,9 @@ BadTwoValuesHashTable t(0, // Negative number goes to the end of the table. BadTwoValuesHash(kReserveSize + 2)); + t.reserve(kReserveSize); // Remove seed to make table layout deterministic. RawHashSetTestOnlyAccess::GetCommon(t).set_no_seed_for_testing(); - - t.reserve(kReserveSize); for (int64_t i = 0; i < static_cast<int64_t>(Group::kWidth); ++i) { ASSERT_TRUE(t.insert(i * kCoef).second); }