New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
proposal: hash/maphash: add Comparable to hash comparable values #54670
Comments
I'm realizing a major caveat with this is that this can hash pointers. In order for |
Note that in #28322 we discussed and rejected the idea of having the package that became hash/maphash support general types. |
Even today, we have moving GC if you count stacks. The built-in maps avoid this problem by never allocating on the stack objects that map pointer keys refer to. For |
I wanted something like https://github.com/dolthub/maphash My use case is a simple stripe-locked map, where a generic hash function is used to pick the stripe: type Map[K comparable, V any] struct {
stripes [64]map[K]V
locks [64]sync.Mutex
} Looking through the history of this issue, it seems like there are a number of interesting applications for this proposal. @bcmills listed a number of relevant examples in #21195 |
In my application, I'm writing a generic data structure for packet processing, where I only care about hashing byte arrays. As a half-step measure, I wonder if there's value in providing a The downside is that generic data structures (that expose |
For posterity, here are the thorny issues with pointers, interfaces, and channels:
|
I don't think it does. Broadly, there are two solutions to pointer hashing in a moving GC:
Today, option 1 would mean rebuilding all maps. This is possible, but would be extremely difficult to do in a low-latency way. If we were to expose hash values of pointers, this would become essentially untenable. (You could imagine that the hash values we expose are opaque, but that severely limits what you can do with them.) Option 2 is, I believe, fairly reasonable. This is what Java does for the default hashCode implementation. The main downside is that, today, hashing a pointer value requires no indirection–we simply hash the pointer value–and this would require us to perform an object lookup to check for an original hash (not just an indirection because it could be an interior pointer). It might be possible on some architectures to use a bit in the pointer to indicate that the object has moved and we need to do this extra work. It would also require us to have somewhere to store the original hash that's easy to access from the pointer. But if we're moving objects, we'd probably have a different heap layout, too, and this would simply have to be a consideration.
I think maphash.Comparable would have to escape its argument in the current implementation. That's not ideal, but doesn't seem like a big deal to me. |
I think there are a couple of additions to Go that make this highly worth reconsidering:
The lack of
Providing |
We were discussing this in the Google compiler/runtime team and had some more thoughts.
Stepping back, the basic property of hashing is that I'm being very careful to say "values of type Values with underlying type Values of interface type are more complicated. Their dynamic type may be It's informative to look at how built-in maps deal with all this today. Built-in maps are known to the compiler's escape analysis and follow very simple rules: OptionsOnce we decouple hashing from data structure operations using that hash, things get more complicated. I see a few options:
1. Change how pointers to the stack are hashedThe hash function for Today, composite types can sometimes be hashed directly with a single large The more concerning thing to me is that this may restrict some future design directions. For example, we're currently exploring dynamic escape analysis, where values can move from stack to the heap at run-time. This would make the simple normalized hash function no longer stable. We could apply the same solutions as a moving GC, but that has a cost for hashing of all pointers. There may be other ways this would hamstring us. 2. Escape
|
Op | Type | Built-in map | User map | Note |
---|---|---|---|---|
Lookup | *T |
No escape | Escapes | Lookup can never succeed for a stack pointer, so this is almost certainly rare. |
Lookup | interface | No escape | Escapes ⚠ | Unfortunate. |
Lookup | string w/ 2i |
No escape | Escapes ⚠⚠ | Very unfortunate. |
Lookup | string w/ 2ii |
No escape | No escape | |
Insert | *T |
Escapes | Escapes | Both hashing and storing cause escape. |
Insert | interface | Escapes | Escapes | Same. |
Insert | string w/ 2i |
Escapes | Escapes | Same. |
Insert | string w/ 2ii |
Escapes | Escapes | Storing causes escape in user map. |
With this approach, lookups in user-defined maps are disadvantaged relative to the built-in map. For *T
, this probably doesn't matter in practice. For interfaces it's unfortunate because interface values often contain pointers that don't affect the hash result. For example, if the interface's dynamic type is int
, the compiler has to box that value and store it as a pointer to an int
value. This solution would force these to escape. For string values, we can close the gap between user-defined maps and built-in maps by special-casing strings in escape analysis.
3. Dynamically escape stack pointers passed to maphash
Dynamic escape analysis allows the compiler's escape analysis to be less conservative by enabling the runtime to move values allocated on the stack to the heap only when necessary. We don't currently have this ability, but we're exploring it as a general optimization when we have hot/cold path information from PGO and the compiler can determine that all escapes of a value happen on cold paths. We could apply it to maphash as well.
4. Track the data flow of hash values
I include this here for completeness, but I'm not sure how plausible it is. The idea is that, if we can bound the lifetime of a hash value, it doesn't need to escape the hashed valued. This may be possible if we could represent hash values as a distinct type, but in general data structures need to use the numerical value of a hash, e.g., to select as hash bucket, and I think at that point it would be very easy to lose track of the data flow.
I'm trying to implement my own map-like data structure. I'm using generics where I have a
comparable
type on hand, but I don't have a way to hash it. To workaround it, I'm adding aHash() uint64
constraint, but that requires every key type to have a customHash
method, which is quite unfortunate, given that the Go runtime knows how to hashcomparable
types.I propose we add:
Under the hood, this function is a thin wrapper over
mapType.hasher
.There are some caveats with the operation of this function, but they're no different than the caveats of using
==
.The text was updated successfully, but these errors were encountered: