10 ms·

Hacking Go's runtime with generics

69 points by awmarthur 4y ago

shp0ngle 4y ago
ELI5. How is maphash different from just using map? I am surely missing something. I thought the builtin map used hashing too?
- barsonme 4y ago
  The maphash package from the blog post provides routines that call into Go's runtime to hash arbitrary types. The maphash package in the standard library (hash/maphash) provides routines that hash string and []byte. The builtin map type is a hash table.
  - shp0ngle 4y ago
    Ahh I somehow misread the post and thought it’s a generic map that uses hash table. I should get some sleep, thanks
- AaronFriel 4y ago
  Maphash is a library for computing hashes of arbitrary types in Go, not a map data structure.
- codesniperjoe 4y ago
  Maphash is an (non-cryptographic-secure) hash function, like CRC32 / CRC64 / XXH3-64 and others, so it turns data in an (almost) uniq uint64. The main difference is, it is an hardware accelerated & optimized compiler function, now exposed via the new maphash package in stdlib. And it is fast. Faster than the former performance leader xxh3(avx2/avx512). Try maphash yourself (example data dedupliction) https://news.ycombinator.com/item?id=34091206 https://news.ycombinator.com/item?id=34091206
voz_ 4y ago
I do not understand the appeal of go. > The proposal argues that Golang developers are forced to work around language when writing hash-based data structures like Tries or concurrent hash maps. Developers who want an efficient hash-based data structure have only the builtin map to choose from. When this issue was originally created in 2017, Golang didn't have generics And then the author goes to tell us about how this is not a stable solution. I get wanting to solve a problem, but at what point into fighting the language, to accomplish something simple, do you take a step back and just pick a better one?
- XorNot 4y ago
  > pick a better one? Such as?
  - innocentoldguy 4y ago
    My choices would be: - Elixir - Rust - Clojure - Crystal In that order.
    - cosmicradiance 4y ago
      Are you an expert in all those languages? To me these are the exotic languages which one gets inspired from when reading the stackoverflow survey, but there is hardly any one person I know who has mastered even half of those.
      - nicoburns 4y ago
        Once you’ve learnt a few languages, learning more becomes easy. Elixir, Rust and Clojure are all reasonably widely used. And I would note: somewhat similar to each other.
      - innocentoldguy 4y ago
        I don't consider myself an expert at anything, but yes, I use these languages on a daily to weekly basis at work. We had some Go code, but replaced it with Elixir. EDIT: I'd also like to add that Elixir and Rust aren't "exotic." Crystal may be, but it's basically just compiled/typed Ruby. I've been using Elixir professionally for seven years across multiple companies: 1. Divvy. 2. GoSkip. 3. Podium. 4. Actiphy.
Traubenfuchs 4y ago
So the reinvented wheel (golang) is now starting to miss / reinvent Java's .hashCode() or an alternative to it?
- masklinn 4y ago
  [flagged]
  - pjmlp 4y ago
    [flagged]
  - ilyt 4y ago
    You'd be hard pressed to name anything in IT that wasn't "discovered" in the 60s-80s but implemented/re-implemented recently
    - masklinn 4y ago
      We're not talking bleeding edge CS topics here mate, we're talking "hashability is a useful property because hashmaps", that was standard >25 years ago. Java had hashCode in 1.0, GvR added __hash__ to Python in March 1993 and shipped it in 0.9.9. Hash maps are 69 years old (nice). Bespoke key types (and thus the requirement for user-defined hash functions) is probably the more recent of the two.
      - ilyt 4y ago
        So you don't understand what's happening here. They are not "hashing a structure", they are digging into internal implementation to reuse code that runtime uses to hash the structure. > Java had hashCode in 1.0, GvR added __hash__ to Python in March 1993 and shipped it in 0.9.9. is not doing that. It is just providing an interface that happens to be filled for builtin types Also Go is not object oriented language and types don't have default set of methods returning things so having type.hash() like Java or Python would make no sense. Whether that's a good or bad call is another discussion but writing generic Hash[T] is few lines of code and would be just encoding/gob into hash of your choosing. There is a case for providing that in function doing what the dolt guys are doing but that would be "just" optimization.
dj_mc_merlin 4y ago
Honest question: isn't Go a bit of a weird choice for a database given the GC? Why not C/C++/Rust?
- kangda123 4y ago
  Ease of use
- naasking 4y ago
  Why can't a database be written in a garbage collected language?
  - maxmcd 4y ago
    I believe you usually want as much control of memory management as possible as it can be a great place for finding performance improvements and also help in delivering very consistent performance. Automatic memory management is a great aid in reduction of the complexity you have to deal with, but you presumably want to deal with that completely in the context of a database. Seems like this: https://www.cockroachlabs.com/blog/why-go-was-the-right-choice-for-cockroachdb/ https://www.cockroachlabs.com/blog/why-go-was-the-right-choi... and more specifically this: https://www.cockroachlabs.com/community/tech-talks/challenges-writing-massive-complex-go-application/ https://www.cockroachlabs.com/community/tech-talks/challenge... would be good to explore for how cockroach has made it work w/ Go+GC.
    - naasking 4y ago
      > I believe you usually want as much control of memory management as possible as it can be a great place for finding performance improvements and also help in delivering very consistent performance. Sure, but premature optimization is the root of all evil right? Get something functional, then make it performant by handling the problematic cases. GC doesn't prevent this progression, it's just a significant help to getting something functional. GC can sometimes lead you into designs that can't be optimized without a change in abstraction, but it's not at all obvious that you would have landed on the right abstraction if you didn't have the GC to begin with anyway. I think getting something working as fast as possible lets you gather the data you need to make a performant design, and having to handle all of that complexity up front without a GC just delays the data gathering stage.

