Files
carbon-lang/common/raw_hashtable_test_helpers.h
Chandler Carruth 13ecad24be Remove the hashtable seed (#7871)
Hashtables seed every hash with the address of a global,
`ComputeSeed()`, so that ASLR varies layout and iteration order between
runs. Debug builds already vary iteration order directly in `entries()`,
so the seed only matters in release builds. There it costs a register
and an XOR on the latency path of every integer or pointer hash, and it
redraws a table's collisions in each process.

Remove the seed from `HashValue`, `Hasher`, `CarbonHashValue`,
`CustomHashValue::Hash`, and `HashKey`. Hashing starts from a zero
buffer, so integer keys hash as `WeakMix(key)`. `global_addr_seed`
remains in debug builds to seed the iteration-order entropy.
`ClangDeclSignature` chained its hash through the seed, and now hashes
its fields with one `Hasher`.

The seed also kept some short-input paths from collapsing. Without it,
every `{i, 0, 0}` array of `int32_t` hashed the same, all-zero 4-8 byte
inputs lost their size, and the 17-32 byte path multiplied the size
sample by a byte-shifted copy of itself. Each `Mix` operand of the
short-input paths now XORs in a 32-bit constant from
`ImmediateRandomData` in place of a 64-bit chunk of `StaticRandomData`,
which they now only sample to encode sizes. `XorImmediate` keeps these
as `xor $imm32` on x86-64; without its `asm` barrier, a read feeding the
XOR is folded in instead and the constant ends up in a register that
loops hoist.

Cycles against trunk on Zen 5, from `bench_runner.py` with 48 runs per
side, each run at a random code layout, and table sizes of 64, 3584, and
57344:
- Integer and pointer hits: -3.0% to -5.7% in `Map`, -0.8% to -2.4% in
`Set`.
- Integer and pointer misses: up to -12.6%, except `Set<int*>` at +1.4%
(64) and +6.1% (3584).
- String keys: -2.8% to +2.1%, with `Map` updates at +1.1% to +1.6%.
- Hash latency, without layout randomization: integers and pointers
-9.8%, empty strings +5.4% (0.1 cycles), other strings not significant.

Same method on an Apple M1, with #7870 on both sides. Without it, this
change moves benchmark loop counters between `sp`- and `x29`-relative
stack slots, which alone makes `Set<int>` lookups up to 49% slower on
the M1.
- Integer and pointer hits: -1.0% to -10.3% in `Map`, -24.5% to +1.2% in
`Set`.
- Integer and pointer misses: -3.9% to -48.0%, except +7.2% to +59.3% at
3584, from longer probes (instructions +6.4% to +70.6%).
- Inserting 64 integer keys: +12.1% to +15.0%, from store memory-order
violations.
- String keys: -6.6% to +3.9%.
- Hash latency: integers and pointers -9.0% to -10.0%, empty strings
+48.8% (1 cycle).

Release builds now iterate a given table in the same order in every run.
Code that depends on that order still fails in debug builds.

Assisted-by: Claude Code
2026-10-06 15:13:10 +00:00

156 lines
4.8 KiB
C++

// Part of the Carbon Language project, under the Apache License v2.0 with LLVM
// Exceptions. See /LICENSE for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
#ifndef CARBON_COMMON_RAW_HASHTABLE_TEST_HELPERS_H_
#define CARBON_COMMON_RAW_HASHTABLE_TEST_HELPERS_H_
#include <compare>
#include "common/check.h"
#include "common/hashing.h"
#include "common/hashtable_key_context.h"
#include "common/ostream.h"
namespace Carbon::RawHashtable {
// Non-trivial type for testing.
struct TestData : Printable<TestData> {
int value;
// NOLINTNEXTLINE: google-explicit-constructor
TestData(int v) : value(v) { CARBON_CHECK(value >= 0); }
~TestData() {
CARBON_CHECK(value >= 0);
value = -1;
}
TestData(const TestData& other) : TestData(other.value) {}
TestData(TestData&& other) noexcept : TestData(other.value) {
other.value = 0;
}
auto Print(llvm::raw_ostream& out) const -> void { out << value; }
friend auto operator==(TestData lhs, TestData rhs) -> bool {
return lhs.value == rhs.value;
}
friend auto operator<=>(TestData lhs, TestData rhs) -> std::strong_ordering {
return lhs.value <=> rhs.value;
}
friend auto CarbonHashValue(TestData data) -> HashCode {
return Carbon::HashValue(data.value);
}
};
static_assert(std::is_copy_constructible_v<TestData>);
inline auto CarbonHashtableEq(int lhs, TestData rhs) -> bool {
return lhs == rhs;
}
// Non-trivial type for testing.
struct MoveOnlyTestData : Printable<TestData> {
int value;
// NOLINTNEXTLINE: google-explicit-constructor
MoveOnlyTestData(int v) : value(v) { CARBON_CHECK(value >= 0); }
~MoveOnlyTestData() {
CARBON_CHECK(value >= 0);
value = -1;
}
MoveOnlyTestData(MoveOnlyTestData&& other) noexcept
: MoveOnlyTestData(other.value) {
other.value = 0;
}
auto operator=(MoveOnlyTestData&& other) noexcept -> MoveOnlyTestData& {
value = other.value;
other.value = 0;
return *this;
}
auto Print(llvm::raw_ostream& out) const -> void { out << value; }
friend auto operator<=>(const MoveOnlyTestData& lhs,
const MoveOnlyTestData& rhs)
-> std::strong_ordering = default;
friend auto CarbonHashValue(const MoveOnlyTestData& data) -> HashCode {
return Carbon::HashValue(data.value);
}
};
static_assert(!std::is_copy_constructible_v<MoveOnlyTestData>);
static_assert(std::is_move_constructible_v<MoveOnlyTestData>);
inline auto CarbonHashtableEq(int lhs, const MoveOnlyTestData& rhs) -> bool {
return lhs == rhs;
}
// Test stateless key context that produces different hashes from normal.
// Changing the hash values should result in test failures if the context ever
// fails to be used.
struct TestKeyContext : DefaultKeyContext {
template <typename KeyT>
auto HashKey(const KeyT& key) const -> HashCode {
Hasher hash;
// Inject some other data to the hash.
hash.HashRaw(42);
hash.HashRaw(HashValue(key));
return static_cast<HashCode>(hash);
}
};
// Hostile fixed hashing key context used for stress testing. Allows control
// over which parts of the hash will be forced to collide, and the values they
// are coerced to. Note that this relies on implementation details and internals
// of `HashCode`.
template <int TagBits, bool FixIndexBits, bool FixTagBits, uint64_t FixedVal>
struct FixedHashKeyContext : DefaultKeyContext {
template <typename KeyT>
auto HashKey(const KeyT& key) const -> HashCode {
HashCode original_hash = HashValue(key);
auto raw_hash = static_cast<uint64_t>(original_hash);
constexpr uint64_t TagMask = (1U << TagBits) - 1;
if (FixIndexBits) {
raw_hash &= TagMask;
raw_hash |= FixedVal << TagBits;
CARBON_DCHECK(HashCode(raw_hash).ExtractIndexAndTag<TagBits>().first ==
(FixedVal & (~static_cast<uint64_t>(0) >> TagBits)));
}
if (FixTagBits) {
raw_hash &= ~TagMask;
raw_hash |= FixedVal & TagMask;
CARBON_DCHECK(HashCode(raw_hash).ExtractIndexAndTag<TagBits>().second ==
(FixedVal & TagMask));
}
return HashCode(raw_hash);
}
};
template <typename T>
class IndexKeyContext : public TranslatingKeyContext<IndexKeyContext<T>> {
using Base = TranslatingKeyContext<IndexKeyContext>;
public:
explicit IndexKeyContext(llvm::ArrayRef<T> array) : array_(array) {}
auto TranslateKey(ssize_t index) const -> const T& { return array_[index]; }
// Override the CRTP approach when we have two indices as we can optimize that
// approach.
using Base::KeyEq;
auto KeyEq(ssize_t lhs_index, ssize_t rhs_index) const -> bool {
// No need to compare the elements, if the indices are equal, the values
// must be.
return lhs_index == rhs_index;
}
private:
llvm::ArrayRef<T> array_;
};
} // namespace Carbon::RawHashtable
#endif // CARBON_COMMON_RAW_HASHTABLE_TEST_HELPERS_H_