golang / golang/go

internal/runtime/maps: use fxhash for very small keys

Open
#80,972 3 comments 0 reactions 0 assignees View on GitHub
compiler/runtime help wanted NeedsInvestigation Performance
Dominant language
Go
Stars
139k
Forks
19.4k
PR merge metrics
PR metrics pending

Description

Currently, we use a mix of a wyhash variant and an AESNI-driven SIMD hash for maps. I am working on a series of CLs to use wyhash for very small keys on x86 and ARM because of the reasons listed here: https://github.com/golang/go/issues/80970.

Go's wyhash derivative performs two data-dependent multiply-xors when hashing a u64, which is really good, but we can do better. The Rust compiler makes extremely aggressive use of `HashMap` for a number of tasks, and rather than using Rust's default SIP implementation (which is _much_ slower than wyhash, because it has hash-flooding resistance), they use something called fxhash, which Firefox also uses for some things. I also use fxhash within [hyperpb](https://github.com/bufbuild/hyperpb-go) for integer keys. fxhash replaces one of the multiplies with a rotate, which is a strictly worse hash but which happens to work really well with SwissTable.

fxhash, as implemented in rustc (and hyperpb) costs a load, an add, an xor, a mul, and a rotate. I need to benchmark it again, but I observed pretty significant improvements on top of my changes to use wyhash in some cases on AESNI-bearing hardware. This has is really bad generically, to the point that it fails some of the hash smashing tests. But the key thing is that it moves the entropy to the low bits with that rotate, which is where SwissTable best makes use of those bits (remember: only absurdly large SwissTables will *ever* use the high 32 bits of the hash!).

```go
// hyperpb's impl
func (h hash) u64(n uint64) hash {
const (
rotate = 26
key = 0xf1357aea2e62a9c5
)
x := mix((uint64(h) + n), key)
return hash(bits.RotateLeft64(x, rotate))
}

```

Most maps are small (say <10k entries or so, sunny is making this number up). Most maps also have string keys so this doesn't help. But small integer keyed maps show up a lot... like in Protobuf reflection.

I think we can improve a lot of common cases by using fxhash for 4- and 8-bit fixed-size keys *only*, and *only* when the map is "small". Because this is only hit in fixed-size cases, this is now a comparison + a branch in the hot path of mapaccess_fast32 and friends. This *must not* be exposed via `hash/maphash`, because it makes the hash so bad it will definitely break other people's data structures. In particular, this would mean the dynamic hash in the `abi.MapType` and the one actually used would be different... which I believe is a problem for reflection, so we need to figure out a way to deal with that.

And of course, hash flooding. fxhash, like wyhash and aeshash, is not flood-resistant, but it does perform worse on smhasher. I spoke to @FiloSottile a bit ago about this and whether Go cares that the hash itself has nice preimage properties (independent of other countermeasures, such as the global random seed), and the answer was "knock yourself out". (It is worth noting that Go's countermeasures are actually stronger than Abseil's, which seeds the hash from ASLR noise (with some of the most cursed constexpr I have ever seen).

Contributor guide

Open the contributing guide

Research direction

Start with mapaccess_fast32 and related fixed-size map access paths, then inspect hash/maphash and abi.MapType to understand how the dynamic and used hashes interact. Benchmark the proposed small-map cases and run the hash-smashing tests; done means an agreed fxhash design improves the targeted cases without breaking reflection or required hash behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
go
Domain
performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.