proposal: hash: export a built-in hash function for comparable values

[bcmills]

Background

The Go runtime contains an efficient hash function that it uses to implement built-in maps.

The runtime hash function is capable of hashing arbitrary comparable values, and usually cannot be pruned away during linking: for example, it would be very difficult for the linker to determine which hash functions are needed in a program that uses reflect.MapOf to construct maps at run-time, or a program that stores interface{} values in a map[interface{}]Anything.

Occasionally, we need an efficient hash function outside the standard library, too: for example, we might want to implement other hash-based data structures, such as hash array mapped tries, concurrent tries, or prototypes for potential additions to the Go standard library (e.g. sync.Map), or write application code to compute hashes for normally-incomparable types (such as slices or maps) to be able to store them in built-in maps. (For the latter case, a built-in hash function would be a building block for a larger application-level hash function.)

Typical workarounds include:

• pushing computation of hashes to application code
  http://godoc.org/github.com/apmckinlay/gsuneido/util/hmap#Key
  http://godoc.org/github.com/hit9/htree#Item
  http://godoc.org/github.com/lleo/go-hamt-key#Key
  http://godoc.org/github.com/Workiva/go-datastructures/trie/dtrie#New
• restricting application code to strings, byte-slices, integers, or pointers:
  http://godoc.org/github.com/Workiva/go-datastructures/trie/ctrie#Ctrie.Insert
  http://godoc.org/github.com/lalonde/hamt#Key
  https://github.com/crawshaw/readmap/blob/master/readmap.go
  http://godoc.org/github.com/orcaman/concurrent-map#ConcurrentMap.Set
  http://godoc.org/github.com/OneOfOne/cmap#CMap.Set
• or, occasionally, using reflect or unsafe to reimplement arbitrary hashing in application code:
  http://godoc.org/github.com/dlsniper/anyhash
  http://godoc.org/github.com/mitchellh/hashstructure
  http://godoc.org/github.com/cnf/structhash

I believe that the toil involved in implementing these workarounds discourages experimentation with more efficient data structures in Go, and needlessly complicates application code.

It would be reckless for us to expose a stable hash function in the standard library. However, it seems like it would be useful to expose a per-process hash function, randomly salted at each invocation of the process, in order to facilitate the use of custom data structures in user code.

Proposal

I propose that we add the following function to the hash package:

// Local returns a hash code for a comparable argument using a hash function
// that is local to the current invocation of the program.
//
// Two values that compare equal using the == operator (and values that are
// unequal but have the same type and representation in memory, such as
// floating-point NaNs with the same bitwise representation) will have the same
// hash code. Values that compare unequal will have a high probability of
// returning different hash codes.
//
// Local panics if the argument is not comparable.
//
// Each call to Local with the same value will return the same result within the
// lifetime of the program, but each run of the program may return different
// results from previous runs.
func Local(interface{}) uintptr

(@orcaman @OneOfOne @aclements @dsnet)

[OneOfOne]

Also this would allow us to use a very efficient version of sync.Map that allows sharding by a key's hash.

[dsnet]

It does feel weird to me though that this would go in the runtime package. Perhaps the reflect package instead?

[OneOfOne]

@dsnet the function(s) in question are a part of the runtime though, for example

go/src/runtime/alg.go

Line 38 in 5a6c580

type typeAlg struct {

However, it's not that big of a deal where it is as long as it matches internally with map's hash.

[dsnet]

I'm aware of where the function is implemented, but that doesn't always correlate to where it should be categorically located. Arguably a lot of logic in reflect is in the "runtime", but we don't move it all to the runtime package either.

[bcmills]

@OneOfOne, sync.Map can technically already use the runtime's hash functions (using //go:linkname shenanigans), so by itself it's not a very compelling use case. However, an exported built-in hash would make it easier to experiment with changes or variations.

[bcmills]

@dsnet I don't feel strongly about which package it should go in, but reflect seems like a bit of an awkward fit: the only type-introspection required in the proposed API is the knowledge that the value is comparable.

[ianlancetaylor]

Previously proposed, more or less, in this golang-dev thread: https://groups.google.com/d/msg/golang-dev/vd5Nnt3Wjj0/a5XFu6d9wsIJ .

Any hash function can only be discussed in conjunction with an equality function, so the docs for your proposed function should make clear that values that are == in Go terms will get the same hash value, and that values that are comparable but != will get different hash values.

You suggest that this should only be used for comparable values, but of course that means that it can not be used for slices, which would seem to leave out many real world applications. (The current runtime hash will panic if used on a slice, as can be seen using a map[interface{}]bool.) Are you sure you want to restrict only to comparable types?

If we do this I definitely don't think it should be in the runtime package. That would suggest that it is specifically the hash function used by things like map, and even if that is in fact what is implemented, it should not be implied.

[bcmills]

Previously proposed, more or less, in this golang-dev thread:

Thanks for the link; an interesting read. It looks like @randall77's objection there was mainly that we would have to specify and freeze the algorithm, but here I'm suggesting the opposite: if we expose a hash function, we should randomize it so that folks won't accidentally rely on the particulars.

You suggest that this should only be used for comparable values, but of course that means that it can not be used for slices, which would seem to leave out many real world applications.

That's true, but having the built-in hash would make it much easier to define application hash functions for slices: it is likely that one could use the built-in hash function for the individual elements and write only a very small function to combine them.

func hashSlice(s []T) uintptr {
  h := uintptr(0)
  for _, e := range s {
    h = Hash([2]uintptr{h, Hash(e)})
  }
  return h
}

Are you sure you want to restrict only to comparable types?

I think that's a good starting point since, as you note, a hash function must be paired with an equality function. The language spec already defines an equality function, so piggybacking on that minimizes the amount of new information one would need to learn in order to use the function.

If we do this I definitely don't think it should be in the runtime package.

That's fair. Any suggestions for alternatives? It could plausibly live in hash (or a subpackage thereof), reflect (as suggested by @dsnet), or perhaps a subpackage of container.

[bcmills]

Any hash function can only be discussed in conjunction with an equality function, so the docs for your proposed function should make clear that values that are == in Go terms will get the same hash value, and that values that are comparable but != will get different hash values.

Updated, with an explicit caveat for NaN values (to avoid the confusion of #20660).

[ianlancetaylor]

Given that the standard library already has a package named "hash", I would vote for that.

[dsnet]

You suggest that this should only be used for comparable values, but of course that means that it can not be used for slices, which would seem to leave out many real world applications.

Comparability is well defined in Go. If we expand this, would it still perform a shallow hash of pointers or would it hash the sub-value pointed to by the pointer?

[dsnet]

If we expand this Hash to operate on incomparable types, ignoring hash collisions, would Hash(x) == Hash(y) be equivalent to reflect.DeepEqual(x, y)? If the answer is no, then reflect would not be a good home since these two don't seem to be consistent with each other.

Currently, the == operator is not identical to reflect.DeepEqual in the cases of pointers.

[martisch]

The runtime hash function is free to use different algorithms on a per architecture and even feature set basis (AES vs non AES). It think it would be nice to take this into account for the proposed std lib hash function too such that we can optimize the hash function used for each architecture and feature set independently if the proposal is accepted. Therefore, apart from only having reproducible results within a process we could clarify that there should not be the expectation that the algorithm and "quality" of the hash is the same between different releases/archs/cpus.

Another discussion could be if we want to extend the compiler to optimize this specific std lib hash function e.g. to a specialized call if the type is known during compile time.