Hacking Go's runtime with generics

https://www.dolthub.com/blog/2022-12-19-maphash/

by awmarthur • 4 years ago

69 101 4 years ago

dolthub.com

shp0ngle2• 4 years ago

ELI5. How is maphash different from just using map?

I am surely missing something. I thought the builtin map used hashing too?

barsonme• 4 years 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.

shp0ngle2• 4 years 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• 4 years ago

Maphash is a library for computing hashes of arbitrary types in Go, not a map data structure.

codesniperjoe• 4 years 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

voz_• 4 years 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• 4 years ago

pick a better one?

Such as?

innocentoldguy3• 4 years ago

My choices would be:

- Elixir

- Rust

- Clojure

- Crystal

In that order.

clumsysmurf2• 4 years ago

I'm hoping Kotlin + GraalVM Native Image can fit the niche of golang.

anacrolix• 4 years ago

I hate Go, but there is no solid alternative for what I do. Documentation quality. Compiler performance. Library support. Easy packaging. Easy language. Consistent cross platform tooling. Easy concurrency. Good for web apps and CLI tools. Reasonably refactorable.

Note I say easy and not good, or simple.

Rust, Haskell, JavaScript, all get caught up on some aspect or another for me.

hnra2• 4 years ago

C# may fit your needs, depending on what you consider a simple language and easy concurrency. The language doesn’t feature any hard to understand concepts. Concurrency is very good, but only async has built in syntax sugar (I believe go has syntax sugar for channels or something?).

The executables may be a bit larger (I’m guessing).

Ingaz2• 4 years ago

You obviously don't hate go.

Everything you listed help programmer to keep own sanity.

It's all compromises but they're mostly reasonable compromises.

the_gipsy8• 4 years ago

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?

My guess is that they got excited at the chance of doing something mildly interesting, beyond the mind numbing "regular" go.

Cthulhu_• 4 years ago

I mean it's a good exercise I guess if you want to flex your language knowledge, but it goes against the mindset of Go to actually use it in production. Said mindset being don't overcomplicate things.

One doesn't need Go to not overcomplicate things either. I wanted to advocate in favor of Go for a long time, and still do recommend it, but it's the mindset that is more important.

erik_seaberg• 4 years ago

What I fear most is starting to absorb the "reserved for language designers, not for me" mindset. Stubbornly bending the language to serve you is a much healthier attitude for anyone who wants to maintain his expertise.

rob742• 4 years ago

What I do not understand is why on every article about Go someone needs to extol their dislike of Go. If you don't understand its appeal, then either you should give it a (serious) try and see if you like it, or if you are unable to bring yourself to do that, just use those better (according to your opinion) languages.

pjmlp9• 4 years ago

Unfortunely that isn't always a choice that we can influence, project => language, and in some cases that implies using a language that we dislike, regardless of how we feel about it.

One can go job hoping as alternative, but then good luck jumping jobs everytime one has to deal with stuff we dislike.

lordgroff• 4 years ago

It's like a hackernews meme at this point, complete with "I used Go before and my life was a meaningless void and then Rust came into my life and now I see the light." It's all so predictable and boring and derails nearly every Go thread.

ilyt5• 4 years ago

Hell, just scroll down in this thread to see the clowns. Maybe envy that their favourite toy/niche language didn't get popular instead ?

Like, there is plenty of flaws clear to see in Go but it does some jobs well and that's all that's needed to be useful language.

silisili• 4 years ago

I've been writing software for 20 years. About half that in Go.

Whenever I see someone say it's a bad language because X, I seriously wonder if the asker just writes terrible code, or if there's whole swaths of domains I've not encountered. Or maybe a little of both.

I've never once been stumped by a lack of generics, for example, despite how many people claim it's unusable without them.

pjmlp9• 4 years ago

Plenty of software has been written on languages without generics, but they have the excuse of coming up before generics were a common feature in mainstream languages.

At least that has been finally fixed.

shakow5• 4 years ago

I've never once been stumped by a lack of generics

Heve you never written a stack structure (since Go doesn't include one)? Never used a min/max function between numbers (go doesn't either)?

ilyt5• 4 years ago

