Add ABSL_SWISSTABLE_ASSUME_SEPARATE_STORAGE and use it in raw_hash_set::control(). Apparently, the manual assume we had with pointer values wasn't doing anything (we previously thought it was valuable but apparently the original change's codegen effects were side effects of e.g. calling `NumControlBytes(capacity())`). Benefits of the new `ABSL_SWISSTABLE_ASSUME_SEPARATE_STORAGE(ctrl, this)` in `raw_hash_set::control()`: * Unlike the previous `reinterpret_cast<uintptr_t>` range comparison inside `ABSL_ASSUME` (which LLVM's `BasicAA` ignores), `__builtin_assume_separate_storage(ctrl, this)` lowers to an `@llvm.assume` `"separate_storage"` operand bundle that `BasicAA` directly uses to prove that pointers derived from `ctrl` (including `slot_array` and iterator slot pointers on the non-SOO path) cannot alias `*this` (or any enclosing object containing the table). * When a caller mutates an element via an iterator returned by `find()` or `begin()` (e.g. `*it = v` or `it->second = v`), the compiler can now prove that the store to the slot does not clobber `CommonFields` metadata (`size`, `capacity`, `seed` in `0(%rdi)`), eliminating redundant reloads of `CommonFields` (and freeing `this` earlier to reduce register pressure) across subsequent `size()`, `capacity()`, or `find()` operations. Benefits of removing the previous assume from `CommonFields::control()` on `raw_hash_set_benchmark` (`--config=benchmark --cpu=haswell`, `llvm-mca -mcpu=znver3`): * `raw_hash_set::find`: Removing `NumControlBytes(capacity())` from `CommonFields::control()` allows `prefetcht2` (`prefetch_heap_block()`) to be scheduled immediately after loading `ctrl` (`movq 8(%rdi), %rax`), ahead of the capacity mask setup (`movq $-1, %r8; shlxq %rdx, %r8, %rcx`). * Under `llvm-mca -mcpu=znver3 -iterations=1`, this promotes `prefetcht2` from the second dispatch group (cycle 1) into the first dispatch group (cycle 0) while leaving static L1-hit latency unchanged (36 cycles for `CodegenAbslRawHashSetInt64Find`, 37 cycles for `CodegenAbslRawHashSetInt64FindNeEnd`, 143 cycles for `StringTable::find`), and avoids a stack spill in `DescriptorByNameHash` `raw_hash_set::find<string_view>` (133 → 131 cycles, RThroughput 29.7 → 29.3). * `raw_hash_set.cc` (`CommonFields`): Removing `reinterpret_cast<uintptr_t>(this)` from `CommonFields::control()` allows LLVM argument promotion on `ReportInsertMissToInfoz` (11 → 8 instructions, 15 → 10 cycles at `-iterations=1`) and slightly reduces instruction counts in `ResizeAllocatedTableWithSeedChange` (377 → 374 instructions, 244 → 243 cycles) and `EraseMetaOnlyLarge` (78 → 77 instructions, RThroughput 13.7 → 13.3). PiperOrigin-RevId: 998681646
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index 4d76862..ad79652 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h
@@ -260,6 +260,63 @@ assert((CONDITION) && "Try enabling sanitizers.") #endif +// ABSL_SWISSTABLE_ASSUME_SEPARATE_STORAGE(a, b) +// +// Informs the compiler that the two pointer arguments point into separately +// allocated storage (either different variable definitions or different dynamic +// storage allocations), allowing the compiler to assume they do not alias for +// optimization purposes. Differences from __restrict: +// - __restrict only applies to the pointer itself, not the pointed-to object. +// - This macro allows the compiler to optimize caller code, not just the +// pointer dereferences of a function argument within that function. +// +// WARNING: If the arguments point into the same storage, the program has +// undefined behavior. Note that the definition of "storage" here refers to the +// outermost enclosing allocation of any particular object (for example, it is +// never correct to call this macro passing the addresses of fields in the same +// struct, elements of the same array, objects on the same arena block, etc.). +// Note that in the example below, the annotation will affect callers of +// SetFirstAndGetSize as well (they may be mis-compiled if the arguments are not +// from separate allocations). +// +// See +// https://clang.llvm.org/docs/LanguageExtensions.html#builtin-assume-separate-storage +// +// Example: +// +// class Buffer { +// public: +// size_t* data() { +// // Safe because `data_` is allocated via `::operator new`, so it is +// // guaranteed to be in a separate allocation from `*this`. +// ABSL_SWISSTABLE_ASSUME_SEPARATE_STORAGE(data_, this); +// return data_; +// } +// size_t size() const { return size_; } +// +// private: +// size_t* data_ = new size_t[10]; +// size_t size_ = 10; +// }; +// +// size_t SetFirstAndGetSize(Buffer& buf) { +// size_t n = buf.size(); +// buf.data()[0] = n; +// // After inlining, the compiler knows storing to `buf.data()[0]` cannot +// // clobber `buf.size_`, and can return `n` without reloading `buf.size_`. +// return buf.size(); +// } +#if ABSL_HAVE_BUILTIN(__builtin_assume_separate_storage) +#define ABSL_SWISSTABLE_ASSUME_SEPARATE_STORAGE(a, b) \ + __builtin_assume_separate_storage(a, b) +#elif ABSL_INTERNAL_CPLUSPLUS_LANG >= 202002L +#define ABSL_SWISSTABLE_ASSUME_SEPARATE_STORAGE(a, b) \ + (decltype((void)(a), (void)(b))()) +#else +#define ABSL_SWISSTABLE_ASSUME_SEPARATE_STORAGE(a, b) \ + (false ? ((void)(a), (void)(b)) : void()) +#endif + // We use uint8_t so we don't need to worry about padding. using GenerationType = uint8_t; @@ -1344,14 +1401,7 @@ ctrl_t* control() const { ABSL_SWISSTABLE_ASSERT(capacity() > 0); - // Assume that the control bytes don't alias `this`. - ctrl_t* ctrl = heap_or_soo_.control().get(); - [[maybe_unused]] size_t num_control_bytes = NumControlBytes(capacity()); - ABSL_ASSUME(reinterpret_cast<uintptr_t>(ctrl + num_control_bytes) <= - reinterpret_cast<uintptr_t>(this) || - reinterpret_cast<uintptr_t>(this + 1) <= - reinterpret_cast<uintptr_t>(ctrl)); - ABSL_SWISSTABLE_IGNORE_UNINITIALIZED_RETURN(ctrl); + ABSL_SWISSTABLE_IGNORE_UNINITIALIZED_RETURN(heap_or_soo_.control().get()); } void set_control(ctrl_t* c) { heap_or_soo_.control().set(c); } @@ -4000,6 +4050,8 @@ template <class K> std::pair<slot_type*, bool> find_or_prepare_insert(const K& key) { AssertOnFind(key); + // TODO(ezb): add ABSL_SWISSTABLE_ASSUME_SEPARATE_STORAGE that the returned + // slot doesn't alias `this` for non-SOO tables with default allocators. return is_small() ? find_or_prepare_insert_small(key) : find_or_prepare_insert_large<FindLargeKey<K>>(key); } @@ -4083,7 +4135,24 @@ } ctrl_t* control() const { ABSL_SWISSTABLE_ASSERT(!is_soo()); - return common().control(); + ctrl_t* ctrl = common().control(); + if constexpr (std::is_same_v<CharAlloc, std::allocator<char>>) { + // Assume that the control bytes don't alias `this`. Example benefit: when + // a caller mutates an element via an iterator returned by find(), the + // compiler can now prove that the store to the slot does not clobber + // CommonFields metadata (size, capacity, etc.). + // Example of benefitting user code: + // if (auto it = m.find(k1); it != m.end()) it->second = v; + // if (auto it = m.find(k2); it != m.end()) it->second = v; + // With this assumption, the second lookup avoids reloading capacity. + // Note: for custom allocators, `this` may be part of the same allocation + // as the control bytes so we cannot make this assumption. + // TODO(ezb): we could move this assumption into CommonFields::control() + // if we template the type-erased functions on whether the allocator is + // default or not. + ABSL_SWISSTABLE_ASSUME_SEPARATE_STORAGE(ctrl, this); + } + return ctrl; } slot_type* slot_array(size_t capacity) const { return static_cast<slot_type*>(common().slot_array(capacity)); @@ -4099,7 +4168,9 @@ } slot_type* single_slot() { ABSL_SWISSTABLE_ASSERT(is_small()); - return SooEnabled() ? soo_slot() : to_slot(common().single_non_soo_slot()); + // Note: we don't use common().single_non_soo_slot() here because + // control() is more efficient (due to separate storage assume). + return SooEnabled() ? soo_slot() : to_slot(control()); } const slot_type* single_slot() const { return const_cast<raw_hash_set*>(this)->single_slot(); @@ -4498,5 +4569,6 @@ #undef ABSL_SWISSTABLE_ENABLE_GENERATIONS #undef ABSL_SWISSTABLE_ASSERT +#undef ABSL_SWISSTABLE_ASSUME_SEPARATE_STORAGE #endif // ABSL_CONTAINER_INTERNAL_RAW_HASH_SET_H_