69 points by awmarthur 4y ago

ELI5. How is maphash different from just using map? I am surely missing something. I thought the builtin map used hashing too?

barsonme 4y ago
The maphash package from the blog post provides routines that call into Go's runtime to hash arbitrary types. The maphash package in the standard library (hash/maphash) provides routines that hash string and []byte. The builtin map type is a hash table.
- shp0ngle 4y ago
  Ahh I somehow misread the post and thought it’s a generic map that uses hash table. I should get some sleep, thanks
AaronFriel 4y ago
Maphash is a library for computing hashes of arbitrary types in Go, not a map data structure.
codesniperjoe 4y ago
Maphash is an (non-cryptographic-secure) hash function, like CRC32 / CRC64 / XXH3-64 and others, so it turns data in an (almost) uniq uint64. The main difference is, it is an hardware accelerated & optimized compiler function, now exposed via the new maphash package in stdlib. And it is fast. Faster than the former performance leader xxh3(avx2/avx512). Try maphash yourself (example data dedupliction) https://news.ycombinator.com/item?id=34091206 https://news.ycombinator.com/item?id=34091206

voz_ 4y ago

I do not understand the appeal of go. > The proposal argues that Golang developers are forced to work around language when writing hash-based data structures like Tries or concurrent hash maps. Developers who want an efficient hash-based data structure have only the builtin map to choose from. When this issue was originally created in 2017, Golang didn't have generics And then the author goes to tell us about how this is not a stable solution. I get wanting to solve a problem, but at what point into fighting the language, to accomplish something simple, do you take a step back and just pick a better one?

XorNot 4y ago
> pick a better one? Such as?
- innocentoldguy 4y ago
  My choices would be: - Elixir - Rust - Clojure - Crystal In that order.
  - cosmicradiance 4y ago
    Are you an expert in all those languages? To me these are the exotic languages which one gets inspired from when reading the stackoverflow survey, but there is hardly any one person I know who has mastered even half of those.
    - nicoburns 4y ago
      Once you’ve learnt a few languages, learning more becomes easy. Elixir, Rust and Clojure are all reasonably widely used. And I would note: somewhat similar to each other.
    - innocentoldguy 4y ago
      I don't consider myself an expert at anything, but yes, I use these languages on a daily to weekly basis at work. We had some Go code, but replaced it with Elixir. EDIT: I'd also like to add that Elixir and Rust aren't "exotic." Crystal may be, but it's basically just compiled/typed Ruby. I've been using Elixir professionally for seven years across multiple companies: 1. Divvy. 2. GoSkip. 3. Podium. 4. Actiphy.

Traubenfuchs 4y ago

So the reinvented wheel (golang) is now starting to miss / reinvent Java's .hashCode() or an alternative to it?

masklinn 4y ago
[flagged]
- pjmlp 4y ago
  [flagged]
- ilyt 4y ago
  You'd be hard pressed to name anything in IT that wasn't "discovered" in the 60s-80s but implemented/re-implemented recently
  - masklinn 4y ago
    We're not talking bleeding edge CS topics here mate, we're talking "hashability is a useful property because hashmaps", that was standard >25 years ago. Java had hashCode in 1.0, GvR added __hash__ to Python in March 1993 and shipped it in 0.9.9. Hash maps are 69 years old (nice). Bespoke key types (and thus the requirement for user-defined hash functions) is probably the more recent of the two.
    - ilyt 4y ago
      So you don't understand what's happening here. They are not "hashing a structure", they are digging into internal implementation to reuse code that runtime uses to hash the structure. > Java had hashCode in 1.0, GvR added __hash__ to Python in March 1993 and shipped it in 0.9.9. is not doing that. It is just providing an interface that happens to be filled for builtin types Also Go is not object oriented language and types don't have default set of methods returning things so having type.hash() like Java or Python would make no sense. Whether that's a good or bad call is another discussion but writing generic Hash[T] is few lines of code and would be just encoding/gob into hash of your choosing. There is a case for providing that in function doing what the dolt guys are doing but that would be "just" optimization.

dj_mc_merlin 4y ago

Honest question: isn't Go a bit of a weird choice for a database given the GC? Why not C/C++/Rust?

kangda123 4y ago
Ease of use
naasking 4y ago
Why can't a database be written in a garbage collected language?
- maxmcd 4y ago
  I believe you usually want as much control of memory management as possible as it can be a great place for finding performance improvements and also help in delivering very consistent performance. Automatic memory management is a great aid in reduction of the complexity you have to deal with, but you presumably want to deal with that completely in the context of a database. Seems like this: https://www.cockroachlabs.com/blog/why-go-was-the-right-choice-for-cockroachdb/ https://www.cockroachlabs.com/blog/why-go-was-the-right-choi... and more specifically this: https://www.cockroachlabs.com/community/tech-talks/challenges-writing-massive-complex-go-application/ https://www.cockroachlabs.com/community/tech-talks/challenge... would be good to explore for how cockroach has made it work w/ Go+GC.
  - naasking 4y ago
    > I believe you usually want as much control of memory management as possible as it can be a great place for finding performance improvements and also help in delivering very consistent performance. Sure, but premature optimization is the root of all evil right? Get something functional, then make it performant by handling the problematic cases. GC doesn't prevent this progression, it's just a significant help to getting something functional. GC can sometimes lead you into designs that can't be optimized without a change in abstraction, but it's not at all obvious that you would have landed on the right abstraction if you didn't have the GC to begin with anyway. I think getting something working as fast as possible lets you gather the data you need to make a performant design, and having to handle all of that complexity up front without a GC just delays the data gathering stage.