Generics were never required, just their lack was annoying and their presence makes some things just cleaner and easier

For example I deal in ops stuff so pretty common task is "here are desired and current set, generate list of add/delete operations to get from one state to another".

I wrote iteration of that function a bunch of times pre-generics, eventually being just copy-paste-change-types but now I can just write [1] one that compares a slice of types and returns the elements present in left or right and [2] another that can do similar difference on disparate types via conversion function.

Then there is a whole slew of map/reduce and math stuff that now can just have `Map` or `Max` function without worrying about types. Hell I can "just" write "parse all the slice elements in parallel, keeping order [3] once and never worry about it. That's also code that I wrote more than once before generics

* [1] https://github.com/XANi/goneric/blob/master/slice.go#L77

* [2] https://github.com/XANi/goneric/blob/master/slice.go#L106

* [3] https://github.com/XANi/goneric/blob/master/parallel.go#L15

valenterry2• 4 years ago

No it's mostly just the blub paradox. You don't feel the pain because you didn't use some features/techniques of other languages that don't exist in Go.

It's the same everyone. I, for example, never felt I was missing something until I learned about type providers. Now that I don't work in a language that supports them, I hate it. If I had never learned about them, I would probably never miss em.

somethingreen• 4 years ago

On one hand, the bar for things to be called bad has now dropped pretty low. Being not as excellent as other thing, or not being excellent throughout is enough.

But I think the actual hate isn't coming from Go technical shortcomings. It's language authors and community attitude towards people asking for obvious QoL improvements.

Generics are a bad enough example of community for years tactfully flipping off everyone asking for them and then, hey, here they are and the sky doesn't seem to be falling. But it's not the only example. Just a couple days ago I was researching if there's a way to somehow build struct tags from constants or use interpolation and sure enough, there's an old bug tracker suggestion entry that got a two sentence "won't do" reply with zero reasoning and a bunch of following entries just marked as duplicate and closed without reply at all. This happens a lot. And people don't appreciate it.

BrandoElFollito• 4 years ago

I do not understand the appeal of go.

I am an amateur dev developer and used to use untyped languages (Python and JS, mostly).

At some point Python was annoying in docker environments (especially for APIs) and I gave a try to Go. Initially I hated it, then learned to like it more and now I kinda like it.

- typed (this is a game changer)

- compiles to a single self-contained binary (easy with Docker)

- great for APIs without the worries of gunicorn and whatnot

I also discovered TypeScript to help with JS.

So the forst one would be "typed language". I have Python for the rest ("the 2nd best language for any task") and since I am an amateur dev, I do not have the time to dig into many languages to find the pearl.

nine_k3• 4 years ago

The appeal of Go:

