4 ms·

I'm excited for generics to land in Golang so we can have efficient set implementations instead of abusing maps.

by hdhjebebeb 5y ago

darkr 5y ago
In many languages (including Python & Scala), sets are not much more than syntactic sugar on a hashmap-like datatype.
- nynx 5y ago
  In rust, hashsets are just hashmaps with a zero-sized type as the value, which results in all the extra getting optimized away.
  - BenTheElder 5y ago
    A zero-sized type + hashmap for sets is also done in Go with a `struct{}`. [1][2] But without generics it must be implemented again for each entry type ... Kubernetes uses a code generator to automate this, but it's a bit kludge. [3] [1]: https://pkg.go.dev/k8s.io/apimachinery/pkg/util/sets#Empty https://pkg.go.dev/k8s.io/apimachinery/pkg/util/sets#Empty [2]: https://dave.cheney.net/2014/03/25/the-empty-struct https://dave.cheney.net/2014/03/25/the-empty-struct [3]: https://github.com/kubernetes/code-generator/blob/master/cmd/set-gen/main.go https://github.com/kubernetes/code-generator/blob/master/cmd...
- cmckn 5y ago
  This is true for Java as well, a `HashSet` is just a `HashMap<T, Object>` where the value is: // Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object(); https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/HashSet.java#L97 https://github.com/openjdk/jdk/blob/master/src/java.base/sha... A thread-safe implementation is available with `ConcurrentHashMap.newKeySet()`, which uses a similar approach: public static <K> KeySetView<K,Boolean> newKeySet() { return new KeySetView<K,Boolean> (new ConcurrentHashMap<K,Boolean>(), Boolean.TRUE); } https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/HashSet.java#L97 https://github.com/openjdk/jdk/blob/master/src/java.base/sha...
- masklinn 5y ago
  There probably aren't many languages where that's different, whether a hashset on a hashmap or a treeset on a treemap. However sets tend to provide support for… set operations. Which currently can't be done generically in go except through interface{} or specialised, neither of which is a great option.
- Philip-J-Fry 5y ago
  Even if that's the case, the thing we want is syntactic sugar. It'd be nice to just do `sets.New[int]()` rather than manipulate maps manually or create bespoke types.

I'm excited for generics to land in Golang so we can have efficient set implementations instead of abusing maps.

darkr 5y ago

In many languages (including Python & Scala), sets are not much more than syntactic sugar on a hashmap-like datatype.

nynx 5y ago
In rust, hashsets are just hashmaps with a zero-sized type as the value, which results in all the extra getting optimized away.
- BenTheElder 5y ago
  A zero-sized type + hashmap for sets is also done in Go with a `struct{}`. [1][2] But without generics it must be implemented again for each entry type ... Kubernetes uses a code generator to automate this, but it's a bit kludge. [3] [1]: https://pkg.go.dev/k8s.io/apimachinery/pkg/util/sets#Empty https://pkg.go.dev/k8s.io/apimachinery/pkg/util/sets#Empty [2]: https://dave.cheney.net/2014/03/25/the-empty-struct https://dave.cheney.net/2014/03/25/the-empty-struct [3]: https://github.com/kubernetes/code-generator/blob/master/cmd/set-gen/main.go https://github.com/kubernetes/code-generator/blob/master/cmd...
cmckn 5y ago
This is true for Java as well, a `HashSet` is just a `HashMap<T, Object>` where the value is: // Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object(); https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/HashSet.java#L97 https://github.com/openjdk/jdk/blob/master/src/java.base/sha... A thread-safe implementation is available with `ConcurrentHashMap.newKeySet()`, which uses a similar approach: public static <K> KeySetView<K,Boolean> newKeySet() { return new KeySetView<K,Boolean> (new ConcurrentHashMap<K,Boolean>(), Boolean.TRUE); } https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/HashSet.java#L97 https://github.com/openjdk/jdk/blob/master/src/java.base/sha...
masklinn 5y ago
There probably aren't many languages where that's different, whether a hashset on a hashmap or a treeset on a treemap. However sets tend to provide support for… set operations. Which currently can't be done generically in go except through interface{} or specialised, neither of which is a great option.
Philip-J-Fry 5y ago
Even if that's the case, the thing we want is syntactic sugar. It'd be nice to just do `sets.New[int]()` rather than manipulate maps manually or create bespoke types.