Hacker News Reader

Comment by Animats | Hacker News Reader

Go hashmaps are generics, or at least parameterized types. You can't create new parameterized types in Go, but you get maps and channels built in.

View on HN

By that definition C89 has generics too (arrays and pointers). The whole point of generics is that they are user definable. Everything else is hairsplitting.

I think it's relevant in the sense that it's not particularly impressive once you know the answer. Basically the answer to the title "How the Go runtime implements maps efficiently (without generics)" is "by using compiler magic".

Furthermore the article presents Go's approach superior to C++ because of the reduced code generation (since it uses a "maptype" struct for the type-specific information) but doesn't talk about the drawback of such an approach: you have additional indirections in the mapping code and the compiler can't inline and optimize for specific types. Of course in some cases that's actually desirable, very large code size can be problematic.

I could also add that you could pretty easily implement Go-style hashes in C++ (actually that's often how you implement generic hashes in C, using helper functions depending on the type) but you can't implement C++-style hashes in Go without hacking the compiler or using codegen.

C11 got user defined generics, FYI.

https://en.cppreference.com/w/c/language/generic

This is something else. C++ has had parametric polymorphism in the form of template metaprogramming for a long time (the article on hashmaps even covers it).

This is one of the reasons I don't really like the name 'generics', it's a little ambiguous.

It was the term coined by CLU, Ada, Modula-3, so it is already widely used in the academia.

Yes, exactly correct. But nonetheless the way Go makes maps efficient is it has generics for maps.

and arrays and slices and pointers.

> You can't create new parameterized types in Go

Or create functions on parameterized types (without providing concrete type parameters), which is possibly a bigger annoyance than the other one: slices are a thing, but you can't operate on arbitrary slices without reflection. As well as generic types being restricted to builtins, generic functions (e.g. close, copy, len) also are.

We're provided with some nice fake type signatures for such builtin functions in the godoc:

https://golang.org/pkg/builtin/#copy

https://golang.org/pkg/builtin/#Type

If Go 2 is bringing us generics, then couldn't that `builtin` package provide real type signatures for the builtin functions instead of fake ones? Instead of

  func delete(m map[Type]Type1, key Type)

it could have

  func Delete(type Type, Type1 somecontract) (m map[Type]Type1, key Type)

in there, and a program compiled with Go 2 would have an implied instance of

  func delete = builtin.Delete(T, U)

in its global namespace for every map with a `delete` used somewhere in the code.

Yeah, for me this is the big problem. For example, I once built a generic flow based library in Go for work (Go was not my choice, and while I like Go it was not really the best choice for this library). The idea is to have a pipeline of go routines where data flows from one stage in the pipeline to the next. Channels and go routines are awesome for this, but setting up all the types for the channels based on the types in the functions being run by the go routines was quite difficult. I had to do it all by reflection and the code was really complicated. With generics, it would have been trivial.

The proposal in the 2.0 spec looks promising and I'm looking forward to hopefully being able to play with an implementation sometime.

> setting up all the types for the channels based on the types in the functions being run by the go routines was quite difficult. I had to do it all by reflection and the code was really complicated.

My guess (and personal experience) is that this would maybe be more convenient to do this via code generation. It's not as ergonomic as generics (well, depending on the implementation...), but still it's less cumbersome and prone to failing at runtime that reflection.

Reflection has its uses and places, but as soon as it gets all over a function then it's time (imho) to look into code generation.

I definitely would have done it that way, but there was no standard code generation in go at the time. I could have whipped something up it's hard to say which would have been more complex.

As an anecdote: my 'code generation' go-to solution in go is text/template's based. The '//go generate' on the first line of the source file generating the final code is a mere helper and I could do without it any time. Again that's just my experience ;)

Don't forget slices and arrays

Reply on news.ycombinator.com