Files
carbon-lang/toolchain/sem_ir/entity_name.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

169 lines
6.5 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_TOOLCHAIN_SEM_IR_ENTITY_NAME_H_
#define CARBON_TOOLCHAIN_SEM_IR_ENTITY_NAME_H_
#include "common/hashing.h"
#include "common/set.h"
#include "toolchain/base/value_store.h"
#include "toolchain/sem_ir/clang_decl.h"
#include "toolchain/sem_ir/ids.h"
namespace Carbon::SemIR {
struct EntityName : public Printable<EntityName> {
auto Print(llvm::raw_ostream& out) const -> void {
out << "{name: " << name_id << ", parent_scope: " << parent_scope_id
<< ", index: " << bind_index_value << ", is_template: " << is_template
<< ", is_unused: " << is_unused;
if (name_id == SemIR::NameId::PeriodSelf) {
out << ", is_frozen_period_self: " << is_frozen_period_self;
}
out << ", form: " << form_id << ", type: " << type_inst_id << "}";
}
// Returns a copy of this name with the fields that are not part of its
// identity cleared. Two `EntityName`s that differ only in how the declared
// type of the binding was written describe the same name.
auto IdentityKey() const -> EntityName {
EntityName key = *this;
key.type_inst_id = TypeInstId::None;
return key;
}
friend auto CarbonHashtableEq(const EntityName& lhs, const EntityName& rhs)
-> bool {
// This requires that there are no padding bits in the type. This is upheld
// since it holds values all of the same size: each is 32 bits, with one
// split into 29, 1, 1, and 1 bits.
EntityName lhs_key = lhs.IdentityKey();
EntityName rhs_key = rhs.IdentityKey();
return std::memcmp(&lhs_key, &rhs_key, sizeof(EntityName)) == 0;
}
// Hashing for EntityName. See common/hashing.h.
friend auto CarbonHashValue(const EntityName& value) -> HashCode {
Hasher hasher;
hasher.HashRaw(value.IdentityKey());
return static_cast<HashCode>(hasher);
}
// The index of the binding, if this is the name of a symbolic binding, or
// `None` otherwise. This is also `None` for a `.Self` symbolic binding,
// because such a binding is not assigned an index.
auto bind_index() const -> CompileTimeBindIndex {
return CompileTimeBindIndex(bind_index_value);
}
// The name.
NameId name_id;
// The parent scope.
NameScopeId parent_scope_id;
// TODO: The following two fields are only meaningful for a symbolic binding.
// Consider splitting them off into a separate type so that we don't store
// them for other kinds of `EntityName`.
// The bind_index() value, unwrapped so it can be stored in a bit-field.
int32_t bind_index_value : 29 = CompileTimeBindIndex::None.index;
// Whether this binding is a template parameter.
bool is_template : 1 = false;
// Whether this binding is marked unused.
bool is_unused : 1 = false;
// Whether this binding is a `.Self` symbolic binding, within the scope of the
// `.Self` name during facet type under construction. Such bindings cannot be
// replaced during identify.
bool is_frozen_period_self : 1 = false;
// The declared form of the binding. This is guaranteed to be set for
// `:?` bindings, and may be set for other binding kinds as well.
//
// TODO: Unify this with the previous three fields, which also represent form
// information.
InstId form_id = InstId::None;
// The declared type of the binding, as written. This describes the same type
// as the binding's `type_id`, but may retain type sugar that `type_id` loses,
// such as the use of an alias to name the type. For a `:?` binding, this is
// the type component of `form_id`. This is `None` if the binding has no
// declared type, or if it was not written in the source, for example because
// the binding was synthesized or imported.
TypeInstId type_inst_id = TypeInstId::None;
};
// Value store for EntityName. In addition to the regular ValueStore
// functionality, this can provide optional canonical IDs for EntityNames.
struct EntityNameStore
: public ValueStore<EntityNameId, EntityName, Tag<CheckIRId>> {
public:
using ValueStore::ValueStore;
// Adds an entity name for a symbolic binding.
auto AddSymbolicBindingName(NameId name_id, NameScopeId parent_scope_id,
CompileTimeBindIndex bind_index, bool is_template,
bool is_unused, bool is_frozen_period_self)
-> EntityNameId {
EntityName name = {.name_id = name_id,
.parent_scope_id = parent_scope_id,
.bind_index_value = bind_index.index,
.is_template = is_template,
.is_unused = is_unused,
.is_frozen_period_self = is_frozen_period_self};
CARBON_CHECK(name.bind_index_value == bind_index.index,
"Bind index out of range for bit-field: {0}",
bind_index.index);
return Add(name);
}
// Convert an `EntityName` to a canonical ID. All calls to this with
// equivalent `EntityName`s will return the same `EntityNameId`. Same as
// `MakeCanonical(Add(name))` except that no new `EntityName` is added if we
// already have a canonical `EntityNameId` for that name.
auto AddCanonical(EntityName name) -> EntityNameId;
// Convert an ID to a canonical ID. All calls to this with equivalent
// `EntityName`s will return the same `EntityNameId`.
auto MakeCanonical(EntityNameId id) -> EntityNameId;
private:
class KeyContext;
Set<EntityNameId, /*SmallSize=*/0, KeyContext> canonical_ids_;
};
class EntityNameStore::KeyContext : public TranslatingKeyContext<KeyContext> {
public:
explicit KeyContext(const EntityNameStore* store) : store_(store) {}
// Note that it is safe to return a `const` reference here as the underlying
// object's lifetime is provided by the `store_`.
auto TranslateKey(EntityNameId id) const -> const EntityName& {
return store_->Get(id);
}
private:
const EntityNameStore* store_;
};
inline auto EntityNameStore::AddCanonical(EntityName name) -> EntityNameId {
return canonical_ids_
.Insert(
name, [&] { return Add(name); }, KeyContext(this))
.key();
}
inline auto EntityNameStore::MakeCanonical(EntityNameId id) -> EntityNameId {
return canonical_ids_.Insert(id, KeyContext(this)).key();
}
} // namespace Carbon::SemIR
namespace Carbon {
extern template class ValueStore<SemIR::EntityNameId, SemIR::EntityName,
Tag<SemIR::CheckIRId>>;
} // namespace Carbon
#endif // CARBON_TOOLCHAIN_SEM_IR_ENTITY_NAME_H_