Specialized versions of Map: CounterMap, ByteSliceMap, etc.
puzpuzpuz opened this issue · 8 comments
Current xsync.Map supports string keys and interface{} values. This is sufficient for many use cases, but not all of them. So, that's why specialized map data structures could be added to the library.
IMO the most interesting one is CounterMap which would hold int64s as both keys and values and support Inc/Dec operations. Such map may be used in certain niche use cases. Also, it should outperform any synchronized built-in map, as well as xsync.Map.
Another option might be a map that would support []byte slices as keys. This is not supported by the built-in maps (both map and sync.Map) since slices are not comparable.
I'll be collecting feedback to understand the demand for specialized map collections, so leave comments on this issue if you need them.
Have a look at https://github.com/SaveTheRbtz/generic-sync-map-go/blob/main/map.go. I would consider exposing a generic kv should be good.
Agreed that generic keys in addition to values would make this a lot more useful in performance-intensive scenarios. If you want to support non-comparable values like slices (dangerous, since their contents are mutable, but... caveat emptor I guess), you could also accept a typed hash function from the user.
Failing that, if you supported uint64 hashes, we could at least hash our own arbitrary data.
Supporting uint64 keys would be great.
I have a use-case where my keys are already uint64, and converting them to strings becomes a big source of overhead. It seems wasteful, since the internal hash function is deriving a uint64 back out of them.
To echo what was said above by @ianwilkes Go 1.18 generics could also be a good fit for the keys, e.g.
type HashableKey interface {
Hash() uint64
}
type StringKey string
func (k StringKey) Hash() uint64 {
return maphash64(k)
}
type UInt64Key uint64
func (k UInt64Key) Hash() uint64 {
return k
}
// etc...It's very performant (near zero overhead, < 1ns/op). However it's a little awkward ergonomics-wise though with all the type casting, and it does break the existing API of MapOf.
Perhaps using a non-generic "any" key and type switching to hash known hashable types (string, ints etc..) into uint64 might be the nicest API to work with in the end? As a bonus, it's a backwards compatible API too.
I'll put up a quick PR at some point which does this.
The trouble with any is that if you stuff a scalar into it, like a uint64, you generally get a fresh heap allocation each time. It's not suitable for passing arguments when perf matters.
"any" is preferable due to allocation since atomic snapshot depends keys having unique pointers. However, it is possible to support scalar types such as uint64 with the design described in #8. One more thing to notice is that such map would need to have changes from #31 reverted due possible hash collisions. So, keeping the same API would require significant changes in the implementation.
However, it is possible to support scalar types such as
uint64with the design described in #8.
My bad, this consideration is only applicable to values, not keys. However, the second consideration still holds.
Closing this one as v1.5.0 added NewIntegerMapOf function. It's not precisely what was meant by CounterMap here since it lacks increment/decrement methods, but I'm not sure if such niche data structure as CounterMap would have any demand.