- A pretty simple, if not very expressive, language (it's anti-Perl, and seems simpler than JS); you can learn it down to a reasonably productive level in a weekend. (I did.)

- A memory-safe language (like Java) with good performance (like Java) without the need to install any runtime, and the ability to ship as a single binary (unlike Java).

- A reasonably good and ergonomic concurrency approach (like JS, unlike Java), based around channels, not futures, and able to embrace multicore parallelism (unlike JS, like Java, and somehow like Erlang).

- Highly opinionated, well-crafted built-in data structures (like Python), and a general approach discouraging you from rolling your own.

- Good cross-platform support; fast compilation.

That is, it's a language that works well in a case where most of your team is junior devs, and you write some kind of a network server. The devs are forced to follow simple, if repetitive and wordy, patterns, and are limited in their ability to raise creative mayhem in the code base, all while writing reasonably performant, concurrency-friendly code that's a piece of cake to deploy. Combined with some overview from more senior folks, this should work reasonably well (and apparently that's what how it works at Google).

No. it's not a joy to use, it has warts (or, rather, deliberate compromises) in many areas, it requires boilerplate which pushes the user towards copy-paste programming, etc. If you can afford to not use it, don't, but sometimes it's the easiest tool for a job, much like, well, PHP.

zachmu• 4 years ago

I actually find go a joy to use, I dunno.

I like statically typed languages, and go makes defining and using types so simple and straightforward that it feels like you get a lot of the benefits of dynamic typing without the headaches.

5e92cb50239222b• 4 years ago

ship as a single binary (unlike Java).

Possible with GraalVM. Has been possible if you were willing to pay long before that. GraalVM produces statically linked binaries with only one external dependency — zlib, which is preinstalled pretty much everywhere. Startup time is measured in milliseconds.

I recently built a mid-size REST backend with quarkus — it ships as a single binary with size comparable to what I'd expect to see if it was written in Go, and starts in about 200 ms (from executing the command to when it's ready to serve its first request).

Having written code in both, I hope GraalVM buries Go in the long term, but in our hype-driven culture it's unlikely.

https://quarkus.io/guides/building-native-image#configuring-...

https://github.com/oracle/graal

A reasonably good and ergonomic concurrency approach (like JS, unlike Java)

This is also very close to being solved.

ilyt5• 4 years ago

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?

..coz they already have code in it ? Coz they are happy with remaining 99% of the language ? It's not hard to figure out cmon.

If people dropped language at slight inconvenience we'd be out of languages

tptacek• 4 years ago

This is an article about an idiosyncratic and fairly interesting approach to writing a fast generic striped map in Golang. Responding to it with a language war appeal is arson; maybe not the "pouring gasoline onto the building" kind of arson, but certainly the "tossing your lit cigarette into the dried up pile of brush" kind. Almost the entire thread on this story has been consumed by a litigation of whether Go is good or not.

If you don't like Go (or Rust or Haskell or Elixir or Ruby), that's fine. Just don't comment.

aatd86• 4 years ago

I think he didn't mean tries which don't generally need hashing but was trying to implement a lock-free map based on Concurrent Hash-Array Mapped Tries.

I had done that myself as an exercise a few years back and had to extract the hash function from the runtime that is used for maps.

In any case, the performance was terrible and code brittle. (lack of sumtypes).

Since then, I've learnt to not bother too much and just use the builtin maps. Never had an issue for my use-cases.

awmarthur• 4 years ago

(OP) I'm mostly interesting in a fast hash for writing a generic, concurrent hash map.

The reference to Tries came from the original issue in the Golang repo about possible uses for a standard library hash function: https://github.com/golang/go/issues/21195

And you're right, the Trie implementation linked there was indeed a Hash-Array Mapped Tried: https://pkg.go.dev/github.com/lleo/go-hamt-key#Key

coldtea• 4 years ago

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?

What makes you think they haven't tried what you think are "better ones" and moved away because they had more problems to fight the language/ecosystem about with those?

Traubenfuchs• 4 years ago

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

skybrian• 4 years ago

Sort of, except the way Java did it is awkward because they put a method on Object instead of making it an interface. It's not clear from the API what's really usable as a map key.

I'm not sure making all comparable objects in Go usable as map keys is a good idea either.

masklinn5• 4 years ago

I'm not sure making all comparable objects in Go usable as map keys is a good idea either.

Was a good idea since, it's part of the spec-definition of Go:

A map is an unordered group of elements of one type, called the element type, indexed by a set of unique keys of another type, called the key type. [...] The comparison operators == and != must be fully defined for operands of the key type

TFA is merely reusing that.

dj_mc_merlin• 4 years ago

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

kangda123• 4 years ago

Ease of use

naasking4• 4 years ago

Why can't a database be written in a garbage collected language?

maxmcd• 4 years 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-choi... and more specifically this: https://www.cockroachlabs.com/community/tech-talks/challenge... would be good to explore for how cockroach has made it work w/ Go+GC.

eatonphil• 4 years ago

If you like/trust dbdb.io, most databases are written in C++ or Java. C# and Go are also high on the list.

https://dbdb.io/stats

Ingaz2• 4 years ago

C/C++/Rust - will not solve anything magically. Anyway you will need to implement some kind of memory management for DB.

Go GC creates problems and they are non-trivial (as all memory management) but it's not so twisted as in JVM.

Examples:

- DGraph: migrated from RocksDB (C++) to Badger (pure go, developed themselves, based on jemalloc)

- CocroachDB - pure go for storage engine

- go 1.20 proposed feature: package `arena` for region-based memory management

Hacking Go's runtime with generics

Related Stories