Mask HashtableInlineData fields from data_ rather than reading bytes and use a 5-bit seed. Reading `capacity` and `seed` through byte loads (`read_byte`) on x86 causes store-to-load forwarding stalls (aka read-after-write (RAW) hazard) after 64-bit stores to `data_` (such as `increment_size()`, etc) and prevents the compiler from sharing a single 64-bit load of `data_` across `is_small()`, `capacity()`, `seed()`, and `empty()` (or folding `is_small() && empty()` into a single `testq` in destructors). Note: the latency of find() increases by one cycle (on e.g. znver3) due to the loss of movzbl so this is a tradeoff of removing RAW hazard and smaller code size in exchange for slower find(). Remove `read_byte` and extract both `capacity()` and `seed()` by masking the 64-bit `data_` word (`data_ & kCapacityMask` and `data_ & kSeedMask`), setting `kSeedShift = kIsAbslHash ? 0 : HashtableInlineData::kSeedShift` so that `absl::Hash` consumes the pre-shifted `data_ & kSeedMask` value directly without a right shift. Because `seed()` is now masked rather than byte-loaded, shrink `kSeedBitCount` from 8 back to 5 while keeping the seed within the second byte of `data_` (so `gbswap_64` on `data_ & kSeedMask` in `absl::Hash` still simplifies to a single shift), returning the 3 extra bits to `size` (40 bits instead of 37). PiperOrigin-RevId: 1003169834
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index 49e5b2e..51826d3 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h
@@ -802,12 +802,8 @@ class HashtableInlineData { // 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. The seed occupies the entire second - // byte of `data_` so that on the critical path of lookups it can be loaded - // with a single byte load and passed to the hash function without any - // masking. 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 = 8; + // together with size and other metadata. + static constexpr size_t kSeedBitCount = 5; public: static constexpr size_t kGrowthInfoLowerBoundBitCount = 8; @@ -815,6 +811,11 @@ static constexpr size_t kMaxBlockedElementCount = (uint64_t{1} << kBlockedElementBitCount) - 1; static constexpr size_t kCapacityBitCount = 6; + static constexpr size_t kHasInfozShift = kCapacityBitCount; + // We have one unused bit so that the seed is within a single byte of `data_`. + // This allows `gbswap_64` in `absl::Hash` to simplify to a single shift. + static constexpr size_t kSeedShift = + kHasInfozShift + /*has_infoz*/ 1 + /*unused*/ 1; static constexpr size_t kSizeBitCount = 64 - (kBlockedElementBitCount + kSeedBitCount + kGrowthInfoLowerBoundBitCount + @@ -829,12 +830,8 @@ (has_tried_sampling ? kSooHasTriedSamplingMask : 0)) {} HashtableCapacity capacity() const { - // Reading the capacity via a single byte load (rather than a wide load of - // `data_` followed by masking) allows the compiler to also use a single - // byte load for the seed on the critical path of lookups. The high bits of - // the byte are not part of the capacity. return HashtableCapacity::FromRawData( - static_cast<uint8_t>(read_byte(kCapacityByteIndex) & kCapacityMask)); + static_cast<uint8_t>(data_ & kCapacityMask)); } bool is_small() const { return capacity().is_small(); } @@ -871,12 +868,7 @@ (data_ & kMetadataMask) | (static_cast<uint64_t>(size) << kSizeShift); } - PerTableSeed seed() const { - // The seed is stored in exactly one byte, so we read it with a single byte - // load. This lets the compiler feed it directly into the hash function - // without a masking instruction on the critical path of lookups. - return PerTableSeed(read_byte(kSeedByteIndex)); - } + PerTableSeed seed() const { return PerTableSeed(data_ & kSeedMask); } void generate_new_seed() { set_seed(NextHashTableSeed()); } @@ -884,7 +876,7 @@ // hashes use the same seed and can e.g. identify stuck bits accurately. void set_sampled_seed() { set_seed(kSampledSeed); } - bool is_sampled_seed() const { return seed().seed() == kSampledSeed; } + bool is_sampled_seed() const { return seed().seed() == kSeedMask; } // Returns true if the table has infoz. bool has_infoz() const { @@ -964,28 +956,24 @@ private: // Bit layout of `data_` from MSB to LSB: - // (37 bits) : size + // (40 bits) : size // (8 bits) : growth_info_lower_bound // (3 bits) : blocked_element_count - // (8 bits) : seed (the whole second byte) + // (5 bits) : seed // (1 bit) : unused // (1 bit) : has_infoz // (6 bits) : capacity (the low 6 bits of the first byte) - // Note: for size to overflow would require ~2^40 bytes of RAM, which is - // impractical. The seed and the capacity are deliberately byte-aligned and - // accessed with byte loads: this lets lookups avoid a wide load plus masking - // on the critical path. We don't split these components of `data_` into - // separate bit field elements because we get worse generated code that way - // (the compiler loads the whole word and extracts the fields). + // Note: for size to overflow would require ~2^43 bytes of RAM, which is + // impractical. We don't split these components of `data_` into separate bit + // field elements because we get worse generated code that way. + // TODO(ezb): if we have 41 bits for size, then on ARM, we will be able to use + // a single instruction for size increase/decrease. static constexpr size_t kSizeShift = 64 - kSizeBitCount; static constexpr uint64_t kSizeOneNoMetadata = uint64_t{1} << kSizeShift; static constexpr uint64_t kMetadataMask = kSizeOneNoMetadata - 1; static constexpr uint64_t kCapacityMask = (1 << kCapacityBitCount) - 1; - static constexpr size_t kHasInfozShift = kCapacityBitCount; static constexpr uint64_t kHasInfozMask = uint64_t{1} << kHasInfozShift; - static constexpr size_t kSeedShift = - kHasInfozShift + /*has_infoz*/ 1 + /*unused*/ 1; static constexpr uint64_t kSeedMask = ((uint64_t{1} << kSeedBitCount) - 1) << kSeedShift; static constexpr uint64_t kBlockedElementsShift = kSeedShift + kSeedBitCount; @@ -1008,34 +996,10 @@ // hashes use the same seed and can e.g. identify stuck bits accurately. static constexpr uint8_t kSampledSeed = (1 << kSeedBitCount) - 1; - // Indices of the bytes of `data_` that hold the capacity and the seed. + // Keep the seed within the second byte of `data_` so that `gbswap_64` on + // `data_ & kSeedMask` in `absl::Hash` simplifies to a single shift. static_assert(kSeedShift == 8); - static_assert(kSeedBitCount == 8); -#ifdef ABSL_IS_LITTLE_ENDIAN - static constexpr size_t kCapacityByteIndex = 0; - static constexpr size_t kSeedByteIndex = 1; -#else - static constexpr size_t kCapacityByteIndex = 7; - static constexpr size_t kSeedByteIndex = 6; -#endif - - // Returns the `index`-th byte of `data_`. Accessing the storage through - // `unsigned char` is always allowed by the aliasing rules. Note: on x86, the - // reason we read the data this way rather than using bit manipulations as - // with other fields is that it results in better generated code (we get - // movzbl to read the seed this way). On other architectures (such as - // AArch64), byte loads prevent load-pair (ldp) of `inline_data_` with - // `control_` and introduce narrow loads after 64-bit stores to `data_`, so we - // use bit shifts on the wide word instead. - uint8_t read_byte(size_t index) const { -#if defined(__x86_64__) || defined(_M_X64) || defined(__i386__) || \ - defined(_M_IX86) - return reinterpret_cast<const unsigned char*>(&data_)[index]; -#else - return static_cast<uint8_t>(little_endian::FromHost64(data_) >> - (8 * index)); -#endif - } + static_assert(kSeedShift + kSeedBitCount <= 16); // Returns the bits of `data_` that encode `capacity`. static uint64_t CapacityBits(HashtableCapacity capacity) { @@ -2546,10 +2510,10 @@ // For non-default hashers the seed is xor'ed with the hash value rather than // being used as a seed for the hash function. Because we require random // iteration order for small tables, the seed must have entropy in its low - // bits. The seed is loaded as a single byte from the inline data, so it - // already has low bits entropy and no shift is needed. - // TODO(ezb): get rid of kSeedShift. - constexpr static size_t kSeedShift = 0; + // bits. For default absl::Hash, the pre-shifted `data_ & kSeedMask` value can + // be passed directly without a right shift. + constexpr static size_t kSeedShift = + kIsAbslHash ? 0 : HashtableInlineData::kSeedShift; constexpr static bool SooEnabled() { return PolicyTraits::soo_enabled() &&